LeetCode(16) -- 509, 520, 530

P509. Fibonacci Number (Easy)

斐波那契数列。

我的思路

从第一个数开始累加就完了。如果非要用递归的话，一定要记录下来前两个数。

我的代码

public class E_509_FibonacciNumber {
    public int fib(int N) {
        if (N == 0) return 0;
        if (N == 1) return 1;
        int count = 2;
        int prev = 1;
        int prevprev = 0;
        int curr = 1;
        while (count <= N) {
            curr = prevprev + prev;
            prevprev = prev;
            prev = curr;
            count++;
        }
        return curr;
    }
}

100%

最优解

class Solution {
    public int fib(int N) {
        double goldenRatio = (1 + Math.sqrt(5)) / 2;
        return (int)Math.round(Math.pow(goldenRatio, N)/ Math.sqrt(5));
    }
}

这题方法非常多。

P520. Detect Capital (Easy)

给一个单词，判断它的大写字母用法是否正确。一个单词可以全是大写，可以全是小写，也可以首字母大写。

我的思路

判断一个字符是不是在大写字母的数值范围内就可以了。

我的代码

public class E_520_DetectCapital {
    public boolean detectCapitalUse(String word) {
        if (word.length() < 2) return true;
        char first = word.charAt(0);
        char second = word.charAt(1);
        if (first >= 'A' && first <= 'Z' && second >= 'A' && second <= 'Z') {
            for (int i = 2; i < word.length(); i++) {
                if (word.charAt(i) > 'Z') {
                    return false;
                }
            }
        } else if (first >= 'A' && first <= 'Z' && second >= 'a' && second <= 'z') {
            for (int i = 2; i < word.length(); i++) {
                if (word.charAt(i) >= 'A' && word.charAt(i) <= 'Z') {
                    return false;
                }
            }
        } else if (first >= 'a' && first <= 'z') {
            for (int i = 1; i < word.length(); i++) {
                if (word.charAt(i) >= 'A' && word.charAt(i) <= 'Z') {
                    return false;
                }
            }
        }
        return true;
    }
}

100%

最优解

class Solution {
    public boolean detectCapitalUse(String word) {
        int count = 0;

        for (int i : word.toCharArray()) {
            //if char within the range of 65 to 90, it's capital
            if (i >= 65 && i <= 90) {
                count++;
            }
        }

        return (count > 1 && count == word.length()) ||
                (count == 1 && word.charAt(0) <= 90) ||
                count == 0;
    }
}

数有多少个大写字母。不用像我那个麻烦地每种情况讨论。

P530. Minimum Absolute Difference in BST (Easy)

BST, 非负整数。找到最小的绝对值，任意两点。

我的思路

做中序遍历就能返回从小到大的值，所以记录一下前一个值，找到最小的差即可。

我的代码

public class E_530_MinimumAbsoluteDifferenceinBST {
    int prev = -1;
    int min = Integer.MAX_VALUE;
    public int getMinimumDifference(TreeNode root) {
        dfs(root);
        return min;
    }

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

100% 无论比较的结果如果，都要更新prev。有个特殊情况就是第一个数，那首先要给prev初始化一下。

最优解

class Solution {
    int min=Integer.MAX_VALUE;
    TreeNode prev=null;

    public int getMinimumDifference(TreeNode root) {
        if(root.left!=null)
             getMinimumDifference(root.left);

        if(prev!=null)
            min=Math.min(min, Math.abs(prev.val-root.val));
        prev=root;

        if(root.right!=null)
            getMinimumDifference(root.right);

        return min;
    }
}