Leetcode 295.數據流的中位數

295.數據流的中位數

問題描述

中位數是有序整數列表中的中間值。如果列表的大小是偶數，則沒有中間值，中位數是兩個中間值的平均值。

例如 arr = [2,3,4] 的中位數是 3 。
例如 arr = [2,3] 的中位數是 (2 + 3) / 2 = 2.5 。

實現 MedianFinder 類:

MedianFinder() 初始化 MedianFinder 對象。
void addNum(int num) 將數據流中的整數 num 添加到數據結構中。
double findMedian() 返回到目前為止所有元素的中位數。與實際答案相差 10-5 以內的答案將被接受。

示例 1：

輸入
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
輸出
[null, null, null, 1.5, null, 2.0]解釋
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

提示:

-105 <= num <= 105
在調用 findMedian 之前，數據結構中至少有一個元素
最多 5 * 104 次調用 addNum 和 findMedian

解題思路與代碼實現

思路：

設置兩個優先隊列（相當于堆）queMin和queMax：

queMin：記錄小于等于中位數的數；

queMax：記錄大于中位數的數

添加元素時維持： queMax元素個數 <=queMin的元素個數 <=queMax元素個數 +1

取中位數時：

若queMax元素個數 ==queMin的元素個數，從queMin和queMax 取出二者隊頭元素的平均值；
若queMax元素個數 <queMin的元素個數，從queMin取出隊頭元素；

代碼實現：

class MedianFinder {PriorityQueue<Integer> queMin; // 記錄小于等于中位數的數PriorityQueue<Integer> queMax; // 記錄大于中位數的數public MedianFinder() {queMin = new PriorityQueue<>(Comparator.reverseOrder()); // 降序排序queMax = new PriorityQueue<>(Comparator.naturalOrder()); // 升序排序}/*** 添加元素時保持：* queMin的元素個數 >= queMax元素個數 && queMin的元素個數 <= queMax元素個數 + 1*/public void addNum(int num) {if (queMin.isEmpty() || queMin.peek() >= num) { // 第一個元素或者num小于等于queMin最大元素queMin.offer(num);// 盡可能保持兩者元素數量相等if (queMin.size() > queMax.size() + 1) {queMax.offer(queMin.poll());}} else { // num大于queMax最小元素queMax.offer(num);// 盡可能保持兩者元素數量相等if (queMax.size() > queMin.size()) {queMin.offer(queMax.poll());}}}public double findMedian() {if (queMin.size() > queMax.size()) {return queMin.peek();}return (queMin.peek() + queMax.peek()) / 2.0;}
}

155. 最小棧

問題描述

設計一個支持 push ，pop ，top 操作，并能在常數時間內檢索到最小元素的棧。

實現 MinStack 類:

MinStack() 初始化堆棧對象。
void push(int val) 將元素val推入堆棧。
void pop() 刪除堆棧頂部的元素。
int top() 獲取堆棧頂部的元素。
int getMin() 獲取堆棧中的最小元素。

示例 1:

輸入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]輸出：
[null,null,null,null,-3,null,0,-2]解釋：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

提示：

-231 <= val <= 231 - 1
pop、top 和 getMin 操作總是在 非空棧 上調用
push, pop, top, and getMin最多被調用 3 * 104 次

解題思路與代碼實現

思路：

設置輔助棧，棧中元素為長度為2的數組，分別存當前插入的val值和它插入后棧中的最小val值。

插入元素時：直接放在棧頂

當前棧為空時，當前插入的val值就是插入后棧中的最小val值；
當前棧為不空時，插入后棧中的最小val值要么是當前插入的val值，要么是插入前棧中的最小val值；

取出最小元素：從棧頂元素獲取當前棧中的最小val值；

代碼實現：

class MinStack {// 棧中元素為長度為2的數組，分別存當前插入的val值和它插入后棧中的最小val值Stack<int[]> stack = null;public MinStack() {stack = new Stack<>();}public void push(int val) {if (stack.isEmpty()) { // 當前堆棧為空stack.push(new int[] { val, val });} else { // 堆棧不為空int[] item = stack.peek();stack.push(new int[] { val, Math.min(item[1], val) });}}// 棧頂元素出棧public void pop() {stack.pop();}public int top() {int[] item = stack.peek();return item[0];}// 獲取堆棧中的最小元素public int getMin() {int[] item = stack.peek();return item[1];}
}

踩坑點

棧頂元素需要記錄當前棧中最小的val值

37. 解數獨

問題描述

編寫一個程序，通過填充空格來解決數獨問題。

數獨的解法需 遵循如下規則：

數字 1-9 在每一行只能出現一次。
數字 1-9 在每一列只能出現一次。
數字 1-9 在每一個以粗實線分隔的 3x3 宮內只能出現一次。（請參考示例圖）

數獨部分空格內已填入了數字，空白格用 '.' 表示。

示例 1：

輸入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
輸出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
解釋：輸入的數獨如上圖所示，唯一有效的解決方案如下所示：

提示：

board.length == 9
board[i].length == 9
board[i][j] 是一位數字或者 '.'
題目數據保證輸入數獨僅有一個解

解題思路與代碼實現

思路：

回溯暴力解，給回溯函數設置返回值，當找到一個可行解時，停止計算，返回結果。

代碼實現：

class Solution {private final int N = 9;public void solveSudoku(char[][] board) {backtracking(board, 0, 0);}/*** 回溯函數* 設置返回值是為了當找到一個可行解時，停止計算，返回結果** @return flag 是否找到了唯一的解*/private boolean backtracking(char[][] board, int row, int col) {if (row == N) { // 遍歷了整個棋盤返回truereturn true;}// 當前位置已有數字，去處理下一位置if (board[row][col] != '.') {int nextRow = col == N - 1 ? row + 1 : row;int nextCol = col == N - 1 ? 0 : col + 1;boolean flag = backtracking(board, nextRow, nextCol);return flag;}for (char k = '1'; k <= '9'; k++) {// 用1-9在當前位置嘗試if (isValid(board, row, col, k)) {board[row][col] = k;int nextRow = col == N - 1 ? row + 1 : row;int nextCol = col == N - 1 ? 0 : col + 1;boolean flag = backtracking(board, nextRow, nextCol);if (flag) { // 找到了可行解，停止計算return true;}board[row][col] = '.'; // 回溯}}// 用1-9在當前位置都不滿足，返回falsereturn false;}/*** 判斷當前位置是否有效*/private boolean isValid(char[][] board, int row, int col, char c) {// 判斷同一行或者同一列是否有重復數字for (int i = 0; i < N; i++) {if (c == board[row][i] // 同一行|| c == board[i][col]) { // 同一列return false;}}// 判斷3*3區域是否有重復數字int startX = row / 3 * 3;int startY = col / 3 * 3;for (int i = startX; i < startX + 3; i++) {for (int j = startY; j < startY + 3; j++) {if (c == board[i][j]) {return false;}}}return true;}}

踩坑點

判斷當前位置試探的數字在所在的3*3棋盤是否重復

71.簡化路徑

問題描述

給你一個字符串 path ，表示指向某一文件或目錄的 Unix 風格 絕對路徑 （以 '/' 開頭），請你將其轉化為更加簡潔的規范路徑。

在 Unix 風格的文件系統中，一個點（.）表示當前目錄本身；此外，兩個點（..）表示將目錄切換到上一級（指向父目錄）；兩者都可以是復雜相對路徑的組成部分。任意多個連續的斜杠（即，'//'）都被視為單個斜杠 '/' 。對于此問題，任何其他格式的點（例如，'...'）均被視為文件/目錄名稱。

請注意，返回的 規范路徑 必須遵循下述格式：

始終以斜杠 '/' 開頭。
兩個目錄名之間必須只有一個斜杠 '/' 。
最后一個目錄名（如果存在）不能以 '/' 結尾。
此外，路徑僅包含從根目錄到目標文件或目錄的路徑上的目錄（即，不含 '.' 或 '..'）。

返回簡化后得到的 規范路徑 。

示例 1：

輸入：path = "/home/"
輸出："/home"
解釋：注意，最后一個目錄名后面沒有斜杠。

示例 2：

輸入：path = "/../"
輸出："/"
解釋：從根目錄向上一級是不可行的，因為根目錄是你可以到達的最高級。

示例 3：

輸入：path = "/home//foo/"
輸出："/home/foo"
解釋：在規范路徑中，多個連續斜杠需要用一個斜杠替換。

示例 4：

輸入：path = "/a/./b/../../c/"
輸出："/c"

提示：

1 <= path.length <= 3000
path 由英文字母，數字，'.'，'/' 或 '_' 組成。
path 是一個有效的 Unix 風格絕對路徑。

解題思路與代碼實現

思路：

使用輔助棧求解，先對字符串先切片，遍歷字符串數組判斷：

如果不是空串且不是".“且不是”…"，加入到棧;
如果是"."，跳過，不作任何處理；
如果是"…"且棧不為空，彈出棧頂元素；

最后拼接棧中字符串返回。

代碼實現：

class Solution {public String simplifyPath(String path) {String[] strs = path.split("/"); // 字符串切片Stack<String> stack = new Stack<>(); // 輔助棧for (String str : strs) {// 切片后：當前字符串不為空串也不為.和..，加入到棧中if (!str.equals("") && !str.equals(".") && !str.equals("..")) {stack.push(str);} else if (str.equals("..") && !stack.isEmpty()) {// 當前字符串為..且棧中不為空，則彈出棧頂元素stack.pop();}}if (stack.isEmpty()) { // 棧為空，返回根目錄return "/";}// 拼接棧中字符串StringBuilder builder = new StringBuilder();while (!stack.isEmpty()) {builder.insert(0, "/" + stack.pop());}return builder.toString();}
}