LeetCode 251-280

257. 二叉树的所有路径

class Solution {
    List<String> res = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();

    private void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        temp.add(root.val);
        if (root.left == null && root.right == null) {
            StringBuilder sb = new StringBuilder();
            sb.append(temp.get(0));
            for (int i = 1; i < temp.size(); i++) {
                sb.append("->" + temp.get(i));
            }
            res.add(sb.toString());
        }
        dfs(root.left);
        dfs(root.right);
        temp.remove(temp.size() - 1);
    }

    public List<String> binaryTreePaths(TreeNode root) {
        dfs(root);
        return res;
    }
}

258. 各位相加

class Solution {
    public int addDigits(int num) {
        while (num >= 10) {
            int sum = 0;
            while (num != 0) {
                sum += num % 10;
                num /= 10;
            }
            num = sum;
        }
        return num;
    }
}

O(1)复杂度:

class Solution {
    public int addDigits(int num) {
        return (num - 1) % 9 + 1;
    }
}

260. 只出现一次的数字 III

使用HashSet，时间复杂度On:

class Solution {
    public int[] singleNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (set.add(nums[i]) == false) {
                set.remove(nums[i]);
            }
        }
        Iterator<Integer> it = set.iterator();
        return new int[]{it.next(), it.next()};
    }
}

263. 丑数

class Solution {
    public boolean isUgly(int num) {
        if (num <= 0) {
            return false;
        }
        while (num % 5 == 0) {
            num /= 5;
        }
        while (num % 3 == 0) {
            num /= 3;
        }
        while (num % 2 == 0) {
            num /= 2;
        }
        return num == 1;
    }
}

264. 丑数 II

最小堆：

class Solution {
    public int nthUglyNumber(int n) {
        int[] ugly = new int[1690];
        Set<Long> isVisit = new HashSet<>();
        Queue<Long> heap = new PriorityQueue<>();
        long curUgly, newUgly;
        int[] primes = {2, 3, 5};
        heap.offer(1L);
        isVisit.add(1L);
        for (int i = 0; i < 1690; i++) {
            curUgly = heap.poll();
            ugly[i] = (int) curUgly;
            for (int j : primes) {
                newUgly = curUgly * j;
                if (!isVisit.contains(newUgly)) {
                    isVisit.add(newUgly);
                    heap.offer(newUgly);
                }
            }
        }
        return ugly[n - 1];
    }
}

三指针：

class Solution {
    public int nthUglyNumber(int n) {
        if (n == 0) {
            return 0;
        }
        int[] uglies = new int[n], pos = {0, 0, 0};
        uglies[0] = 1;
        for (int i = 1; i < n; i++) {
            int a = uglies[pos[0]] * 2, b = uglies[pos[1]] * 3, c = uglies[pos[2]] * 5;
            int next = Math.min(a, Math.min(b, c));
            if (next == a) {
                pos[0]++;
            }
            if (next == b) {
                pos[1]++;
            }
            if (next == c) {
                pos[2]++;
            }
            uglies[i] = next;
        }
        return uglies[n - 1];
    }
}

268. 丢失的数字

容易想到的方法有排序或者使用哈希表。
下面使用异或，时间复杂度On，空间复杂度O1。

class Solution {
    public int missingNumber(int[] nums) {
        int res = nums.length;
        for (int i = 0; i < nums.length; i++) {
            res ^= nums[i] ^ i;
        }
        return res;
    }
}

274. H 指数

class Solution {
    public int hIndex(int[] citations) {
        Arrays.sort(citations);
        int len = citations.length;
        for (int i = len; i >= 1; i--) {
            if (citations[len - i] >= i) {
                return i;
            }
        }
        return 0;
    }
}

275. H 指数 II

时间复杂度On：

class Solution {
    public int hIndex(int[] citations) {
        int len = citations.length;
        for (int i = len; i >= 1; i--) {
            if (citations[len - i] >= i) {
                return i;
            }
        }
        return 0;
    }
}

278. 第一个错误的版本

套模板，找到第一个满足isBadVersion(mid) == true的数。

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int lo = 1, hi = n;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (isBadVersion(mid) == true) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }
}

279. 完全平方数

dp[i]代表给定正整数i，最少的完全平方数之和等于i的个数。
边界：
dp[0] = 0
转移方程：
dp[i] 等于 所有 dp[i - j * j]的最小者再加1， 其中 j * j <= i。
时间 30 ms。

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 1; j * j <= i; j++) {
                min = Math.min(min, dp[i - j * j] + 1);
            }
            dp[i] = min;
        }
        return dp[n];
    }
}

优化，把dp设为静态变量，它属于整个类所有，而不是某个对象所有，即被类的所有对象共享，这样就不用每次不用重新算一遍dp数组了。
时间 8 ms。

class Solution {
    static ArrayList<Integer> dp = new ArrayList<>();

    public int numSquares(int n) {
        //第一次进入将 0 加入
        if (dp.size() == 0) {
            dp.add(0);
        }
        //之前是否计算过 n
        if (dp.size() <= n) {
            //接着之前最后一个值开始计算
            for (int i = dp.size(); i <= n; i++) {
                int min = Integer.MAX_VALUE;
                for (int j = 1; j * j <= i; j++) {
                    min = Math.min(min, dp.get(i - j * j) + 1);
                }
                dp.add(min);
            }
        }
        return dp.get(n);
    }
}