LeetCode(26) -- 669, 671, 674

P669. Trim a Binary Search Tree (Easy)

BST, 给定一个范围，只保留这个范围内的节点。

我的思路

如果发现某个数小于下限值，就看它有没有右子节点，如果有，再看它是否小于下限值。如果大于下限值， 就直接替换。如果

我的代码

public class E_669_TrimaBinarySearchTree {
    public TreeNode trimBST(TreeNode root, int L, int R) {
        TreeNode min = new TreeNode(Integer.MIN_VALUE);
        min.right = root;
        while (min.right.val < L) {
            min.right = root.right;
        }
        substitute(min, root, L, R, false);
        return min.right;
    }

    private void substitute(TreeNode parent, TreeNode node, int L, int R, boolean isLeft) {
        if (node == null) {
            return;
        }
        if (isLeft && node.val < L) {
            parent.left = node.right;
            substitute(parent, parent.left, L, R, true);
        } else if (!isLeft && node.val > R) {
            parent.right = node.left;
            substitute(parent, parent.right, L, R, false);
        } else {
            substitute(node, node.left, L, R, true);
            substitute(node, node.right, L, R, false);
        }
    }
}

结果是错的。

答案

class Solution {
    public TreeNode trimBST(TreeNode root, int L, int R) {
        if (root == null) return root;
        if (root.val > R) return trimBST(root.left, L, R);
        if (root.val < L) return trimBST(root.right, L, R);

        root.left = trimBST(root.left, L, R);
        root.right = trimBST(root.right, L, R);
        return root;
    }
}

P671. Second Minimum Node In a Binary Tree (Easy)

我的代码

class Solution {
    int min = Integer.MAX_VALUE;
    int secondMin = Integer.MAX_VALUE;
    public int findSecondMinimumValue(TreeNode root) {
        dfs(root);
        return secondMin == Integer.MAX_VALUE ? -1 : secondMin;
    }

    private void dfs(TreeNode node) {
        if (node == null) {
            return;
        }
        dfs(node.left);
        if (node.val < min) {
            secondMin = min;
            min = node.val;
        } else if (node.val < secondMin) {
            secondMin = node.val;
        }
        dfs(node.right);
    }
}

又错了，不知道哪里有bug，懒得找了。。。

答案

class Solution {
    int min1;
    long ans = Long.MAX_VALUE;

    public void dfs(TreeNode root) {
        if (root != null) {
            if (min1 < root.val && root.val < ans) {
                ans = root.val;
            } else if (min1 == root.val) {
                dfs(root.left);
                dfs(root.right);
            }
        }
    }
    public int findSecondMinimumValue(TreeNode root) {
        min1 = root.val;
        dfs(root);
        return ans < Long.MAX_VALUE ? (int) ans : -1;
    }
}

我的错误是dfs方法里算法不对。不需要每次去更新最小值和第二小的值，因为根节点肯定是最小值， 没必要更新。

P674. Longest Continuous Increasing Subsequence (Easy)

最长的增长子数组的长度

我的思路

只要一直在增长，就count++, 下降或持平就回到1。保存一个最大值。

我的代码

public class E_674_LongestContinuousIncreasingSubsequence {

    public int findLengthOfLCIS(int[] nums) {
        if (nums == null || nums.length == 0){
            return 0;
        }
        int maxLength = 1;
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i - 1]) {
                count++;
                maxLength = Math.max(count, maxLength);
            } else {
                count = 1;
            }
        }
        return maxLength;
    }
}

99%，终于遇到一个简单题。。。

最优解

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        if (nums.length == 0) { return 0; }
        else if (nums.length == 1) { return 1; }
        int maxLen = 1;
        int i = 0;
        while (i<nums.length-maxLen) {
            boolean isSkippable = false;
            for (int j=i+maxLen; j>i; j--) {
                if (nums[j-1]>=nums[j]) {
                    i=j;
                    isSkippable = true;
                    break;
                }
            }
            if (!isSkippable) {
                i += maxLen;
                while (i<nums.length && nums[i-1]<nums[i]) {
                    i++;
                    maxLen++;
                }
            }
        }

        return maxLen;
    }
}

P680. Valid Palindrome II (Easy)

一个非空的字符串，最多删除一个字符，判断是否可以把它变成一个回文

我的思路

从两侧向中间依次比较，如果发现有不一样的，就分两种情况，一种是左边前进一格，另一种是右边前进一格。无论哪种，只要再发现有不一样的，这种方向标记为false。只要两条道路都是false，结果才是false.

我的代码

public class E_680_ValidPalindromeII {
    public boolean validPalindrome(String s) {
        char[] chars = s.toCharArray();
        int l = 0;
        int r = chars.length - 1;
        int count = 0;
        boolean left = true;
        boolean right = true;
        while (l < r) {
            if (chars[l] != chars[r]) {
                count++;
                if (count > 1) {
                    left = false;
                    break;
                }
                l++;
            } else {
                l++;
                r--;
            }
        }

        l = 0;
        r = chars.length - 1;
        count = 0;
        while (l < r) {
            if (chars[l] != chars[r]) {
                count++;
                if (count > 1) {
                    right = false;
                    break;
                }
                r--;
            } else {
                l++;
                r--;
            }
        }

        if (!left && !right) {
            return false;
        }
        return true;
    }
}

91.52%，虽然代码非常难看，但一次性过了。

最优解

class Solution {
    public boolean validPalindrome(String s) {
        if(s==null ||s.length()==0){
            return true;
        }
        return validPalindrome(s,0,s.length()-1, 0);
    }

    private boolean validPalindrome(String s, int i, int j, int noMatchCount){
        if(noMatchCount>1){
            return false;
        }
        while(j>i){
            if(s.charAt(i) !=s.charAt(j)){
                    return validPalindrome(s, i+1, j, noMatchCount+1) ||
                    validPalindrome(s,i, j-1, noMatchCount+1);
            }else {
                i++;
                j--;
            }
        }
        return true;
    }
}

总体思路跟我差不多，但因为用了递归，避免了代码的大片重复。而且前面不需要再重头开始了，哪里不一样从哪里开始递归。