我的算法刷题笔记(3.18-3.22)
- 1. 螺旋矩阵
- 1. total是总共走的步数
- 2. int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};方位
- 3. visited[row][column] = true;用于判断是否走完一圈
- 2. 生命游戏
- 1. 使用额外的状态2
- 2. 再复制一份数组
- 3. 旋转图像
- 观察规律,只需四分之一
- 4. 矩阵置零
- 1. 用第一列存储状态,但是需要从后往前
- 5. 有效的括号
- 1. Map存储 put('{','}'); put('[',']'); put('(',')'); put('?','?')
- 6. 二叉树的中序遍历
- 7. 移掉 K 位数字
- 用12345 54321 15324 作为找规律
- 8. 去除重复字母
- 先拼接到答案,看后面逻辑是否回删
- 如何遇到重复,那么跳过即可
- 9. 字符串中的第一个唯一字符
- 10. 最近的请求次数
- 11. 数组中的第K个最大元素
- 1. 小根堆创建
- 前k个入队列,然后与剩下的对比
- 12. 查找和最小的 K 对数字
- 堆中的第一个元素一定是答案
- 13. 丑数Ⅱ
- 14. 删除有序数组中的重复项
- 15.下一个排列
- 16. 合并两个有序数组
- 17. 轮转数组
- 18. 比较版本号
- 19. 验证回文串
- 20. 重复的DNA序列
- 21. 找到 K 个最接近的元素
- 22. 两数相加
- 23. 旋转链表
- 24. 删除排序链表中的重复元素 II
- 25. 反转链表 II
- 26. 两两交换链表中的节点
- 27. 重排链表
- 28. 相交链表
- 29. 存在重复元素 II
1. 螺旋矩阵
原题链接
1. total是总共走的步数
2. int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};方位
3. visited[row][column] = true;用于判断是否走完一圈
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> order = new ArrayList<Integer>();
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return order;
}
int rows = matrix.length, columns = matrix[0].length;
boolean[][] visited = new boolean[rows][columns];
int total = rows * columns;
int row = 0, column = 0;
int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int directionIndex = 0;
for (int i = 0; i < total; i++) {
order.add(matrix[row][column]);
visited[row][column] = true;
int nextRow = row + directions[directionIndex][0], nextColumn = column + directions[directionIndex][1];
if (nextRow < 0 || nextRow >= rows || nextColumn < 0 || nextColumn >= columns || visited[nextRow][nextColumn]) {
directionIndex = (directionIndex + 1) % 4;
}
row += directions[directionIndex][0];
column += directions[directionIndex][1];
}
return order;
}
}
2. 生命游戏
原题链接
1. 使用额外的状态2
class Solution {
public void gameOfLife(int[][] board) {
int[] neighbors = {0, 1, -1};
int rows = board.length;
int cols = board[0].length;
// 遍历面板每一个格子里的细胞
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
// 对于每一个细胞统计其八个相邻位置里的活细胞数量
int liveNeighbors = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (!(neighbors[i] == 0 && neighbors[j] == 0)) {
// 相邻位置的坐标
int r = (row + neighbors[i]);
int c = (col + neighbors[j]);
// 查看相邻的细胞是否是活细胞
if ((r < rows && r >= 0) && (c < cols && c >= 0) && (Math.abs(board[r][c]) == 1)) {
liveNeighbors += 1;
}
}
}
}
// 规则 1 或规则 3
if ((board[row][col] == 1) && (liveNeighbors < 2 || liveNeighbors > 3)) {
// -1 代表这个细胞过去是活的现在死了
board[row][col] = -1;
}
// 规则 4
if (board[row][col] == 0 && liveNeighbors == 3) {
// 2 代表这个细胞过去是死的现在活了
board[row][col] = 2;
}
}
}
// 遍历 board 得到一次更新后的状态
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
if (board[row][col] > 0) {
board[row][col] = 1;
} else {
board[row][col] = 0;
}
}
}
}
}
作者:力扣官方题解
链接:https://leetcode.cn/problems/game-of-life/solutions/179750/sheng-ming-you-xi-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
2. 再复制一份数组
class Solution {
public void gameOfLife(int[][] board) {
int[] neighbors = {0, 1, -1};
int rows = board.length;
int cols = board[0].length;
// 创建复制数组 copyBoard
int[][] copyBoard = new int[rows][cols];
// 从原数组复制一份到 copyBoard 中
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
copyBoard[row][col] = board[row][col];
}
}
// 遍历面板每一个格子里的细胞
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
// 对于每一个细胞统计其八个相邻位置里的活细胞数量
int liveNeighbors = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (!(neighbors[i] == 0 && neighbors[j] == 0)) {
int r = (row + neighbors[i]);
int c = (col + neighbors[j]);
// 查看相邻的细胞是否是活细胞
if ((r < rows && r >= 0) && (c < cols && c >= 0) && (copyBoard[r][c] == 1)) {
liveNeighbors += 1;
}
}
}
}
// 规则 1 或规则 3
if ((copyBoard[row][col] == 1) && (liveNeighbors < 2 || liveNeighbors > 3)) {
board[row][col] = 0;
}
// 规则 4
if (copyBoard[row][col] == 0 && liveNeighbors == 3) {
board[row][col] = 1;
}
}
}
}
}
3. 旋转图像
原题链接
观察规律,只需四分之一
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
for (int i = 0; i < n / 2; ++i) {
for (int j = 0; j < (n + 1) / 2; ++j) {
int temp = matrix[i][j];
matrix[i][j] = matrix[n - j - 1][i];
matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
matrix[j][n - i - 1] = temp;
}
}
}
}
4. 矩阵置零
1. 用第一列存储状态,但是需要从后往前
原题链接
class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
boolean flagCol0 = false;
for (int i = 0; i < m; i++) {
if (matrix[i][0] == 0) {
flagCol0 = true;
}
for (int j = 1; j < n; j++) {
if (matrix[i][j] == 0) {
matrix[i][0] = matrix[0][j] = 0;
}
}
}
for (int i = m - 1; i >= 0; i--) {
for (int j = 1; j < n; j++) {
if (matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
if (flagCol0) {
matrix[i][0] = 0;
}
}
}
}
5. 有效的括号
1. Map存储 put(‘{’,‘}’); put(‘[’,‘]’); put(‘(’,‘)’); put(‘?’,‘?’)
原题链接
class Solution {
private static final Map<Character,Character> map = new HashMap<Character,Character>(){{
put('{','}'); put('[',']'); put('(',')');
}};
public boolean isValid(String s) {
if(s.length() > 0 && !map.containsKey(s.charAt(0))) return false;
Stack<Character> stack = new Stack<Character>(){};
for(Character c : s.toCharArray()){
if(map.containsKey(c)) stack.add(c);
else if(stack.isEmpty() == true || map.get(stack.pop()) != c) return false;
}
return stack.size() == 0;
}
}
6. 二叉树的中序遍历
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
inorder(root, res);
return res;
}
public void inorder(TreeNode root, List<Integer> res) {
if (root == null) {
return;
}
inorder(root.left, res);
res.add(root.val);
inorder(root.right, res);
}
}
7. 移掉 K 位数字
用12345 54321 15324 作为找规律
原题链接
class Solution {
class Solution {
public String removeKdigits(String num, int k) {
Deque<Character> stk = new ArrayDeque<>();
for (char c : num.toCharArray()) {
while (!stk.isEmpty() && c < stk.getLast() && k > 0) {
stk.pollLast();
k--;
}
stk.addLast(c);
}
String res = stk.stream().map(Object::toString).collect(Collectors.joining());
res = res.substring(0, res.