1351. 統計有序矩陣中的負數

題目鏈接

1351. 統計有序矩陣中的負數

標簽

數組 二分查找 矩陣

簡答二分查找

思路

由于矩陣每行都是按 降序 排列的，所以可以針對每行都使用二分查找來查找最后一個不是負數的元素的索引，然后給 總數 加上 本行元素個數 減去 這個索引 再 減一，不過要注意的一點是，最后一個不是負數的元素可能是重復的，所以不能在找到最后一個不是負數的元素后就退出查找，而應該繼續到 右子區間 查找，直到找到 最右邊的 不是最后一個負數的元素。

代碼

class Solution {public int countNegatives(int[][] grid) {int m = grid[0].length; // m是矩陣的列數int left, right;int cnt = 0; // 統計負數的個數for (int[] row : grid) { // 針對矩陣的每行進行操作// 每次都把查找區間限制在 [0, m - 1] 之間left = 0;right = m - 1;while (left <= right) {int mid = left + (right - left >> 1);if (0 > row[mid]) { // 如果 row[mid] < 0right = mid - 1; // 則到左子區間查詢(降序數組)} else if (0 < row[mid]) { // 如果 row[mid] > 0left = mid + 1; // 則到右子區間查詢(降序數組)} else { // 如果 row[mid] == 0left = mid + 1; // 則到右子區間查詢(降序數組)}}cnt += m - right - 1; // 統計本行的負數個數}return cnt;}
}

優化

思路

像上面的多個二分查找之間沒有任何聯系，每次都是在 $[0,m?1]$ 這個大區間進行查詢，這樣就浪費了這個矩陣的另一個特性：每列也是按降序排列的。

那么該如何利用這個特性呢？很簡單，有這個特性再加上每行都是降序排列的，就意味著 在上一行中最后一個0出現的位置 一定比 本行中最后一個0出現的位置 要更靠右或相同，所以二分查找本行時不需要將右端點重置為 m - 1，繼承上一次的右端點即可。

代碼

class Solution {public int countNegatives(int[][] grid) {int m = grid[0].length;int left, right = m - 1;int cnt = 0;for (int[] row : grid) {left = 0;while (left <= right) {int mid = left + (right - left >> 1);if (0 > row[mid]) {right = mid - 1;} else if (0 < row[mid]) {left = mid + 1;} else {left = mid + 1;}}cnt += m - right - 1;}return cnt;}
}

1. 兩數之和

題目鏈接

1. 兩數之和

標簽

數組 哈希表

思路

本題需要返回元素對應的索引，而不是只返回真假值，所以可以使用 Map 來存儲元素的值和索引的鍵值對，key為元素的值，value為元素的索引。每遍歷到一個元素就在 Map 中查找是否有 目標元素 減去 當前元素 的元素，如果有，則返回當前元素和這個元素的索引組成的數組；否則就把當前元素的值和索引存儲到 Map 中，遍歷下一個元素。

代碼

class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums.length; i++) {int curr = nums[i]; // 當前遍歷到的元素int need = target - curr; // 需要的元素，滿足 當前元素 + 需要元素 = 目標元素if (map.containsKey(need)) {return new int[]{i, map.get(need)};}map.put(curr, i);}return null;}
}

208. 實現 Trie (前綴樹)

題目鏈接

208. 實現 Trie (前綴樹)

標簽

設計 字典樹 哈希表 字符串

思路

本題和 二叉樹 有些類似，不過本題是以 小寫字符 作為區分子節點的標識，故應該叫 二十六叉樹，每個節點都有26個指針，分別指向從 'a' 到 'z' 的所有字符的節點。

可以把字符串想像成一串字符序列，而這個字符序列就是二十六叉樹的 一條路徑，比如對于字符串word = "apple"，它的路徑就是a -> p -> p -> l -> e，按照路徑把這個字符串添加到各層節點上。這就是添加方法 void insert(String word)。

在查找時，可以查找這個字符串的字符序列對應的路徑是否存在與這個二十六叉樹中，即按照這個路徑遍歷，如果有一個節點不存在，則這個字符串不存在；否則就代表字符串一定存在嗎？不一定，例如只添加了一個字符串"apple"，而現在要查詢"app"是否存在。

那么就不能只保存路徑，應該還要保存字符串的結尾字符，也就是保存這個字符是否是字符串的結尾，這樣在查找時，就可以通過是否是字符串的結尾來判斷這個單詞是否存在了。這就是查詢方法boolean search(String word)。

此外，還要實現boolean startsWith(String prefix)方法。這個方法就是 沒添加是否是字符串的結尾的標記前 的查找方法，只要存在這條路徑就滿足條件，返回true；否則就返回false。

代碼

class Trie {private static class Node {private static final int SIZE = 26; // 字符數Node[] nexts = new Node[SIZE]; // 存儲下一字母的指針數組boolean isEnd; // 記錄本節點是否是單詞的結尾}private Node root; // 前綴樹的根節點public Trie() {root = new Node();}public void insert(String word) {char[] str = word.toCharArray();Node curr = root;for (char c : str){int idx = c - 'a'; // 獲取在指針數組中的索引if (curr.nexts[idx] == null) { // 如果這個位置沒有字符節點curr.nexts[idx] = new Node(); // 則新建一個字符節點}curr = curr.nexts[idx]; // 往下一個字符節點移動}curr.isEnd = true; // 保存該字符是字符串的最后一個字符}public boolean search(String word) {char[] str = word.toCharArray();Node curr = root;for (char c : str) {int idx = c - 'a'; // 獲取在指針數組中的索引if (curr.nexts[idx] == null) { // 如果這個位置沒有字符節點return false; // 則說明字符串不存在該樹中，返回false}curr = curr.nexts[idx]; // 往下一個字符節點移動}return curr.isEnd; // 返回這個字符是否是字符串的結尾}public boolean startsWith(String prefix) {char[] str = prefix.toCharArray();Node curr = root;for (char c : str) {int idx = c - 'a'; // 獲取在指針數組中的索引if (curr.nexts[idx] == null) { // 如果這個位置沒有字符節點return false; // 則說明該樹中的字符串不以 prefix 為前綴，返回false}curr = curr.nexts[idx]; // 往下一個字符節點移動}return true; // 該樹中一定有字符串以prefix為前綴，返回true}
}