LeetCode中常用技巧
LeetCode
1. 递归
递归要素：
- 参数中要有操作的数组或集合，以及目标。
- 结束条件，结束的判断需要由其它参数参与确定。
- 根据实际情况方法是否有返回。
2. 动态规划
动态规划要素：
- 创建一个(n+1)的数组来存放规划值。
- 数组第一个需要虚拟赋值，一般为0或false等。
- 由数组的最后一个或最后几个确定结果。
2.1 LeetCode198. 打家劫舍
创建一个长于数组的数组，用来存放每一次计算的结果，而每一次的计算又是从第一个到当前的最佳结果，一直重复到结束。
public int rob(int[] nums) {int result = 0;int length = nums.length;if (length == 1) {result = nums[0];} else if (length == 2) {result = Math.max(nums[0], nums[1]);} else if (length > 2) {int[] dp = new int[length + 1];dp[0] = 0;dp[1] = nums[0];dp[2] = nums[1];for (int i = 3; i <= length; i++) {// 动态规划(dynamic programming), 妙 啊！dp[i] = Math.max(dp[i - 2], dp[i - 3]) + nums[i - 1];}result = Math.max(dp[length], dp[length - 1]);}return result;}
2.2 LeetCode139. 单词拆分
/*** 动态规划 (dynamic programming)* 以示例1为例，s为"leetcode"，wordDict为{"leet", "code"}* dp数组为[true, false, false, false, true, false, false, false, true]*/public static boolean wordBreak(String s, List<String> wordDict) {HashSet<String> wordSet = new HashSet<>(wordDict); // 去除词典重复项int length = s.length();boolean[] dp = new boolean[length + 1];dp[0] = true;for (int i = 1; i <= length; i++) {for (int j = 0; j < i; j++) {if (dp[j] && wordSet.contains(s.substring(j, i))) {dp[i] = true;break;}}}return dp[length];}
3. 队列
3.1 优先队列 (PriorityQueue) 重排序
实例化示例：
// 需要指定队列中存储的对象类型，如下为Integer。
// 可以指定初始容量，initialCapacity。
// 可以指定排序规则，如下为从小到大排序。
PriorityQueue<Integer> queueMin = new PriorityQueue<Integer>(new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return (o1 < o2) ? 1 : ((o1 == o2) ? 0 : -1);}});
| 常用方法 | 描述 | 返回 | 参数 |
|---|---|---|---|
| size() | 获取队列大小 | int：队列中元素的个数 | |
| isEmpty() | 队列是否为空 | boolean：元素的个数是否为0，size()==0 | |
| offer(E e) | 向队列中添加元素，自动排在最末尾 | boolean：是否添加成功 | 要添加的元素 |
| peek() | 获取最后位置的元素，但实际是类中一个数组的第一个 | E：最后位置的元素 | |
| poll() | 弹出最后位置的元素，并且能得到此元素 | E：最后位置的元素 |
3.1 阻塞队列 (BlockingQueue) 重阻塞
实例化示例：
// 可以指定初始容量，initialCapacity。
// fair为阻塞时的策略，为true按队列先进先出的顺序处理元素，否则为未指定处理顺序。
BlockingQueue<CachedLocation> pendingLocations = new ArrayBlockingQueue<>(10000, true);
| 常用方法 | 描述 | 返回 | 参数 |
|---|---|---|---|
| size() | 获取队列大小，获取时会加锁，所以尽量少获取 | int：队列中元素的个数 | |
| isEmpty() | 队列是否为空，会使用size()，所以尽量少获取 | boolean：元素的个数是否为0，size()==0 | |
| offer(E e) | 向队列中添加元素，自动排在最末尾 | boolean：是否添加成功 | 要添加的元素 |
| drainTo(Collection c) | 从此队列中删除所有可用元素并将它们添加到给定集合 | int：传输的元素数 | 存放所有元素的集合 |
4. 前缀和
4.1 LeetCode437. 路径总和 III
前缀和结合二叉树TreeNode来使用。还使用Map来记录一些特殊值的次数。
public static void main(String[] arg0) {Object[] nums = {10, 5, -3, 3, 2, null, 11, 3, -2, null, 1};System.out.println("路径总和 = " + pathSum(new TreeNode(nums), 8));}public static int pathSum(TreeNode root, int targetSum) {Map<Integer, Integer> counts = new HashMap<>();// 这里设置0对应的值为1，这样如果第一个根节点就等于目标和，在递归中给res赋的值就是1，不需要再判断counts.put(0, 1);return childMethod(root, counts, 0, targetSum);}/*** 递归 + 前缀和*/public static int childMethod(TreeNode node, Map<Integer, Integer> counts, int currSum, int targetSum) {if (node == null || !node.isValidVal()) { // 递归到了最末端终止，并且返回0条符合条件路径return 0;}int res = 0;currSum += node.val;res = counts.getOrDefault(currSum - targetSum, 0); // 这里赋值不明白counts.put(currSum, counts.getOrDefault(currSum, 0) + 1); // 记录前缀和的次数res += childMethod(node.left, counts, currSum, targetSum);res += childMethod(node.right, counts, currSum, targetSum);counts.put(currSum, counts.getOrDefault(currSum, 0) - 1); // 检查完当前分支就要减少当前前缀和的次数return res;}
附：时间复杂度 和 空间复杂度
- 时间复杂度：假设单次操作的时间为单位时间，求出结果总共需要的大概次数。
- 递归的时间复杂度一般为n。- 动态规划的时间复杂度一般为n的平方。
- 空间复杂度：整个操作需要开辟的内存空间。
- 递归需要在栈上开辟空间。首次执行开辟一个空间，每次递归多开辟一个空间，最多递归多少次就是空间复杂度。- 动态规划需要创建一个(总长度+1)的数组来存放规划值，空间复杂度即为数组长度。
牛客
1. 对一个数组或者集合中的所有元素做全部组合
– 采用递归，而且递归中含有for循环
– 数组或集合数据要全局，判断标准要全局
– 新建两个全局的数组，大小要和源数据相同，一个记录选中下标，一个记录对应的值
– dfs递归两个参数，一个p记录当前赋值位置并且下次递归也可使用，一个count记录使用前几个数据
public static int[] data; // 源数据
public static int number; // 判断标准
public static int[] tempIndex; // 记录选中下标
public static int[] tempData; // 记录选中下标对应的数据{List<List<Integer>> ans = new ArrayList<>();dfs(0, 0, ans); // p 和 count 必须从0开始}// 递归方法，第三个参数是结果，其实也可以做成全局变量public static void dfs(int p, int count, List<List<Integer>> ans) {int total = 0;List<Integer> temp = new ArrayList<>();for (int i = 0; i < count; i++) {temp.add(tempData[i]);total += temp.get(i);if (total == number) {ans.add(temp);return; // 要根据判断标准来写，是否需要再增加count}if (total > number) {return; // 要根据判断标准来写，是否需要再增加count}}int i = 0;if (p - 1 >= 0 && tempIndex[p - 1] != -1) {i = tempIndex[p - 1] + 1;}for (; i < data.length; i++) {tempData[p] = data[i];tempIndex[p] = i;dfs(p + 1, count + 1, ans);}}
- 举个例子并列下递归的执行顺序，例如：
4, 3, 2, 1。- dfs for循环第一个
4，临时数据数组第一个位置为4， count也变成1，之后第二次递归又for循环， 临时数据数组第一个位置为3，count也变成2，得到4, 3，类推走完4, 3, 2，4, 3, 2, 1，4, 3, 1。- 之后第二次递归的for循环走下一个，也就是临时数据第二个位置是源数组第三个位置，得到
4, 2，再4, 2, 1结束。- 之后第二次递归的for循环走最后一个，得到
4, 1，整个第一个循环以4开头的就全部完成。- 接下来第一个循环以3开头，顺序
3，3, 2，3, 2, 1，3, 1。- 继续第一个循环以2开头，顺序为
2，2, 1。- 最后第一次循环只剩下
1。
2. 数组只能向上下左右感染的问题
– 先将上下左右的偏移数组列出来，循环用
– 需要有一个队列记录已感染位置，先进先处理的原则，并且处理后做标记已处理
– 用感染数增加到最后的值做判断得结论，或者有dp[]记录感染步骤得结论
static int[][] offsets = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};Queue<int[]> queue = new LinkedList<>();
queue.offer(p1);
queue.offer(p2);int count = m * n - 2; // 已经有两个作为扩散点了
int[][] dp = new int[m][n];
dp[p1[0]][p1[1]] = 1;
dp[p2[0]][p2[1]] = 1;int day = 1;
while (!queue.isEmpty() && count > 0) {int[] p = queue.poll(); // 弹出并获取到队列首部对象int x = p[0];int y = p[1];day = dp[x][y] + 1;for (int[] offset : offsets) {int newX = x + offset[0];int newY = y + offset[1];if (newX >= 0 && newX < m && newY >= 0 && newY < n && dp[newX][newY] == 0) {dp[newX][newY] = day;queue.offer(new int[]{newX, newY});count --;}}
}System.out.println(day - 1);
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！