慢刷Leetcode算法题
|
预计 11 min read
2024-06-24
Ideas
- mergeTrees方法:
- 如果
root1
或root2
为null
,直接返回另一棵树。 - 否则,先将
root1
和root2
对应节点的值相加,并将结果存储在root1
中。 - 递归地合并左子树和右子树。
- 如果
1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 * int val;5 * TreeNode left;6 * TreeNode right;7 * TreeNode() {}8 * TreeNode(int val) { this.val = val; }9 * TreeNode(int val, TreeNode left, TreeNode right) {10 * this.val = val;11 * this.left = left;12 * this.right = right;13 * }14 * }15 */16class Solution {17 public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {18 // 如果root1为空,则直接返回root2,表示第一棵树已经被完全合并到第二棵树中19 if (root1 == null) {20 return root2;21 }22 // 如果root2为空,则直接返回root1,表示第二棵树已经被完全合并到第一棵树中23 if (root2 == null) {24 return root1;25 }26 // 创建一个新的节点,其值为root1和root2的值之和,然后递归合并左右子树27 return new TreeNode( root1.val + root2.val ,28 mergeTrees(root1.left,root2.left),29 mergeTrees(root1.right,root2.right));30
31 }32}

503. 下一个更大元素 II
Ideas
- 初始化:
- 创建一个
result
数组,初始值全部设为-1
,表示如果某个元素没有找到下一个更大元素,则默认值为-1
。 - 创建一个栈
stack
用于存储元素的索引。
- 创建一个
- 遍历数组:
- 使用
for
循环遍历2 * n
次,利用i % n
模拟循环数组。 - 每次从
nums
数组中取出当前元素num
。
- 使用
- 更新结果数组:
- 使用
while
循环,当栈不为空且当前元素num
大于栈顶元素对应的元素时,更新结果数组中栈顶元素对应的下一个更大元素为当前元素,并弹出栈顶。
- 使用
- 压入栈:
- 如果当前索引
i
小于数组长度n
,则将当前索引压入栈中。
- 如果当前索引
1class Solution {2 public int[] nextGreaterElements(int[] nums) {3
4 // 数组长度5 int n = nums.length;6 // 结果数组,初始化为-1,表示没有下一个更大元素7 int[] result = new int[n];8 Arrays.fill(result, -1);9 // 使用栈来辅助寻找下一个更大元素10 Stack<Integer> stack = new Stack<>();11
12 // 遍历数组两次,以处理环形数组的特性13 for (int i = 0; i < 2 * n; i++) {14 // 当前遍历到的元素15 int num = nums[i % n];16 // 如果栈不为空且栈顶元素小于当前元素,则栈顶元素的下一个更大元素为当前元素17 while (!stack.isEmpty() && nums[stack.peek()] < num) {18 result[stack.pop()] = num;19 }20 // 如果当前遍历位置小于原数组长度,则将位置入栈,用于后续寻找下一个更大元素21 if (i < n) {22 stack.push(i);23 }24 }25
26 // 返回结果数组27 return result;28 }29}

2024-06-23
456. 132 模式
Ideas
- 初始化一个空栈和一个
third
变量为Integer.MIN_VALUE
。 - 从后往前遍历数组:
- 如果
nums[i] < third
,说明存在132
模式的子序列,返回true
。 - 如果
nums[i] > stack.peek()
,不断弹出栈顶元素并更新third
,直到栈顶元素不再小于当前元素。 - 将当前元素压入栈。
- 如果
- 如果遍历完数组后没有找到符合条件的子序列,返回
false
。
1class Solution {2 public boolean find132pattern(int[] nums) {3 if (nums == null || nums.length < 3) {4 return false;5 }6
7 Stack<Integer> stack = new Stack<>();8 int third = Integer.MIN_VALUE;9
10 // 从后往前遍历数组11 for (int i = nums.length - 1; i >= 0; i--) {12 if (nums[i] < third) {13 return true;14 }15 // 维护单调递减栈16 while (!stack.isEmpty() && nums[i] > stack.peek()) {17 third = stack.pop();18 }19 stack.push(nums[i]);20 }21
22 return false;23 }24}

- 时间复杂度: O(n)。每个元素最多被压入和弹出栈一次,因此总时间复杂度是线性的。
- 空间复杂度: O(n)。在最坏情况下(严格递增的序列),栈需要存储所有的元素。
520. 检测大写字母
Ideas
-
首先检查单词是否为空或只有一个字符,如果是,直接返回
true
。 -
使用
equals
方法检查整个单词是否全部大写或全部小写。 -
使用
Character.isUpperCase
方法检查首字母是否大写,然后使用substring
和equals
方法检查剩余部分是否全部小写。 -
如果都不符合,返回
false
。
1class Solution {2 public boolean detectCapitalUse(String word) {3 // 如果单词为空或只有一个字符,直接返回 true4 if (word == null || word.length() <= 1) {5 return true;6 }7
8 // 检查是否全部大写9 if (word.equals(word.toUpperCase())) {10 return true;11 }12
13 // 检查是否全部小写14 if (word.equals(word.toLowerCase())) {15 return true;16 }17
18 // 检查是否只有首字母大写19 if (Character.isUpperCase(word.charAt(0)) &&20 word.substring(1).equals(word.substring(1).toLowerCase())) {21 return true;22 }23
24 // 如果都不符合,返回 false25 return false;26 }27}
- 时间复杂度: O(n),其中 n 是字符串的长度。
- 空间复杂度: O(n),主要来自于字符串操作
toUpperCase()
和toLowerCase()

519. 随机翻转矩阵
Ideas
1: 初始化和数据表示
- 使用一个字典
map
记录已经翻转的坐标(避免使用额外的二维数组)。 - 使用一个变量
total
记录剩余可翻转的位置数量。
2: 执行 flip
操作
- 使用随机数生成器在剩余可翻转的位置中选取一个随机下标
x
。 - 判断下标
x
是否已经被翻转过:- 如果已被翻转,使用映射字典找到当前
x
实际对应的位置。
- 如果已被翻转,使用映射字典找到当前
- 更新映射字典,将当前
x
位置映射到末尾(减少多次随机选择重复位置)。 - 返回二维矩阵中的对应坐标
[i, j]
。
3: 重置操作
- 清空映射字典,并将
total
重置为m * n
。
1class Solution {2
3 private int m, n, total;4 private Map<Integer, Integer> map;5 private Random rand;6
7 public Solution(int m, int n) {8 this.m = m;9 this.n = n;10 this.total = m * n;11 this.map = new HashMap<>();12 this.rand = new Random();13 }14
15 public int[] flip() {16
17 int x = rand.nextInt(total);18 total--;19
20 // 查找 x 是否已经映射21 int idx = map.getOrDefault(x, x);22 // 将 x 映射到总计数末尾23 map.put(x, map.getOrDefault(total, total));24
25 // 计算出二维矩阵的坐标26 return new int[]{idx / n, idx % n};27 }28
29 public void reset() {30 map.clear();31 total = m * n;32 }33}34
35/**36 * Your Solution object will be instantiated and called as such:37 * Solution obj = new Solution(m, n);38 * int[] param_1 = obj.flip();39 * obj.reset();40 */

2024-06-21
LCP 61. 气温变化趋势
Ideas
-
计算气温变化趋势:对于每个地区,计算每一天与下一天的气温变化趋势。我们可以用一个数组来存储这些变化趋势。
-
比较两个地区的气温变化趋势:遍历两个变化趋势数组,找到连续相同的最大天数。
1public class Solution {2
3 /**4 * 计算两个地区气温变化趋势相同的最大连续天数5 *6 * @param temperatureA 地区A的气温数组7 * @param temperatureB 地区B的气温数组8 * @return 两地气温变化趋势相同的最大连续天数9 */10 public int temperatureTrend(int[] temperatureA, int[] temperatureB) {11 int maxLength = 0; // 最大连续天数12 int currentLength = 0; // 当前连续天数13
14 // 遍历两个温度数组15 for (int i = 0; i < temperatureA.length - 1; i++) {16 // 计算第i天和第i+1天之间的气温变化趋势17 int trendA = getTrends(temperatureA[i], temperatureA[i + 1]);18 int trendB = getTrends(temperatureB[i], temperatureB[i + 1]);19
20 // 如果两个地区的气温变化趋势相同21 if (trendA == trendB) {22 currentLength++; // 当前连续天数加123 maxLength = Math.max(maxLength, currentLength); // 更新最大连续天数24 } else {25 currentLength = 0; // 重置当前连续天数26 }27 }28
29 return maxLength; // 返回最大连续天数30 }31
32 /**33 * 计算两个温度之间的变化趋势34 *35 * @param A 第一天的气温36 * @param B 第二天的气温37 * @return 变化趋势:0表示平稳,-1表示下降,1表示上升38 */39 private int getTrends(int A, int B) {40 if (A == B) {41 return 0; // 平稳趋势42 }43 return A < B ? -1 : 1; // 上升趋势或下降趋势44 }45
46 public static void main(String[] args) {47 Solution solution = new Solution();48 int[] temperatureA = {21, 18, 18, 18, 31}; // 地区A的气温数组49 int[] temperatureB = {34, 32, 16, 16, 17}; // 地区B的气温数组50
51 // 输出两地气温变化趋势相同的最大连续天数52 System.out.println(solution.temperatureTrend(temperatureA, temperatureB)); // 输出:253 }54}

思考
随着不断深入学习,发现算法才是代码的唯一解,或者说是他的最优解。从而我开始逐步的进行力扣的刷题之路。
随着公司压力的逐渐增大,我所承担的任务在难度和复杂度上都明显高于同组其他任务。然而,我并未获得应有的激励
和奖励
,这让我开始思考这份工作的付出与收益是否值得,于是我开始有了以快速提升自己从而得到更高的回报的内容。
评论