LeetCode(87) -- 79, 80

P79. Word Search (Medium)

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

My Solution

class Solution {
    Set<Integer> visited = new HashSet<>();
    public boolean exist(char[][] board, String word) {
        if (board.length == 0 || board[0].length == 0) {
            return false;
        }
        if (word == null || word.length() == 0) {
            return false;
        }
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == word.charAt(0)) {
                    visited.clear();
                    if (DFS(board, word, 1, i * n + j)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    private boolean DFS(char[][] board, String word, int start, int index) {
        if (start == word.length()) {
            return true;
        }
        visited.add(index);
        char current = word.charAt(start);
        int m = board.length;
        int n = board[0].length;
        if (index >= n) {
            int up = index - n;
            if (!visited.contains(up)) {
                if (board[up / n][up % n] == current) {
                    if (DFS(board, word, start + 1, up)) {
                        return true;
                    } else {
                        visited.remove(up);
                    }
                }
            }
        }
        if (index % n > 0) {
            int left = index - 1;
            if (!visited.contains(left)) {
                if (board[left / n][left % n] == current) {
                    if (DFS(board, word, start + 1, left)) {
                        return true;
                    } else {
                        visited.remove(left);
                    }
                }
            }
        }
        if (index + n < m * n) {
            int down = index + n;
            if (!visited.contains(down)) {
                if (board[down / n][down % n] == current) {
                    if (DFS(board, word, start + 1, down)) {
                        return true;
                    } else {
                        visited.remove(down);
                    }
                }
            }
        }
        if (index % n < n - 1) {
            int right = index + 1;
            if (!visited.contains(right)) {
                if (board[right / n][right % n] == current) {
                    if (DFS(board, word, start + 1, right)) {
                        return true;
                    } else {
                        visited.remove(right);
                    }
                }
            }
        }
        return false;
    }
}

9%

The Best Solution

class Solution {
    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        char[] arr = word.toCharArray();
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(board[i][j] == arr[0]){
                    if(dfs(i, j, board, arr, 0)){
                        return true;
                    }
                }
            }
        }
        return false;
    }
    public boolean dfs(int i, int j, char[][] board, char[] arr, int index){
        if(index == arr.length){
            return true;
        }
        if(i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != arr[index]) {
            return false;
        }
        board[i][j] ^= 256;
        
        boolean ans = false;
        ans = dfs(i + 1, j, board, arr, index + 1) || dfs(i - 1, j, board, arr, index + 1) || dfs(i, j + 1, board, arr, index + 1) || dfs(i, j - 1, board, arr, index + 1);
        board[i][j] ^= 256;
        return ans;
    }
}

总结一下为什么我的代码完成同样的功能比人家的复杂那么多。

1. 首先我检查了一下index是否在界内。因为四种边界不一样，所以每次在进入之前都检查了一遍。而最优解是大胆地把index传进去，如果出界了直接返回false，就不需要每次在递归之前就检查了。

2. 我在第二层if中检查了一下是否已经访问过，如果访问过了就不调用递归函数了。而最优解用了一个非常巧妙的办法：把当前检查的字母（矩阵里的字母）跟256做“异或”运算。这样做的结果就是，这个字母的二进制码，在从右数的第九位加了一个1，实际上也就是加了256，这就不可能是一个正常的ASCII字符了，也就不可能等于要找的字母了，相当于把这个位置暂时标记为访问过了。后面经过下一层递归之后，再跟256做“异或”，相当于又把这个字符标记成原来的字符了。这样做的优势是省去了HashSet标记，同时也不需要出递归之后把这个字符从set中移除掉。

3. 我在第三层if中检查了这个字符是否跟要找的字符相同，相同再找下一个。而最优解把这一步直接放在前面，如果不相同直接就返回false了。

P80. Remove Duplicates from Sorted Array II (Medium)

Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

My Solution

class Solution {
    public int removeDuplicates(int[] nums) {
        int length = nums.length;
        if (length <= 2) {
            return length;
        }
        int i = 2;
        while (i < length && (nums[i] != nums[i - 1] || nums[i] != nums[i - 2])) {
            i++;
        }
        int j = i + 1;
        while (j < length) {
            if (nums[j] == nums[i - 1] && nums[j] == nums[i - 2]) {
                j++;
            } else {
                int temp = nums[i];
                nums[i++] = nums[j];
                nums[j++] = temp;
            }
        }
        return i;
    }
}

63% 1ms

The Best Solution

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int count = 1;
        int len = 1;
        for (int i = 1; i < nums.length; i++) {            
            if (nums[i] == nums[i - 1]) {                
                count++;                
            } else {
                count = 1;                
            }
            if (count <= 2) {
                nums[len++] = nums[i];                        
            }
        }
        return len;
    }
}

这个方法非常好，不需要互换，只要覆盖了前面的就行了。用一个计数器检查是否超过了2。