网站兼容,中国网上购物平台有哪些,临沧网站建设公司招聘,网站换域名了怎么办leetcode 150道题 计划花两个月时候刷完#xff0c;今天#xff08;第三十六天#xff09;完成了4道(78-81)150#xff1a;
78.#xff08;230. 二叉搜索树中第K小的元素#xff09;题目描述#xff1a;
给定一个二叉搜索树的根节点 root #xff0c;和一个整数 k 今天第三十六天完成了4道(78-81)150
78.230. 二叉搜索树中第K小的元素题目描述
给定一个二叉搜索树的根节点 root 和一个整数 k 请你设计一个算法查找其中第 k 个最小元素从 1 开始计数。第一版铭记二叉搜索树的中序遍历为递增的
class Solution {public int kthSmallest(TreeNode root, int k) {StackTreeNode stacknew Stack();while(!stack.isEmpty()||root!null){while(root!null){stack.push(root);rootroot.left;}rootstack.pop();if(--k0){return root.val;}rootroot.right;}return -1;}
}79.98. 验证二叉搜索树题目描述
给你一个二叉树的根节点 root 判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。第一版我第一反应就是递归但是递归了好久没弄出来就用中序遍历为递增的去判断了算是个兜底办法
class Solution {public boolean isValidBST(TreeNode root) {if(rootnull){return true;}Integer preNumnull;StackTreeNode stacknew Stack();while(!stack.isEmpty()||root!null){while(root!null){stack.push(root);rootroot.left;}rootstack.pop();if(preNum!nullroot.valpreNum){return false;}preNumroot.val;rootroot.right;}return true;}
}第二版看了解题递归是真的牛但是这个我也应该能想出来的。。但是没有
class Solution {public boolean isValidBST(TreeNode root) {if(rootnull){return true;}return isValidBST(root,Long.MIN_VALUE,Long.MAX_VALUE);}public boolean isValidBST(TreeNode root,long min,long max) {if(rootnull){return true;}if(root.valmin||root.valmax){return false;}return isValidBST(root.left,min,root.val)isValidBST(root.right,root.val,max);}
}80.200. 岛屿数量题目描述
给你一个由 1陆地和 0水组成的的二维网格请你计算网格中岛屿的数量。
岛屿总是被水包围并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外你可以假设该网格的四条边均被水包围。
输入grid [[1,1,0,0,0],[1,1,0,0,0],[0,0,1,0,0],[0,0,0,1,1]
]
输出3第一版这题我是真不会看了解题怎么说解题无敌
class Solution {public int numIslands(char[][] grid) {// 卧槽解题太叼了int mgrid.length;int ngrid[0].length;int resNum0;for(int i0;im;i){for(int j0;jn;j){if(grid[i][j]1){resNum;dfs(grid,i,j);}}}return resNum;}public void dfs(char[][] grid,int l,int r){int mgrid.length;int ngrid[0].length;if(l0||r0||lm||rn||grid[l][r]0){return ;}grid[l][r]0;dfs(grid,l,r-1);dfs(grid,l,r1);dfs(grid,l-1,r);dfs(grid,l1,r);}
}81.130. 被围绕的区域题目描述
给你一个 m x n 的矩阵 board 由若干字符 X 和 O 找到所有被 X 围绕的区域并将这些区域里所有的 O 用 X 填充。第一版有了上一题经验在做这一题时候确实有一点点思路但是还是没转过来。。还是那句话解题真牛
class Solution {public void solve(char[][] board) {int mboard.length;int nboard[0].length;int[][] flagnew int[m][n];// 标记for(int i0;im;i){if(board[i][n-1]O){dfs(flag,board,i,n-1);}if(board[i][0]O){dfs(flag,board,i,0);}}for(int i0;in;i){if(board[m-1][i]O){dfs(flag,board,m-1,i);}if(board[0][i]O){dfs(flag,board,0,i);}}for(int i0;im;i){for(int j0;jn;j){if(board[i][j]Oflag[i][j]0){board[i][j]X;}}}}public void dfs(int[][] flag,char[][] grid,int l,int r){int mgrid.length;int ngrid[0].length;if(l0||r0||lm||rn||grid[l][r]X||flag[l][r]1){return ;}flag[l][r]1;dfs(flag,grid,l,r-1);dfs(flag,grid,l,r1);dfs(flag,grid,l-1,r);dfs(flag,grid,l1,r);}
}今天这图这一块真的我看了都害怕。。。是一点想法都没有。。图咋这么难
