继三月开始的每天一道算法题，现在到四月份啦，继续努力！
力扣每日一题（三月）
发现这几天不知不觉每天都做了一道力扣题，刚好也一边做题一边写了注释当笔记，那搬来博客也不耗费多大精力，现在感觉写日记实在提不起劲了，每天好像都是那些事，不断地重复着（明明高中的时候也是，但那时候有好多的想法想要书写，现在
04-30 土 晴
- 01 矩阵
这个月的最后一题，完毕！五一要出去玩散散心放松放松啦~
- 参照评论区优化了一下
执行用时：12 ms, 在所有 Java 提交中击败了62.54%的用户
内存消耗：43.9 MB, 在所有 Java 提交中击败了66.95%的用户
class Solution {
public int[][] updateMatrix(int[][] mat) {
int row = mat.length;
int col = mat[0].length;
int[][] flag = new int[row][col];
int[][] dirs ={{-1,0},{1,0},{0,-1},{0,1}};
Queue<int[]> queue = new LinkedList<int[]>();
for(int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if(mat[i][j] == 0)
queue.offer(new int[]{i, j});
}
}
int count = 0;
while(!queue.isEmpty()){
count++;
int size = queue.size();
while(size-- > 0){
int[] point = queue.poll();//将该步的坐标出队
for(int[] dir : dirs){
int x = point [0] + dir[0];
int y = point [1] + dir[1];
if(x < 0 || y < 0 || x > row - 1 || y > col - 1 || mat[x][y] == 0)
continue;
else {
mat[x][y] = 0;
queue.offer(new int[]{x, y});
flag[x][y] = count;
}
}
}
}
return flag;
}
}- 广度优先搜索
执行用时：15 ms, 在所有 Java 提交中击败了19.07%的用户
内存消耗：44.2 MB, 在所有 Java 提交中击败了53.52%的用户
class Solution {
public int[][] updateMatrix(int[][] mat) {
int row = mat.length;
int col = mat[0].length;
int[][] flag = new int[row][col];
int[][] dirs ={{-1,0},{1,0},{0,-1},{0,1}};
Queue<int[]> queue = new LinkedList<int[]>();
for(int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if(mat[i][j] == 0)
queue.offer(new int[]{i, j});
}
}
while(!queue.isEmpty()){
int[] point = queue.poll();//将该步的坐标出队
for(int[] dir : dirs){
int x = point [0] + dir[0];
int y = point [1] + dir[1];
if(x < 0 || y < 0 || x > row - 1 || y > col - 1 || mat[x][y] == 0 || flag[x][y] != 0)
continue;
else {
queue.offer(new int[]{x, y});
flag[x][y] = flag[point [0]][point [1]] + 1;
}
}
}
return flag;
}
}- 广度优先搜索
执行用时：10 ms, 在所有 Java 提交中击败了97.76%的用户
内存消耗：42.7 MB, 在所有 Java 提交中击败了41.39%的用户
class Solution {
public int shortestPathBinaryMatrix(int[][] grid) {
if(grid[0][0] != 0)
return -1;//当起点不为0时，直接无路可走
int row = grid.length;
int col = grid[0].length;
int path = 1;//路径步数，起步默认为一步
int[][] dirs = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};//八个方向的坐标变化量
Queue<int[]> queue = new LinkedList<int[]>();
queue.offer(new int[]{0, 0});
while(!queue.isEmpty()){//队列不为空说明还有路没走完
int size = queue.size();//记录队列的长度，即每一步的方向个数
while (size-- > 0){
int[] coordinate = queue.poll();//将该步的坐标出队
if(coordinate[0] == row - 1 && coordinate[1] == col - 1)
return path;//如果已经到了终点，则返回路径长度
for(int[] dir : dirs){//对八个方向进行广度优先搜索，将可走的路（为0）的坐标入队并标记为1
int x = coordinate[0] + dir[0];//某方向的纵坐标值
int y = coordinate[1] + dir[1];//某方向的横坐标值
if(x < 0 || y < 0 || x > row - 1 || y > col - 1 || grid[x][y] == 1)
continue;//越界或该方向的坐标不可走的话，跳过该方向的步骤
queue.offer(new int[]{x, y});//若该方向可走，则坐标入队
grid[x][y] = 1;//并标记为1
}
}
path++;//执行一次循环说明走了一步，因此加一步
}
return -1;//队为空之前都没有到达终点，说明没有路走得通，返回-1
}
}04-29 金 晴
- 太平洋大西洋水流问题
这两天的题都好折磨人啊，代码又长又新颖啊啊啊啊，心态有点裂开……
- 广度优先搜索 + 双数组标记
再写个广度练练手，熟悉各种写法
执行用时：7 ms, 在所有 Java 提交中击败了25.53%的用户
内存消耗：42.2 MB, 在所有 Java 提交中击败了88.45%的用户
class Solution {
int row, col;
public List<List<Integer>> pacificAtlantic(int[][] heights) {
List<List<Integer>> listList = new ArrayList<>();
row = heights.length;
col = heights[0].length;
Queue<int[]> queueP = new LinkedList<>(), queueA = new LinkedList<>();
boolean[][] toPacific = new boolean[row][col];//记录该点能否到达太平洋
boolean[][] toAtlantic = new boolean[row][col];//记录该点能否到达大西洋
for(int i = 0; i < row; i++){
toPacific[i][0] = true;
queueP.offer(new int[]{i, 0});
toAtlantic[i][col - 1] = true;
queueA.offer(new int[]{i, col - 1});
}
for(int i = 0; i < col; i++){
toPacific[0][i] = true;
queueP.offer(new int[]{0, i});
toAtlantic[row - 1][i] = true;
queueA.offer(new int[]{row - 1, i});
}
BFS(heights, queueP, toPacific);
BFS(heights, queueA, toAtlantic);
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
if(toPacific[i][j] && toAtlantic[i][j]){
listList.add(Arrays.asList(i,j));
}
}
}
return listList;
}
public void BFS(int[][] heights, Queue<int []> queue, boolean[][] flag){
while(!queue.isEmpty()){
int[] temp = queue.poll();
int x = temp[0], y = temp[1];
if(x > 0 && heights[x - 1][y] >= heights[x][y] && !flag[x - 1][y]){
flag[x - 1][y] = true;
queue.offer(new int[]{x - 1, y});
}
if(x < row - 1 && heights[x + 1][y] >= heights[x][y] && !flag[x + 1][y]){
flag[x + 1][y] = true;
queue.offer(new int[]{x + 1, y});
}
if(y > 0 && heights[x][y - 1] >= heights[x][y] && !flag[x][y - 1]){
flag[x][y - 1] = true;
queue.offer(new int[]{x, y - 1});
}
if(y < col - 1 && heights[x][y + 1] >= heights[x][y] && !flag[x][y + 1]){
flag[x][y + 1] = true;
queue.offer(new int[]{x, y + 1});
}
}
}
}- 深度优先搜索 + 双数组标记
执行用时：4 ms, 在所有 Java 提交中击败了89.14%的用户
内存消耗：42.6 MB, 在所有 Java 提交中击败了58.53%的用户
class Solution {
int row, col;
public List<List<Integer>> pacificAtlantic(int[][] heights) {
List<List<Integer>> listList = new ArrayList<>();
row = heights.length;
col = heights[0].length;
boolean[][] toPacific = new boolean[row][col];//记录该点能否到达太平洋
boolean[][] toAtlantic = new boolean[row][col];//记录该点能否到达大西洋
for(int i = 0; i < row; i++){
DFS(heights, i, 0, toPacific);//上边界开始的深度优先搜索
DFS(heights, i, col - 1, toAtlantic);//下边界开始的深度优先搜索
}
for(int i = 0; i < col; i++){
DFS(heights, 0, i, toPacific);//左边界开始的深度优先搜索
DFS(heights, row - 1, i, toAtlantic);//右边界开始的深度优先搜索
}
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (toPacific[i][j] && toAtlantic[i][j]) {
listList.add(Arrays.asList(i,j));//添加既能到达太平洋又能到达大西洋的坐标
}
}
}
return listList;
}
public void DFS(int[][] heights, int x, int y, boolean[][] toFlag) {
if(toFlag[x][y])
return;//标记过的返回防止爆栈
toFlag[x][y] = true;//标记为访问过，即该点可到达大洋
if (x > 0 && heights[x - 1][y] >= heights[x][y])
DFS(heights, x - 1, y, toFlag);
if (x < row - 1 && heights[x + 1][y] >= heights[x][y])
DFS(heights, x + 1, y, toFlag);
if (y > 0 && heights[x][y - 1] >= heights[x][y])
DFS(heights, x, y - 1, toFlag);
if (y < col - 1 && heights[x][y + 1] >= heights[x][y])
DFS(heights, x, y + 1, toFlag);
}
}04-28 水 晴
- 地图分析
这题好难啊，果然我只会深度不会广度……虽然考虑多个思路但总是有不对劲的地方，还是搬个答案当笔记吧 
第一次遇到多源广度……
这是一道典型的BFS基础应用，为什么这么说呢？
因为我们只要先把所有的陆地都入队，然后从各个陆地同时开始一层一层的向海洋扩散，那么最后扩散到的海洋就是最远的海洋！
并且这个海洋肯定是被离他最近的陆地给扩散到的！
下面是扩散的图示，1表示陆地，0表示海洋。每次扩散的时候会标记相邻的4个位置的海洋：
你可以想象成你从每个陆地上派了很多支船去踏上伟大航道，踏遍所有的海洋。每当船到了新的海洋，就会分裂成4条新的船，向新的未知海洋前进（访问过的海洋就不去了）。如果船到达了某个未访问过的海洋，那他们是第一个到这片海洋的。很明显，这么多船最后访问到的海洋，肯定是离陆地最远的海洋。
class Solution {
public int maxDistance(int[][] grid) {
int[] dx = {0, 0, 1, -1};
int[] dy = {1, -1, 0, 0};
Queue<int[]> queue = new ArrayDeque<>();
int m = grid.length, n = grid[0].length;
// 先把所有的陆地都入队。
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
queue.offer(new int[] {i, j});
}
}
}
// 从各个陆地开始，一圈一圈的遍历海洋，最后遍历到的海洋就是离陆地最远的海洋。
boolean hasOcean = false;
int[] point = null;
while (!queue.isEmpty()) {
point = queue.poll();
int x = point[0], y = point[1];
// 取出队列的元素，将其四周的海洋入队。
for (int i = 0; i < 4; i++) {
int newX = x + dx[i];
int newY = y + dy[i];
if (newX < 0 || newX >= m || newY < 0 || newY >= n || grid[newX][newY] != 0) {
continue;
}
grid[newX][newY] = grid[x][y] + 1; // 这里我直接修改了原数组，因此就不需要额外的数组来标志是否访问
hasOcean = true;
queue.offer(new int[] {newX, newY});
}
}
// 没有陆地或者没有海洋，返回-1。
if (point == null || !hasOcean) {
return -1;
}
// 返回最后一次遍历到的海洋的距离。
return grid[point[0]][point[1]] - 1;
}
}- 广度优先搜索
执行用时：12 ms, 在所有 Java 提交中击败了90.43%的用户
内存消耗：42.2 MB, 在所有 Java 提交中击败了82.19%的用户
class Solution {
public int maxDistance(int[][] grid) {
int row = grid.length;
int col = grid[0].length;
Queue<int[]> queue = new LinkedList<int[]>();
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
if(grid[i][j] == 1){
queue.offer(new int[]{i,j});//先将每个岛屿入队，从每个岛屿发船
}
}
}
boolean flag = false;//标记是否全为陆地
int post[] = null;//记录坐标，若最后还是null说明全为海洋
while(!queue.isEmpty()){
post = queue.poll();//将坐标出队
int x = post[0];//x坐标
int y = post[1];//y坐标
if(x > 0 && grid[x - 1][y] == 0){//上下左右进行前进
queue.offer(new int[]{x-1, y});//如果该方向是0（即为海洋）说明还没有船只来过，可以进一步深入
grid[x - 1][y] = grid[x][y] + 1;//把该方向的海域标记为到岛屿的距离
flag = true;//说明不是全为陆地
}
if(x < row - 1 && grid[x + 1][y] == 0){
queue.offer(new int[]{x + 1, y});
grid[x + 1][y] = grid[x][y] + 1;
flag = true;
}
if(y > 0 && grid[x][y - 1] == 0){
queue.offer(new int[]{x, y - 1});
grid[x][y - 1] = grid[x][y] + 1;
flag = true;
}
if(y < col - 1 && grid[x][y + 1] == 0){
queue.offer(new int[]{x, y + 1});
grid[x][y + 1] = grid[x][y] + 1;
flag = true;
}
}
if(post == null || !flag)
return -1;//若全为陆地或海域返回-1
return grid[post[0]][post[1]] - 1;//返回距离-1
}
}04-27 木 晴
- 深度优先搜索——单次遍历矩阵二
在标记访问过的单元格时，习惯标记为2，因为感觉标记回0的话会破坏矩阵的信息，而标记为2的话只要改动判断时==0改为!=1即可（相当于0和2都一样处理，但不会破坏矩阵的原意，需要复原的时候把2改回1即可）
另外还是那个知识点，如果flag为false，&&后面的dfs()就不会执行，所以要用单个&
执行用时：20 ms, 在所有 Java 提交中击败了84.11%的用户
内存消耗：72.4 MB, 在所有 Java 提交中击败了27.90%的用户
class Solution {
public int countSubIslands(int[][] grid1, int[][] grid2) {
int count = 0;
for(int x = 0; x < grid2.length; x++){
for(int y = 0; y < grid2[0].length; y++){
if(grid2[x][y] == 1 && DFS(grid1, grid2, x, y))
count++;//当矩阵2为岛屿且属于矩阵1的字岛屿时，计数+1
}
}
return count;
}
public boolean DFS(int[][] grid1, int[][] grid2, int x, int y){
if(x < 0 || y < 0 || x > grid1.length - 1 || y > grid1[0].length - 1 || grid2[x][y] != 1)
return true;//越界或矩阵2为0时返回，并且返回值为true
else if(grid1[x][y] != 1)
return false;//当且仅当矩阵1为0，矩阵2为1时，返回并且返回false
//注：由于上面已经判断了矩阵2为0时返回，所以在这里加不加&&grid12[x][y]==1都是一样的
// 下面两个不用再加判断也是同理
grid1[x][y] = 2;//标记访问过的单元格
grid2[x][y] = 2;
return DFS(grid1, grid2, x - 1, y) & DFS(grid1, grid2, x + 1, y) & DFS(grid1, grid2, x, y - 1) & DFS(grid1, grid2, x, y + 1);
}
}- 直接switch
利用switch的default……只要不是纯运算符的就进栈得了，没必要写一堆判断(´இ皿இ｀)
执行用时：5 ms, 在所有 Java 提交中击败了93.91%的用户
内存消耗：41.2 MB, 在所有 Java 提交中击败了21.09%的用户
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<Integer>();
for(int i = 0; i < tokens.length; i++){
switch (tokens[i]){
case "+": stack.push(stack.pop() + stack.pop());break;
case "-": stack.push(-stack.pop() + stack.pop());break;
case "*": stack.push(stack.pop() * stack.pop());break;
case "/":
int temp = stack.pop();
stack.push(stack.pop() / temp);break;
default:stack.push(Integer.parseInt(tokens[i]));
}
}
return stack.pop();
}
}- 判断运算符
自己耍自己了，加了一堆判断才能得出结果，不过也学到了几个字符串转变库方法。另外有个细节是出栈顺序的原因，减法和除法需要格外注意先后
执行用时：7 ms
内存消耗：41.3 MB
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<Integer>();
for(int i = 0; i < tokens.length; i++){
String s = tokens[i];
if(s.length() == 1 && (s.contains("+") || s.contains("-") || s.contains("*") || s.contains("/"))){
int num1 = stack.pop();
int num2 = stack.pop();
switch (s) {
case "+": stack.push(num2 + num1);break;
case "-": stack.push(num2 - num1);break;
case "*": stack.push(num2 * num1);break;
case "/": stack.push(num2 / num1);break;
}
}
else
stack.push(Integer.parseInt(tokens[i]));
}
return stack.pop();
}
}04-26 火 晴
- 飞地的数量
今天数据结构考了试，又做了半天pta的题，感觉状态不佳……
- 深度优先遍历
老想着一次数组遍历就通过递归得到结果，看了题解才反应过来可以先从周边标记掉不为飞地的单元格，最后再照常遍历一边得到结果，就不用加别的条件判断了。不过最后还是写出来了个一次性遍历的，标记出该区域上下左右四个方向是否有挨着边界的，如果有就一路返回-1，否则计算得出单元格数量，这样就能在遍历中判断是否要+=此次遍历得到的结果了。
执行用时：6 ms, 在所有 Java 提交中击败了40.43%的用户
内存消耗：48.8 MB, 在所有 Java 提交中击败了53.72%的用户
class Solution {
public int numEnclaves(int[][] grid) {
int count = 0;
for(int x = 0; x < grid.length; x++){
for(int y = 0; y < grid[0].length; y++){
if(grid[x][y] == 1){
int temp = DFS(grid, x, y);
count += temp > 0 ? temp : 0;
}
}
}
return count;
}
public int DFS(int[][] grid, int x, int y){
if(x < 0 || y < 0 || x > grid.length - 1 || y > grid[0].length - 1)
return -1;//越界时说明不为飞地，返回-1标记
if(grid[x][y] != 1)
return 0;//不为土地时返回0表示单元格数量+0
grid[x][y] = 2;//标记访问过的单元格
int up = DFS(grid, x + 1, y);//递归上下左右
int down = DFS(grid, x - 1, y);
int left = DFS(grid, x, y - 1);
int right = DFS(grid, x, y + 1);
if(up == -1 || down == -1 || left == -1 || right == -1)
return -1;//如果上下左右中有被标记为-1的，说明整块都不是飞地，继续返回标记-1
return up + down + left + right + 1;//返回单元格数量
}
}04-25 月 晴
- 平衡二叉树
最近在讲树，想写点平衡树的题，特别是左旋右旋，以为很难的算法，书上竟然思路这么清晰简洁，果然还是得多看书多学习呀
- 自底向上递归
了解到从上向下找会重复地查找子树的高度，造成时间上的浪费，而自底向上的话，首先计算高度的时间大大减少也不会重复计算，其次找到为非平衡树的根节点时，一路往上返回即可，不再需要计算其他节点的子树高度 
感觉这个算法妙到家了
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：40.7 MB, 在所有 Java 提交中击败了82.55%的用户
class Solution {
public boolean isBalanced(TreeNode root) {
return height(root) >= 0;
}
public int height(TreeNode root){
if(root == null)
return 0;
int leftHeight = height(root.left);
int rightHeight = height(root.right);
if(leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1)
return -1;
return Math.max(leftHeight, rightHeight) + 1;
}
}- 自顶向下递归
比较左右子树的高度差，大于1时为false，这里两个函数都得递归，一个是递归查深度，一个是递归查左右子树的高度差（主根节点左右子树高度差不超过1不代表其子树的子树的高度差也不超过1，在这里入了点误区）
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：40.9 MB, 在所有 Java 提交中击败了51.77%的用户
class Solution {
public boolean isBalanced(TreeNode root) {
if(root == null)
return true;//为空时没有子树，也就没有高度差，返回true
if(Math.abs(getHeight(root.left) - getHeight(root.right)) > 1)//Math.abs():返回一个数的绝对值
return false;//左右子树高度差大于1时返回false
return isBalanced(root.left) && isBalanced(root.right);//当左右子树都为true时为true，有一边为false时为false
}
public int getHeight(TreeNode root){
if(root == null)
return 0;
return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
}
}- 深度优先搜索
感觉自己代码越来越骚了2333
执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：41.5 MB, 在所有 Java 提交中击败了77.79%的用户
class Solution {
public int closedIsland(int[][] grid) {
int count = 0;
for(int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if(grid[i][j] == 0 && DFS(grid, i, j))
count++;
}
}
return count;
}
public boolean DFS(int[][] grid, int x, int y){
if(x < 0 || y < 0 || x > grid.length - 1 || y > grid[0].length - 1)
return false;//越界返回false
else if(grid[x][y] != 0)
return true;//为1或2（即为海域：1 或 该土地已经标记过：2）说明这个方向被海域围上了
grid[x][y] = 2;//上面条件都不成立时，说明是土地，将该土地标记，然后在下面return语句进行递归
//&&是前面如果有false，后面就不执行，导致后面置为2的操作不做了
//&& 会短路，而 & 不会，因此 && 会导致岛屿可能无法遍历完全
return DFS(grid, x - 1, y) & DFS(grid, x + 1, y) & DFS(grid, x, y - 1) & DFS(grid, x, y + 1);
}
}- 深度优先搜索
执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：41.6 MB, 在所有 Java 提交中击败了25.23%的用户
class Solution {
public int maxAreaOfIsland(int[][] grid) {
int max = 0;
for(int i = 0; i < grid.length; i++){
for(int j = 0; j < grid[0].length; j++){
if(grid[i][j] == 1){
max = Math.max(DFS(grid, i, j), max);
}
}
}
return max;
}
public int DFS(int[][] grid, int x, int y){
int count = 1;
grid[x][y] = 2;
if(x > 0 && grid[x - 1][y] == 1)//若上为土地
count += DFS(grid, x - 1, y);//去上土地进行岛屿地域扩展
if(x < grid.length - 1 && grid[x + 1][y] == 1)//下
count += DFS(grid, x + 1, y);
if(y > 0 && grid[x][y - 1] == 1)//左
count += DFS(grid, x, y - 1);
if(y < grid[0].length - 1 && grid[x][y + 1] == 1)//右
count += DFS(grid, x, y + 1);
return count;
}
}思路是一样的，试一下别人的写法，改个判断条件变成和树的递归类似——先越界后返回（树中会递归到null后再返回，反之为先判断不为null再递归）
执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：41.1 MB, 在所有 Java 提交中击败了85.49%的用户
class Solution {
public int maxAreaOfIsland(int[][] grid) {
int max = 0;
for(int i = 0; i < grid.length; i++){
for(int j = 0; j < grid[0].length; j++){
if(grid[i][j] == 1){
max = Math.max(DFS(grid, i, j), max);
}
}
}
return max;
}
public int DFS(int[][] grid, int x, int y){
if(x < 0 || y < 0 || x > grid.length - 1 || y > grid[0].length - 1 || grid[x][y] != 1)
return 0;//不是土地时返回0（不是岛屿区域）
int count = 1;//1为当前区域是岛屿默认为1
grid[x][y] = 2;//标记当前区域
count += DFS(grid,x - 1, y);//上下左右深度优先搜索取得区域数量
count += DFS(grid,x + 1, y);
count += DFS(grid,x, y - 1);
count += DFS(grid,x, y + 1);
return count;
}
}04-24 日 雨
- 广度优先搜索
广度反而不太会了 感觉深度好写一些，而且为啥广度慢这么多……
执行用时：10 ms, 在所有 Java 提交中击败了6.77%的用户
内存消耗：48.6 MB, 在所有 Java 提交中击败了89.45%的用户
class Solution {
public int numIslands(char[][] grid) {
int count = 0;
for(int i = 0; i < grid.length; i++) {//遍历每块区域
for (int j = 0; j < grid[0].length; j++) {
if(grid[i][j] == '1'){
Queue<Integer> queue = new LinkedList<>();
queue.offer(i);
queue.offer(j);
count++;
while(!queue.isEmpty()){
int x = queue.poll();
int y = queue.poll();
if(x > 0 && grid[x - 1][y] == '1') {
queue.offer(x - 1);
queue.offer(y);
grid[x - 1][y] = '2';
}
if(x < grid.length - 1 && grid[x + 1][y] == '1'){
queue.offer(x + 1);
queue.offer(y);
grid[x + 1][y] = '2';
}
if(y > 0 && grid[x][y - 1] == '1') {
queue.offer(x);
queue.offer(y - 1);
grid[x][y - 1] = '2';
}
if(y < grid[0].length - 1 && grid[x][y + 1] == '1') {
queue.offer(x);
queue.offer(y + 1);
grid[x][y + 1] = '2';
}
}
}
}
}
return count;
}
}- 深度优先搜索
套用上一题的思路，遍历数组的同时遇到‘1’时执行“上色”，即标记属于当前岛屿的区域，防止后面遍历到当前岛屿的区域时不会改变岛屿数量。
执行用时：2 ms, 在所有 Java 提交中击败了99.98%的用户
内存消耗：49.9 MB, 在所有 Java 提交中击败了19.04%的用户
class Solution {
public int numIslands(char[][] grid) {
int count = 0;//岛屿数量
for(int i = 0; i < grid.length; i++){//遍历每块区域
for(int j = 0; j < grid[0].length; j++){
if(grid[i][j] == '1'){//当前区域为土地时，进行深度优先搜索把该岛屿的区域标记
fill(grid, i, j);
count++;//岛屿数量+1
}
}
}
return count;
}
public void fill(char[][] grid, int x, int y){
grid[x][y] = '2';//给当前土地标记为岛归属
if(x > 0 && grid[x - 1][y] == '1')//若上为土地
fill(grid, x - 1, y);//去上土地进行岛屿地域扩展
if(x < grid.length - 1 && grid[x + 1][y] == '1')//下
fill(grid, x + 1, y);
if(y > 0 && grid[x][y - 1] == '1')//左
fill(grid, x, y - 1);
if(y < grid[0].length - 1 && grid[x][y + 1] == '1')//右
fill(grid, x, y + 1);
return;
}
}- 图像渲染
今天开始正式学习图~（数据结构入门+基础的题库刷完了，进阶的题要会员 
）
- 深度优先搜索
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：42.3 MB, 在所有 Java 提交中击败了31.44%的用户
class Solution {
public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
//本来是一遍过的，被初始颜色和新颜色相同的情况下绊了一下，所以得加个判断，不然会一直左右横跳最后爆栈了……StackOverflowError
return image[sr][sc] == newColor ? image : fill(image, sr,sc, newColor, image[sr][sc]);
}
public int[][] fill(int[][] image, int sr, int sc, int newColor, int oldColor){
image[sr][sc] = newColor;//给当前像素点渲染上新颜色
if(sr > 0 && image[sr - 1][sc] == oldColor)//若上为相同像素点
fill(image, sr - 1, sc, newColor, oldColor);//去上像素点进行深一轮的上下左右查找
if(sr < image.length - 1 && image[sr + 1][sc] == oldColor)//下
fill(image, sr + 1, sc, newColor, oldColor);
if(sc > 0 && image[sr][sc - 1] == oldColor)//左
fill(image, sr, sc - 1, newColor, oldColor);
if(sc < image[0].length - 1 && image[sr][sc + 1] == oldColor)//右
fill(image, sr, sc + 1, newColor, oldColor);
return image;
}
}04-23 土 雨
- 写法三：直接根据坐标距离排序
一行的拉姆达表达式……直接根据计算出来的值进行排序……不需要任何多余的变量…… 不说了，我去补补拉姆达表达式的知识……
执行用时：24 ms, 在所有 Java 提交中击败了67.42%的用户
内存消耗：49.3 MB, 在所有 Java 提交中击败了65.64%的用户
class Solution {
public int[][] kClosest(int[][] points, int k) {
Arrays.sort(points, Comparator.comparingInt(a -> (a[0] * a[0] + a[1] * a[1])));
return Arrays.copyOfRange(points,0,k);
}
}官方的原写法：
class Solution {
public int[][] kClosest(int[][] points, int k) {
Arrays.sort(points, new Comparator<int[]>() {
public int compare(int[] point1, int[] point2) {
return (point1[0] * point1[0] + point1[1] * point1[1]) - (point2[0] * point2[0] + point2[1] * point2[1]);
}
});
return Arrays.copyOfRange(points, 0, k);
}
}- 写法二：数组做哈希表
和之前一样多用一列数组当哈希表的值，一样排序，但这样得手动重新赋值k行数组返回
执行用时：31 ms, 在所有 Java 提交中击败了41.72%的用户
内存消耗：49.2 MB, 在所有 Java 提交中击败了75.05%的用户
class Solution {
public int[][] kClosest(int[][] points, int k) {
int[][] map = new int[points.length][17];
for(int i = 0; i < points.length; i++){
map[i][0] = points[i][0] * points[i][0] + points[i][18] * points[i][19];
map[i][20] = points[i][0];
map[i][21] = points[i][22];
}
Arrays.sort(map, Comparator.comparingInt(a -> a[0]));
int[][] ints = new int[k][23];
for(int i = 0; i < k; i++){
ints[i][0] = map[i][24];
ints[i][25] = map[i][26];
}
return ints;
}
}- 写法一：哈希表值排序
用哈希表键记录坐标，值记录距离，根据每个坐标对应的距离（值）进行排序，最后返回k行数组
执行用时：69 ms, 在所有 Java 提交中击败了15.16%的用户
内存消耗：49.5 MB, 在所有 Java 提交中击败了41.12%的用户
class Solution {
public int[][] kClosest(int[][] points, int k) {
Map<int[], Integer> map = new HashMap<int[] ,Integer>();
for(int i = 0; i < points.length; i++){
int temp = points[i][0] * points[i][0] + points[i][27] * points[i][28];
map.put(points[i], temp);
}
Arrays.sort(points, Comparator.comparingInt(map::get));
return Arrays.copyOfRange(points,0,k);
}
}04-22 金 晴
- 哈希表+集合排序
这个是我第一思路，不过对拉姆达表达式不太会表达，中间几段将哈希表的键转为集合的过程也没用过 ，不过这样竟然反而更慢了……还是数组打表好！
执行用时：15 ms, 在所有 Java 提交中击败了52.62%的用户
内存消耗：41.7 MB, 在所有 Java 提交中击败了80.83%的用户
class Solution {
public String frequencySort(String s) {
Map<Character, Integer> map = new HashMap<Character, Integer>();
for(int i = 0; i < s.length(); i++){
char ch = s.charAt(i);
map.put(ch, map.getOrDefault(ch, 0) + 1);//打表
}
List<Character> list = new ArrayList<Character>(map.keySet());//将哈希表的所有建制成集合
Collections.sort(list, (a, b) -> map.get(b) - map.get(a));//通过哈希表的值对集合进行降序排序
StringBuilder sb = new StringBuilder();
for(int i = 0; i < list.size(); i++){
char ch = list.get(i);//记录第i个集合的字符
for(int j = 0; j < map.get(ch); j++){
sb.append(ch);//拼接哈希表中值记录j次
}
}
return sb.toString();
}
}
- 双列数组打表
和昨天那题一样的做法，只不过要转换一下ASCII码 
不过为啥好像没看到类似的做法，都是优先队列和堆排序之类的，感觉有些深，周末得认真看看他们的解题方法了。
执行用时：6 ms, 在所有 Java 提交中击败了90.87%的用户
内存消耗：41.2 MB, 在所有 Java 提交中击败了87.69%的用户
class Solution {
public String frequencySort(String s) {
int[][] map = new int[128][30];//整型数组做哈希表
for(int i = 0; i < s.length(); i++){
char ch = s.charAt(i);//获取第i个字符
if(map[ch][31] == 0){
map[ch][0] = ch;//若该字符还未出现过，先给该字符的ASCII码对应的行的第一列记录下该字符
}
map[ch][32]++;//记录每个字符出现的次数
}
Arrays.sort(map, (a, b) -> b[1] - a[1]);//用拉姆达表达式将出现次数进行降序排列
StringBuilder sb = new StringBuilder();//拼接字符用StringBuilder
int count = 0;//记录第几个字符
while(map[count][33] != 0){//出现次数到0时结束循环
for(int j = 0; j < map[count][34]; j++){
sb.append((char)map[count][0]);//拼接每个字符的次数
}
count++;
}
return sb.toString();
}
}04-21 木 阴
- 双列数组打表
既然需要根据出现频率来获取结果，那就记录频率和结果呗，一开始想用哈希表写，不过这样只能到打表一步，之后取值有点懵了，所以换个思路从数组入手，但数组的话首先题目给的数组的值不确定，也就是无法确定哪个数的位置，至于出现频率还是好记录的，于是先想到用哈希表记录每个数的层数，然后通过get方法获取那个数所在层的次数+1。提交通过后感觉还能优化，可以先进行一次排序，然后遍历，当遍历到和这层的数不一样时，说明需要进入下一层新的一个数的次数查找了 
这里又用到了之前做过的用Lambda表达式改写sort方法对二维数组进行升序排列
执行用时：10 ms, 在所有 Java 提交中击败了97.72%的用户
内存消耗：44.3 MB, 在所有 Java 提交中击败了5.10%的用户
class Solution {
public int[] topKFrequent(int[] nums, int k) {
//用哈希表记录每个数字在第几行耗时：13 ms
// Map<Integer, Integer> map = new HashMap<Integer, Integer>();
Arrays.sort(nums);//不用哈希表，改用先进行一次排序，当检查到不相等时再下一层即可
int[][] record = new int[nums.length][36];//定义记录数组，第一列为出现次数，第二列为对应的数
int count = 0;//记录第几行
record[count][0] = nums[0];//先默认第一个值
for(int i = 0; i < nums.length; i++){
if (record[count][0] != nums[i]) {
record[++count][0] = nums[i];//检查和当前层的数不相等时，说明需要进入下一层（新的一个数）了
}
record[count][37]++;//出现次数+1
}
Arrays.sort(record, (a, b) -> b[1] - a[1]);//用拉姆达表达式将出现次数进行降序排列
int[] result = new int[k];//定义结果数组
for(int i = 0; i < k; i++){
result[i] = record[i][0];//取k个值到结果数组里
}
return result;
}
}04-20 水 阴
- 数组中的第K个最大元素
今天不刷题~写一晚上的数据库操作，JDBC终于实操上啦，随便水一题吧2333
- 无敌的Arrays.sort()
（其实跟作弊一样哈哈哈）
执行用时：2 ms,在所有 Java提交中击败81.65%
的用户
内存消耗：41.4 MB,在所有Java提交中击败54.84%的用户
class Solution {
public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length - k];
}
}04-19 火 阴
- 钥匙和房间
挺有意思的，又考察到了深度和广度搜索，不过有个疑问：将整型数组该用bool类型的数组同样的代码为啥结果不一样了，是无法返回bool类型的值吗？？？用全局变量就好了……
- 广度优先搜索
一开始写的是直接按房间号搜集钥匙，这样的话会导致如果是从后往前推（后面的房间找到前面房间的钥匙）的情况则答案错误，但是可以通过队列来实现：在0号房搜集到第一批钥匙，然后从这批钥匙中挨个访问对应的房间并搜集房间内的钥匙，访问和搜集顺序为先进先出，即可用队列实现。
执行用时：1 ms, 在所有 Java 提交中击败了61.35%的用户
内存消耗：41.1 MB, 在所有 Java 提交中击败了37.52%的用户
class Solution {
public boolean canVisitAllRooms(List<List<Integer>> rooms) {
int nums = 0;//访问过的房间数
boolean[] map = new boolean[rooms.size()];
Queue<Integer> queue = new LinkedList<Integer>();
map[0] = true;//0号房不需要钥匙
queue.offer(0);//从0号房开始搜集钥匙
while(!queue.isEmpty()){
int i = queue.poll();//在i号房搜集
nums++;//访问过的房间数+1
for(int key : rooms.get(i)){
if(!map[key]){//若没有访问过该钥匙对应的房间
map[key] = true;//先标记为有钥匙
queue.offer(key);//入队按钥匙到手顺序搜索房间
}
}
}
return nums == rooms.size();
}
}- 深度优先搜索
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：40.9 MB, 在所有 Java 提交中击败了61.66%的用户
class Solution {
public boolean canVisitAllRooms(List<List<Integer>> rooms) {
int[] map = new int[rooms.size()];//定义n个房间数量的数组
map = findKey(rooms, 0, map);//执行递归
for(int i = 1; i < rooms.size(); i++){
if(map[i] == 0)//如果有未访问过的房间，则说明没有该房间的钥匙
return false;
}
return true;
}
public int[] findKey(List<List<Integer>> rooms, int i, int[] map){
for(int key : rooms.get(i)){//在当前房间搜集钥匙，并判断是否已经访问过钥匙的房间，没有则访问
if(map[key] == 0)
{
map[key]++;//访问次数改为1
findKey(rooms, key, map);//去该钥匙的房间搜集
}
}
return map;//返回搜集结果
}
}- 可以到达所有点的最少点数目
这不是和昨天的一样吗……判断入度为0的节点即可
- 数据打表
执行用时：9 ms, 在所有 Java 提交中击败了86.50%的用户
内存消耗：76.9 MB, 在所有 Java 提交中击败了76.61%的用户
class Solution {
public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
List<Integer> list = new ArrayList<>();
int[] map = new int[n];
for(int i = 0; i < edges.size(); i++){
map[edges.get(i).get(1)]++;//遍历点集，将入度的节点自增
}
for(int i = 0; i < n; i++){
if(map[i] == 0)//找入度为0的节点
list.add(i);
}
return list;
}
}04-18 月 阴
- 找到小镇的法官
第一次接触图的题目，今天上数据结构的时候也讲到了树的概念，让我对前几天做的建树和拆树的题有了更深一步的了解，也让我意识到……不能无脑刷算法了，靠刷算法学知识是不行的……刷题应该是巩固知识而不是从零开始，所以……我要主打看书巩固基础了 题嘛，每天一题就够了~挑刚学的做！
- 方法二：计算入度和出度
运用到图的知识，在这题里是定义n个人的一个数组，然后被人信任则该人所在下标的值+1，信任别人则-1，最后再遍历一次找到值为n-1的那个人，若没有就会返回-1
执行用时：2 ms, 在所有 Java 提交中击败了97.98%的用户
内存消耗：48.7 MB, 在所有 Java 提交中击败了51.96%的用户
class Solution {
public int findJudge(int n, int[][] trust) {
int[] judge = new int[n];
for(int i = 0; i < trust.length; i++){
judge[trust[i][42] - 1]++;
judge[trust[i][0] - 1]--;
}
for(int i = 0; i < judge.length; i++){
if(judge[i] == n - 1)
return i + 1;
}
return -1;
}
}- 方法一：用set遍历两次
呆狗做法……没错就是我……
执行用时：8 ms, 在所有 Java 提交中击败了18.03%的用户
内存消耗：49.2 MB, 在所有 Java 提交中击败了7.75%的用户
class Solution {
public int findJudge(int n, int[][] trust) {
if(n == 1)
return 1;
int count = 0;
int judge = -1;
Set<Integer> set = new HashSet<Integer>();
for(int i = 0; i < trust.length; i++){
set.add(trust[i][0]);
}
for(int i = 0; i < trust.length; i++){
if(judge != -1 && judge == trust[i][43]){
count++;
}
else if(!set.contains(trust[i][44])){
judge = trust[i][45];
count = 1;
}
}
if(count == n - 1)
return judge;
else
return -1;
}
}04-17 日 阴
- 二叉树的序列化与反序列化
了解完什么是序列化之后，联想到了之前写的用题目给的前序遍历＋中序遍历造树的题，既然前序+中序或中序+后序可以造出唯一的二叉树，那序列化的时候就可以写入二叉树的两种遍历数据，反序列化的时候用那题类似的方法构造出来即可…… 但！这样不仅耗时耗力，还在造树时遇到大大小小的问题……
参考评论区可以直接用一种遍历方法序列化之后造树，只要把所有节点都记录下来即可（这里指包括null的节点，即看做满二叉树），这样当前序遍历的时候造树就可以通过判断是否为null而进行递归的出口
这题知识点还挺多的，首先各种遍历的递归非递归写法都可以尝试一遍，然后由于返回的是字符串，造树时得到的也是字符串，而节点的值是整型，所以有必要给每个节点之间的值加上分隔符，但在造树时分隔符是没用的，这里用到了字符串分割的方法：split()，之前有一题已经接触过这个了。还有一个就是Arrays的aslist方法，作用为将数组转成List：java中asList()方法的使用
- 前序遍历序列化
执行用时：12 ms, 在所有 Java 提交中击败了68.68%的用户
内存消耗：43.4 MB, 在所有 Java 提交中击败了40.97%的用户
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
Stack<TreeNode> stack = new Stack<TreeNode>();
//前序遍历字符串
while(root != null || !stack.empty()){
while(root != null){
sb.append(root.val);
sb.append(",");
stack.push(root);
root = root.left;
}
sb.append("null,");
root = stack.pop().right;
}
sb.append("null");//最后一个右子树节点的时候需要手动添加一下null，不然在下面会出现节点个数少一个的问题
//递归写法的调用
//StringBuilder sb = preorder(root, new StringBuilder());
return sb.toString();
}
//递归写法的方法定义
public StringBuilder preorder(TreeNode root, StringBuilder sb){
if(root == null){
sb.append("null,");
return sb;
}
sb.append(root.val);
//这一步很离谱，上下两句如果连在一起写成sb.append(root.val+",");的话耗时直接翻倍！
//执行用时：8 ms, 在所有 Java 提交中击败了84.69%的用户
//内存消耗：43 MB, 在所有 Java 提交中击败了63.26%的用户
//而分开写才能达到8ms的效果，这是在字符串拼接上出现了耗时吗？？？
sb.append(",");
sb = preorder(root.left, sb);
sb = preorder(root.right, sb);
return sb;
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String[] str = data.split(",");
List<String> list = new LinkedList<String>(Arrays.asList(str));
return buildTree(list);
}
public TreeNode buildTree(List<String> list){
if(list.get(0).equals("null")){
list.remove(0);
return null;
}
TreeNode root = new TreeNode(Integer.valueOf(list.get(0)));
list.remove(0);
root.left = buildTree(list);
root.right = buildTree(list);
return root;
}
}04-16 土 阴
- 二叉树的最近公共祖先
只能想到找路径然后对比路径来找最近的公共祖先
- 直接递归
评论区一个很有趣的描述
执行用时：6 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：42.9 MB, 在所有 Java 提交中击败了19.37%的用户
//公司技术部出了两个叛徒，技术部的每个小部门都有两个部门（二叉树）要找出他们的Line Manager
//各单位开始排查，从基层员工查起，最后汇总，找第一个Line manager
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null) return null;
//我自己是叛徒之一，但是我不一定受到惩罚，因为要找的是叛徒的老板，但是你代表你的团队找到了一个叛徒
if(root == p || root == q) return root;
//在各层级团队找叛徒
TreeNode first_traitor = lowestCommonAncestor(root.left, p,q);
//在各层级团队找叛徒
TreeNode second_traitor = lowestCommonAncestor(root.right, p,q);
//我们团队找到两叛徒了，game over,倒霉的就是我。接下去我会被一层一层的往上提交，最后到老板那。
if(first_traitor != null && second_traitor != null){
return root;
}
//我们团队只找到一个叛徒，这个叛徒代表整个团队，就用这个叛徒来向上（回溯）提交甩锅
//这里感觉描述有点问题，不为null时，不代表只有一个，可能是只找到表面的一个（深度较小的那个节点），而另一个在下面就没去找因为已经return了，而递归返回到最后时，另一边会没找到而为null，所以返回的还是之前找到的表面的那个叛徒的团队
//p.s. 太好了，跟我这个小manager没啥关系
if(first_traitor != null) return first_traitor;
if(second_traitor != null) return second_traitor;
//我们是最干净的团队！
return null;
}
}感觉描述有点问题，这个或许更好理解（解法是一样的）
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root==p||root==q) {
return root;
}
if (root!=null){
TreeNode lNode=lowestCommonAncestor(root.left,p,q);
TreeNode rNode=lowestCommonAncestor(root.right,p,q);
if (lNode!=null&&rNode!=null)
return root;
else if(lNode==null) {//两个都在右子树
return rNode;
}
else { //两个都在左子树里面
return lNode;
}
}
return null;
}
}- 路径查找
模仿13号做的路径总和那题
执行用时：9 ms, 在所有 Java 提交中击败了17.08%的用户
内存消耗：42.8 MB, 在所有 Java 提交中击败了28.90%的用户
class Solution {
TreeNode[][] arr = new TreeNode[2][];
int k = 0;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
List<TreeNode> list = new ArrayList<TreeNode>();
List cur = list;
findRoute(cur, root, p.val);
cur.clear();
findRoute(cur, root, q.val);
int count = 0;
while(count < arr[0].length && count < arr[1].length && arr[0][count].val == arr[1][count].val){
count++;
}
return arr[0][count - 1];
}
public void findRoute(List cur, TreeNode root, int target){
List<TreeNode> temp = new ArrayList<TreeNode>();
if(root == null)
return;
cur.add(root);
if(root.val == target){
arr[k] = new TreeNode[cur.size()];
cur.toArray(arr[k++]);
cur.remove(cur.size() - 1);
return;
}
findRoute(cur, root.left, target);
findRoute(cur, root.right, target);
cur.remove(cur.size() - 1);
}
}改良了一点点
然而完全没有减少复杂度啊！！！！
执行用时：9 ms, 在所有 Java 提交中击败了17.08%的用户
内存消耗：42.4 MB, 在所有 Java 提交中击败了68.18%的用户
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
List<TreeNode> pList = new ArrayList<TreeNode>();
List<TreeNode> qList = new ArrayList<TreeNode>();
List cur = pList;
findRoute(cur, root, p.val);
cur = qList;
findRoute(cur, root, q.val);
int count = 0;
while(count < pList.size() && count < qList.size() && pList.get(count) == qList.get(count)){
count++;
}
return pList.get(count - 1);
}
public boolean findRoute(List cur, TreeNode root, int target){
List<TreeNode> temp = new ArrayList<TreeNode>();
if(root == null)
return false;
cur.add(root);
if(root.val == target){
return true;
}
if(findRoute(cur, root.left, target))
return true;
if(findRoute(cur, root.right, target))
return true;
cur.remove(cur.size() - 1);
return false;
}
}04-15 金 晴
- 方法一：创建数组
看了官方题解后再来写个思路，还以为直接查询会快一点，结果更慢了！
执行用时：21 ms, 在所有 Java 提交中击败了7.78%的用户
内存消耗：45.3 MB, 在所有 Java 提交中击败了27.64%的用户
class BSTIterator {
List<Integer> list;
int count = 0;
public BSTIterator(TreeNode root) {
list = new ArrayList<Integer>();
setList(root, list);
list.add(list.get(count) - 1);
}
public int next() {
return list.get(count++);
}
public boolean hasNext() {
return count < list.size() - 1;
}
public void setList(TreeNode root, List list){
if(root == null)
return;
setList(root.left, list);
list.add(root.val);
setList(root.right, list);
return;
}
}- 方法二：模拟中序遍历
按着中序遍历的写法答题吧…… 
当做复习中序遍历了
执行用时：16 ms, 在所有 Java 提交中击败了97.48%的用户
内存消耗：44.8 MB, 在所有 Java 提交中击败了76.85%的用户
class BSTIterator {
Stack<TreeNode> stack = new Stack<TreeNode>();//既然是中序遍历肯定要用到栈了
TreeNode cur;//操作指针
public BSTIterator(TreeNode root) {
cur = root;//先将cur指向root
while (cur != null) {//节点入栈，一直往左找到最小的节点
stack.push(cur);
cur = cur.left;
}
cur = new TreeNode(stack.peek().val - 1,null, stack.peek());//新建一个比给的树所有节点还小的节点，并右节点连上树的最小节点
root = cur;//root指向cur
}
public int next() {
cur = stack.pop();//中序遍历的操作，先出栈后得到比上一次大的值
int temp = cur.val;//记录下来
cur = cur.right;//到右子树
while (cur != null) {//找到右子树中最小的节点并入栈
stack.push(cur);
cur = cur.left;
}
return temp;//返回记录的值
}
public boolean hasNext() {
return !stack.empty();//直接判断栈是否为空即可
}
}- 中序遍历
是二叉搜索树并且用中序遍历的话，得到的就是从小到大的值……那就直接可以用计数来判断是否为第k个最小的元素了 
不过效率就另说了2333
执行用时：1 ms, 在所有 Java 提交中击败了28.30%的用户
内存消耗：41.3 MB, 在所有 Java 提交中击败了34.66%的用户
class Solution {
public int kthSmallest(TreeNode root, int k) {
Stack<TreeNode> stack = new Stack<TreeNode>();
int count = 0;
while(root != null || !stack.empty()){
while(root != null){
stack.push(root);
root = root.left;
}
root = stack.pop();
count++;
if(count == k)
return root.val;
root = root.right;
}
return root.val;
}
}04-14 水 晴
- 长度最小的子数组
做题前缀和提提自信吧……
- 前缀和+滑动窗口
执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：41.1 MB, 在所有 Java 提交中击败了67.44%的用户
class Solution {
public int minSubArrayLen(int target, int[] nums) {
for(int i = 1; i < nums.length; i++){
nums[i] += nums[i - 1];//计算前缀和
}
int left = -1;//左臂默认为-1以免min为数组长度时不正确
int right = 0;
int min = 0;
while(right < nums.length && nums[right] < target)
right++;//右臂扩展到最小的符合要求的前缀和上
if(right < nums.length)
min = right - left;//右臂为有效数时更新min
while(right < nums.length){
while(nums[right] - nums[left + 1] >= target){
left++;//当右臂和左臂+1的数之间的差值可以进行区间缩短时，收缩左臂
min = Math.min(right - left, min);
}
left++;//每次循环移动窗口
right++;
}
return min;
}
}- 删除二叉搜索树中的节点
好难……虽然思路不难，一直在想迭代的方法，但是需要判断的点太多了，看了递归的解法也太好理解了……
- 方法二：递归 节点替换
由于方法一的拼接思路会让树的高度猛增，而对于二叉搜索树来说，这样的做法会导致搜索效率成倍降低，最坏的情况下会退化成链表。 今天（2022年4月19日）上数据结构讲到这里真的茅塞顿开，明明有这么好的方法为什么要拼接树呢！
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：41.7 MB, 在所有 Java 提交中击败了45.66%的用户
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if(root == null)
return null;//为空返回
if(root.val < key)//值大于节点值，去右子树删除
root.right = deleteNode(root.right, key);
else if(root.val > key)//值小于节点值，去左子树删除
root.left = deleteNode(root.left, key);
else {//当前节点为删除节点时，分三种情况
if(root.left != null && root.right != null){//情况一：既有左子树又有右子树
TreeNode post = root.right;
while(post.left != null)//找到右子树最小的节点
post = post.left;
root.val = post.val;//右子树最小节点顶替当前被删除节点
root.right = deleteNode(root.right, root.val);//去将右子树最小节点给删掉
}
else {
if(root.left != null)
root = root.left;//情况二：只有左子树
else
root = root.right;//情况三：只有右子树或者没有子节点（当前节点为叶子结点）
}
}
return root;//返回当前节点
}
}- 方法一：递归 拼接两棵树（不过这个解法会增加树的高度，最坏的情况下会退化成链表……）
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：41.6 MB, 在所有 Java 提交中击败了56.38%的用户
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if(root == null)
return null;
if(root.val < key)
root.right = deleteNode(root.right, key);//当前节点值比key小时，去右子树查找
else if(root.val > key)
root.left = deleteNode(root.left, key);//当前节点的值比key小时，去左子树查找
else {
if(root.left == null)//第一种情况，要删除的节点没有左节点，
return root.right;
else if(root.right ==null)//第二种情况：要删除的节点没有右节点
return root.left;
else if(root.left != null && root.right != null){//既有左节点又有右节点
TreeNode post = root.right;//标记节点
while(post.left != null)
post = post.left;//找到要删除节点的右子树的最左边的节点
post.left = root.left;//两棵子树拼接
return root.right;//返回右子树的根节点
}
}
return root;
}
}04-13 水 阴
- 路径总和 II
第一思路就是递归了，在传list的值方面有些不理解，在加完一条路径的值之后，需要新建一个list
- 深度优先搜索、回溯
执行用时：1 ms, 在所有 Java 提交中击败了99.99%的用户
内存消耗：41.8 MB, 在所有 Java 提交中击败了26.21%的用户
class Solution {
List<List<Integer>> listList = new ArrayList<List<Integer>>();
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<Integer> list = new ArrayList<Integer>();//存路径上的值
List cur = list;//cur操作list
sum(cur, root, targetSum);
return listList;
}
public void sum(List cur, TreeNode root, int target){
if(root == null)
return;//当为空节点时返回
cur.add(root.val);//不为空就先默认存入list
if(target == root.val && root.left == null && root.right == null){//当当前节点为叶子结点并且值和目标值target相等时，说明路径是正确的
listList.add(new ArrayList<Integer>(cur));//将这条路径上的值存入listList
cur.remove(cur.size() - 1);//加入之后把该节点的值从list里删除，开始回溯，败者食尘！
return;
}
sum(cur, root.left, target - root.val);//往左子树递归
sum(cur, root.right, target - root.val);//往右子树递归
cur.remove(cur.size() - 1);//回溯到当前节点时当前节点的值也要删除
}
}- 二叉树的右视图
第一反应就是层序遍历+记录每层最后一个节点了，途中竟然把队列写成了栈2333，明明草稿纸上画着队列的图却new了个栈，广度和深度优先搜索都还不太了解，看了题解发现层序遍历的那种方法其实就是实现了广度优先搜索，至于深度优先搜索，就优先访问右节点再访问左节点，这样递归下去的话就会达到每层都先访问最右边节点的效果，这时判断层数是否为新深入的一层即可得出是否添加节点的值
- 方法二：深度优先搜索（DFS ）
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：40.1 MB, 在所有 Java 提交中击败了32.15%的用户
class Solution {
List<Integer> list = new ArrayList<Integer>();//由于调用了方法所以定义在全局
public List<Integer> rightSideView(TreeNode root) {
DFS(root, 1);//调用深度优先搜索方法
return list;
}
public void DFS(TreeNode root, int depth){
if(root == null)
return;//为空时返回上一层
if(depth > list.size())//当层数大于已存节点个数时，说明到达了新的一层
list.add(root.val);//并且在每层第一个访问的总是最右边的节点，所以直接记录该节点的值
depth++;//进入下一层之前层数加一
DFS(root.right, depth);//优先访问右节点
DFS(root.left, depth);//没有右节点时再访问左节点
return;
}
}- 方法一：广度优先搜索（BFS）利用层序遍历只记录每行最右边的节点值
执行用时：1 ms, 在所有 Java 提交中击败了80.74%的用户
内存消耗：39.8 MB, 在所有 Java 提交中击败了76.90%的用户
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
int count = queue.size();
while(root != null && !queue.isEmpty()){
if(!queue.isEmpty()) {
root = queue.poll();
count--;
}
if(root.left != null)
queue.offer(root.left);
if(root.right != null)
queue.offer(root.right);
if(count == 0){
list.add(root.val);
count = queue.size();
}
}
return list;
}
}04-12 火 晴
- 二叉树的锯齿形层序遍历
看到广度优先搜索有点蒙，特意先去补了一下相关知识，但发现没啥用一时半会理解不来，就硬做吧 看上去能找到规律的样子
双向队列快一点！双栈其实实现的就是双向队列的功能啦哈哈哈哈，学到了个新的方法：Deque
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：40.2 MB, 在所有 Java 提交中击败了40.67%的用户
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> listList = new ArrayList<>();
if(root == null)
return listList;
Deque<TreeNode> deque = new ArrayDeque<TreeNode>();
int toLeft = 0;
deque.addFirst(root);
int toRight = 1;
while(deque.peek() != null){
if(toRight != 0){
List<Integer> listInt = new ArrayList<Integer>();
while(toRight != 0){
root = deque.pollLast();
toRight--;
listInt.add(root.val);
if(root.left != null){
deque.addFirst(root.left);
toLeft++;
}
if(root.right != null){
deque.addFirst(root.right);
toLeft++;
}
}
listList.add(listInt);
}
if(toLeft != 0){
List<Integer> listInt = new ArrayList<Integer>();
while(toLeft != 0){
root = deque.pollFirst();
toLeft--;
listInt.add(root.val);
if(root.right != null){
deque.addLast(root.right);
toRight++;
}
if(root.left != null){
deque.addLast(root.left);
toRight++;
}
}
listList.add(listInt);
}
}
return listList;
}
}- 双栈操作
由于是锯齿形的层序遍历，那把两层的遍历看做一个循环，就是一个规律的变化了，这样的话需要用到两个栈来分别记录从左往右和从右往左的节点，而当两个栈都为空时结束循环。 感觉会有更好的解决方案但我只能想到这样了……
执行用时：1 ms, 在所有 Java 提交中击败了76.15%的用户
内存消耗：40 MB, 在所有 Java 提交中击败了56.49%的用户
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> listList = new ArrayList<List<Integer>>();//先来个存List的List
if(root == null)
return listList;//当空树时直接return
//分别定义往左和往右的栈，记录下一层往右和往左的移动方向
Stack<TreeNode> toLeft = new Stack<TreeNode>();
Stack<TreeNode> toRight = new Stack<TreeNode>();
toRight.push(root);//默认进个根（才能开始下面的循环）
while(!toLeft.empty() || !toRight.empty()){//当两个栈同时为空时结束循环
if(!toRight.empty()){//往右栈不为空，说明需要执行奇数层的遍历，默认从根节点的奇数第一层开始遍历
List<Integer> listToRightInt = new ArrayList<Integer>();//记录向右遍历的节点的值
while(!toRight.empty()){
root = toRight.pop();//节点移动到新节点
listToRightInt.add(root.val);//新节点的值添加到list中
if(root.left != null)//往右遍历时，记录的是往左遍历的节点，所以先左后右入栈，出栈时则会从下一层最右边的节点开始，达到从右往左遍历的效果
toLeft.push(root.left);
if(root.right != null)//先左后右
toLeft.push(root.right);
}
listList.add(listToRightInt);
}
else if(!toLeft.empty()){//往左栈不为空，说明需要执行偶数层的遍历
List<Integer> listToLeftInt = new ArrayList<Integer>();//记录往左遍历的节点的值
while(!toLeft.empty()){
root = toLeft.pop();//移动到往左栈弹出的节点上，逐渐往左遍历
listToLeftInt.add(root.val);//添加值
if(root.right != null)//往左遍历记录的是下一层往右遍历的节点的值，所以先右后左，出栈时则会先左后右，达到从左往右遍历的效果
toRight.push(root.right);
if(root.left != null)
toRight.push(root.left);
}
listList.add(listToLeftInt);
}
}
return listList;
}
}- 从前序与中序遍历序列构造二叉树
好难的一题……刚好今天数据结构也讲到二叉树了，但这题有思路却很难用算法描述出来，要自闭了
- 递归
执行用时：1 ms, 在所有 Java 提交中击败了99.35%的用户
内存消耗：40.8 MB, 在所有 Java 提交中击败了73.54%的用户
class Solution {
Map<Integer,Integer> map = new HashMap<Integer, Integer>();//全局定义哈希表
public TreeNode buildTree(int[] preorder, int[] inorder) {
for (int i = 0; i < inorder.length; i++)
map.put(inorder[i], i);//记录中序遍历的值的下标（用来找中序遍历中根节点的位置）
return buildTree(preorder, 0, preorder.length - 1, 0, inorder.length - 1);
}
public TreeNode buildTree(int[] preorder, int up, int low, int left , int right){
if(up > low || left > right)
return null;//越界时返回null
int preorderPost = up;//前序遍历中根节点为第一个
int inorderPost = map.get(preorder[preorderPost]);//通过哈希表找到中序遍历中的根节点位置
int size = inorderPost - left;//计算该段中的节点个数：根节点位置减去左臂位置
TreeNode root = new TreeNode(preorder[preorderPost]);//先添加根节点
root.left = buildTree(preorder, up + 1, up + size, left, inorderPost - 1);
root.right = buildTree(preorder, up + size + 1, low, inorderPost + 1, right);
return root;
}
}04-11 月 晴
- 将有序数组转换为二叉搜索树
看到标签有分治，刚好今天数据结构也讲到分治和递归了，感觉这题用递归会挺好写（不用递归好像反而不会了(´இ皿இ｀)）
- 递归
思路很简单，但感觉还是老样子不能一口气把思路写出来，总是一点点小毛病，甚至怀疑自己写错了，写烦了去评论区看了个c++的写法，虽然没看懂，但确定了是可以这样写的，就回到题目继续写下去， 要是够熟练一口气写出来就好了，明明思路很清晰了……
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：40.8 MB, 在所有 Java 提交中击败了79.47%的用户
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return toBST(nums, 0, nums.length - 1);//需要的形参不一样，所以新写一个方法来传入参数
}
public TreeNode toBST(int[] nums, int left, int right){
int mid = left + (right - left) / 2;//取中值，该方法可以防溢出
TreeNode cur = new TreeNode(nums[mid]);//新建一个存有中值的节点
if(left > right)
return null;//当左臂超过右臂时，说明为空了，返回null（左或右孩子没有时就为null了）
else if(left == right)//这里看了评论区发现可以不用这个判断，把new节点步骤移到这里就行，因为在当前这步返回没有左右孩子的cur节点和在下一次递归时将左右孩子都返回为null是一样的！
return cur;//当左右臂相等时，说明是最后一个存在的节点了，返回cur即可
cur.left = toBST(nums, left, mid - 1);//左孩子递归
cur.right = toBST(nums, mid + 1, right);//右孩子递归
return cur;//最后返回cur为根节点
}
}- 移除无效的括号
傻嗨题 简单的思路折磨人，官方题解都是一堆文字没啥含金量的感觉，题解下的第一条评论：“硬是整出这么多文字出来， 有这时间看文章，自己都想出来了。” 
- 栈和数组
执行用时：29 ms, 在所有 Java 提交中击败了42.54%的用户
内存消耗：41.8 MB, 在所有 Java 提交中击败了61.38%的用户
class Solution {
public String minRemoveToMakeValid(String s) {
Stack<Integer> stack = new Stack<Integer>();//栈里存括号的下标
char[] chars = new char[s.length()];//定义一个空字符数组，长度为字符串的长度
for(int i = 0; i < s.length(); i++){
char ch = s.charAt(i);
if(ch == '('){//当遇到左括号时，入栈并跳过该循环
stack.push(i);
continue;
}
else if(ch == ')'){//当遇到右括号时，分两种情况
if(stack.empty())
continue;//如果栈为空，那就是没有对应的左括号，直接跳过该循环
else
chars[stack.pop()] = '(';//否则出栈并给对应的左括号的下标改为(
}
chars[i] = ch;//只要没跳过的循环都给赋值，右括号里第二种情况时也会赋值
}
StringBuilder sb = new StringBuilder();//来个sb
for(int i = 0; i < chars.length; i++){
if(chars[i] == '\u0000')
continue;//如果是空的也就是没有赋值的下标，跳过
else
sb.append(chars[i]);//否则给sb加上
}
return sb.toString();//转为字符串返回
}
}04-10 日 晴
- 重排链表
想练递归的，结果给我上了一课……不说了，直接贴题解吧，这题不得不硬搬官方题解表达我的内心
- 方法一：线性表
这方法我是真的醉了！！！
执行用时：3 ms, 在所有 Java 提交中击败了33.94%的用户
内存消耗：43.5 MB, 在所有 Java 提交中击败了78.43%的用户
class Solution {
public void reorderList(ListNode head) {
if (head == null) {
return;
}
List<ListNode> list = new ArrayList<ListNode>();
ListNode node = head;
while (node != null) {
list.add(node);
node = node.next;
}
int i = 0, j = list.size() - 1;
while (i < j) {
list.get(i).next = list.get(j);
i++;
if (i == j) {
break;
}
list.get(j).next = list.get(i);
j--;
}
list.get(i).next = null;
}
}- 方法二：寻找链表中点 + 链表逆序 + 合并链表
步骤多了点，但还算可以接受吧
执行用时：1 ms, 在所有 Java 提交中击败了99.99%的用户
内存消耗：43.6 MB, 在所有 Java 提交中击败了73.88%的用户
class Solution {
public void reorderList(ListNode head) {
ListNode slow = head;//慢指针
ListNode fast = head;//快指针
while(fast != null && fast.next != null){//先找中间节点
slow = slow.next;
fast = fast.next.next;
}
ListNode pre = null;//反转后半段链表时用到的前驱节点
ListNode cur = slow.next;//改变指向的当前节点
slow.next = null;//从中间节点处断开
while(cur != null){//反转后半段链表
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
while(pre != null){//后半段链表的节点一一插入前半段链表的间隙中
ListNode temp1 = head.next;
ListNode temp2 = pre.next;
head.next = pre;
pre.next = temp1;
head = temp1;
pre = temp2;
}
}
}- 方法三：快慢指针取中位插入
想到了取中间节点，但没想到用快慢指针可以取到…… 还以为得遍历两次计数呢
执行用时：5 ms, 在所有 Java 提交中击败了8.19%的用户
内存消耗：43.9 MB, 在所有 Java 提交中击败了55.06%的用户
class Solution {
public void reorderList(ListNode head) {
ListNode slow = head;//慢指针
ListNode fast = head;//快指针
while(fast != null && fast.next != null){//找中间节点
slow = slow.next;
fast = fast.next.next;
}
fast = slow;//记录下中间节点，待会要断链
slow = slow.next;//进一位防止把自己断了
Stack<ListNode> stack = new Stack<ListNode>();
while(slow != null){
stack.add(slow);//将后半段节点一一入栈
slow = slow.next;
}
fast.next = null;//断链
while(!stack.empty() && head != null){//将后半段节点一一出栈后插入前半段节点的间隙中
ListNode temp = head.next;//记录插入位置的右边节点的位置
head.next = stack.pop();//出入节点并连接上
head.next.next = temp;//连上右边的节点
head = temp;//移动到右节点的位置上，下一轮继续插入
}
}
}- 方法四：递归写法
效率没想到会这么低……这次也太惨了
执行用时：533 ms, 在所有 Java 提交中击败了5.00%的用户
内存消耗：44.5 MB, 在所有 Java 提交中击败了5.10%的用户
class Solution {
public void reorderList(ListNode head) {
if(head == null || head.next == null)
return;//当上一轮的next节点是null或只有一个节点（该节点的next会被断掉）时，开始归
ListNode post = head;//定义一个回溯指针，败者食尘！
while(post.next.next != null)
post = post.next;//使回溯指针移动到倒数第二个节点上
ListNode tail = post.next;//尾指针顾名思义在最后一个节点上
post.next = null;//先断开头尾和中间节点的链接
tail.next = head.next;//尾部连头的下一个节点
head.next = tail;//头结点连尾节点
reorderList(tail.next);//开始往链表中间递归
}
}K 个一组翻转链表
久违的做一道困难题……果然挺难的，但是思路不难，无非就是每段处理然后将每段的第一个节点的next递归下去，但在做24. 两两交换链表中的节点时，我思路是从前往后翻转的，而在这题里会被最后一段当节点数小于k时不需要翻转给迷惑了 ，因为从前往后翻转的话就无法得知是否在最后一段，就算加了判断条件可以返回对应的节点，但该段的链式已经被破坏翻转了 
。所以最好的方法应该是从后往前翻转 ，于是每段的时候都需要先遍历一边当前段的k个节点，若遍历到节点为null，那就说明是最后一段节点数小于k的段了，这时候可以直接返回该段第一个节点，其余段则进行正常的从后往前翻转的操作（整段翻转需要用到三个指针变量，老知识点了）- 递归写法
思路和评论区的大佬大致是一样的，只可惜没能想到正难则反呀，死磕在从前往后翻转了
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode post = head;//记录一段k个节点的第k+1个节点位置
for(int i = 0; i < k; i++){
if(post == null)//如果当前段不满足k个节点，那说明是最后一段了，不需要翻转，直接返回head
return head;
post = post.next;//移动k次，最后到达nk+k+1的位置上
}
ListNode pre = null;//前驱节点
ListNode cur = head;//当前变动节点
while(cur != post){//翻转直到当前节点指针移动到第nk+k+1个节点上
ListNode temp = cur.next;//记录当前变动节点的下一节点位置，方便移动
cur.next = pre;//开始翻转，第nk+1节点的下一节点先默认为null，之后下一节点则改为上一节点
pre = cur;//前驱移动到当前节点位置
cur = temp;//当前节点指针移动到原链表的下一节点位置
}
head.next = reverseKGroup(post, k);//进行下一轮（n+1轮）翻转的递归操作
return pre;//最终返回的应该是第一段的第k个节点为头结点，也就是第一轮时的pre最终指向的位置
}
}04-09 土 晴
- 找出游戏的获胜者
上题看了递归后又想试着写写递归玩~，于是找了这题
- 方法一：递归
评论区的一行递归……tql
class Solution {
public int findTheWinner(int n, int k) {
return n == 1 ? n : (findTheWinner(n - 1, k) + k - 1) % n + 1;
}
}- 方法二：数学公式解法
评论区的约瑟夫环——公式法（递推公式）
class Solution {
public int findTheWinner(int n, int k) {
int p = 0;
for (int i = 2; i <= n; i++) {
p = (p + k) % i;
}
return p + 1;
}
}- 方法三：模拟
用循环链表模拟一个圈，模拟淘汰的过程，思路挺好理解的，但这压根不怎么递归吧！！！！
执行用时：5 ms
内存消耗：38.2 MB
public class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class Solution {
public int findTheWinner(int n, int k) {
int count = 1;//从1开始建立一个环形链表
ListNode list = new ListNode(count++);//n最小是1所以至少一个，顺便做头结点
ListNode p = list;//p做操作指针
while(count <= n) {//建立一共k个节点
p.next = new ListNode(count++);
p = p.next;
}
p.next = list;//最后成环
return find(p, k);//开始递归
}
int find(ListNode p, int k){
if(p.next == p)//当p的下一位是本身时，说明只剩下一个人了，递归结束返回p的值
return p.val;
for(int i = 1; i < k; i++)
p = p.next;//p移动到到被淘汰的人的前一名
p.next = p.next.next;//隔位连接，断掉被淘汰的人的节点
return find(p, k);//继续淘汰
}
}- 两两交换链表中的节点
哼，链表，撒撒碎！ 洗澡啦~
来自评论区的递归写法，这就妙到家了 递归也太爽了
三道题套路解决递归问题
class Solution {
public ListNode swapPairs(ListNode head) {
//终止条件：链表只剩一个节点或者没节点了，没得交换了。返回的是已经处理好的链表
if(head == null || head.next == null){
return head;
}
//一共三个节点:head, next, swapPairs(next.next)
//下面的任务便是交换这3个节点中的前两个节点
ListNode next = head.next;
head.next = swapPairs(next.next);
next.next = head;
//根据第二步：返回给上一级的是当前已经完成交换后，即处理好了的链表部分
return next;
}
}交换没啥难的，C语言的时候写的多了，来个临时变量储存就行，不过这里是链表，一个指针里有两个节点的信息（当前节点和下一节点的地址），所以两两交换的时候不需要第三变量，但在下一轮交换的时候，忽略了两个节点与两个节点之间的连接问题，也就是上一轮的第二个节点应该连到当前一轮的第二个节点上，再进行两两节点的交换，不然会有节点丢失 
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：38.8 MB, 在所有 Java 提交中击败了77.98%的用户
class Solution {
public ListNode swapPairs(ListNode head) {
if(head == null || head.next == null)
return head;//空头或独头直接返回
ListNode pre = head;//前指针
ListNode next = head.next;//后指针
head = head.next;//由于前后指针的位置会交换，直接返回头指针的话相当于返回从第二个元素开始的链表，所以需要头指针移动到下一节点（也就是新的头结点）
ListNode temp = null;//中间变量先定为null，第一次交换时用不上
while(pre != null && next != null){//前后指针都不为零时执行循环
if(temp != null)//第一二个元素交换时，也就是第一轮循环时不执行该语句
temp.next = next;
pre.next = next.next;//前指针（n）的箭头改向后指针的下一个节点（n+2）
next.next = pre;//后指针（n+1）的箭头改向前指针所指的节点（n）
temp = pre;//记录前指针（n）所在节点的位置（也就是第偶数个节点），每两个节点交换后，需要重新改变上一轮前指针（即temp）的指向为当前循环的后指针所在节点
pre = pre.next;//前指针的next指向已改为后指针的next，所以前指针（n）移动到第n+2个节点上
if(pre != null)//若前指针（n+2）处不为null
next = pre.next;//后指针也移动到下一轮的位置上（n+3）
}
return head;
}
}- 删除排序链表中的重复元素II
做来做去又到链表了呀，做完这题想看会css去了~
双指针(yyds)，本来思路不难的，但是我不知道为什么想了很久，可能是因为中午一起来就和舍友一块在卷，有点被动的状态……
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：40.7 MB, 在所有 Java 提交中击败了68.05%的用户
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head == null || head.next == null)
return head;//空头或者只有头直接返回
ListNode list = new ListNode();//新建一个链表的哑头结点//由于头部可能会是重复元素，所以第一个元素先稍安勿躁，等待原链表判断出非重复后再加节点
ListNode p = list;//链表操作指针
while(head != null){//只要原链表不为null就循环
if(head.next != null && head.val == head.next.val){//当原链表当前节点和下一节点的值相等时，执行跳过节点的语句（因为用到了next，所以要加个next不为null的判断
while(head.next != null && head.val == head.next.val)//跳过节点
head = head.next;
}
else{//否则将原链表的当前节点的值加到新节点上，并将操作指针移动
p.next = new ListNode(head.val);
p = p.next;
}
head = head.next;//每次循环都要移动原链表的指针，关键在跳过节点时，会跳到重复元素的最后一个节点上，此时再执行一次指针移动才会移出重复的区域
//比如2,2,2,2,3时，跳过节点的语句会将指针移动到最后一个2上，而再执行该语句，才会移动到3的位置上，即重复区域外
}
return list.next;//返回哑头结点的下一元素
}
}暴力打表解（链表题效率这么低真是菜啊……）
执行用时：2 ms, 在所有 Java 提交中击败了7.37%的用户
内存消耗：40.8 MB, 在所有 Java 提交中击败了53.65%的用户
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head == null || head.next == null)
return head;
ListNode list = new ListNode();
ListNode p1 = list;
ListNode p2 = head;
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
while(p2 != null){
if(map.containsKey(p2.val))
map.replace(p2.val, map.get(p2.val) + 1);
else
map.put(p2.val, 1);
p2 = p2.next;
}
p2 = head;
while(p2 != null){
if(map.get(p2.val) == 1){
p1.next = new ListNode(p2.val);
p1 = p1.next;
}
p2 = p2.next;
}
return list.next;
}
}- 相交链表
笑死我了这题，简单题搞出了这么多花样，感觉到有一丝丝的进步，从思路直白的暴力打表很快解出来，然后自己构思优化出用栈做回头法，最后看评论区学到了两路走的方法。写的真是开心啊！
走过你走过的路（doge）
执行用时：1 ms, 在所有 Java 提交中击败了98.67%的用户
内存消耗：44.1 MB, 在所有 Java 提交中击败了53.81%的用户
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
/**
定义两个指针, 第一轮让两个到达末尾的节点指向另一个链表的头部, 最后如果相遇则为交点(在第一轮移动中恰好抹除了长度差)
两个指针等于移动了相同的距离, 有交点就返回, 无交点就是各走了两条指针的长度
**/
ListNode pA = headA;
ListNode pB = headB;
// 在这里第一轮体现在pA和pB第一次到达尾部会移向另一链表的表头, 而第二轮体现在如果pA或pB相交就返回交点, 不相交最后就是null==null
while(pA != pB){
pA = pA == null ? headB : pA.next;
pB = pB == null ? headA : pB.next;
}
return pA;
}
}到终点时一起回头（doge）
执行用时：3 ms, 在所有 Java 提交中击败了24.72%的用户
内存消耗：43.4 MB, 在所有 Java 提交中击败了80.71%的用户
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == headB)
return headA;
ListNode pA = headA;
ListNode pB = headB;
Stack<ListNode> stackA = new Stack<ListNode>();//A走过的路
stackA.add(null);//站底给个null防止在0号相交时不出栈
Stack<ListNode> stackB = new Stack<ListNode>();//B走过的路
stackB.add(null);//同理
while(pA != null){
stackA.add(pA);//记录我走过的路
pA = pA.next;
}
while(pB != null){
stackB.add(pB);//记录你走过的路
pB = pB.next;
}
while(pA == pB){//携手回头（当不在一条路上的时候，就没有一起回头的步骤了，但最终两人都会在null所以至少会执行一次）
if(!stackA.empty())//当还有回头路时，继续回头
pA = stackA.pop();
if(!stackB.empty())//同理
pB = stackB.pop();
}
return pA == null ? pB.next : pA.next;//返回不为null的下一节点，
}
}暴力打表没有浪漫，看到你的身影时，我开始追寻你（doge）
执行用时：9 ms, 在所有 Java 提交中击败了5.98%的用户
内存消耗：44.1 MB, 在所有 Java 提交中击败了55.55%的用户
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode pA = headA;
ListNode pB = headB;
Set<ListNode> set = new HashSet<ListNode>();//暴力打表有什么好说的！
while(pA != null || pB != null){
if(set.contains(pA))//已在表中，直接返回该节点
return pA;
if(pA != null){//不到终点就继续走继续打表
set.add(pA);
pA = pA.next;
}
if(set.contains(pB))//同理
return pB;
if(pB != null){
set.add(pB);
pB = pB.next;
}
}
return null;//都走完时表示没相交，null了
}
}04-08 金 晴
- 环形链表 II
做过I的了，II多了个需要返回入环口，也就是难点在于入环口了
快指针一直是慢指针的两倍步数，进环快慢指针相遇后慢指针一定只走了部分圈，这时候让慢指针继续走，并定义一个新指针和慢指针同步走，最后新指针和慢指针会在入环也是出环口相遇，写个更深层的解释：由于fast是slow的两倍速，所以当slow入环时，fast除了走了slow一样的路程x外，还在环里走了相同的路程x，设环的长度为s，那么fast还差s-x步到环出口，此时需要继续走知道slow和fast相遇，也就是会再走s-x步后会相遇，相遇后，slow在环里走了s-x步，此时定义一个新指针p，让它从头开始和slow以一样的速度走，知道他们相遇，关键来了，此时slow在环中距离环口的距离刚好为s-（s-x）=x步，也就是当p和slow相遇时，它们都在环入口处！！！
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：41.2 MB, 在所有 Java 提交中击败了78.32%的用户
public class Solution {
public ListNode detectCycle(ListNode head) {
if(head == null)
return null;//测试例子有个空头结点，需要判断一下
ListNode slow = head;//定义慢指针
ListNode fast = head;//定义快指针
while(fast.next != null && fast.next.next != null){
slow = slow.next;//满指针每次走一步
fast = fast.next.next;//快指针每次走两步
if(slow == fast){//当快慢指针相遇的时候
ListNode p = head;//定义一个新指针
while(p != slow){//只要新指针还没和慢指针相遇就一直走
p = p.next;
slow = slow.next;
}
return p;//最后得到的就是入环口
}
}
return null;//没有环就返回null
}
}直接遍历存入哈希表中，效率挺低的……不过很容易想到
执行用时：3 ms, 在所有 Java 提交中击败了20.08%的用户
内存消耗：42.1 MB, 在所有 Java 提交中击败了11.29%的用户
public class Solution {
public ListNode detectCycle(ListNode head) {
Set<ListNode> set = new HashSet<ListNode>();
ListNode p1 = head;
ListNode p2 = null;
while(p1 != null){//逐个遍历，若不成环则会p1==null并退出
if(set.contains(p1))//当p1存在于哈希表中时，手动退出循环防止死循环
break;
set.add(p1);//记录每一个节点信息
p1 = p1.next;
}
return p1;
}
}- 两数相加
第二次还是第三次写这题了，这下完全不缺思路了好吧，干！
已经会用%和/来取进位数了，不需要另外的变量来标记啦~~~（这就是刷题的进步吧！）
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode list = new ListNode();
ListNode l = list;
int num = 0;
while(l1 != null || l2 != null){
int val1 = l1 == null ? 0 : l1.val;//当l1或l2为null时赋值为0（有可能一长一短，短的结束后长的还要继续
int val2 = l2 == null ? 0 : l2.val;
num += val1 + val2;//包括上一轮的进位数
l.next = new ListNode(num % 10);//新建节点的同时赋值并连接上
l = l.next;//进到下一个节点
num = num / 10;//取进位数，在下一轮用
if (l1 != null) l1 = l1.next;//不为null时才继续遍历
if (l2 != null) l2 = l2.next;
}
if(num != 0){//两条链表都遍历完后若有进位数，则再建一个节点储存该数
l.next = new ListNode(num % 10);
l = l.next;
}
l.next = null;//Java好像不需要，C语言里得最后一个指向NULL不然测试会报错
return list.next;//返回头结点的下一个节点
}
}标签有位运算，但响了一下没想到做梦用，还是打表好了，很简短啊，一下子就写完通过了
这竟然是中等题，可能位运算比较难吧题解也确实难看懂，不过我的方法竟然比官方的打表和位运算都要快……（当然位运算省空间就是了）
直接用Set写的，长度为10的滑动窗口一一判断，已存在的就加到list里，还没有的就加到set里
执行用时：16 ms, 在所有 Java 提交中击败了90.79%的用户
内存消耗：49.5 MB, 在所有 Java 提交中击败了54.95%的用户
class Solution {
public List<String> findRepeatedDnaSequences(String s) {
List<String> list = new ArrayList<>();//需要返回的list
Set<String> set = new HashSet<>();//用来判断是否已经存在的set
// Map<String, Integer> map = new HashMap<>();//试了用哈希表判断，发现更慢了，不如Set！
for(int i = 0; i < s.length() - 9; i++){
String str = s.substring(i, i+10);//长度为10的滑动窗口
if(set.contains(str) && !list.contains(str)){//若str存在且list里还未加上
list.add(str);//就给list加上该子串
}
set.add(str);//每一个窗口都需要加上（set里若有重复的会自动判断不加入）
}
return list;
}
}04-07 木 晴
/**
* 2022年4月7日20:54:25
* 43. 字符串相乘
* 思路有就不怕难，虽然写的长，但相加部分是前几天做过的题，相乘也就不缺思路了，嘎嘎乱写！
*/
//看了评论区后的新思路，用数组做，速度会快很多
//执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
//内存消耗：41.5 MB, 在所有 Java 提交中击败了36.08%的用户
/**
* 具体思路：
* 9 9 9
* × 6 7 8
* ----------------------
* 72 72 72
* 63 63 63
* 54 54 54
* ----------------------
* 54 117 189 135 72
* ----------------------
* 54 117 189 142 2
* -----------------------
* 54 117 203 2 2
* -----------------------
* 54 137 3 2 2
* -----------------------
* 67 7 3 2 2
* -----------------------
* 6 7 7 3 2 2
*/
class Solution {
public String multiply(String num1, String num2) {
if(num1.charAt(0) == '0' || num2.charAt(0) == '0')
return "0";//当有一个字符串开头是0的情况直接返回0，任何数乘0都为0
int[] num = new int[num1.length()];//定义一个长度为字符串1的被乘以数的整型数组（上面的数要乘以下面数的每一个数字）
int[] sum = new int[num1.length() + num2.length()];//定义一个长度为字符串1+字符串2长度的整型数组（两数相乘的长度最长为这个，参考99*99为四位数）
int temp = 0;//定义在相加阶段的临时变量
for(int i = 0; i < num.length; i++)
num[i] = num1.charAt(i) - '0';//将字符串1先全转为整型数组
for(int i = num.length - 1; i >= 0; i--){
for(int j = num2.length() - 1; j >= 0; j--){
sum[i + j + 1] += (num2.charAt(j) - '0') * num[i];//将上面的乘数整个数乘以下面乘数的每一个数，i+j+1可自动为相乘结果进位到对应的数组下标上
}
}
StringBuilder sb = new StringBuilder();//定义相加的结果字符串
for(int i = sum.length - 1; i >= 0; i--){
if (i == 0 && temp == 0) {
continue;//若最后用不到最后一个位数（如99*10为三位数，第四位没用到），则跳过这一个（不然会多一个0）
}
temp += sum[i];//当前数加上上一轮的余数
sb.append(temp % 10);//插入个位数
temp = temp / 10;//取余数，用在下一轮
}
return sb.reverse().toString();//反转再转为字符串并return
}
}
//自己的思路
//执行用时: 14 ms
//内存消耗: 41.7 MB
class Solution {
public String multiply(String num1, String num2) {
if(num1.charAt(0) == '0' || num2.charAt(0) == '0')
return "0";//当有一个字符串开头是0的情况直接返回0，任何数乘0都为0
StringBuilder sb = new StringBuilder();//定义一个每轮乘以的结果
StringBuilder sbNum = new StringBuilder();//定义一个乘数相加的结果
int count = 0;//乘数相加时补0的个数，每乘一轮多加一个0（多进一位）
int num;//每轮乘以结果中两个数一一相乘的结果数
for(int i = num2.length() - 1; i >= 0; i--, count++){
int temp2 = num2.charAt(i) - '0';
num = 0;//重新赋值
sb.delete(0,sb.length());//清空
for(int j = num1.length() - 1; j >= 0; j--){
int temp1 = num1.charAt(j) - '0';
num += temp1 * temp2;
sb.append(num % 10);//两个数一一相乘的结果插入sb中
num = num / 10;//若有余数则到下一轮用
}
if(num != 0)//若有漏掉没加的额外补上，如9*9=81时会漏掉8
sb.append(num);
sb.reverse().toString();//讲每次相乘后得到的数反转回来
for(int k = 0; k < count; k++)
sb.append(0);//为新乘的数补位数（即补0）
String s1 = sb.toString();//s1字符串和s2字符串相加
String s2 = sbNum.toString();
sbNum.delete(0, sbNum.length());
int size1 = s1.length() - 1;//s1和s2的最后一个元素下标
int size2 = s2.length() - 1;
int temp = 0;
while(size1 >= 0 || size2 >= 0 || temp != 0){
if(size1 >=0)
temp += s1.charAt(size1) - '0';//将字符串1的第size1个数转为整型
if(size2 >= 0)
temp += s2.charAt(size2) - '0';//将字符串2的第size2个数转为整型
sbNum.append(temp % 10);//这里和s = s.concat(String.valueOf(temp%10));效果一样，但String类最后需要手动反转
temp = temp / 10;//不需要flag判断进位了，直接除以10让下一次循环加上即可！！！
size1--;
size2--;
}
sbNum.reverse();//每次加完都需要反转一下
}
return sbNum.toString();//返回结果转为String类型
}
}/**
* 2022年4月7日19:22:36
* 49. 字母异位词分组
* 看到哈希表的标签就想找规律打表啦，于是想了这些单词判断的规律
* 一开始就想到可以将每个单词先排序一遍再比较（排序后就是同一个单词）
* 但一开始方法写错了写成了ch.toString()应该用Arrays.toString()
* 期间尝试了别的规律判断，比如ASCII码相乘比较，但是在倒数第二个变态长的示例中没通过
* 这个打表效率好低，再去看看题解是咋样的吧
*/
//看了评论后修改的，哈希表中val值直接写入list值（太骚了！）
//执行用时：6 ms, 在所有 Java 提交中击败了84.53%的用户
//内存消耗：44.1 MB, 在所有 Java 提交中击败了63.56%的用户
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();//直接在表里写入list
for(int i = 0; i < strs.length; i++){
//将每个单词排序好再判断（思路是一样的）
char[] ch = strs[i].toCharArray();
Arrays.sort(ch);
String s = String.valueOf(ch);//用String.valueOf(ch)也可以转字符串
if(!map.containsKey(s))//当表里没有该异位词时
map.put(s, new ArrayList<String>());//添加新的异位词list组
map.get(s).add(strs[i]);//所有单词都需要写入某个list组里，用哈希表的get方法获取就行
}
return new ArrayList<>(map.values());//返回的时候直接new一个新的list然后写入哈希表的所有val值进去即可
}
}
//直接写的，将哈希表和list分开用
//执行用时：9 ms, 在所有 Java 提交中击败了30.48%的用户
//内存消耗：44.7 MB, 在所有 Java 提交中击败了16.15%的用户
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, Integer> map = new HashMap<String, Integer>();//打表打表
List<List<String>> list = new ArrayList<List<String>>();//返回的值
List l;//操作里面的list
int count = 0;//记录是第几个list
for(int i = 0; i < strs.length; i++){
//将每个单词排序好再判断
char[] ch = strs[i].toCharArray();
Arrays.sort(ch);
String s = Arrays.toString(ch);
if(map.containsKey(s)){//该单词存在有异位词时，添加到对应的list中
l = list.get(map.get(s));
l.add(strs[i]);
}
else {//否则添加到新list和写入表中，表中记录异位词和list的位置
List<String> listString = new ArrayList<String>();
listString.add(strs[i]);
list.add(listString);
map.put(s,count);
count++;
}
}
return list;
}
}04-06 水 晴
/**
* 2022年4月6日21:57:32
* 763. 划分字母区间
* 打表的时候不一定要记录出现个数嘛，也可以记录最后出现的位置，第一次遍历打表
* 第二次遍历的时候就能通过比较扫描区间而不断更新区间内字母最后出现位置的最大值了
*/
class Solution {
public List<Integer> partitionLabels(String s) {
List<Integer> list = new ArrayList<Integer>();
int[] map = new int[26];//打表
int left = 0;
int right = 0;
for(int i = 0; i < s.length(); i++)
map[s.charAt(i) - 'a'] = i;//记录每个字母最后一次出现的位置
for(int i = 0; i < s.length(); i++) {
right = Math.max(right, map[s.charAt(i) - 'a']);//当有新的字母的位置在更后面的时候，更新right
if (right == i) {//当right和i相等时则达到范围内已有字母的最后一个位置
list.add(right - left + 1);//加上区间
left = right + 1;//更新左臂的位置
}
}
return list;
}
}/**
* 2022年4月6日16:23:21
* 290. 单词规律
* 哈希表建制对应判断，一开始在想怎么分割字符串s，找到了一个String类的split() 方法，可以进匹配正则表达式来拆分字符串
* 分割完后就直接成了n个单词数组了，只要用哈希表进行对应判断即可，判断方式写在注释里
*/
class Solution {
public boolean wordPattern(String pattern, String s) {
String[] string = s.split(" ");//用正则表达式将字符串s以空格为分隔符拆成数组的形式
if(pattern.length() != string.length)//当数量不一一对应的时候直接就是false
return false;
HashMap<Character, String> hashMap = new HashMap<>();
for(int i = 0; i < pattern.length(); i++){
char ch = pattern.charAt(i);//方便起见定义个ch字符接收第i个pattern里的字符
if(hashMap.containsKey(ch)){//当该字符已添加时
if(!hashMap.get(ch).equals(string[i]))//如果已添加的字符的单词和当前判断的单词不一样
return false;//则返回false
}
else {//当该字符未添加时
if (hashMap.containsValue(string[i]))//如果当前单词对应的字符未添加，但单词却已经存在时
return false;//说明出现了多（字符）对一（单词）的关系，也返回false
else//否则将新的字符和对应的单词添加
hashMap.put(ch, string[i]);
}
}
return true;//最终返回true
}
}04-05 火 晴
/**
* 2022年4月5日13:29:02
* 409. 最长回文串
* 用数组做哈希表，然后判断是奇是偶即可，过程中漏了奇数且不为1的情况可以取奇数减一的个数
* 也就是偶数直接取，奇数减一再取，当1时减一则为0，但一个的可以放在最中间，所以还需要判断有无单个的字母
*/
class Solution {
public int longestPalindrome(String s) {
// int[] map = new int[52];
int[] map = new int[128];//没必要省空间，反而可能会浪费时间再判断上
int count = 0;
for(int i = 0; i < s.length(); i++){
// char ch = s.charAt(i);
// if('A' <= ch && ch <= 'Z')
// map[ch - 'A']++;
// else if('a' <= ch && ch <= 'z')
// map[ch - 'a' + 26]++;
map[s.charAt(i)]++;
}
for(int i : map){
/*一开始没注意到当个数为奇数但不为1的时候，是可以取部分做回文的
漏了这一点就不能这样判断了，一个很巧妙的写法：count += i / 2 * 2;
当i为奇数且为1时，它是为0的，而为奇数但不为1时，它是i-1的，偶数则没影响
对此可以有当i为1且count为偶数时，count++
在此之后count总为奇数不再会变成偶数，所以该判断只会执行至多一次！！！妙啊
if(i % 2 == 0)
count += i;
else if(i > flag)
flag = i;*/
count += i / 2 * 2;
if(i % 2 == 1 && count % 2 == 0)
count++;
}
return count;
}
}/**
* 2022年4月5日11:37:08
* 415. 字符串相加
* 思路不难但卡在字符串拼接上了……最后才发现是自己方法用错了
* 字符串拼接：s = s.concat(); 而不是直接引用s.concat();
* 另外学到了StringBuilder类，直接解决了最后需要字符串反转的步骤
*
* 在每次对 String 类型进行改变的时候，都会生成一个新的 String 对象，然后将指针指向新的 String 对象，
* 所以经常改变内容的字符串最好不要用 String ，因为每次生成对象都会对系统性能产生影响，
* 特别当内存中无引用对象多了以后，JVM 的 GC 就会开始工作，性能就会降低。
* StringBuilder类也代表可变字符串对象。实际上，StringBuilder和StringBuffer基本相似，两个类的构造器和方法也基本相同。
* 不同的是：StringBuffer是线程安全的，而StringBuilder则没有实现线程安全功能，所以性能略高。
*/
class Solution {
public String addStrings(String num1, String num2) {
int size1 = num1.length() - 1;
int size2 = num2.length() - 1;
int temp = 0;
StringBuilder num = new StringBuilder();
while(size1 >= 0 || size2 >= 0 || temp != 0){
if(size1 >=0)
temp += num1.charAt(size1) - '0';//将字符串1的第size1个数转为整型
if(size2 >= 0)
temp += num2.charAt(size2) - '0';//将字符串2的第size2个数转为整型
num.append(temp % 10);//这里和s = s.concat(String.valueOf(temp%10));效果一样，但String类最后需要手动反转
temp = temp / 10;//不需要flag判断进位了，直接除以10让下一次循环加上即可！！！
size1--;
size2--;
}
return num.reverse().toString();
}
}
04-04 月 晴
/**
* 2022年4月4日23:44:08
* 560. 和为 K 的子数组
* 其实昨天就开始做这题了，一直没思路，今晚也以为做不出来了，就先做了一道简单题
* 结果晒个衣服回来突然想通了，原来是在判断前缀和在当前数之前存在否需要看是否有多个符合的！
* yes改一遍后过了！
*/
class Solution {
public int subarraySum(int[] nums, int k) {
if(nums.length == 1 && nums[0] != k)
return 0;
HashMap<Integer, Integer> hashMap = new HashMap<>();
int count = 0;
int sum = 0;
for(int i = 0; i < nums.length; i++){
sum += nums[i];
if(hashMap.containsKey(sum - k))
count += hashMap.get(sum - k);
if(sum == k)
count++;
if(hashMap.containsKey(sum))
hashMap.replace(sum, hashMap.get(sum) + 1);
else
hashMap.put(sum, 1);
}
return count;
}
}/**
* 2022年4月4日22:08:46
* 852. 山脉数组的峰顶索引
* 二分查找的应用吧，第一遍写的时候前两个左右臂更改判断多加了个&&，导致会有数组越界的问题
* 但发觉这个判断不用前后顾虑，只需要往中间靠就行了，因为题目给的一定是一个山脉数组，往中间靠则不会越界了
*/
class Solution {
public int peakIndexInMountainArray(int[] arr) {
int left = 0;
int right = arr.length - 1;
int mid = left + (right - left) / 2;
while(left <= right){
if(left > right)
break;
else if(arr[mid] < arr[mid + 1])//这里可以只判断往峰顶靠的那一边的数
left = mid + 1;
else if(arr[mid] < arr[mid - 1])//这里可以只判断往峰顶靠的那一边的数
right = mid - 1;
else if(arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1])//这里可以前后都判断，因为山脉驻足的峰顶一定不在边界
return mid;
mid = left + (right - left) / 2;
}
return mid;
}
}04-03 日 晴
/**
* 2022年4月3日15:47:47
* 238. 除自身以外数组的乘积
* 好难啊……思维能力跟不上了，感觉一个简单的原理要梳理好久
*/
class Solution {
public int[] productExceptSelf(int[] nums) {
int[] answer = new int[nums.length];
answer[0] = 1;
for(int i = 1; i < answer.length; i++){
answer[i] = nums[i - 1] * answer[i - 1];
}
int temp = 1;
/* for(int j = nums.length - 2; j >= 0; j--){
nums[j + 1] = nums[j + 1] * temp;
answer[j] = nums[j + 1] * answer[j];
temp = nums[j + 1];
}*/
for(int i = answer.length - 1; i >= 0; i--){
answer[i] = answer[i] * temp;
temp *= nums[i];
}
return answer;
}
}04-02 土 晴
/*
2022年4月2日22:20:53
C语言网：题目 1004: [递归]母牛的故事
蓝桥杯的题，没用递归，数学问题……
*/
#include<stdio.h>
int main()
{
int n;
while (scanf("%d", &n) && n)
{
int num = 1;
int year4 = 1;
int year3 = 0;
int year2 = 0;
int year1 = 0;
for (int i = 1; i < n; i++)
{
year4 += year3;
year3 = year2;
year2 = year1;
year1 = year4;
num += year1;
}
printf("%d\n", num);
}
}/**
* 2022年4月2日15:20:22
* 334. 递增的三元子序列
* 贪心算法，好巧妙，还不熟练
*/
class Solution {
public boolean increasingTriplet(int[] nums) {
int first = nums[0];
int second = Integer.MAX_VALUE;
for(int i = 1; i < nums.length; i++){
if(nums[i] > second)
return true;
else if (nums[i] > first)
second = nums[i];
else
first = nums[i];
}
return false;
}
}
04-01 金 晴
/**
* 2022年4月1日21:22:18
* 35. 搜索插入位置
* 照搬套路二分搜索，但这题多了个下标插入的判断
* 即当left==right并且不为target的时候，mid下标的值域target做对比，大+1小不变
*/
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
int mid = left + (right - left)/2;
while(left <= right){
if(nums[mid] == target)
return mid;
else if(left == right)
return nums[mid] > target ? mid : mid + 1;
else if(nums[mid] < target)
left = mid + 1;
else if(nums[mid] > target)
right = mid - 1;
mid = left + (right - left)/2;
}
return mid;
}
}/**
* 2022年4月1日12:25:40
* 435. 无重叠区间
* 贪心算法
* 开始接触贪心了执行用时：47 ms,在所有Java提交中击败了98.78%的用户，这怎么看爷不贪心吧！！！（指耗时
*/
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals, (a, b)->a[1]-b[1]);
int count = 0;
int pre= intervals[0][73];
for(int i = 1; i < intervals.length; i++){
if(intervals[i][0] < pre)
count++;
else
pre = intervals[i][74];
}
return count;
}
}
还是止步于这个版本吧
太强了
，我总是三天打鱼两天晒网 
（╯‵□′）╯︵┴─┴
好卷啊 才大一就开始算法了
Leetcode 做过几个，对于我干运维的有点难啊