CodeTop每日系列三题------------------2021.12.15

CodeTop每日系列三题------------------2021.12.15

LC75. 颜色分类

class Solution {
    public void sortColors(int[] nums) {
        int ptr = 0;
        for(int i = 0;i < nums.length;i++){
            if(nums[i] == 0){
                int temp = nums[i];
                nums[i] =nums[ptr];
                nums[ptr] = temp;
                ptr++;
            }
        }
         for(int i = 0;i < nums.length;i++){
            if(nums[i] == 1){
                int temp = nums[i];
                nums[i] =nums[ptr];
                nums[ptr] = temp;
                ptr++;
            }
        }
    }
}

LC125. 验证回文串
//回文串的题型就是 双指针左右指针回到中间，栈push进pop出来相同，reverse()是否相同，本道题目学到了一个比较少用的API,Character.isLetterOrDigit判断当前字符是否为数字或者字母。不论大小写的话还要转换字符Character.toLowerCase

//双指针做法
class Solution {
    public boolean isPalindrome(String s) {
        int left = 0,right = s.length() - 1;
        while(left < right){
            while(left < right && !Character.isLetterOrDigit(s.charAt(left))) left++;
            while(left < right && !Character.isLetterOrDigit(s.charAt(right))) right--;
            if(left < right){
                if(left < right && Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))){
                    return false;
                }
                left++;
                right--;
            }
        }
        return true;
    }
}

//reverse（）做法
class Solution {
    public boolean isPalindrome(String s) {
        int left = 0,right = s.length() - 1;
        StringBuffer remainstr = new StringBuffer();
        for(int i = left;i <= right;i++){
            if(Character.isLetterOrDigit(s.charAt(i))){
                remainstr.append(Character.toLowerCase(s.charAt(i)));
            }
        }
        StringBuffer reversestr = new StringBuffer(remainstr).reverse();
        return remainstr.toString().equals(reversestr.toString());
    }
}

LC230. 二叉搜索树中第K小的元素
//对于二叉搜索树来说中序遍历的结果就是升序，那么求第k小也就是说从开始遍历时候就可以做递减当k为0的时候此时的root就是结果。中序遍历的模板有点忘记并且在遍历条件以及节点转换处出了差错

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        Deque stack = new linkedList();
        //这里也发生错误！
        while(root != null || !stack.isEmpty()){
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            //这里发生错误！
            root = stack.pop();
            --k;
            if(k == 0){
                break;
            }
            root = root.right;
        }
        return root.val;
    }
}