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
, andgetMin
最多被调用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();}
}
踩坑点
没想到字符串切片,纯指针实现切片,代码臃肿。