原记录于2023-10-21(创建),目前提前至此于调整布局用
力扣算法题记录 s: simple m:middle h:hard
P88 合并两个有序数组 S 数组 思路一 先合并在排序 思路二 合并的时候就进行排序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public static void merge (int [] nums1, int m, int [] nums2, int n) { int index = 0 ; for (int i = m; i < nums1.length; i++) { nums1[i] = nums2[index++]; } Arrays.sort(nums1); }
P27 移除元素 S 数组 给你一个数组 nums
和一个值 val
,你需要 原地 移除所有数值等于 val
的元素,并返回移除后数组的新长度。
不要使用额外的数组空间,你必须仅使用 O(1)
额外空间并 原地 修改输入数组 。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
思路: 快慢差
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 public static int removeElement (int [] nums, int val) { int count = 0 ; for (int num : nums) { if (num != val) { nums[count++] = num; } } return count; }
P169 多数元素 S 数组 给定一个大小为 n
的数组 nums
,返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋
的元素
思路一 排序取中间(题目 进阶:尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题)
1 2 3 4 public static int majorityElement (int [] nums) { Arrays.sort(nums); return nums[nums.length >> 1 ] ; }
思路二 候选人正票数和负票数的抵消问题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 public static int majorityElement (int [] nums) { int candidate = nums[0 ]; int count = 1 ; for (int i = 1 ; i < nums.length; i++) { if (nums[i] == candidate) { count++; } else { count--; if (count == 0 ) { candidate = nums[i]; count = 1 ; } } } return candidate; }
双指针(技巧) 对于双指针, 用的最多的无非就是左右指针, 那么左右指针一般都有类似的解法
1 2 3 4 5 6 7 8 9 10 11 public static void template (int []nums) { int left=0 , right=nums.length-1 ; while (left < right){ if (){ left++; }else { right++; } } }
例如题P11 盛水最多的容器 就是左右指针, 其中还有一种为中间发散指针(从中间到两边)5. 最长回文子串 - 力扣(LeetCode)
P11 盛水最多的容器 M 数组 1 2 3 4 5 6 7 8 9 10 11 12 13 14 public int maxArea (int [] height) { int left = 0 , right = height.length - 1 ; int ans = 0 ; while (left < right) { int area = (right - left) * Math.min(height[right], height[left]); ans = Math.max(ans, area); if (height[left] < height[right]) { left++; } else { right--; } } return ans; }
模板都是类似固定的, 同样的模板模式还出现在二叉树
P125 验证回文串 S 字符串 对于该题的要点有:
需要跳过非字符的元素
通过Java的API Character.isLetterOrDigit 判断是字符还是数字(is: true not: false)
java.lang.Character.isLetterOrDigit(char ch) 这个方法确定指定的字符是否为字母或数字。字符被认为是字母或数字,如果字符是字母或数字则此方法返回true,否则为false
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 public boolean isPalindrome (String s) { int left = 0 , right = s.length() - 1 ; if (s == "" || s == null ) { return true ; } while (left < right) { while (left < right && !Character.isLetterOrDigit(s.charAt(left))) { left++; } while (left < right && !Character.isLetterOrDigit(s.charAt(right))) { right--; } if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) { return false ; } left++; right--; } return true ; }
可以看出来, 大体的模板是不动的, 唯一变化的就是中间, 当前案例由于需要俩头一起遍历并且跳过非字符, 那么需要一直判断(while)
然后学习新的API java.lang.Character.isLetterOrDigit(char ch)
1 2 3 4 5 6 7 8 9 10 11 public boolean isPalindrome (String s) { int left = 0 , right = s.length() - 1 ; while (left < right) { left++; right--; } return true ; }
P20 有效的括号 S 字符串 #栈 20. 有效的括号
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 public boolean isValid (String s) { if (s.length() % 2 == 1 ) return false ; Stack<Character> stack = new Stack <Character>(); char [] chars = s.toCharArray(); for (char item : chars) { if (item == '(' || item == '[' || item == '{' ) { stack.push(item); } else { if (stack.empty()) return false ; char top = stack.peek(); if ((top == '(' && item == ')' ) || (top == '[' && item == ']' ) || (top == '{' && item == '}' )) { stack.pop(); } else { return false ; } } } return stack.empty(); }
P26-80 删除有序数组中的重复项(I and II) S-M 数组 同类的两道题目, 这两个题目的快慢指针都是同类解法
26. 删除有序数组中的重复项(简单)
1 2 3 4 5 6 7 8 9 10 11 12 13 public int removeDuplicates (int [] nums) { int slow = 1 , fast = 1 ; while (fast < nums.length) { if (nums[slow - 1 ] == nums[fast]) { } else { nums[slow] = nums[fast]; slow++; } fast++; } return slow; }
80. 删除有序数组中的重复项 II (中等)
1 2 3 4 5 6 7 8 9 10 11 12 13 public int removeDuplicates (int [] nums) { int slow = 2 , fast = 2 ; while (fast < nums.length) { if (nums[slow - 2 ] == nums[fast]) { fast++; } else { nums[slow] = nums[fast]; fast++; slow++; } } return slow; }
可以看出来, 差距只有在指针判断的间隔上(对于判断不需要重复的情况那么指针间隔为1, 至多两个重复的情况则间隔为2)可参考 B站 两题的详细视频讲解
P392 判断子序列 S 字符串 P392 判断子序列
双指针
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public boolean isSubsequence (String s, String t) { int left = 0 , right = 0 ; if (s.length() == 0 ) return true ; if (t.length() == 0 ) return false ; while (right < t.length() && left < s.length()) { if (s.charAt(left) == t.charAt(right)) { left++; } right++; } return left >= s.length(); }
P21 合并两个有序链表 S 链表 合并两个有序链表
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 public ListNode mergeTwoLists (ListNode list1, ListNode list2) { if (list1 == null ) return list2; if (list2 == null ) return list1; ListNode ans = new ListNode (-1 ); ListNode margin = ans; while (list1 != null && list2 != null ) { if (list1.val < list2.val) { margin.next = list1; list1 = list1.next; } else { margin.next = list2; list2 = list2.next; } margin = margin.next; } if (list1 == null ) margin.next = list2; if (list2 == null ) margin.next = list1; return ans.next; }
对于上题,通过采用新链表+双指针,双指针判断两个链表,新链表用于构建答案
易踩坑:1. 在构建新链表时,不保存头节点而直接赋值,导致数据丢失(7-8行) 需要使用一个新的链表节点+另外一个指向新节点的节点变量,然后用于构建ans(错误案例:ListNode ans = new ListNode(-1); 只使用一个头节点进行操作,不进行头节点的保存引用)
对于循环内的赋值,需要使用赋值节点的下一个节点赋值,而不是他自己(错误案例:margin= list1;margin = margin.next;)
对于当前题:注意到还有一个收尾的操作,笔者在debug的时候发现最后一个节点被忽略了,因而才引入排尾阶段
P83 删除排序链表中的重复元素 S 链表 删除排序链表中的重复元素
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 public ListNode deleteDuplicates (ListNode head) { if (head == null ) return null ; ListNode slow = head; ListNode fast = head.next; while (fast != null ){ if (slow.val != fast.val){ slow.next = fast; slow = slow.next; } fast = fast.next; } if (slow != null ) slow.next = null ; return head; }
对于上述的两题(链表), 都有收尾操作
P160 相交链表 S 链表 #hash表(map) 160. 相交链表
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 public ListNode getIntersectionNode (ListNode headA, ListNode headB) { Map<ListNode, Integer> ans = new HashMap <>(); if (headA == null ) return null ; ListNode p = headA; while (p != null ) { ans.put(p, p.val); p = p.next; } ListNode b = headB; while (b != null ) { if (ans.containsKey(b)) return b; b = b.next; } return null ; }
P141 环形链表 S 链表 #hash表(set) 141. 环形链表
1 2 3 4 5 6 7 8 9 10 11 12 public boolean hasCycle (ListNode head) { ListNode t = head; HashSet<ListNode> set = new HashSet <>(); while (t != null ) { int leftLen = set.size(); set.add(t); int rightLen = set.size(); if (leftLen == rightLen) return true ; t = t.next; } return false ; }
Pxxx 返回倒数第 k 个节点 S 链表 #快慢 面试题 02.02. 返回倒数第 k 个节点
相同题:LCR 140. 训练计划 II - 力扣(LeetCode)
先让fast
走n
步,然后让 p1
和 p2
同时向前走,p1
走到链表末尾的空指针时前进了 n - k
步,p2
也从 head
开始前进了 n - k
步,停留在第 n - k + 1
个节点上,即恰好停链表的倒数第 k
个节点上
1 2 3 4 5 6 7 8 9 10 11 12 13 public ListNode kthToLast (ListNode head, int cnt) { ListNode fast = head; for (int i = 0 ; i < cnt; i++) { fast = fast.next; } ListNode slow = head; while (fast != null ){ slow = slow.next; fast = fast.next; } return slow; }
P19 删除链表的倒数第 N 个结点 M 链表 #快慢指针 #虚拟节点 19. 删除链表的倒数第 N 个结点
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 public ListNode removeNthFromEnd (ListNode head, int n) { ListNode dummy = new ListNode (-1 ); dummy.next = head; ListNode shoudDel = kthToLast(dummy, n + 1 ); shoudDel.next = shoudDel.next.next; return dummy.next; } public ListNode kthToLast (ListNode head, int cnt) { ListNode fast = head; for (int i = 0 ; i < cnt; i++) { fast = fast.next; } ListNode slow = head; while (fast != null ){ slow = slow.next; fast = fast.next; } return slow; }
P61 旋转链表 M 链表 #环形链表解法 #快慢指针 61. 旋转链表
给你一个链表的头节点 head
,旋转链表,将链表每个节点向右移动 k
个位置。
这个题很妙好吧,与前面的那个获取倒数第k个结合起来了。
首先我们拿到长度,然后拿到需要旋转的节点
例如题:1 - > 2 - > 3 - > 4 - > 5,我们需要旋转两个长度单位,此时结果应该为 4 - > 5 - > 1 - > 2 - > 3
1 2 3 4 第一步:size = 5,K=2 =>我们只需要拿到倒数第 s-k=3个位置的节点作为newHead即可 第二步: newT newH tail(指针位置) 样例: 1 - > 2 - > 3 - > 4 - > 5 第三步:tail连接头节点构成循环链表,然后newT的下一个指针断开
详细代码如下
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 class Solution { public ListNode rotateRight (ListNode head, int k) { if (head == null || k == 0 ) return head; ListNode tail = head; int size = 1 ; while (tail.next != null ) { size++; tail = tail.next; } k %= size; if (k == 0 ) return head; ListNode fast = getNode(head, size - k); ListNode newHead = fast.next; tail.next = head; fast.next = null ; return newHead; } public ListNode getNode (ListNode head, int k) { ListNode p = head; for (int i = 1 ; i < k && p != null ; i++) p = p.next; return p; } }
P2 两数相加 M 链表 #模拟进位 2. 两数相加
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 public ListNode addTwoNumbers (ListNode l1, ListNode l2) { ListNode p1 = l1, p2 = l2; ListNode dummyHead = new ListNode (-1 ); ListNode current = dummyHead; int carry = 0 ; while (p1 != null || p2 != null || carry != 0 ) { int sum = carry; if (p1 != null ) { sum += p1.val; p1 = p1.next; } if (p2 != null ) { sum += p2.val; p2 = p2.next; } carry = sum / 10 ; sum %= 10 ; current.next = new ListNode (sum); current = current.next; } return dummyHead.next; }
对于题目中的(1)(2)(3)出进行答疑:
(1)进位初始化全局变量
(2)对于上一次运算的进位在本次(即 本次是上一次的前一位:如目前是百位,那么上一次就是十位,那么此时进位是在百位操作的)
(3)每一次对于当前进位运算后,需要计算当前位进行运算后的进位值(结果0-1,)即是否影响下一位
P144 二叉树的前序遍历 S 二叉树 144. 二叉树的前序遍历
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 public List<Integer> preorderTraversal (TreeNode root) { List<Integer> ans = new ArrayList <>(); middle(root, ans); return ans; } private TreeNode middle (TreeNode node, List<Integer> res) { if (node == null ) { return null ; } else { res.add(node.val); middle(node.left, res); middle(node.right,res); } return null ; }
P145 二叉树的后序遍历 S 二叉树 145. 二叉树的后序遍历
1 2 3 4 5 6 7 8 9 10 11 12 13 14 public List<Integer> postorderTraversal (TreeNode root) { List<Integer> ans = new ArrayList <>(); func(root, ans); return ans; } private TreeNode func (TreeNode node, List<Integer> ans) { if (node==null ) return null ; else { func(node.left,ans); func(node.right,ans); ans.add(node.val); } return null ; }
二叉树(技巧) 对于二叉树来说,无非就是有两种拆分问题的方案,一个是遍历,一个是分解
二叉树解题的思维模式分两类:
1、是否可以通过遍历一遍二叉树得到答案 ?如果可以,用一个 traverse
函数配合外部变量来实现,这叫「遍历」的思维模式。
2、是否可以定义一个递归函数,通过子问题(子树)的答案推导出原问题的答案 ?如果可以,写出这个递归函数的定义,并充分利用这个函数的返回值,这叫「分解问题」的思维模式。
无论使用哪种思维模式,你都需要思考:
如果单独抽出一个二叉树节点,它需要做什么事情?需要在什么时候(前/中/后序位置)做 ?其他的节点不用你操心,递归函数会帮你在所有节点上执行相同的操作。
这是一个链接
那么我们以226. 翻转二叉树 - 力扣(LeetCode) 为例
遍历 常规写法
1 2 3 4 5 6 7 8 9 10 11 12 public TreeNode invertTree (TreeNode root) { if (root == null ) return null ; TreeNode t = root.left; root.left = root.right; root.right = t; invertTree(root.left); invertTree(root.right); return root; }
分解 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public TreeNode invertTree (TreeNode root) { if (root == null ) return null ; TreeNode left = invertTree(root.left); TreeNode right = invertTree(root.right); root.left = right; root.right = left; return root; }
这种「分解问题」的思路,核心在于你要给递归函数一个合适的定义,然后用函数的定义来解释你的代码;
小结 二叉树解题的思维模式分两类:
1、是否可以通过遍历一遍二叉树得到答案 ?如果可以,用一个 traverse
函数配合外部变量来实现,这叫「遍历」的思维模式。
2、是否可以定义一个递归函数,通过子问题(子树)的答案推导出原问题的答案 ?如果可以,写出这个递归函数的定义,并充分利用这个函数的返回值,这叫「分解问题」的思维模式。
无论使用哪种思维模式,你都需要思考:
如果单独抽出一个二叉树节点,它需要做什么事情?需要在什么时候(前/中/后序位置)做 ?其他的节点不用你操心,递归函数会帮你在所有节点上执行相同的操作。
P128 最长连续序列 M 哈希表 128. 最长连续序列
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 public int longestConsecutive (int [] nums) { if (nums.length <= 1 ) return nums.length; HashSet<Integer> set = new HashSet <>(); for (Integer num : nums) { set.add(num); } int ans = 0 ; for (Integer item : set) { int curAns = 1 , curNum = item; if (!set.contains(item - 1 )) { while (set.contains(curNum + 1 )) { curNum++; curAns++; } } ans = Math.max(ans, curAns); } return ans; }
P71 简化路径 M 栈 71. 简化路径
1 2 3 Linux下的路径 输入:path = "/a/./b/../../c/" 输出:"/c"
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 public static String simplifyPath (String path) { Stack<String> stack = new Stack <>(); String[] split = path.split("/" ); for (String part : split) { if (part.isEmpty() || part.equals("." )) continue ; else if (part.equals(".." )) { if (!stack.empty()) stack.pop(); } else stack.push(part); } StringBuilder sb = new StringBuilder (); for (String s : stack) sb.append("/" ).append(s); if (sb.length() == 0 ) return "/" ; return sb.toString(); }
其实很好理解,如果遇到.
则什么都不做处理,如果遇到..
那么则需要出栈
当然此题还可以使用队列去实现,笔者最开始就是使用的队列,如果遇到上述的相同情况则出入队列,原理一致(Queue)
P150 逆波兰表达式求值 M 栈 150. 逆波兰表达式求值
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 public int evalRPN (String[] tokens) { Stack<Integer> stack = new Stack <>(); for (String token : tokens) { if ("+" .equals(token) || "-" .equals(token) || "*" .equals(token) || "/" .equals(token)) { Integer left = stack.pop(); Integer right = stack.pop(); switch (token) { case "+" : stack.push(left + right); break ; case "*" : stack.push(left * right); break ; case "-" : stack.push(right - left); break ; case "/" : stack.push(right / left); break ; } } else { stack.push(Integer.parseInt(token)); } } return stack.peek(); }
其实这个题和上面那个题很像
场景题 除了算法题还有场景题欧
分金条问题 问题描述:雇1个人工作7天,你有1根金条可以分成7份,只能切2刀 ,如何保证每天都得到1份金条
我们首先,把金条看出七份,然后我们我们切两刀(1/7,2/7,4/7)那么可以看成一个线段从1/7处和3/7处切了(切金条CSDN )
然后七天的话: 第一天给工人 1/7,那么我们还有(剩2/7 + 4/7 = 6/7 )
第二天:我们给他2/7,然后他返回第一天我们给他的1/7(剩1/7 + 4/7 = 5/7 )
第三天:我们给他第二天要回的1/7,此时我们(剩4/7 )
第四天:要回所有的金条(3/7),我们给他我们剩的4/7. (剩1/7 + 2/7 = 3/7 )
第五天:给他1/7。我们(剩2/7 )
第六天:要回1/7,然后给剩下的2/7。(剩1/7 )
第七天:给他1/7。我们(剩0 )