我是靠谱客的博主 负责画笔,这篇文章主要介绍HOT100(一)2021.9月4日题解链接,现在分享给大家,希望可以做个参考。

2021.9月4日

题解链接

1. 两数之和

1.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
27
28
29
30
31
32
33
34
package Hot100; /** * @author : lkw * @data : 2021/9/4 9:47 * @description :暴力 * 时间复杂度O(n^2) **/ public class twoSum01_1 { public static void main(String[] args) { int[] nums={2,7,11,15}; int target = 9; int[] a=twoSum(nums,target); System.out.println(a.toString()); } public static int[] twoSum(int[] nums, int target){ int[] ans = new int[2]; for (int i = 0; i < nums.length-1; i++) { for (int j = i+1; j < nums.length; j++) { if (nums[i]+nums[j]==target){ ans[0]=i; ans[1]=j; } } } return ans; } }

1.2 hash表(推荐)

复制代码
1
2
3
4
5
6
7
8
9
10
11
//map<key,value>放的是<值,在nums的下标> public static int[] twoSum(int[] nums, int target){ Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { if (map.containsKey(target-nums[i])){ return new int[] {map.get(target-nums[i]),i}; } map.put(nums[i],i); } return new int[0];

2. 两数相加

2.1 三个样例未通过,超过long长度)

下次要看清题目的位数,

long long的最大值:9223372036854775807(19位)

long long的最小值:-9223372036854775808

复制代码
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
public static ListNode addTwoNumbers(ListNode l1, ListNode l2) { //l1 = [2,4,3], l2 = [5,6,4] StringBuffer str1 = new StringBuffer(); StringBuffer str2 = new StringBuffer(); while (l1!=null){ str1.insert(0,l1.val); // str1.append(l1.val); l1=l1.next; } while (l2!=null){ str2.insert(0,l2.val); // str2.append(l2.val); l2=l2.next; } long num=Long.parseLong(str1.toString())+Long.parseLong(str2.toString()); String num1=String.valueOf(num); char n=num1.charAt(0);//char型输出的是ASCII码54 //首节点 ListNode node = new ListNode(num1.charAt(num1.length()-1)-'0'); ListNode nextNode; nextNode=node; for (int i = num1.length()-2; i >= 0; i--) { ListNode newNode=new ListNode(num1.charAt(i)-'0'); nextNode.next=newNode; nextNode=nextNode.next; } return node; }

2.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
32
33
34
35
36
37
38
39
40
41
package Hot100; import Hot100.addTwoNumbers02_1.ListNode; /** * @author : lkw * @data : 2021/9/4 20:12 * @description :有进位的 **/ public class addTwoNumbers02_2 { public static ListNode addTwoNumbers(ListNode l1,ListNode l2) { //l1 = [2,4,3], l2 = [5,6] //3->4->2->null + 6->5 ListNode pre=new ListNode(0);//l3为起始指针的前一个 ListNode nextNode=pre; int carry =0;//进位 while (l1!=null || l2!=null){ int x= l1!=null ? l1.val: 0;//位数不够补零进行计算 int y= l2!=null ? l2.val: 0; int num = x+y+carry; int curNum=num%10;//当前位 carry=num/10;//进位 nextNode.next=new ListNode(curNum); nextNode=nextNode.next; if(l1!=null){ l1=l1.next; } if(l2!=null){ l2=l2.next; } } //如果最后有进位,则在最前面添加1 if (carry==1) { nextNode.next=new ListNode(carry); } return pre.next; } }

9月5日

3. 无重复字符的最长子串

3.1 循环两次,记录从每个元素开始的最长子串长度

时间复杂度O(n^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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
package Hot100; import java.util.HashMap; import java.util.HashSet; import java.util.Set; /** * @author : lkw * @data : 2021/9/5 10:24 * @description :3. 无重复字符的最长子串 * 新建一个数组,放从这个词往后的不重复的长度,最后取出数组中最大的值 * **/ public class lengthOfLongestSubstring3_01 { public static void main(String[] args) { String s = "pwwkew"; lengthOfLongestSubstring(s); } public static int lengthOfLongestSubstring(String s) { int max =0; int nums[]=new int[s.length()]; if (s=="") return 0; if (s.length()==1) return 1; if (s.length()>1){ for (int i = 0; i < s.length()-1; i++) { Set<String> set = new HashSet<>(); set.add(s.substring(i,i+1)); int j; for (j = i+1; j <s.length() ; j++) { String m=s.substring(j,j+1); if(!set.contains(m)){ set.add(m); }else {break;} } nums[i]=j-i; max =max>j-i ? max :j-i; } nums[s.length()-1]=1; } return max; } }

3.2 滑动窗口 

https://leetcode.cn/problems/longest-substring-without-repeating-characters/solution/hua-jie-suan-fa-3-wu-zhong-fu-zi-fu-de-zui-chang-z/

  1. start不动,end向后移动
  2. 当end遇到重复字符,start应该放在上一个重复字符的位置的后一位,同时记录最长的长度
  3. 怎样判断是否遇到重复字符,且怎么知道上一个重复字符的位置?--用哈希字典的key来判断是否重复,用value来记录该字符的下一个不重复的位置。

时间复杂度O(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
26
27
28
29
30
31
32
33
34
35
36
37
38
package Hot100; import java.util.HashMap; /** * @author : lkw * @data : 2021/9/5 11:13 * @description :可以不用循环两次, * map中存的是<值,值的位置>,如果有重复的值出现,重新定义窗口左侧,并且重写put新的位置 **/ public class lengthOfLongestSubstring3_02 { public static void main(String[] args) { String s = "au"; lengthOfLongestSubstring(s); } public static int lengthOfLongestSubstring(String s) { int max = 0; int left=0; char m; if (s == "") return 0; if (s.length() == 1) return 1; if (s.length() > 1) { HashMap<Character, Integer> map = new HashMap() ; for (int i = 0; i < s.length() ; i++) { m=s.charAt(i); if (map.containsKey(m)){ left=Math.max(left,map.get(m)+1); } map.put(m,i); max=Math.max(max,i-left+1); } } return max; } }

4. 寻找两个正序数组的中位数

4.1 合并数组,再找到中位数

时间复杂度:O(m+n)

空间复杂度:O(m+n)

 左边界下标是:(n-1)/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
32
33
34
35
36
37
38
39
40
package Hot100; /** * @author : lkw * @data : 2021/9/5 15:12 * @description :4. 寻找两个正序数组的中位数 * 先排序,找中位数 **/ public class findMedianSortedArrays4_01 { public static void main(String[] args) { int[] nums1 = {1,3}; int[] nums2 = {2}; findMedianSortedArrays(nums1,nums2); } public static double findMedianSortedArrays(int[] nums1, int[] nums2) { int[] num3= new int[nums1.length+nums2.length]; int i=0,j=0,n=0; while (i<nums1.length && j<nums2.length){ if (nums1[i]<nums2[j]){ num3[n++]=nums1[i++]; }else { num3[n++]=nums2[j++]; } } while (i<nums1.length){ num3[n++]=nums1[i++]; } while (j<nums2.length){ num3[n++]=nums2[j++]; } // 0 1 2 3 if ((n-1)%2==0){ return num3[(n-1)/2]; }else return (num3[(n-1)/2]+num3[(n-1)/2+1])/2.0; } }

9.7日

5. 最长回文子串

中心扩展算法

题解链接:力扣

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution { //从中间向两边比较好判断 public String longestPalindrome(String s) { int len=s.length(); String s1 = "", s2="",res=""; if (len<=1) return s; for (int i = 0; i < len; i++) { s1=Palindrome(s,i,i); s2=Palindrome(s,i,i+1); res=(res.length()>s2.length())?res:s2; res=(res.length()>s1.length())?res:s1; } return res; } private String Palindrome(String s, int left, int right) { //向两边延伸 while (left>=0 && right<s.length() && s.charAt(left)==s.charAt(right)){ left--; right++; } return s.substring(left+1,right);//substring是前闭后开区间 } }

注意: while ( s.charAt(start)==s.charAt(end) && start>=0 && end<s.length()){ }和

 while ( start>=0 && end<s.length() && s.charAt(start)==s.charAt(end) ){ }

前者会报错,因为start和end可能越界会报错,&&连接的判断,前面的不满足,后面的就不会执行。

9月11日10. 正则表达式匹配

10. 正则表达式匹配(难)

题解链接

本题未全部理解

 char[] cs = s.toCharArray();//将字符串转为字符串数组

复制代码
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
44
45
46
47
48
49
50
51
52
53
54
55
56
package Hot100; /** * @author : lkw * @data : 2021/9/11 14:27 * @description :'.' 匹配任意单个字符 '*' 匹配零个或多个前面的那一个元素 **/ public class isMatch10_01 { public static void main(String[] args) { String s = "aab"; String p = "c*a*b"; isMatch(s,p); } public static boolean isMatch(String s, String p) { char[] cs = s.toCharArray(); char[] cp = p.toCharArray(); // dp[i][j]:表示s的前i个字符,p的前j个字符是否能够匹配 boolean[][] dp = new boolean[cs.length + 1][cp.length + 1]; // 初期值 // s为空,p为空,能匹配上 dp[0][0] = true; // p为空,s不为空,必为false(boolean数组默认值为false,无需处理) // s为空,p不为空,由于*可以匹配0个字符,所以有可能为true //减2的原因:若出现*,则要裁掉2个 // 例如:aa* c*可以匹配空裁掉之后只剩下a,若裁后的不可以匹配空dp[0][j - 2],则dp[0][j]也不行行 for (int j = 1; j <= cp.length; j++) { if (cp[j - 1] == '*') {//若出现*,则要裁掉2个 dp[0][j] = dp[0][j - 2];//a*b*,若a*可以匹配空dp[0][j - 2],则b*也能匹配空dp[0][j] } } // 填格子 for (int i = 1; i <= cs.length; i++) { for (int j = 1; j <= cp.length; j++) { // 文本串和模式串末位字符能匹配上 if (cs[i - 1] == cp[j - 1] || cp[j - 1] == '.') { dp[i][j] = dp[i - 1][j - 1]; } else if (cp[j - 1] == '*') { // 模式串末位是* // 模式串*的前一个字符能够跟文本串的末位匹配上 if (cs[i - 1] == cp[j - 2] || cp[j - 2] == '.') { dp[i][j] = dp[i][j - 2] // *匹配0次的情况 || dp[i - 1][j]; // *匹配1次或多次的情况 } else { // 模式串*的前一个字符不能够跟文本串的末位匹配 dp[i][j] = dp[i][j - 2]; // *只能匹配0次 } } } } return dp[cs.length][cp.length]; } }

因为这边定义的dp[i][j]是表示s的前i个字符和p的前j个字符能否匹配。s一共有s.length个字符,p一共有p.length个字符。最终答案就是dp[s.length][p.length],而数组是从下标0开始的,所以dp数组的长度是s.length+1和p.length+1。

11. 盛最多水的容器

题解链接

暴力超时

复制代码
1
2
3
4
5
6
7
8
9
10
public static int maxArea(int[] height) { //将短板忘内挪 int i = 0, j = height.length - 1, max = 0; while (i<j){ max = height[i]<height[j]? Math.max(max,(j-i)*height[i++]): Math.max(max,(j-i)*height[j--]); } return max; }

15. 三数之和

题解链接

复制代码
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 static List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> ans = new ArrayList<>(); int len = nums.length; if (nums == null || len < 3) { return ans; } Arrays.sort(nums); for (int i = 0; i < len; i++) { if (nums[i] > 0) break; if (i > 0 && nums[i] == nums[i - 1]) continue;//i>0只是为了让i-1不越界 int L = i + 1; int R = len - 1; while (L < R) { int sum = nums[i] + nums[L] + nums[R]; if (sum == 0) { ans.add(Arrays.asList(nums[i], nums[L], nums[R])); while (L < R && nums[L] == nums[L + 1]) { L++; } while (L < R && nums[R] == nums[R - 1]) { R--; } L++; R--; } else if (sum < 0) L++; else if (sum > 0) R--; } } return ans; }

2021年9月20

17. 电话号码的字母组合

题解

回溯 

复制代码
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
package Hot100; import java.security.Key; import java.util.*; /** * @author : lkw * @data : 2021/9/20 10:30 * @description :map.put("2", Arrays.asList("a", "b", "c"));//Map<String,List<String>>的写法 **/ public class letterCombinations17_01 { private static final String[] KET ={"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; public static void main(String[] args) { final String[] KET; String digits = "23"; letterCombinations(digits); } public static List<String> letterCombinations(String digits) { List<String> list=new ArrayList<>(); if (digits.length()==0 || digits==null) return list; Combinations(new StringBuffer(),list,digits); return list; } public static void Combinations(StringBuffer pre, List<String> list,String digits){ if (pre.length()==digits.length()){ list.add(pre.toString()); return ; } int curDigits=digits.charAt(pre.length())-'0'; String str= KET[curDigits]; for (char c: str.toCharArray()) { pre.append(c); Combinations(pre,list,digits); pre.deleteCharAt(pre.length()-1); } } }

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
package Hot100; /** * @author : lkw * @data : 2021/9/20 20:41 * @description : **/ public class removeNthFromEnd19_01 { public static class ListNode { int val; ListNode next; ListNode() { } ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; } } public static void main(String[] args) { ListNode head = new ListNode(1); ListNode node = head; int n = 1; for (int i = 2; i <= n; i++) { node.next = new ListNode(i); node = node.next; } removeNthFromEnd(head, 1); } public static ListNode removeNthFromEnd(ListNode head, int n) { ListNode node = head; int len = 0; while (node != null) { len++;//计算长度 node = node.next; } node = head; if (len == n){ return node.next;//如果删除的是头 } node = head; for (int i = 1; i < len - n; i++) { node = node.next; } node.next = node.next.next;//删除的是中间元素 return head; } }

方法二:优化方法一(哑节点) 

在对链表进行操作时,一种常用的技巧是添加一个哑节点(dummy node),它的next 指针指向链表的头节点。这样一来,我们就不需要对头节点进行特殊的判断了。

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static ListNode removeNthFromEnd(ListNode head, int n) { //哑节点,不需要考虑头 ListNode dummy = new ListNode(0, head); ListNode cur = dummy; int len = 0; while (head != null) { len++;//计算长度 head = head.next; } for (int i = 1; i < len-n+1; i++) { cur=cur.next; } cur.next=cur.next.next; return dummy.next; }

方法三:双指针

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static ListNode removeNthFromEnd(ListNode head, int n) { //哑节点,不需要考虑头 ListNode dummy = new ListNode(0, head); ListNode first =head;//first比second前挪nge ListNode second = dummy; //挪到要删节点的前驱 for (int i = 0; i < n; i++) { first=first.next; } while (first!=null) { first=first.next; second=second.next; } second.next=second.next.next; return dummy.next; }

9月21日

20. 有效的括号

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//pop() 方法弹出栈顶元素, 调用后, 栈顶元素从栈中被永久性地删除。 //peek() 方法则只返回栈顶元素, 而不删除它。 public static boolean isValid(String s) { Stack<Character> stack=new Stack<>(); stack.push('?'); HashMap<Character,Character> map =new HashMap<>(); map.put('(',')'); map.put('{','}'); map.put('[',']'); map.put('?','?'); for (Character c:s.toCharArray()) { if (map.containsKey(c)){ stack.push(c);//如果是左括号则放入 }else if(c!=map.get(stack.pop())){ return false; } } return stack.size()==1; }

9月22

23. 合并K个升序链表

复制代码
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
package Hot100; /** * @author : lkw * @data : 2021/10/2 9:48 * @description :每次都得比较k个中最小的 **/ public class mergeKLists23_01 { public static class ListNode { int val; ListNode next; ListNode() { } ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; } } public ListNode mergeKLists(ListNode[] lists) { ListNode ans = null; int nums=lists.length; for (int i = 0; i < nums; i++) { ans= mergetwoLists(ans,lists[i]); } return ans; } public ListNode mergetwoLists(ListNode l1,ListNode l2) { if (l1==null || l2==null){ return l1!=null?l1:l2; } ListNode dummy = new ListNode(0); ListNode newnode = dummy; //怎么三者比出最小的? while (l1!=null && l2!=null){ if (l1.val<=l2.val){ newnode.next=l1; l1=l1.next; }else { newnode.next=l2; l2=l2.next; } newnode=newnode.next; } newnode.next=l1!=null?l1:l2; return dummy.next; } }

21. 合并两个有序链表

复制代码
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
44
45
46
47
48
49
50
51
52
53
54
55
package Hot100; /** * @author : lkw * @data : 2021/9/22 20:11 * @description :不需要节点再记录l1和l2的位置 **/ public class mergeTwoLists21_01 { public static class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; } } public static void main(String[] args) { // l1 = [1,2,4], l2 = [1,3,4]; // ListNode l1= new ListNode(1); // l1.next=new ListNode(2); // l1.next.next=new ListNode(4); // // ListNode l2= new ListNode(1); // l2.next=new ListNode(3); // l2.next.next=new ListNode(4); ListNode l1= null; ListNode l2= null; mergeTwoLists(l1,l2); } public static ListNode mergeTwoLists(ListNode l1, ListNode l2) { //哑节点 ListNode ans = new ListNode(-999); ListNode cur3 = ans; while (l1!=null && l2!=null){ if (l1.val<=l2.val){ cur3.next= l1; l1=l1.next; }else { cur3.next= l2; l2=l2.next; } cur3=cur3.next; } // if (l1!=null){ // cur3.next=l1; // }else cur3.next=l2; cur3.next= l1!=null?l1:l2; return ans.next; } }

9月25日

22. 括号生成

题解

回溯法:

如果左括号数量不大于 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
26
class Solution { public static List<String> generateParenthesis(int n) { List<String> ans = new ArrayList<>(); backing(ans,0,0,new StringBuffer(),n); return ans; } public static void backing( List<String> ans,int left,int right,StringBuffer str,int n){ if (str.length()==2*n){ ans.add(str.toString()); return; } //如果左括号的个数少于n,则可以加入左括号 if (left<n){ str.append("("); backing(ans,left+1,right,str,n); str.deleteCharAt(str.length()-1); } //右括号的个数少于左括号,可以加入左括号 if (right<left){ str.append(")"); backing(ans,left,right+1,str,n); str.deleteCharAt(str.length()-1); } } }

10.2日

23. 合并K个升序链表

方法一:顺序合并

复制代码
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
package Hot100; /** * @author : lkw * @data : 2021/10/2 9:48 * @description : **/ public class mergeKLists23_01 { public static class ListNode { int val; ListNode next; ListNode() { } ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; } } public ListNode mergeKLists(ListNode[] lists) { ListNode ans = null; int nums=lists.length; for (int i = 0; i < nums; i++) { ans= mergetwoLists(ans,lists[i]); } return ans; } public ListNode mergetwoLists(ListNode l1,ListNode l2) { if (l1==null || l2==null){ return l1!=null?l1:l2; } ListNode dummy = new ListNode(0); ListNode newnode = dummy; //怎么三者比出最小的? while (l1!=null && l2!=null){ if (l1.val<=l2.val){ newnode.next=l1; l1=l1.next; }else { newnode.next=l2; l2=l2.next; } newnode=newnode.next; } newnode.next=l1!=null?l1:l2; return dummy.next; } }

方法二:分治合并

复制代码
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 mergeKLists(ListNode[] lists) { return merge(lists,0, lists.length-1); } public ListNode merge(ListNode[] lists,int left,int right){ if (left==right) return lists[left]; if (left>right) return null; int mid = left+(right-left)/2;//防止溢出 return mergetwoLists(merge(lists,left,mid),merge(lists,mid+1,right)); } public ListNode mergetwoLists(ListNode l1, ListNode l2) { if (l1==null || l2==null){ return l1!=null?l1:l2; } ListNode dummy = new ListNode(0); ListNode newnode = dummy; //怎么三者比出最小的? while (l1!=null && l2!=null){ if (l1.val<=l2.val){ newnode.next=l1; l1=l1.next; }else { newnode.next=l2; l2=l2.next; } newnode=newnode.next; } newnode.next=l1!=null?l1:l2; return dummy.next; }

31. 下一个排列

 思路

 1.从后往前找到第一次出现升序的地方(位置是i和i+1)

2.找到i之后比i大的最小值k

3.调换i和k位置上的值

4.将i之后的数字升序排序

代码看:https://leetcode-cn.com/problems/next-permutation/solution/xia-yi-ge-pai-lie-by-leetcode-solution/

题解思路看:https://leetcode-cn.com/problems/next-permutation/solution/xia-yi-ge-pai-lie-suan-fa-xiang-jie-si-lu-tui-dao-/

复制代码
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
package Hot100; /** * @author : lkw * @data : 2021/10/2 9:57 * @description : **/ public class nextPermutation31_01 { public static void main(String[] args) { int[] nums={5,4,7,5,3,2}; nextPermutation(nums); } public static void nextPermutation(int[] nums) { if (nums.length<2) return;//1,3 int i; //从后往前找到第一次出现升序 nums[i]<nums[i+1]的地方(因为是第一次出现的,因此i+1之后的都是降序的) for (i = nums.length-2; i >=0 && nums[i]>=nums[i+1]; i--); int k; //如果序列本来是倒序,例如:3,2,1 则i=-1 if (i>=0){ //k是找到i后面比i大的最小值 for (k = nums.length-1; k >i && nums[k]<=nums[i]; k--); swap(nums,i,k); } reverse(nums,i+1); } public static void swap(int[] nums,int index1,int index2){ int temp=nums[index1]; nums[index1]=nums[index2]; nums[index2]=temp; } //重排从start开始的元素 public static void reverse(int[] nums,int start){ int end=nums.length-1; while (start<end){ swap(nums,start++,end--); } } }

10月3日

32. 最长有效括号

题解

复制代码
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
package Hot100; import java.util.Stack; /** * @author : lkw * @data : 2021/10/3 10:22 * @description : **/ public class longestValidParentheses32_01 { public static void main(String[] args) { String s = "()(()"; longestValidParentheses(s); } public static int longestValidParentheses(String s) { char[] str=s.toCharArray(); int max=0; Stack<Integer> stack = new Stack<>(); stack.push(-1); for (int i = 0; i < s.length(); i++) { if (str[i]=='('){ stack.push(i); }else { //遇到右括号先出栈 stack.pop(); if (stack.isEmpty()){ stack.push(i); }else max=Math.max(i-stack.peek(),max); } } return max; } }

10月4日 

33. 搜索旋转排序数组

二分法:题解

将数组从中间分开成左右两部分的时候,一定有一部分的数组是有序的。先判断目标值是否在有序部分(因为有序的好判断,通过左右边界大小直接判断),如果不在有序这边,那一定在另一部分。

先判断目标值是否在有序的这边,如果不在搜索另一部分。

那如何判断是否为有序数组:

如果nums[left]<=nums[mid]则是有界的,判断其左右边界与target大小关系。

复制代码
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
package Hot100; /** * @author : lkw * @data : 2021/10/4 15:10 * @description :旋转排序数组,实际是想告诉我们两个升序数组 **/ public class search33_01 { public static void main(String[] args) { int[] nums = {3,1}; int target = 1; search(nums,target); } public static int search(int[] nums, int target) { int len=nums.length; if (len==0) return -1; if (len==1) return nums[0]==target?0:-1; int left=0; int right= len-1; while(left<=right){ int mid = (left+right)/2; if (nums[mid]==target) return mid; //左侧有序 if (nums[left]<=nums[mid]){//等于的情况就是mid就是left if (nums[left]<=target && nums[mid]>target ){ right=mid-1; }else left=mid+1; }else{//右侧有序 if (nums[right]>=target && nums[mid]<target ){ left=mid+1; }else right=mid-1; } } return -1; } }

10月7日

34. 在排序数组中查找元素的第一个和最后一个位置

1.二分法: 

题解链接

1.1容易理解,推荐

思路:

1.二分查找找到nums[mid]==target.

2.再找出mid左侧和右侧,是否还存在target.

复制代码
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 int[] searchRange(int[] nums, int target) { //1.二分查找找到nums[mid]==target 2.再找出mid左侧和右侧,是否还存在target if (nums.length==0) return new int[]{-1,-1}; int mid=0; int left=0; int right= nums.length-1; while (left<=right){ mid=left+(right-left)/2; if (nums[mid]==target) break; else if (nums[mid]<target){ left=mid+1; }else right=mid-1; } if (nums[mid]==target) { left=right=mid; }else return new int[]{-1,-1}; while (left>=1 && nums[left]==nums[left-1]){ left--; } while (right< nums.length-1 && nums[right]==nums[right+1]){ right++; } return new int[]{left,right}; }

1.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
32
public static int[] searchRange(int[] nums, int target) { int leftNum=binary(nums,target,true); int rightNum=binary(nums,target,false)-1;//右侧找到的是大于target的第一个元素 if (leftNum<=rightNum && leftNum>=0 && rightNum<=nums.length-1 &&nums[rightNum]==target && nums[leftNum]==target ){ return new int[]{leftNum,rightNum}; } return new int[]{-1,-1}; } public static int binary(int[] nums, int target,boolean le){ //le为true代表找到是最左侧元素 int left=0; int right= nums.length-1; int ans= nums.length;//若未找到目标元素,返回ans,在上级判断是会越界,则返回{-1,-1} while(left<=right){ //nums[mid]<target时,查找leftNum和rightNum都找左侧区间, //在nums[mid]=target情况下,查找leftNum时查找左侧区间,查找rightNum是查找右侧区间, //因此使用le标记查找的是leftNum还是rightNum int mid= left+(right-left)/2; if (nums[mid]>target || (le==true && nums[mid]==target) ){ //查找[left,mid-1] right=mid-1; ans=mid; }else{ left=mid+1; } } return ans; }

 2.暴力解法:

找到第一个与target相等的值为左边届,然后记录其后面,与target相等的个数,来定位右边界。

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static int[] searchRange(int[] nums, int target) { boolean flag=false; int count=0; int left=-1; for (int i = 0; i < nums.length; i++) { if (nums[i]>target){ break; } if (nums[i]==target){ if (!flag){ left=i; flag=true; }else count++; } } return new int[]{left, left+count}; }

39. 组合总和

res.add(ans);//存的是实时的ans,ans变则res中的值也变。引用的是同一个地址

因此要使用res.add(new ArrayList<>(ans));

  

复制代码
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
package Hot100; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; /** * @author : lkw * @data : 2021/10/7 15:52 * @description : **/ public class combinationSum39_01 { public static void main(String[] args) { int[] candidates = {2,3,6,7}; int target = 7; combinationSum(candidates,target); } public static List<List<Integer>> combinationSum(int[] candidates, int target) { List<List<Integer>> lists =new ArrayList<>(); List<Integer> ans=new ArrayList<>(); backing(candidates,lists,ans,0,target); return lists; } public static void backing(int[] candidates, List<List<Integer>> lists, List<Integer> ans,int start,int target){ if (target ==0){ lists.add(new ArrayList<>(ans)); return; } for (int i = start; i < candidates.length ; i++) { if (candidates[i]<=target){ ans.add(candidates[i]); backing(candidates,lists,ans,i,target-candidates[i]); ans.remove(ans.size()-1); } } } }

10月8日

42. 接雨水

题解

1.动态编程

复制代码
1
从左往右找最大的left,从右往左找最大的right
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int trap(int[] height) { int size=height.length; if(size==0 || height==null){ return 0; } int ans=0; int[] left_max=new int[size]; int[] right_max=new int[size]; left_max[0]=height[0]; for (int i = 1; i < size; i++) { left_max[i]=Math.max(left_max[i-1],height[i]); } right_max[size-1]=height[size-1]; for (int i = size-2; i >=0 ; i--) { right_max[i]=Math.max(right_max[i+1],height[i]); } for (int i = 0; i < size; i++) { ans+=Math.min(right_max[i],left_max[i])-height[i]; } return ans; }
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int trap(int[] height) { int len=height.length; //从左往右找最大的left,从右往左找最大的right int[] left=new int[len]; int[] right=new int[len]; right[len-1]=height[len-1]; left[0]=height[0]; int sum=0; for (int i = 1; i < len; i++) { int j=len-1-i; left[i]=Math.max(left[i-1],height[i]); right[j]=Math.max(right[j+1],height[j]); } for (int i = 0; i < len; i++) { sum+=Math.min(left[i],right[i])-height[i]; } return sum; }

46. 全排列

题解

复制代码
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 List<List<Integer>> permute(int[] nums) { List<List<Integer>> lists =new ArrayList<>(); List<Integer> ans= new ArrayList<>(); boolean[] visited=new boolean[nums.length]; backing(nums,lists,ans,visited); return lists; } private static void backing(int[] nums,List<List<Integer>> lists, List<Integer> ans,boolean[] visited) { if (ans.size()== nums.length){ lists.add(new ArrayList<>(ans)); } for (int i = 0; i < nums.length ; i++) { if (visited[i]){ continue; } visited[i]=true; ans.add(nums[i]); backing(nums,lists,ans,visited); ans.remove(ans.size()-1);//移除索引位置,从0开始 visited[i]=false; } }

48. 旋转图像

题解

1.方法一:使用辅助数组

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void rotate(int[][] matrix) { int len = matrix.length; int[][] max_new = new int[len][len]; for (int i = len-1; i >=0; i--) { for (int j = 0; j < len; j++) { max_new[j][len-i-1]=matrix[i][j]; } } for (int i = 0; i < len; i++) { for (int j = 0; j < len; j++) { matrix[i][j]=max_new[i][j]; } } }

2.方法二:旋转

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public void rotate(int[][] matrix) { int len =matrix.length; int temp; //上下翻转 for (int i = 0; i < len/2; i++) { for (int j = 0; j < len; j++) { temp=matrix[len-i-1][j]; matrix[len-i-1][j]=matrix[i][j]; matrix[i][j]=temp; } } //对称轴翻转 for (int i = 0; i < len; i++) { for (int j = 0; j < i; j++) { temp=matrix[j][i]; matrix[j][i]=matrix[i][j]; matrix[i][j]=temp; } } }

10月11日

49. 字母异位词分组

复制代码
1
2
//String key=strChar.toString();//通过不了,引用的是地址 String key=new String(strChar);
复制代码
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
package Hot100; import java.util.*; public class groupAnagrams_49 { public static void main(String[] args) { String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"}; groupAnagrams(strs); } public static List<List<String>> groupAnagrams(String[] strs) { Map<String,List<String>> map=new HashMap<String,List<String>>(); for (String str:strs) { char array[]=str.toCharArray(); Arrays.sort(array); String key = new String(array); String key1 =array.toString();//这样转字符串不对,因为数组是对象,没有重写toString方法,因此得到的是类签名 List<String> list=map.getOrDefault(key,new ArrayList<>()); list.add(str); map.put(key,list); } return new ArrayList<List<String>>(map.values()); } }

注意:

1.getOrDefault() 方法获取指定 key 对应对 value,如果找不到 key ,则返回设置的默认值。

 2. new String() 和 toString()的区别

Java对象都继承于Object,Object中提供了toString方法,用于简单返回该类的类签名。在Java中,数组也可以看作是一种对象,显然byte[]也是一种继承与Object的对象,并且它没有重写Object的toString方法,因此使用byte[]的toString返回的字符串,仅仅是byte[]的类签名,而不是对应的值。

改为使用new String()构造方法,将byte[]转换为字符串,得到的就会是一个根据字节数组内容构造的字符串。

总结:new String()一般使用字符转码的时候,例如byte[]数组的时候。
          toString()将对象打印的时候使用。

53. 最大子序和

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static int maxSubArray(int[] nums) { int cur=nums[0]; int max=nums[0]; for (int i = 1; i < nums.length; i++) { if(cur>0){ cur=cur+nums[i]; }else { //如果当前值前面的和为负数,则舍弃前面的值, cur=nums[i]; } max=Math.max(cur,max); } return max; }

10月12日

  55. 跳跃游戏

题解

复制代码
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
public static boolean canJump(int[] nums) { int n= nums.length; if (n==1) { return nums.length>=0;} int rightmost=nums[0];//若nums={0},则通过不了,需要加if判断n==1 //int rightmost=0;//for循环从0开始 for (int i = 1; i < n; i++) { if (i<=rightmost){ rightmost=Math.max(rightmost,i+nums[i]); if (rightmost>=n-1){ return true; } } } return false; } } // public boolean canJump(int[] nums) { // int n = nums.length; // int rightmost = 0; // for (int i = 0; i < n; ++i) { // if (i <= rightmost) { // rightmost = Math.max(rightmost, i + nums[i]); // if (rightmost >= n - 1) { // return true; // } // } // } // return false; // }

56. 合并区间

题解

复制代码
1
2
3
4
思路: 1.按首元素排序 2.取当前遍历元素的左右边界,若列表最后一个元素右边界<左边界,则不能合并,直接插入。 3.若能合并,只修改列表最后一个元素右边界即可。merges.get(merges.size()-1)[1]=right;//取的是地址,因此直接赋值就行
复制代码
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 static int[][] merge(int[][] intervals) { List<int[]> merges=new ArrayList<>(); if (intervals.length==0){ return new int[0][2]; } //按首元素升序排序 Arrays.sort(intervals, new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) { return o1[0]-o2[0];//o1-o2为升序,o2-o1为降序 } }); //取当前遍历元素的左右边界,若列表最后一个元素右边界<左边界,则不能合并,直接插入 //合并,只修改列表最后一个元素右边界即可 for (int i = 0; i < intervals.length; i++) { int left=intervals[i][0]; int right=intervals[i][1]; if (merges.size()==0|| merges.get(merges.size()-1)[1]<left){ merges.add(new int[]{left,right}); }else{ merges.get(merges.size()-1)[1]=Math.max(merges.get(merges.size()-1)[1],right);//取的是地址,因此直接赋值就行 } } return merges.toArray(new int[merges.size()][]); }

 注意:

复制代码
1
2
3
4
5
6
7
//按首元素升序排序 Arrays.sort(intervals, new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) { return o1[0]-o2[0];//o1-o2为升序,o2-o1为降序 } });

return merges.toArray(new int[merges.size()][]);//括号是merges转成的int数组大小 

 

10月13日

62. 不同路径

题解

1.动态规划

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int uniquePaths(int m, int n) { int[][] de=new int[m][n]; for (int i = 0; i < m; i++) { de[i][0]=1; } for (int i = 0; i < n; i++) { de[0][i]=1; } for (int i = 1; i < m; i++) { for (int j = 1; j <n ; j++) { de[i][j]=de[i-1][j]+de[i][j-1]; } } return de[m-1][n-1]; }

2.数学

复制代码
1
2
3
4
5
6
7
public int uniquePaths(int m, int n) { double ans=1; for (int x = 1,y=n; x < m; x++,y++) { ans=ans*y/x; } return (int)ans; }

64. 最小路径和

题解

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int minPathSum(int[][] grid) { if (grid==null||grid.length==0){ return 0; } int m=grid.length; int n=grid[0].length; int[][] de =new int[m][n]; de[0][0]=grid[0][0]; for (int i = 1; i < m; i++) { de[i][0]=de[i-1][0]+grid[i][0]; } for (int i = 1; i <n; i++) { de[0][i]=de[0][i-1]+grid[0][i]; } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { de[i][j]=Math.min(de[i-1][j],de[i][j-1])+grid[i][j]; } } return de[m-1][n-1]; }

10月14日

70. 爬楼梯

1.动态规划:动态数组

题解

复制代码
1
2
3
4
5
6
7
8
9
public static int climbStairs(int n){ int a=1;int b=1;int c=1; for (int i = 1; i < n; i++) { a=b; b=c; c=a+b; } return c; }

75. 颜色分类

方法一:排序

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
//冒泡排序 public static void sortColors(int[] nums) { int len= nums.length; for (int i = len-1; i >=0; i--) { for (int j = 0; j < i; j++) { if (nums[j]>nums[j+1]){ int temp=nums[j+1]; nums[j+1]=nums[j]; nums[j]=temp; } } } }

方法二: 

此代码中: 0 的优先级> 1 的优先级 >2 的优先级

即时2先被填入,但是若最后值不为2,会被覆盖掉。

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static void sortColors(int[] nums) { //zero表示数字0的右侧边界,one、two分别表示1 和 2 的右侧边界 int zero = 0;int one = 0;int two = 0; int length = nums.length; for(int i = 0; i < length; i++) { //记录下待处理的值 int temp = nums[i]; //不管怎样,我先给你填个2 nums[two++] = 2; // <=1的话 1的右侧边界one要向右挪一格 if(temp <= 1){ nums[one++] = 1; } //为0的话 0的右侧边界zero要向右挪一格 if(temp == 0) { nums[zero++] = 0; } } }

10月16日

72. 编辑距离

题解

 

 

dp数组类似这样:

 

复制代码
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
public int minDistance(String word1, String word2) { int m=word1.length(); int n=word2.length(); //一个字符串为空 if (m*n==0) return m+n; int dp[][]=new int[m+1][n+1]; for (int i = 0; i < m+1; i++) { dp[i][0]=i; } for (int i = 0; i < n+1; i++) { dp[0][i]=i; } for (int i = 1; i < m+1; i++) { for (int j = 1; j < n+1; j++) { int delete=dp[i-1][j]+1; int insert=dp[i][j-1]+1; int alert=dp[i-1][j-1]; //修改后前一个字符不相等,编辑距离加一 if (word1.charAt(i-1)!=word2.charAt(j-1)){ alert++; } dp[i][j] =Math.min(delete,Math.min(insert,alert)); } } return dp[m][n]; }

10月19日

94. 二叉树的中序遍历

1.递归

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res=new ArrayList<>(); inord(root,res); return res; } public void inord(TreeNode root,List<Integer> res){ if (root==null){ return; } inord(root.left,res); res.add(root.val); inord(root.right,res); }

2.迭代

Java中LinkedList add 是加在list尾部.

LinkedList push 施加在list头部.

  res.add(root.val);的位置决定前中后序遍历

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public List<Integer> inorderTraversal(TreeNode root) { //!deque.isEmpty List<Integer> res=new ArrayList<>(); Stack<TreeNode> deque=new Stack<>(); while(root!=null || !deque.isEmpty()){ //判断栈是否为空用:deque.isEmpty() while (root!=null){ deque.push(root);//deque.push(root); root=root.left; } root=deque.pop(); res.add(root.val); root=root.right; } return res; }

3.颜色标记法

题解

复制代码
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
class ClassNode{ TreeNode node; boolean flag; ClassNode(TreeNode node,boolean flag){ this.flag=flag; this.node=node; } } public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res=new ArrayList<>(); Stack<ClassNode> stack =new Stack<>(); if (root==null) return new ArrayList<>(); stack.push(new ClassNode(root,false)); while (!stack.isEmpty()){ ClassNode cn=stack.pop(); if (cn.flag==false){ if (cn.node.right!=null) stack.push(new ClassNode(cn.node.right,false)); stack.push(new ClassNode(cn.node, true)); if (cn.node.left!=null)stack.push(new ClassNode(cn.node.left,false)); }else { res.add(cn.node.val); } } return res; }

10月20日

只要求形状不同,不要求节点的值。

96. 不同的二叉搜索树

题解

1.动态规划(自底向上,并且前面计算的G[i]后面会用到)

G[n]代表n个节点时的排列组合数。(中间为一个节点j,左边j-1个节点,右边i-j个)

复制代码
1
2
3
4
5
6
7
8
9
10
public static int numTrees(int n) { int G[]=new int[n+1]; G[0]=1;G[1]=1; for (int i = 2; i <= n; i++) { for (int j = 1; j <=i; j++) { G[i]+=G[j-1]*G[i-j]; } } return G[n]; }

10月21

98. 验证二叉搜索树

1.中序遍历是顺序的

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//中序遍历是顺序的 public boolean isValidBST(TreeNode root) { boolean flag=true; List<Integer> list = new ArrayList<>(); inord(root,list); for (int i = 0; i < list.size()-1; i++) { for (int j = i+1; j < list.size(); j++) { if (list.get(i)>=list.get(j)){ flag=false; break; } } } return flag; } public void inord(TreeNode root,List<Integer> list){ if(root==null){return;} inord(root.left,list); list.add(root.val); inord(root.right,list); }

2.判断当前节点和中序遍历的前一个节点大小

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution { long pre = Long.MIN_VALUE; public boolean isValidBST(TreeNode root) { if (root==null) return true; if (!isValidBST(root.left)){ return false; } if (root.val<=pre){ return false; } pre=root.val; return isValidBST(root.right); } }

101. 对称二叉树

1.递归

复制代码
1
2
3
4
5
6
7
8
9
10
public boolean isSymmetric(TreeNode root) { return check(root,root); } public boolean check(TreeNode left,TreeNode right){ if (left==null && right==null)return true; if (left==null || right==null) return false; return left.val==right.val && check(left.right,right.left) && check(left.left,right.right); }

2.迭代

Queue 中 add() 和 offer()都是用来向队列添加一个元素。
在容量已满的情况下,add() 方法会抛出IllegalStateException异常,offer() 方法只会返回 false 。

Queue使用时要尽量避免Collection的add()和remove()方法,add()和remove()方法在失败的时候会抛出异常。

要使用offer()来加入元素,使用poll()来获取并移出元素。

它们的优点是通过返回值可以判断成功与否, 如果要使用前端而不移出该元素,使用element()或者peek()方法。

复制代码
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
public boolean isSymmetric(TreeNode root) { return check(root,root); } public boolean check(TreeNode left, TreeNode right){ Queue<TreeNode> que = new LinkedList<>(); que.offer(right); que.offer(left); while(!que.isEmpty()){ right=que.poll(); left=que.poll(); if (right==null && left==null){ continue; } if (right==null || left==null || right.val!= left.val){ return false; } que.offer(right.right); que.offer(left.left); que.offer(right.left); que.offer(left.right); } return true; }

10月22

102. 二叉树的层序遍历

题解

层次遍历可由宽度优先遍历bfs而得。

宽度优先遍历bfs如下:

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
void bfs(TreeNode root) { Queue<TreeNode> queue = new ArrayDeque<>(); queue.add(root); while (!queue.isEmpty()) { TreeNode node = queue.poll(); if (node.left != null) { queue.add(node.left); } if (node.right != null) { queue.add(node.right); } } }

本题题解: 

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> list = new ArrayList<>(); Queue<TreeNode> queue =new ArrayDeque<>(); if (root!=null) queue.offer(root); while(!queue.isEmpty()){ ArrayList<Integer> leval = new ArrayList<>(); int n=queue.size(); for (int i = 0; i < n; i++) { TreeNode node =queue.poll(); leval.add(node.val); if (node.left!=null) { queue.offer(node.left); } if (node.right!=null) { queue.offer(node.right);//add会抛异常,offer返回false } } list.add(leval); } return list; }

补充

deque和queue的区别:

 从上图看出,Queue以及Deque都是继承于Collection,Deque是Queue的子接口。

在java中,Queue被定义成单端队列使用,Deque被定义成双端队列使用
而由于双端队列的定义,Deque可以作为栈或者队列使用,而Queue只能作为队列或者依赖于子类的实现作为堆使用

ArrayDeque通常作为栈或队列使用,但是栈的效率不如LinkedList高。
LinkedList通常作为或队列使用,但是队列的效率不如ArrayQueue高。

ArrayDeque.add()方法用于在双端队列的末尾添加给定元素。

ArrayDeque.poll() 此方法检索并删除此双端队列表示的队列的头部,如果此双端队列为空,则返回null。

104. 二叉树的最大深度

题解

1.dfs深度优先遍历

复制代码
1
2
3
4
5
6
7
8
9
10
//dfs深度优先遍历 public int maxDepth(TreeNode root) { if (root == null) { return 0; } else { int leftHeight = maxDepth(root.left); int rightHeight = maxDepth(root.right); return Math.max(leftHeight, rightHeight) + 1; } }

2. 层次遍历

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//输出上题层次遍历的size即可 public int maxDepth(TreeNode root) { List<List<Integer>> list = new ArrayList<>(); Queue<TreeNode> queue =new ArrayDeque<>(); if (root==null) return 0; queue.add(root); while(!queue.isEmpty()){ List<Integer> level = new ArrayList<>(); int n=queue.size(); for (int i = 0; i < n; i++) { TreeNode node = queue.poll(); level.add(node.val); if (node.left!=null) { queue.add(node.left); } if (node.right!=null) { queue.add(node.right); } } list.add(level); } return list.size(); }

 3.根据bfs不存储最终结果,只输出高度

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int maxDepth(TreeNode root) { int hight =0; Queue<TreeNode> queue =new ArrayDeque<>(); if (root==null) return 0; queue.add(root); while(!queue.isEmpty()){ int n =queue.size(); while(n>0){ TreeNode node = queue.poll(); if (node.left!=null) { queue.add(node.left); } if (node.right!=null) { queue.add(node.right); } n--; } hight++; } return hight; }

10月24日

105. 从前序与中序遍历序列构造二叉树

题解

复制代码
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
HashMap<Integer, Integer> map = new HashMap<>(); public TreeNode buildTree(int[] preorder, int[] inorder) { int n = preorder.length; //为了定位root所在位置 for (int i = 0; i < n; i++) { map.put(inorder[i], i); } return mybuildTree(preorder, inorder, 0, n - 1, 0, n - 1); } public TreeNode mybuildTree(int[] preorder, int[] inorder, int pre_left, int pre_right, int in_left, int in_right) { if (pre_left > pre_right) { return null; } //1.找到root后,在inorder中找到索引,得到左子树长度len=(中序root定位序号-left边界) 右子树preorder[root定位+1,root+len+1],就可以分开左右子树 //前序的第一个就是根节点 int pre_root = pre_left; int in_root = map.get(preorder[pre_root]); TreeNode root = new TreeNode(preorder[pre_root]); int leftTree_len = in_root - in_left; //2.使用递归,将前序和中序传递(前序中序都不算根节点),此处pre_left 换为pre_root 也可 root.left = mybuildTree(preorder, inorder, pre_left + 1, pre_left + leftTree_len, in_left, in_root - 1); root.right = mybuildTree(preorder, inorder, pre_left + leftTree_len + 1, pre_right, in_root + 1, in_right); return root; }

10月25

114. 二叉树展开为链表

1.递归

前序遍历

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static void flatten(TreeNode root) { List<TreeNode> list =new ArrayList<>(); preorder(root,list); int size = list.size(); // TreeNode pre = root; // TreeNode cur = root; for (int i = 0; i < size-1; i++) { TreeNode pre=list.get(i); TreeNode cur=list.get(i+1); pre.left=null; pre.right=cur; } } public static void preorder(TreeNode root,List<TreeNode> list) { if (root==null){ return; } list.add(root); preorder(root.left,list); preorder(root.right,list); }

2.迭代

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//poll:将首个元素从队列中弹出,如果队列是空的,就返回null // peek:查看首个元素,不会移除首个元素 public static void flatten(TreeNode root) { List<TreeNode> list = new ArrayList<>(); Deque<TreeNode> stack=new LinkedList<TreeNode>(); TreeNode node = root; while (node!=null || !stack.isEmpty()){ while (node!=null){ list.add(node); stack.push(node); node=node.left; } node =stack.poll();//pop() node=node.right; } int size=list.size(); for (int i = 0; i < size-1; i++) { TreeNode pre =list.get(i); TreeNode cur =list.get(i+1); pre.left=null; pre.right=cur; } }

121. 买卖股票的最佳时机

复制代码
1
2
3
4
5
6
7
8
9
10
public int maxProfit(int[] prices) { int len = prices.length; int min = prices[0]; int profile = 0; for (int i = 0; i < len; i++) { if (prices[i] < min) min = prices[i]; else profile = Math.max(profile, prices[i] - min); } return profile; }

11月20日

128. 最长连续序列

方法一:

sort为当前的最长连续序列长度,max为此时最长的连续序列长度。

首先给给数组排序

排序后,看num[i]与num[i+1]的关系。

如果num[i]==num[i+1],则继续循环

若num[i]+1==num[i+1],则说明连续,sort++;

否则就是不连续,sort清零

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static int longestConsecutive(int[] nums) { int sort; int max; if (nums.length==0 || nums==null){ return 0; }else { sort=1;max=1; } Arrays.sort(nums); for (int i = 0; i < nums.length-1; i++) { if (nums[i]+1==nums[i+1]){ sort++; }else if(nums[i]==nums[i+1]){ continue; }else{ max=Math.max(sort,max); sort=1; } } return Math.max(sort,max); }

方法二:

题解链接

set集合可以去重

循环当前值时,若set集合中,存在比起小的连续值,则跳过。举例:set集合存在0、1,显然从0开始计算的最大序列长度更长。

复制代码
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 longestConsecutive(int[] nums) { Set<Integer> nums_set = new HashSet<Integer>(); for (int num : nums) { nums_set.add(num);//去重 } int max, sort; if (nums.length==0 || nums==null){ return 0; }else { sort=1;max=1; } int curNum; for (int num : nums_set) { sort=1; if (nums_set.contains(num - 1)) { continue;//如果存在比其小的连续值,则跳过 } curNum = num; while (nums_set.contains(curNum+1)) { curNum++; sort++; } max=Math.max(sort,max); } return max; }

136. 只出现一次的数字

方法一:位运算

题解

复制代码
1
2
3
4
5
6
7
public static int singleNumber(int[] nums) { int sin=0; for (int num:nums) { sin^=num; } return sin; }

 方法二:

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
public static int singleNumber(int[] nums) { Arrays.sort(nums); for (int i = 0; i < nums.length; i=i+2) { if (i==nums.length-1){ return nums[i]; } if (nums[i]!=nums[i+1]){ return nums[i]; } } return 0; }

11月22日

139. 单词拆分

题解视频

题解文字参考

题目的含义是:能否将单词字典wordDict中每个word拼凑为s,且wordDict中的每个word可以重复使用。

单词字典wordDict中每个word相当于物品,s相当于背包。向背包中装入物品,并考虑顺序性。

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//wordDict中每个word相当于物品,s相当于背包。向背包中装入物品,并考虑顺序性。 public static boolean wordBreak(String s, List<String> wordDict) { //set去重 Set<String> wordSet=new HashSet<String>(wordDict); int n=s.length(); boolean[] dp=new boolean[n+1]; dp[0]=true; for (int i = 1; i < dp.length; i++) { for (String word:wordSet) { int len=word.length(); if (i>=len && word.equals(s.substring(i-len,i))){ //装还是不装 dp[i]=dp[i-len]||dp[i]; } } } return dp[n]; }

11月23

141. 环形链表

方法一:哈希表

注意这个有错:

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//四个样例未通过 public boolean hasCycle(ListNode head) { Set<Integer> set =new HashSet<Integer>(); ListNode cur=head; while (cur!=null){ if (set.contains(cur.val)){ return true;//有环 }else { set.add(cur.val); cur=cur.next; } } return false; }

 错误原因:set集合中存储的是Interger类型的,若数值val一样,则视为此节点被访问过。

修改:将set集合存储的类型改为ListNode类型,val相同,但next不同,被视为不同节点。

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//set中存储ListNode类型 public boolean hasCycle(ListNode head) { Set<ListNode> set =new HashSet<ListNode>(); ListNode cur=head; while (cur!=null){ if (set.contains(cur)){ return true;//有环 }else { set.add(cur); cur=cur.next; } } return false; }

方法二:快慢指针

题解链接

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean hasCycle(ListNode head) { if (head==null || head.next==null){ return false; } ListNode slow = head; ListNode fast = head.next; while (fast!=slow){ if (fast==null || fast.next==null){ return false; } slow=slow.next; fast=fast.next.next; } return true; }

11月24日 

142. 环形链表 II

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
public ListNode detectCycle(ListNode head) { Set<ListNode> set = new HashSet<ListNode>(); ListNode cur = head; while(cur!=null){ if (set.contains(cur)){ return cur; } set.add(cur); cur=cur.next; } return null; }

146. LRU 缓存机制

题解链接

复制代码
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
public class LRUCache { /** * Your LRUCache object will be instantiated and called as such: * LRUCache obj = new LRUCache(capacity); * int param_1 = obj.get(key); * obj.put(key,value); */ class DLinkedNode{ int key;int value; DLinkedNode prev; DLinkedNode next; public DLinkedNode(){} public DLinkedNode(int _key,int _value){ key=_key; value=_value; } } private Map<Integer,DLinkedNode> cache = new HashMap<Integer,DLinkedNode>(); private int size; private int capacity; private DLinkedNode head,tail; public LRUCache(int capacity) { this.size=0; this.capacity=capacity; //两个哑节点,头部和尾部 head=new DLinkedNode(); tail=new DLinkedNode(); head.next=tail; tail.prev=head; } public int get(int key) { DLinkedNode node =cache.get(key); if (node==null){return -1;} //若key存在,移到头部 moveToHead(node); return node.value; } public void put(int key, int value) { DLinkedNode node = cache.get(key); if (node==null){ //若不存在,则先插入链表头部,判断链表长度,若大于容量,则删除尾部元素 DLinkedNode newNode= new DLinkedNode(key,value); cache.put(key,newNode);//添加进哈希表 addToHead(newNode);//添加至双向链表头部 size++;//链表长度,初始化为0,还有头尾两个哑节点 if (size>capacity){ //如果超出容量,删除双向链表尾部节点 DLinkedNode tail =removeTail(); cache.remove(tail.key); size--;//链表长度减一 } } else { node.value=value; moveToHead(node); } } private void removeNode(DLinkedNode node) { node.prev.next=node.next; node.next.prev=node.prev; } private void moveToHead(DLinkedNode node) { //先删除,再加入至头部 removeNode(node); addToHead(node); } private void addToHead(DLinkedNode newNode) { head.next.prev=newNode; newNode.next=head.next; head.next=newNode; newNode.prev=head; } private DLinkedNode removeTail() { DLinkedNode res=tail.prev; removeNode(res); return res; } }

11月25日

148. 排序链表

方法一:将链表转为数组,对数组进行排序,对链表重新赋值。

时间复杂度:O(nlogn)

空间复杂度:O(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
26
public class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; } } public ListNode sortList(ListNode head) { List<Integer> list =new ArrayList<Integer>(); ListNode cur=head; while (cur!=null){ list.add(cur.val); cur=cur.next; } Object[] arr=list.toArray(); Arrays.sort(arr); ListNode cu=head; for (int i = 0; i < arr.length && cu!=null; i++) { cu.val=(int)arr[i]; cu=cu.next; } return head; }

方法二:归并排序(快慢指针)

题解

空间复杂度:O(1)

时间复杂度:O(nlogn)

补充快慢指针:

  • 寻找链表中点
    起点都为head时,我们可以让快指针一次前进两步,慢指针一次前进一步,当快指针到达链表尽头时,慢指针就处于链表的中间位置。
  • slow起点为head,fast起点为head.next,当程序结束时,如果链表的长度是奇数时,slow 恰巧停在中点位置;如果长度是偶数,slow 最终的位置是中间偏左;可以利用这个方法去进行归并排序。
  • 寻找链表的倒数第k个节点
    让快指针先走 k 步,然后快慢指针开始同速前进。这样当快指针走到链表末尾 null 时,慢指针所在的位置就是倒数第 k 个链表节点(假设 k 不会超过链表长度)

参考其他博主: 

slow起始点为1,fast起始点是2.如果fast在8,则slow停到了4。(偶数的话在中点左侧)

slow起始点为1,fast起始点是2.如果fast在7,则slow也停到了4。(奇数的话在中点)

复制代码
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 ListNode sortList(ListNode head) { if (head==null || head.next==null) {return head;} ListNode slow=head; ListNode fast=head.next; while (fast!=null && fast.next!=null){ fast=fast.next.next; slow=slow.next; } ListNode tep=slow.next;//停的位置是中点(或者偶数的左侧) slow.next=null; ListNode left=sortList(head); ListNode right=sortList(tep); ListNode h=new ListNode(0); ListNode dummy=h; //合并 while (left!=null && right!=null){ if (left.val<=right.val){ h.next=left; left=left.next; }else { h.next=right; right=right.next; } h=h.next; } h.next=left!=null?left:right; return dummy.next; }

最后

以上就是负责画笔最近收集整理的关于HOT100(一)2021.9月4日题解链接的全部内容,更多相关HOT100(一)2021内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(66)

评论列表共有 0 条评论

立即
投稿
返回
顶部