慢刷Leetcode算法题

|
#leetcode
最后更新于


预计 11 min read


2024-06-24

Ideas

  • mergeTrees方法:
    • 如果 root1root2null,直接返回另一棵树。
    • 否则,先将 root1root2 对应节点的值相加,并将结果存储在 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
*/
16
class 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
}
result
result

503. 下一个更大元素 II

Ideas

  1. 初始化
    • 创建一个 result 数组,初始值全部设为 -1,表示如果某个元素没有找到下一个更大元素,则默认值为 -1
    • 创建一个栈 stack 用于存储元素的索引。
  2. 遍历数组
    • 使用 for 循环遍历 2 * n 次,利用 i % n 模拟循环数组。
    • 每次从 nums 数组中取出当前元素 num
  3. 更新结果数组
    • 使用 while 循环,当栈不为空且当前元素 num 大于栈顶元素对应的元素时,更新结果数组中栈顶元素对应的下一个更大元素为当前元素,并弹出栈顶。
  4. 压入栈
    • 如果当前索引 i 小于数组长度 n,则将当前索引压入栈中。
1
class 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
}
result
result

2024-06-23

456. 132 模式

Ideas

  1. 初始化一个空栈和一个 third 变量为 Integer.MIN_VALUE
  2. 从后往前遍历数组:
    • 如果 nums[i] < third,说明存在 132 模式的子序列,返回 true
    • 如果 nums[i] > stack.peek(),不断弹出栈顶元素并更新 third,直到栈顶元素不再小于当前元素。
    • 将当前元素压入栈。
  3. 如果遍历完数组后没有找到符合条件的子序列,返回 false
1
class 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
}
result
result
  • 时间复杂度: O(n)。每个元素最多被压入和弹出栈一次,因此总时间复杂度是线性的。
  • 空间复杂度: O(n)。在最坏情况下(严格递增的序列),栈需要存储所有的元素。

520. 检测大写字母

Ideas

  1. 首先检查单词是否为空或只有一个字符,如果是,直接返回 true

  2. 使用 equals 方法检查整个单词是否全部大写或全部小写。

  3. 使用 Character.isUpperCase 方法检查首字母是否大写,然后使用 substringequals 方法检查剩余部分是否全部小写。

  4. 如果都不符合,返回 false

java
1
class Solution {
2
public boolean detectCapitalUse(String word) {
3
// 如果单词为空或只有一个字符,直接返回 true
4
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
// 如果都不符合,返回 false
25
return false;
26
}
27
}
  • 时间复杂度: O(n),其中 n 是字符串的长度。
  • 空间复杂度: O(n),主要来自于字符串操作 toUpperCase()toLowerCase()
result
result

519. 随机翻转矩阵

Ideas

1: 初始化和数据表示

  • 使用一个字典 map 记录已经翻转的坐标(避免使用额外的二维数组)。
  • 使用一个变量 total 记录剩余可翻转的位置数量。

2: 执行 flip 操作

  • 使用随机数生成器在剩余可翻转的位置中选取一个随机下标 x
  • 判断下标x是否已经被翻转过:
    • 如果已被翻转,使用映射字典找到当前 x 实际对应的位置。
  • 更新映射字典,将当前 x 位置映射到末尾(减少多次随机选择重复位置)。
  • 返回二维矩阵中的对应坐标 [i, j]

3: 重置操作

  • 清空映射字典,并将 total 重置为 m * n
java
1
class 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
*/
result
result

2024-06-21

LCP 61. 气温变化趋势

Ideas

  • 计算气温变化趋势:对于每个地区,计算每一天与下一天的气温变化趋势。我们可以用一个数组来存储这些变化趋势。

  • 比较两个地区的气温变化趋势:遍历两个变化趋势数组,找到连续相同的最大天数。

java
1
public 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++; // 当前连续天数加1
23
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)); // 输出:2
53
}
54
}
result
result

思考

随着不断深入学习,发现算法才是代码的唯一解,或者说是他的最优解。从而我开始逐步的进行力扣的刷题之路。

随着公司压力的逐渐增大,我所承担的任务在难度和复杂度上都明显高于同组其他任务。然而,我并未获得应有的激励奖励,这让我开始思考这份工作的付出与收益是否值得,于是我开始有了以快速提升自己从而得到更高的回报的内容。

   
评论