196. 刪除重復的電子郵箱

題目鏈接

196. 刪除重復的電子郵箱

表

• 表Person的字段為id和email。

要求

編寫解決方案 刪除 所有重復的電子郵件，只保留一個具有最小 id 的唯一電子郵件。

（對于 SQL 用戶，請注意你應該編寫一個 DELETE 語句而不是 SELECT 語句。）

（對于 Pandas 用戶，請注意你應該直接修改 Person 表。）

運行腳本后，顯示的答案是 Person 表。驅動程序將首先編譯并運行您的代碼片段，然后再顯示 Person 表。Person 表的最終順序 無關緊要 。

知識點

1. delete：刪除數據。形式上類似于select。

思路

保留一個具有最小 id 的唯一電子郵件意味著刪除所有 比最小 id 的電子郵件的 id 大 且 與其 email 相同 的電子郵件，所以可以使用多表“查詢”，首先得限制兩個表的 email 相同，然后刪除 id 大的那些數據即可。

代碼

deletep_big
fromPerson p_big,Person p_small
wherep_big.email = p_small.email
andp_big.id > p_small.id

73. 矩陣置零

題目鏈接

73. 矩陣置零

標簽

數組 哈希表 矩陣

簡單版

思路

如果一個元素為 0 ，則將其所在行和列的所有元素都設為 0 。這意味著只需要用兩個數組，分別存儲這行和這列是否有0，如果這行有0，則將這行元素置零；如果這列有0，則將這列元素置零。

代碼

class Solution {public void setZeroes(int[][] matrix) {int m = matrix.length, n = matrix[0].length;boolean[] isRow0 = new boolean[m];boolean[] isCol0 = new boolean[n];// 檢查每一行和每一列是否有為0的數字for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (matrix[i][j] == 0) {isRow0[i] = true;isCol0[j] = true;}}}// 置零for (int i = 0; i < m; i++) {if (isRow0[i]) {for (int j = 0; j < n; j++) {matrix[i][j] = 0;}}}for (int j = 0; j < n; j++) {if (isCol0[j]) {for (int i = 0; i < m; i++) {matrix[i][j] = 0;}}}}
}

優化版

思路

可以將統計每行每列是否有0的數組放到原矩陣中，這里使用每行的第一個元素（列首）和每列的第一個元素（行首）來統計當前行是否有0和當前列是否有0，如果有0，則列首或行首置為0。然后對“整個”（從第二行到最后一行，從第二列到最后一列的）矩陣進行掃描，如果這行第一個元素或這列第一個元素是0，則將該元素置零。

那么問題就來了，既然在此處修改了第一行和第一列，那么該如何判斷原始的第一行和第一列是否需要置零呢？使用兩個變量提前對第一行和第一列進行判斷即可。在 對“整個”（從第二行到最后一行，從第二列到最后一列的）矩陣進行掃描 完畢后，對第一行和第一列進行操作，如果原先第一行有0，則將第一行置零；如果原先第一列有0，則將第一列置零。

注意：這樣做不會破壞原矩陣（或者說不影響結果），因為如果某行（或某列）有0，那么這行（或這列）的所有元素都需要被置零。

代碼

class Solution {public void setZeroes(int[][] matrix) {int m = matrix.length, n = matrix[0].length;boolean isFirstRow0 = false, isFirstCol0 = false;// 檢查第一列是否有為0的數字for (int i = 0; i < m; i++) {if (matrix[i][0] == 0) {isFirstCol0 = true;break;}}// 檢查第一行是否有為0的數字for (int i = 0; i < n; i++) {if (matrix[0][i] == 0) {isFirstRow0 = true;break;}}// 檢查 第二行到最后一行 第二列到最后一列 是否有為0的數字for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {if (matrix[i][j] == 0) { // 如果有重復數字matrix[i][0] = matrix[0][j] = 0; // 則將本矩陣的 行首 和 列首 記為0}}}// 將 第二行到最后一行 第二列到最后一列 的元素置零for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {if (matrix[i][0] == 0 || matrix[0][j] == 0) { // 如果 本行首 或 本列首 被置零matrix[i][j] = 0; // 則將該元素置為0}}}// 如果原先矩陣的第一行有0，則將第一行置零if (isFirstRow0) {for (int j = 0; j < n; j++) {matrix[0][j] = 0;}}// 如果原先矩陣的第一列有0，則將第一行置零if (isFirstCol0) {for (int i = 0; i < m; i++) {matrix[i][0] = 0;}}}
}

105. 從前序與中序遍歷序列構造二叉樹

題目鏈接

105. 從前序與中序遍歷序列構造二叉樹

標簽

樹 數組 哈希表 分治 二叉樹

思路

注意：如果遍歷的結果中有相同的元素，則無法構造二叉樹，所以本題中的遍歷結果都是無重復值的。

先來思考一下只有中序遍歷應該如何構造二叉樹？眾所周知，中序遍歷是先遍歷左子樹、再處理本節點、最后遍歷右子樹，所以說在中序遍歷的結果中，中間元素是父節點（前提是它左子樹的節點數等于右子樹的節點數），中間元素的左子區間為它的左子樹，中間元素的右子區間為它的右子樹。

根據中間節點把整個遍歷結果拆分為兩個子區間，這兩個子區間也有這樣的性質：子區間的中間元素是父節點（前提是它左子樹的節點數等于右子樹的節點數），中間元素的左子區間為它的左子樹，右子區間為它的右子樹。

例如底下的二叉樹，它的中序遍歷結果為[1, 2, 3, 4, 5, 6, 7]，第一個父節點（根節點）為4，然后分出[1, 2, 3]和[5, 6, 7]這兩個子區間。在[1, 2, 3]中找到父節點2，在[5, 6, 7]中找到父節點6，接著將區間分為長度為1的子區間。此時直接將這個值作為葉子節點（沒有子節點的節點）即可。

既然只需要知道中序遍歷就能夠構造二叉樹，那為什么還要前序遍歷的結果？這是因為存在一種二叉樹，這種二叉樹有些節點只有一個子節點，就不能確定哪個節點是父節點。

比如底下的二叉樹，它的中序遍歷結果為[2, 3, 4, 5, 6, 7]，此時就不能輕易地將4作為第一個父節點了，因為4的左右子樹的節點數不相等。所以只知道中序遍歷的結果是無法構造二叉樹的，因為無法確定父節點。

在前序遍歷的結果[4, 2, 3, 6, 5, 7]中，第一個元素4就是第一個父節點，然后在中序遍歷的結果[2, 3, 4, 5, 6, 7]中尋找父節點，并劃分左子樹[2, 3]和右子樹[5, 6, 7]。

發現左子樹含有的元素[2, 3] 和 前序遍歷結果[4, 2, 3, 6, 5, 7]去掉父節點4后截取前2個元素（2是左子樹的長度）的結果[2, 3]含有的元素 恰好相同，右子樹含有的元素[5, 6, 7] 和 前序遍歷結果[4, 2, 3, 6, 5, 7]去掉父節點4后截取后3個元素（3是右子樹的長度）的結果[6, 5, 7]含有的元素 恰好相同。

所以構造二叉樹的策略就確定了：將前序遍歷區間內第一個值作為二叉樹的父節點，在中序遍歷的結果中尋找這個值，然后將這個值左邊的區間定義為左子樹，右邊的區間定義為右子樹，接著將前序遍歷的結果也進行劃分，去除第一個元素后，將前n（n是中序遍歷劃分的左子樹的長度）個元素作為左子樹，將后m（m是中序遍歷劃分的右子樹的長度）個元素作為右子樹。劃分完這兩個數組后，分別構造左子樹和右子樹。

代碼

class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {if (preorder.length == 0) { // 如果preorder的長度為0return null; // 則退出遞歸}int parentValue = preorder[0]; // 記錄父節點的值TreeNode parent = new TreeNode(parentValue); // 以preorder的第一個值作為父節點for (int i = 0; i < preorder.length; i++) {if (inorder[i] == parentValue) { // 如果在inorder中找到父節點int[] preLeft = Arrays.copyOfRange(preorder, 1, i + 1); // 截取preorder的左子樹區間int[] preRight = Arrays.copyOfRange(preorder, i + 1, inorder.length); // 截取preorder的右子樹區間int[] inLeft = Arrays.copyOfRange(inorder, 0, i); // 截取inorder的左子樹區間int[] inRight = Arrays.copyOfRange(inorder, i + 1, inorder.length); // 截取inorder的右子樹區間parent.left = buildTree(preLeft, inLeft); // 構造左子樹parent.right = buildTree(preRight, inRight); // 構造右子樹break;}}return parent; // 返回本輪遞歸的父節點}
}