当前位置: 首页 > news >正文

力扣爆刷第161天之TOP100五连刷71-75(搜索二叉树、二维矩阵、路径总和)

力扣爆刷第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) {LinkedList<Integer> stk1 = new LinkedList<>();LinkedList<String> 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 = mid+1;}}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 {List<List<Integer>> result = new ArrayList<>();List<Integer> list = new ArrayList<>();int sum = 0;public List<List<Integer>> 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, x+1, y);}
}
http://www.lryc.cn/news/394730.html

相关文章:

  • 你真的了解Java内存模型JMM吗?
  • Springboot整合Jsch-Sftp
  • 生成随机的验证码图片(Python)
  • 0/1背包问题总结
  • 模电基础 - 放大电路的频率响应
  • Java 8 到 Java 22 新特性详解
  • 华为OD机试题-提取字符串中最长数学表达式
  • 专家指南:如何为您的电路选择理想的压敏电阻或热敏电阻
  • 基于主流SpringBoot进行JavaWeb开发的学习路线
  • 医疗机器人中的具身智能进展——自主超声策略模型的任务编码和局部探索
  • 探索人工智能在电子商务平台与游戏发行商竞争中几种应用方式
  • 【Altium】AD-网络版一个用户非人为异常占用多个License的解决方法
  • *算法训练(leetcode)第二十五天 | 134. 加油站、135. 分发糖果、860. 柠檬水找零、406. 根据身高重建队列
  • 乐鑫ESPC3 ESP8685 WiFi蓝牙模块透传程序设置教程,抛开繁琐AT指令,简单Web页面配置,即可实现透传
  • 怎么样才能为公司申请OV证书?
  • Python的`queue`模块
  • 牛客周赛 Round 50
  • 后端之路——登录校验
  • 无线网卡怎么连接台式电脑?让上网更便捷!
  • 【45 Pandas+Pyecharts | 去哪儿海南旅游攻略数据分析可视化】
  • Vue3项目给ElementPlus设置中文的两个方案
  • C#开发单实例应用程序并响应后续进程启动参数
  • STM32智能机器人导航系统教程
  • Android 15 适配之16K Page Size :为什么它会是最坑的一个适配点
  • 下载linux的吐槽
  • 【HTML入门】第四课 - 换行、分割横线和html的注释
  • 基于Hadoop平台的电信客服数据的处理与分析④项目实现:任务15:数据生产
  • Kotlin中的数据类型
  • 提高交易决策质量,Anzo Capital昂首资本只需两个交易策略
  • Ubuntu TensorRT安装