2020-06-19

题目汇总

LeetCode 1048. Longest String Chain

算法思路

动态规划

用hashmap存储每个string的最长的chain length。记住先排序！！！

class Solution {
    public int longestStrChain(String[] words) {
        // 按照长度对words进行排序
        Arrays.sort(words, (word1, word2) -> word1.length() - word2.length());
        // 创建一个hashmap，记录当前每个word的最长的word chain是多少
        Map<String, Integer> dp = new HashMap();
        int longest = -1;

        for (int i = 0; i < words.length; i++) {
            String temp = words[i];
            int chainLength = -1;
            for (int j = 0; j < temp.length(); j++) {
                StringBuilder sb= new StringBuilder();
                String newStr = sb.append(temp.substring(0, j)).append(temp.substring(j + 1, temp.length())).toString();
                chainLength = Math.max(chainLength, dp.getOrDefault(newStr, 0) + 1);
            }
            dp.put(words[i], chainLength);
            longest = Math.max(longest, chainLength);
        }

        return longest;
    }
}

DFS + memorization（待完成）

LeetCode 268. Missing Number

算法思路

用一个boolean数组即可解决该问题。或者使用异或运算。

数组

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        boolean[] check = new boolean[n + 1];

        for (int num : nums) {
            check[num] = true;
        }

        for (int i = 0; i <= n; i++) {
            if (check[i] == false) {
                return i;
            }
        }

        return 0;
    }
}

异或

简单举个例子就能看懂了：

详情见: LeetCode Solution 3

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