网站加密传输怎么做,莱州网站建设哪家好,免费域名网站哪个最好,做网站一定需要icp么力扣爆刷第161天之TOP100五连刷71-75#xff08;搜索二叉树、二维矩阵、路径总和#xff09; 文章目录 力扣爆刷第161天之TOP100五连刷71-75#xff08;搜索二叉树、二维矩阵、路径总和#xff09;一、98. 验证二叉搜索树二、394. 字符串解码三、34. 在排序数组中查找元素的…力扣爆刷第161天之TOP100五连刷71-75搜索二叉树、二维矩阵、路径总和 文章目录 力扣爆刷第161天之TOP100五连刷71-75搜索二叉树、二维矩阵、路径总和一、98. 验证二叉搜索树二、394. 字符串解码三、34. 在排序数组中查找元素的第一个和最后一个位置四、113. 路径总和 II五、240. 搜索二维矩阵 II 一、98. 验证二叉搜索树
题目链接https://leetcode.cn/problems/validate-binary-search-tree/description/ 思路验证二叉搜索树二叉搜索数要求任意节点大于左孩子小于右孩子。这么来看二叉搜索树的中序遍历正好是单调递增序列所以要判断是否是二叉搜索树只需要使用中序遍历并且记录前一个节点的值用来比较即可。
class Solution {TreeNode pro null;boolean flag true;public boolean isValidBST(TreeNode root) {traverse(root);return flag;}void traverse(TreeNode root) {if(root null || !flag) return ;traverse(root.left);if(pro ! null pro.val root.val) {flag false;return;}pro root;traverse(root.right);}
}二、394. 字符串解码
题目链接https://leetcode.cn/problems/decode-string/description/ 思路类似于拼接字符串又带有左右括号一般看到左右括号类型的题目都要考虑一下能不能使用栈来做因为一般左右匹配都是使用栈。本题仔细思考可以发现确实是的类似于计算表达式使用两个栈一个是数字栈一个是字符串栈每次遇到左括号就把收集到的字符串和数字压栈然后启用一个新的字符串和数字记录最新的左括号内的内容直到遇到右括号就可以根据数字栈内的内容复制次数然后拼接字符串栈栈顶元素以此往复即可。
class Solution {public String decodeString(String s) {LinkedListInteger stk1 new LinkedList();LinkedListString stk2 new LinkedList();StringBuilder res new StringBuilder();int num 0;for(char c : s.toCharArray()) {if(c 0 c 9) {num num * 10 Integer.parseInt(c );}else if(c [) {stk1.push(num);num 0;stk2.push(res.toString());res new StringBuilder();}else if(c ]) {StringBuilder t new StringBuilder();int count stk1.pop();for(int i 0; i count; i) {t.append(res);}res new StringBuilder(stk2.pop() t);}else{res.append(c);}}return res.toString();}}三、34. 在排序数组中查找元素的第一个和最后一个位置
题目链接https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/ 思路求排序数组中目标元素出现的最左位置和最右位置其实就是采用二分查找分开查找先查找左边界再查找右边界。然后注意边界条件即元素是否存在查出来的边是否超界。
class Solution {public int[] searchRange(int[] nums, int target) {int left findLeft(nums, target);int right findRight(nums, target);return new int[]{left, right};}int findLeft(int[] nums, int target) {int left 0, right nums.length-1;while(left right) {int mid left (right - left) / 2;if(nums[mid] target) {right mid-1;}else{left mid1;}}if(left 0 || left nums.length) return -1;return nums[left] target ? left : -1;}int findRight(int[] nums, int target) {int left 0, right nums.length-1;while(left right) {int mid left (right - left) / 2;if(nums[mid] target) {left mid 1;}else{right mid - 1;}}if(right 0 || right nums.length) return -1;return nums[right] target ? right : -1;}}四、113. 路径总和 II
题目链接https://leetcode.cn/problems/path-sum-ii/description/ 思路求和满足目标的路径相当于在二叉树上做回溯从上往下进行搜索本质还是回溯只需要把前序位置收集在后序位置丢弃对应了回溯的开始与结束后序位置表示左右子树都遍历完了要返回上一级自然需要删除收集的元素完成回溯。
class Solution {ListListInteger result new ArrayList();ListInteger list new ArrayList();int sum 0;public ListListInteger pathSum(TreeNode root, int targetSum) {backTracking(root, targetSum);return result;}void backTracking(TreeNode root, int targetSum) {if(root null) return;sum root.val;list.add(root.val);if(root.left null root.right null sum targetSum) {result.add(new ArrayList(list));}backTracking(root.left, targetSum);backTracking(root.right, targetSum);list.remove(list.size()-1);sum - root.val;}
}五、240. 搜索二维矩阵 II
题目链接https://leetcode.cn/problems/search-a-2d-matrix-ii/description/ 思路搜索二维矩阵这个二维矩阵有一个特点就是从左往右是递增的从上往下是递增那么也就在右上角构成了一个分界线可以从这个位置开始深度优先搜索如果当前元素小于目标元素那就向下搜索如果当前元素大于目标元素那就是向左搜索。
class Solution {boolean flag false;public boolean searchMatrix(int[][] matrix, int target) {dfs(matrix, target, 0, matrix[0].length-1);return flag;}void dfs(int[][] matrix, int target, int x, int y) {if(x 0 || x matrix.length || y 0 || y matrix[0].length) return;if(matrix[x][y] target) {flag true;return;}else if(matrix[x][y] target) dfs(matrix, target, x, y-1);else dfs(matrix, target, x1, y);}
}
