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
34package 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
30public 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
41package 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
45package 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/
- start不动,end向后移动
- 当end遇到重复字符,start应该放在上一个重复字符的位置的后一位,同时记录最长的长度
- 怎样判断是否遇到重复字符,且怎么知道上一个重复字符的位置?--用哈希字典的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
38package 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
40package 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
24class 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
56package 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
10public 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
31public 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
41package 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
56package 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
16public 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
17public 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
57package 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
55package 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
26class 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
57package 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
31public 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
42package 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
37package 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
38package 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
25public 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
32public 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
18public 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
42package 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
21public 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
19public 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
26public 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
16public 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
20public 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
25package 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
14public 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
32public 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
25public 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
15public 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
7public 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
21public 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
9public 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
19public 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
27public 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
14public 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
16public 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
25class 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
10public 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
14class 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
10public 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
27public 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
13void 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
22public 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
21public 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
30HashMap<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
22public 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
10public 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
21public 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
26public 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
7public 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
12public 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
15public 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
12public 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
84public 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
26public 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
29public 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内容请搜索靠谱客的其他文章。
发表评论 取消回复