LeetCode 211-220

211. 添加与搜索单词 - 数据结构设计

class WordDictionary {
    class TrieNode {
        TrieNode[] links;
        boolean end;

        public TrieNode() {
            this.links = new TrieNode[26];
        }
    }

    TrieNode root;

    public WordDictionary() {
        this.root = new TrieNode();
    }

    public void addWord(String word) {
        TrieNode cur = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (cur.links[c - 'a'] == null) {
                cur.links[c - 'a'] = new TrieNode();
            }
            cur = cur.links[c - 'a'];
        }
        cur.end = true;
    }

    private boolean helper(String word, TrieNode root) {
        TrieNode cur = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (c != '.') {
                if (cur.links[c - 'a'] != null) {
                    cur = cur.links[c - 'a'];
                } else {
                    return false;
                }
            } else {
                for (int j = 0; j < 26; j++) {
                    if (cur.links[j] != null && helper(word.substring(i + 1), cur.links[j])) {
                        return true;
                    }
                }
                return false;
            }
        }
        return cur.end;
    }

    public boolean search(String word) {
        return helper(word, root);
    }
}

212. 单词搜索 II

class Solution {
    int[] X = {0, 0, 1, -1}, Y = {1, -1, 0, 0};
    boolean[][] isVisit;

    private boolean helper(char[][] board, int i, int j, int num, String word) {
        if (num == word.length()) {
            return true;
        }
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || isVisit[i][j] == true) {
            return false;
        }
        if (board[i][j] == word.charAt(num)) {
            isVisit[i][j] = true;
            for (int k = 0; k < 4; k++) {
                int newI = i + X[k], newJ = j + Y[k];
                if (helper(board, newI, newJ, num + 1, word) == true) {
                    return true;
                }
            }
            isVisit[i][j] = false;
            return false;
        } else {
            return false;
        }
    }

    public List<String> findWords(char[][] board, String[] words) {
        isVisit = new boolean[board.length][board[0].length];
        Set<String> set = new HashSet<>();
        for (String word : words) {
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[0].length; j++) {
                    for (int k = 0; k < board.length; k++) {
                        Arrays.fill(isVisit[k], false);
                    }
                    if (helper(board, i, j, 0, word)) {
                        set.add(word);
                    }
                }
            }
        }
        return new ArrayList<>(set);
    }
}

213. 打家劫舍 II

偷第一间就不能偷最后一间，不偷第一间就可以偷最后一间。取两种情况的较大值。

class Solution {
    public int rob(int[] nums) {
        int[] dp = new int[nums.length];//偷第一间
        dp[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (i == nums.length - 1) {
                dp[i] = dp[i - 1];
                continue;
            }
            dp[i] = Math.max((i - 2 >= 0 ? dp[i - 2] : 0) + nums[i], dp[i - 1]);
        }
        int res = dp[nums.length - 1];
        Arrays.fill(dp, 0);//不偷第一间
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max((i - 2 >= 0 ? dp[i - 2] : 0) + nums[i], dp[i - 1]);
        }
        return Math.max(res, dp[nums.length - 1]);
    }
}

214. 最短回文串

暴力法：
不断从大到小枚举s的前缀，只要某个前缀是回文串，那么把后面的子串反转之后加到前面，便是最短的回文串。
时间复杂度On2，最后一个案例超时。

class Solution {
    private boolean isPar(String s) {
        if ("".equals(s)) {
            return true;
        }
        int i = 0, j = s.length() - 1;
        while (i < j) {
            if (s.charAt(i++) != s.charAt(j--)) {
                return false;
            }
        }
        return true;
    }

    public String shortestPalindrome(String s) {
        if ("".equals(s)) {
            return "";
        }
        StringBuilder res = new StringBuilder();
        for (int i = s.length() - 1; i >= 0; i--) {
            if (isPar(s.substring(0, i + 1))) {
                StringBuilder str = new StringBuilder(s.substring(i + 1));
                str.reverse();
                res.append(str).append(s);
                return res.toString();
            }
        }
        StringBuilder str = new StringBuilder(s.substring(1));
        str.reverse();
        res.append(str).append(s);
        return res.toString();
    }
}

字符串哈希:
如果测试数据比较刁钻，改一下base和mod或者在left==right的时候加一个双重验证，手动判断是不是回文串。

class Solution {
    public String shortestPalindrome(String s) {
        int len = s.length();
        long base = 131, mod = 1000000007;
        long left = 0, right = 0, mul = 1, best = -1;
        for (int i = 0; i < len; i++) {
            left = (left * base + s.charAt(i)) % mod;
            right = (right + mul * s.charAt(i)) % mod;
            if (left == right) {
                best = i;
            }
            mul = mul * base % mod;
        }
        String add = (best == len - 1 ? "" : s.substring((int) best + 1));
        StringBuilder res = new StringBuilder(add).reverse();
        res.append(s);
        return res.toString();
    }
}

215. 数组中的第K个最大元素

自己写的快排37ms。

class Solution {
    public int partition(int lo, int hi, int[] nums) {
        int temp = nums[lo];
        while (lo < hi) {
            while (lo < hi && nums[hi] > temp) {
                hi--;
            }
            nums[lo] = nums[hi];
            while (lo < hi && nums[lo] < temp) {
                lo++;
            }
            nums[hi] = nums[lo];
        }
        nums[lo] = temp;
        return lo;
    }

    public void quickSort(int lo, int hi, int[] nums) {
        if (lo < hi) {
            int pivot = partition(lo, hi, nums);
            quickSort(lo, pivot - 1, nums);
            quickSort(pivot + 1, hi, nums);
        }
    }

    public int findKthLargest(int[] nums, int k) {
        quickSort(0, nums.length - 1, nums);
        return nums[nums.length - k];
    }
}

库函数的快排2ms。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }
}

最大堆 2ms：

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int heapSize = nums.length;
        buildMaxHeap(nums, heapSize);
        for (int i = nums.length - 1; i >= nums.length - k + 1; --i) {
            swap(nums, 0, i);
            --heapSize;
            maxHeapify(nums, 0, heapSize);
        }
        return nums[0];
    }

    public void buildMaxHeap(int[] a, int heapSize) {
        for (int i = heapSize / 2; i >= 0; --i) {
            maxHeapify(a, i, heapSize);
        } 
    }

    public void maxHeapify(int[] a, int i, int heapSize) {
        int l = i * 2 + 1, r = i * 2 + 2, largest = i;
        if (l < heapSize && a[l] > a[largest]) {
            largest = l;
        } 
        if (r < heapSize && a[r] > a[largest]) {
            largest = r;
        }
        if (largest != i) {
            swap(a, i, largest);
            maxHeapify(a, largest, heapSize);
        }
    }

    public void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

216. 组合总和 III

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

    public void dfs(int begin, int k, int n) {
        if (n < 0 || k < 0) {
            return;
        }
        if (k == 0 && n == 0) {
            res.add(new ArrayList<>(temp));
        }
        for (int i = begin; i <= 9; i++) {
            temp.add(i);
            dfs(i + 1, k - 1, n - i);
            temp.remove(temp.size() - 1);
        }
    }

    public List<List<Integer>> combinationSum3(int k, int n) {
        dfs(1, k, n);
        return res;
    }
}

217. 存在重复元素

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int i : nums) {
            if (!set.add(i)) {
                return true;
            }
        }
        return false;
    }
}

218. 天际线问题

线段树，面试应该不会考，先不做了。

219. 存在重复元素 II

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                if (i - map.get(nums[i]) <= k) {
                    return true;
                } else {
                    map.put(nums[i], i);
                }
            } else {
                map.put(nums[i], i);
            }
        }
        return false;
    }
}