活跃农民
- 积分
- 765
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2018-6-6
- 最后登录
- 1970-1-1
|
04/13
80. Remove Duplicates from Sorted Array II
26题的follow-up，典型的two pointers问题。
1）维护两个pointer：right指向第一个未被扫描的元素；left指向最后一个已去重的元素，而非第一个可被放入的位置（即最后一个去重的元素的下一位）
2）如果left != 0 且 nums[right] == nums[left] 且 nums[left] == nums[left - 1]这三个条件同时满足时，表示已经有两个相同的当前元素了，所以直接跳过当前元素，right++
3）否则，nums[++left] = nums[right++];
- class Solution {
- public int removeDuplicates(int[] nums) {
- if (nums == null || nums.length == 0) return 0;
- int left = 0, right = 1;
-
- while (right < nums.length) {
- if (nums[right] == nums[left] && left != 0 && nums[left] == nums[left - 1]) right++;
- else nums[++left] = nums[right++];
- }
- return left + 1;
- }
- }
79. Word Search
典型的DFS问题，用recursion。
1）遍历每个board中的元素，利用helper method判断能否从当前元素开始找到word
2）helper method中，因为是recursion，所以需要先写明终止条件，如过界、遍历到了已经被遍历过的元素、当前元素不在word相应位置等，返回false
3）另一个终止条件是，如果遍历完了整个word，那么返回true表示找到了
4）判断从当前元素开始的四个邻居能否找到，如果有至少一个邻居能找到就能返回true
5）如果没有一个邻居能找到，返回false
- class Solution {
- public boolean exist(char[][] board, String word) {
- if (word == null || word.length() == 0) return false;
-
- int rowLen = board.length, colLen = rowLen == 0 ? 0 : board[0].length;
- char[] wArray = word.toCharArray();
- boolean[][] visited = new boolean[rowLen][colLen];
-
- for (int row = 0; row < rowLen; row++) {
- for (int col = 0; col < colLen; col++) {
- if (find(board, row, col, wArray, 0, visited)) return true;
- }
- }
- return false;
- }
-
- private boolean find(char[][] board, int row, int col, char[] wArray, int pos, boolean[][] visited) {
- if (row < 0 || row >= board.length || col < 0 || col >= board[0].length || board[row][col] != wArray[pos] || visited[row][col]) return false;
- if (pos == wArray.length - 1) return true;
- visited[row][col] = true;
- if(find(board, row + 1, col, wArray, pos + 1, visited)
- || find(board, row - 1, col, wArray, pos + 1, visited)
- || find(board, row, col + 1, wArray, pos + 1, visited)
- || find(board, row, col - 1, wArray, pos + 1, visited)) return true;
- visited[row][col] = false;
- return false;
- }
- }
212. Word Search II
79题的follow-up，难度增加是因为要搜索一个dictionary里存在的words而不是只看某一个word是否存在。做法是，将这些words以trie的形式表示，然后按每个character搜索。换言之单个word搜索是trie的特殊形式。
1）自己构建TrieNode，内部维护TrieNode array表示出现过的character。注意：和一般的trie不同的地方在于，平常的trie还会维护一个boolean来表示上一个字母是不是某个word的最后一个字母，但由于题目的要求，可以直接维护一个String来表示这个word。
2）将dictionary里的所有words填进trie里，返回head
3）遍历board里的所有元素，用helper method来判断从这个元素开始能否找到一个word
4）确定终止条件
5）如果当前的TrieNode的word变量存在，说明找到了这样一个word，加入list，同时注意要把word变为null，把这个word从trie里删除，来避免重复加入
6）把当前的board元素标记为#，避免走回头路。搜索完成后在恢复为原来的元素
- class Solution {
- List<String> list = new ArrayList<>();
- int[] dir = new int[]{0, 1, 0, -1, 0};
- public List<String> findWords(char[][] board, String[] words) {
- if (words == null || words.length == 0) return list;
- int rowLen = board.length, colLen = rowLen == 0? 0 : board[0].length;
-
- TrieNode head = buildTrie(words);
- for (int row = 0; row < rowLen; row++) {
- for (int col = 0; col < colLen; col++) {
- dfs(board, row, col, head);
- }
- }
- return list;
- }
-
- private void dfs(char[][] board, int row, int col, TrieNode node) {
- if (row < 0 || row >= board.length || col < 0 || col >= board[0].length || board[row][col] == '#' || node.next[board[row][col]] == null) return;
- char c = board[row][col];
- if (node.next[c].word != null) {
- list.add(node.next[c].word);
- node.next[c].word = null;
- }
- board[row][col] = '#';
- for (int i = 0; i < 4; i++) {
- dfs(board, row + dir[i], col + dir[i + 1], node.next[c]);
- }
- board[row][col] = c;
- }
-
- private TrieNode buildTrie(String[] words) {
- TrieNode head = new TrieNode();
- for (String word: words) {
- TrieNode node = head;
- for (char c: word.toCharArray()) {
- if (node.next[c] == null) node.next[c] = new TrieNode();
- node = node.next[c];
- }
- node.word = word;
- }
- return head;
- }
-
- class TrieNode {
- TrieNode[] next;
- String word;
- TrieNode() {
- next = new TrieNode[128];
- }
- }
- }
75. Sort Colors
简化的quicksort，元素只有3个。
1）维护3个pointers，其中left指向最后一个0的下一个元素（即第一个1）表示新的0可插入的位置；right指向第一个2的前一个元素表示新的2可插入的位置；mid指向第一个未被扫描的元素（即最后一个1的下一个元素）。[mid, right] inclusively是未扫描的元素。
2）循环条件：mid <= right
3）nums[mid]为1，什么都不做，mid++
4）nums[mid]为0，和nums[left]交换元素，同时left++，mid++
5）nums[mid]为2，和nums[right]交换元素，同时right--
- class Solution {
- public void sortColors(int[] nums) {
- if (nums == null || nums.length < 2) return;
- int left = 0, mid = 0, right = nums.length - 1;
- while (mid <= right) {
- if (nums[mid] == 1) mid++;
- else if (nums[mid] == 0) swap(nums, left++, mid++);
- else swap(nums, mid, right--);
- }
- }
- private void swap(int[] nums, int i, int j) {
- int temp = nums[i];
- nums[i] = nums[j];
- nums[j] = temp;
- }
- }
66. Plus One
简单数学的应用。从右向左，当carry不为零时，继续加，否则跳出循环。
64. Minimum Path Sum
典型的DP题。可以维护一个二维dp数组，但观察发现实际上dp[i]只和自身和dp[i - 1]有关，所以可以降维至一维，动态更新。
1）单独更新dp[0]
2）row == 0时，dp更新不需要经过选择，只和dp[i - 1]有关
3）除了第0行/列，dp[i]更新为自身和dp[i - 1]的较小值与grid[row][col]的和。
4）最后返回dp[n - 1]
- class Solution {
- public int minPathSum(int[][] grid) {
- int rowLen = grid.length, colLen = rowLen == 0? 0 : grid[0].length;
- int[] dp = new int[colLen];
-
- for (int row = 0; row < rowLen; row++) {
- dp[0] += grid[row][0];
- for (int col = 1; col < colLen; col++) {
- if (row == 0) dp[col] = grid[row][col] + dp[col - 1];
- else dp[col] = grid[row][col] + Math.min(dp[col], dp[col - 1]);
- }
- }
- return dp[colLen - 1];
- }
- }
|
|
楼主: Garhom
狗仔卡
楼主
