力扣笔记_v2

这篇文章主要是记录刷过的题以及里面一些需要注意的关键点(https://www.programmercarl.com/)

1.做题记录

序号	题目	日期	类型	链接
1	1732. 找到最高海拔	2024年10月25日	数组	https://leetcode.cn/problems/find-the-highest-altitude/description/?envType=study-plan-v2&envId=leetcode-75
2	933. 最近的请求次数	2024年10月25日	链表	https://leetcode.cn/problems/number-of-recent-calls/description/?envType=study-plan-v2&envId=leetcode-75
3	374. 猜数字大小	2024年10月25日	数学	https://leetcode.cn/problems/guess-number-higher-or-lower/description/?envType=study-plan-v2&envId=leetcode-75
4	1768. 交替合并字符串	2024年10月25日	字符串	https://leetcode.cn/problems/merge-strings-alternately/description/?envType=study-plan-v2&envId=leetcode-75
5	1161. 最大层内元素和	2024年10月25日	二叉树	https://leetcode.cn/problems/maximum-level-sum-of-a-binary-tree/description/?envType=study-plan-v2&envId=leetcode-75
6	215. 数组中的第K个最大元素	2024年10月25日	数组	https://leetcode.cn/problems/kth-largest-element-in-an-array/description/?envType=study-plan-v2&envId=leetcode-75
7	1679. K 和数对的最大数目	2024年10月26日	哈希表	https://leetcode.cn/problems/max-number-of-k-sum-pairs/description/?envType=study-plan-v2&envId=leetcode-75
8	735. 小行星碰撞	2024年10月26日	栈与队列	https://leetcode.cn/problems/asteroid-collision/description/?envType=study-plan-v2&envId=leetcode-75
9	1071. 字符串的最大公因子	2024年10月27日	数学	https://leetcode.cn/problems/greatest-common-divisor-of-strings/description/?envType=study-plan-v2&envId=leetcode-75
10	2095. 删除链表的中间节点	2024年10月28日	链表	https://leetcode.cn/problems/delete-the-middle-node-of-a-linked-list/description/?envType=study-plan-v2&envId=leetcode-75
11	69. x 的平方根	2024年11月1日	数学	https://leetcode.cn/problems/sqrtx/description/?envType=study-plan-v2&envId=2024-spring-sprint-100
12	LCR 003. 比特位计数	2024年11月2日	动态规划	https://leetcode.cn/problems/w3tCBm/description/?envType=study-plan-v2&envId=coding-interviews-special
13	387. 字符串中的第一个唯一字符	2024年11月3日	字符串	https://leetcode.cn/problems/first-unique-character-in-a-string/description/?envType=study-plan-v2&envId=2024-spring-sprint-100
14	125. 验证回文串	2024年11月3日	字符串	https://leetcode.cn/problems/valid-palindrome/description/?envType=study-plan-v2&envId=2024-spring-sprint-100
15	88. 合并两个有序数组	2024年11月4日	数组	https://leetcode.cn/problems/merge-sorted-array/description/?envType=study-plan-v2&envId=2024-spring-sprint-100
16	100. 相同的树	2024年11月7日	二叉树	https://leetcode.cn/problems/same-tree/description/?envType=study-plan-v2&envId=2024-spring-sprint-100
17	50. Pow(x, n)	2024年11月7日	数学	https://leetcode.cn/problems/powx-n/description/?envType=study-plan-v2&envId=2024-spring-sprint-100
18	204. 计数质数	2024年11月8日	数学	https://leetcode.cn/problems/count-primes/description/?envType=study-plan-v2&envId=2024-spring-sprint-100
19	268. 丢失的数字	2024年11月8日	数学	https://leetcode.cn/problems/missing-number/description/?envType=study-plan-v2&envId=2024-spring-sprint-100
20	1979. 找出数组的最大公约数	2024年11月9日	数学	https://leetcode.cn/problems/find-greatest-common-divisor-of-array/description/?envType=study-plan-v2&envId=2024-spring-sprint-100
21	61. 旋转链表	2024年11月9日	链表	https://leetcode.cn/problems/rotate-list/description/?envType=study-plan-v2&envId=2024-spring-sprint-100
22	82. 删除排序链表中的重复元素 II	2024年11月9日	链表	https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/description/?envType=study-plan-v2&envId=2024-spring-sprint-100
23	219. 存在重复元素 II	2024年11月11日	数组	https://leetcode.cn/problems/contains-duplicate-ii/description/?envType=study-plan-v2&envId=2024-spring-sprint-100
24	658. 找到 K 个最接近的元素	2024年11月12日	数组	https://leetcode.cn/problems/find-k-closest-elements/description/?envType=study-plan-v2&envId=2024-spring-sprint-100
25	264. 丑数 II	2024年11月13日	动态规划	https://leetcode.cn/problems/ugly-number-ii/description/?envType=study-plan-v2&envId=2024-spring-sprint-100
26	98. 所有可达路径	2024年11月25日	图论	https://kamacoder.com/problempage.php?pid=1170
27	397. 整数替换	2024年11月29日	数学	https://leetcode.cn/problems/integer-replacement/description/
28
29
30
31
32
33

2.一些java用法

数组

215. 数组中的第K个最大元素

借用快排的思路即可

3.做题笔记

数组

1732. 找到最高海拔

i位置的真正海拔等于gain[0到i]的sum加和

88. 合并两个有序数组

把nums1当中的前m个数字串到最后再合并即可（注意是倒序）

219. 存在重复元素 II

这个问题是滑动窗口问题

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        // 1.暴力解法
        int len = nums.length;
        for (int left = 0; left < len; left++) {
            for (int right = left + 1; right <= left + k && right < len; right++) {
                if (nums[left] == nums[right]) {
                    return true;
                }
            }
        }
        return false;

        // 2.可以通过哈希记录当前窗口的值，其中i表示窗口的右侧
        int len = nums.length;
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < len; i++) {
            if (set.contains(nums[i])) {
                return true;
            } else {
                set.add(nums[i]);
            }
            if (i - k >= 0) {
                set.remove(nums[i - k]);
            }
        }
        return false;
    }
}

658. 找到 K 个最接近的元素

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        // 先二分查找到x应该在的位置，然后以这个位置为中心展开成长度为k的滑动窗口
        int index = search(arr, x);
        int len = arr.length;
        int left = index + 1, right = index - 1;
        while (left - 1 >= 0 && right + 1 < len && right - left + 1 < k) {
            if (x - arr[left - 1] <= arr[right + 1] - x) {
                left--;
            } else {
                right++;
            }
        }
        if (left == 0) {
            right = k - 1 + left;
        } else if (right == len - 1) {
            left = -k + 1 + right;
        }
        
        List<Integer> result = new LinkedList<>();
        for (int i = left; i <= right; i++) {
            result.add(arr[i]);
        }
        return result;
    }

    public int search(int[] arr, int x) {
        int left = 0;
        int right = arr.length - 1;
        while (left < right) {
            int mid = (right - left) / 2 + left;
            if (arr[mid] == x) {
                return mid;
            } else if (arr[mid] > x) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

链表

933. 最近的请求次数

为了减少遍历时间，可以让list只存储符合当前时间的时间戳

注意不能使用以下方式删除元素，因为for遍历过程当中，需要验证对list修改次数不变才能继续遍历

for (Integer i : log) {
	if (i < t - 3000) {
		log.remove(i);
	}
}

2095. 删除链表的中间节点

快慢指针即可

61. 旋转链表

找到倒数第k%length个位置即可

82. 删除排序链表中的重复元素 II

注意：头结点可能被删除，所以需要构造一个假头结点开始遍历

哈希表

1679. K 和数对的最大数目

使用哈希表记录元素出现的次数即可

字符串

1768. 交替合并字符串

可以使用StringBuilder构造字符串，更加方便

387. 字符串中的第一个唯一字符

使用数组记录每一个字母的出现次数即可

125. 验证回文串

注意把大写字母转化成小写字母的两种方式即可：

originalString.toLowerCase();
Character.toLowerCase(c);

注意：如果是以下的形式，会得到ASCII码

c - ‘A‘ + ’a’

动态规划

LCR 003. 比特位计数

1.dp[i]是指数字i的1的个数

2.dp[i]=dp[i-t]+1，t是2^(当前位数)，例如dp[7]=dp[3]+1

3.dp[0]=0,t=1

4.i从小到大

264. 丑数 II

class Solution {
    public int nthUglyNumber(int n) {
        // 1.dp[i]表示第i个丑数
        // 2.dp[i]=min(dp[p2]*2,dp[p3]*3,dp[p5]*5)
        // 3.dp[0]=1
        // 4.i从小到大
        int[] dp = new int[n];
        dp[0] = 1;
        int p2 = 0, p3 = 0, p5 = 0;
        for (int i = 1; i < n; i++) {
            dp[i] = Math.min(Math.min(dp[p2] * 2, dp[p3] * 3), dp[p5] * 5);
            // 注意以下三个if的判断不能写成else，因为严格要求每一个dp[i]都不能重复
            if (dp[i] == dp[p2] * 2) {
                p2++;
            }
            if (dp[i] == dp[p3] * 3) {
                p3++;
            }
            if (dp[i] == dp[p5] * 5) {
                p5++;
            }
        }
        return dp[n - 1];
    }
}

栈与队列

735. 小行星碰撞

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        Stack<Integer> stack = new Stack<>();
        for (int asteroid : asteroids) {
            boolean valid = true;
            while (!stack.isEmpty() && asteroid < 0 && stack.peek() > 0 && valid) {
                valid = Math.abs(asteroid) > Math.abs(stack.peek());
                if (Math.abs(asteroid) >= Math.abs(stack.peek())) {
                    stack.pop();
                }
            }
            if (valid) {
                stack.push(asteroid);
            }
        }

        int[] result = new int[stack.size()];
        for (int i = result.length - 1; i >= 0; i--) {
            result[i] = stack.pop();
            System.out.println(result[i]);
        }
        return result;
    }
}

贪心算法

回溯算法

数学

374. 猜数字大小

二分查找即可

1071. 字符串的最大公因子

class Solution {
    public String gcdOfStrings(String str1, String str2) {
        // 寻找str1和str2长度的最大公因数n，检查str1和str2是否为该n长度的子串拼接而成的
        int n = this.gcd(str1.length(), str2.length());
        String result = str1.substring(0, n);
        String newString1 = result.repeat(str1.length() / n);
        String newString2 = result.repeat(str2.length() / n);
        if (newString1.equals(str1) && newString2.equals(str2)) {
            return result;
        } else {
            return "";
        }
    }

    // 使用辗转相除法求取最大公因数
    // 567 / 405 = 1 (余162)
    // 405 / 162 = 2（余81）
    // 162 / 81 = 2（余0）
    public int gcd(int a, int b) {
        int c;
        if (a > b) {
            c = a % b;
        } else {
            c = b % a;
        }
        while (c != 0) {
            a = b;
            b = c;
            c = a % b;
        }
        return Math.min(a, b);
    }
}

69. x 的平方根

class Solution {
    public int mySqrt(int x) {
        return search(x);
    }

    public int search(int x) {
        if (x == 0 || x == 1) {
            return x;
        }
        int begin = 0;
        int end = x;
        int result = 0;
        while (begin <= end) {
            int mid = (end - begin) / 2 + begin;
            // 以下两种方法都可以
            // if ((long) mid * mid <= x) {
            if (mid <= x / mid) {
                result = mid;
                begin = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return result;
    }
}

50. Pow(x, n)

用递归的思想即可，注意：这个方法超时了

int half = n / 2;
return my(x, half) * my(x, n - half);

需要减少运算my(x, half)的时间

double result = my(x, n / 2);
return n % 2 == 0 ? result * result : result * result * x;

204. 计数质数

如果一个数字x是质数，那么2x，3x，，一定是合数。

为了简化时间复杂度：可以从x*x开始赋值，因为在考虑到x之前，遇到2的时候就已经把2x赋值过了

268. 丢失的数字

把问题转化成：所有数字nums和0-n当中，有一个数字只出现了1次，把这个数字找出来。因此，把nums[i]和0-i异或一遍即可

1979. 找出数组的最大公约数

辗转相除法即可

397. 整数替换

class Solution {
    public int integerReplacement(int n) {
        // 法一：动态规划，超时
        // 1.dp[i]表示替换成i位置，所需的最小替换次数
        // 2.i是偶数：dp[i]=dp[i/2]+1
        // i是奇数：dp[i]=min(dp[(i-1)/2],dp[(i+1)/2])+2
        // 3.dp[1]=0
        // 4.i正向
        int[] dp = new int[n + 1];
        dp[1] = 0;
        for (int i = 2; i < n + 1;) {
            dp[i] = dp[i / 2] + 1;
            i++;
            if (i < n + 1) {
                int x = (i - 1) / 2, y = (i + 1) / 2;
                dp[i] = Math.min(dp[x], dp[y]) + 2;
                i++;
            }
        }
        return dp[n];
        // 法二：递归
        Map<Integer, Integer> map = new HashMap<>();
        if (n == 1) {
            return 0;
        }
        if (!map.containsKey(n)) {
            if (n % 2 == 0) {
                map.put(n, integerReplacement(n / 2) + 1);
            } else {
                map.put(n, Math.min(integerReplacement(n / 2), integerReplacement(n / 2 + 1)) + 2);
            }
        }
        return map.get(n);
    }
}

单调栈

二叉树

1161. 最大层内元素和

层序遍历即可

100. 相同的树

前序遍历即可

图论

相关知识

连通性

连通图：无向图当中，任何两个节点都是可以到达的

连通分量：无向图当中的极大连通子图

强连通图：有向图中，任何两个节点是可以相互到达的

强连通分量：有向图当中的极大强连通子图

表示方法

1.邻接矩阵： 二维数组

grid[2] [5] = 6，表示节点2 指向 节点5，边的权值为6

2.邻接表：数组 + 链表

描述的图是：

节点1 指向 节点3、节点5；节点2 指向 节点4、节点3、节点5；节点3 指向 节点4；节点4 指向 节点1

深搜 & 宽搜

深搜先按照一个方向搜索下去，如果碰壁就回溯，其框架和回溯基本一致：

void dfs(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本节点所连接的其他节点) {
        处理节点;
        dfs(图，选择的节点); // 递归
        回溯，撤销处理结果
    }
}

回顾一下回溯的框架：

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }
    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

宽搜：

98. 所有可达路径

import java.util.*;

public class Main {
    static List<List<Integer>> result = new LinkedList<>();
    static List<Integer> path = new LinkedList<>();

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(), m = scan.nextInt();
        // 邻接表
        List<Integer>[] graph = new List[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new LinkedList<>();
        }
        while (scan.hasNext()) {
            int x = scan.nextInt();
            int y = scan.nextInt();
            // 把节点的1到n编号改成0到n-1
            graph[x - 1].add(y - 1);
        }
        int[] used = new int[n];
        path.add(0);
        dfs(used, 0, n, graph);
        if (result.size() == 0) {
            System.out.println(-1);
        }
        for (List<Integer> p : result) {
            StringBuilder sb = new StringBuilder();
            sb.append(p.get(0) + 1);
            for (int i = 1; i < p.size(); i++) {
                sb.append(" " + (p.get(i) + 1));
            }
            System.out.println(sb);
        }
    }

    // 查看x节点的邻接节点，used表示当前所有节点是否遍历
    public static void dfs(int[] used, int x, int n, List<Integer>[] graph) {
        if (x == n - 1) {
            result.add(new LinkedList<>(path));
            return;
        }
        for (int i = 0; i < graph[x].size(); i++) {
            int y = graph[x].get(i);
            if (used[y] == 0) {
                used[y] = 1;
                path.add(y);
                dfs(used, y, n, graph);
                // path.removeLast();
                path.remove(path.size() - 1);
                used[y] = 0;
            }
        }
    }
}