转码野生老农刷题打卡

元旦定了个计划是今年刷100题，结果谁想到下半年才开始T T。
希望立了个帖子之后能刷完。

题目	Link	Tag	Note	Solution	Date
Interview 16.19 水域大小	https://leetcode-cn.com/problems/pond-sizes-lcci/	DFS	1. 水域的点上下左右，上左，下右，上右，下左都有可能被连上。可以把pond想象成一个未封口的圈，就明白了。 2. 排序后的数组可以用stream().mapToInt(i -> i).toArray()转换为int[]	https://gitee.com/vincentmliu/Al ... _PondSizesLcci.java	2022-07-12

2022-07-13打卡
207    课程表
Link：https://leetcode.cn/problems/course-schedule/
题解：https://gitee.com/vincentmliu/Al ... CourseSchedule.java

DFS
笔记：
1. 确定目标：环检测 。如果一旦出现环，证明无法完成课程。DFS
2. 生成每门课程的邻接表
3. 依次DFS每一门课程，
    如果没遍历过，标识：0
    被别的节点遍历过，没出现环：-1
    被当前遍历过：1
4. 终止条件是，如果碰到节点flag=1，说明出现环，直接返回false
    如果碰到flag=-1, 无需往下遍历，此节点没问题，不会出现环
    如果碰到0，则需要遍历
5. 时间复杂度: 节点数为n，边数为m，每个节点都要遍历一次，每条边也要遍历一次，有的节点没有边。O(n+m)
6. 空间复杂度: 需要存储每个节点的邻接表，所以O(n+m)

2023-04-03
148. Sort List
想到归并，但是这题怎么也想不出怎么O(1)空间复杂度。题解太巧妙了。一段段的排序。。直接贴代码吧

1. /**
   
2. * Definition for singly-linked list.
   
3. * public class ListNode {
   
4. *     int val;
   
5. *     ListNode next;
   
6. *     ListNode() {}
   
7. *     ListNode(int val) { this.val = val; }
   
8. *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
   
9. * }
   
10. */
    
11. class Solution {
    
12.     public ListNode sortList(ListNode head) {
    
13.         if (head == null) {
    
14.             return head;
    
15.         }
    
16.         //计算长度
    
17.         int length = 0;
    
18.         ListNode node = head;
    
19.         while (node != null) {
    
20.             length++;
    
21.             node = node.next;
    
22.         }
    
23.         //哨兵
    
24.         ListNode dummyHead = new ListNode(0, head);
    
25.         //每轮循环排序subLength长度的链表
    
26.         for (int subLength = 1; subLength < length; subLength <<= 1) {
    
27.             ListNode prev = dummyHead, curr = dummyHead.next;
    
28.             while (curr != null) {
    
29.                 //拆分前半段长度为sublength的链表
    
30.                 ListNode head1 = curr;
    
31.                 for (int i = 1; i < subLength && curr.next != null; i++) {
    
32.                     curr = curr.next;
    
33.                 }
    
34.                 //记录后半段的头，拆分后半段sublength链表
    
35.                 ListNode head2 = curr.next;
    
36.                 curr.next = null;//切断第一段和第二段
    
37.                 curr = head2;
    
38.                 for (int i = 1; i < subLength && curr != null && curr.next != null; i++) {
    
39.                     curr = curr.next;
    
40.                 }
    
41.                 //记录下一次循环排序的链表头
    
42.                 ListNode next = null;
    
43.                 if (curr != null) {
    
44.                     next = curr.next;
    
45.                     curr.next = null;//切断第二段链表尾部
    
46.                 }
    
47.                 //合并第一段和第二段
    
48.                 ListNode merged = merge(head1, head2);
    
49.                 //连接已经排序好的sublength * 2链表
    
50.                 prev.next = merged;
    
51.                 //将prev移动到sublength的末尾
    
52.                 while (prev.next != null) {
    
53.                     prev = prev.next;
    
54.                 }
    
55.                 //curr移动到未排序部分的链表头
    
56.                 curr = next;
    
57.             }
    
58.         }
    
59.         return dummyHead.next;
    
60.     }
    
61. 
    
62.     public ListNode merge(ListNode head1, ListNode head2) {
    
63.         ListNode dummyHead = new ListNode(0);
    
64.         ListNode temp = dummyHead, temp1 = head1, temp2 = head2;
    
65.         while (temp1 != null && temp2 != null) {
    
66.             if (temp1.val <= temp2.val) {
    
67.                 temp.next = temp1;
    
68.                 temp1 = temp1.next;
    
69.             } else {
    
70.                 temp.next = temp2;
    
71.                 temp2 = temp2.next;
    
72.             }
    
73.             temp = temp.next;
    
74.         }
    
75.         if (temp1 != null) {
    
76.             temp.next = temp1;
    
77.         } else if (temp2 != null) {
    
78.             temp.next = temp2;
    
79.         }
    
80.         return dummyHead.next;
    
81.     }
    
82. }
    

复制代码

2023-03-31
215. Kth Largest Element in an Array
这题太好了，考了小顶堆，堆的实现
快排或者归并排序。
最牛逼的还是看了下题解，大神太牛了，用的是快排的思想，快速定位position。服了，直接贴代码

1. class Solution {
   
2.     private final static Random random = new Random();
   
3.     public int findKthLargest(int[] nums, int k) {
   
4.         int len = nums.length;
   
5. 
   
6.         //1st len - 1;
   
7.         //2nd len - 2;
   
8.         //the kth largest number target index after sort is len - k
   
9.         int target = len - k;
   
10.         
    
11.         //binery search for a random number's positions
    
12.         //searching range shrink every search
    
13.         //why random? cuz inverse order array will lead the algrithm time cost become o(N2);
    
14.         int left = 0;
    
15.         int right = len - 1;
    
16.         
    
17.         //there must a position equals to target
    
18.         while(true){
    
19.             //find a random numbers position
    
20.             int pivodPosition = partition(nums, left, right);
    
21.             if(pivodPosition == target){
    
22.                 return nums[pivodPosition];
    
23.             }else if(pivodPosition < target){
    
24.                 left = pivodPosition + 1;
    
25.             }else if(pivodPosition > target){
    
26.                 right = pivodPosition - 1;
    
27.             }
    
28. 
    
29.         }
    
30. 
    
31. 
    
32.     }
    
33. 
    
34.     private int partition(int[] nums, int left, int right){
    
35.         int randomIndex = left + random.nextInt(right - left + 1);
    
36.         //random find a pivot , temprory put it on the first ele in range
    
37.         swap(nums, left, randomIndex);
    
38.         int pivot = nums[left];
    
39.         int le = left + 1;
    
40.         int ge = right;
    
41. 
    
42.         while(true){
    
43.             //exclusive the lesser ele
    
44.             while(le <= ge && nums[le] < pivot){
    
45.                 le++;
    
46.             }
    
47.             //exclusive greater ele
    
48.             while(le <= ge && nums[ge] > pivot){
    
49.                 ge--;
    
50.             }
    
51.             //found, ge is the position, cus le move first, so le will stop at the first ele larger than pivot's position
    
52.             if(le >= ge){
    
53.                 break;
    
54.             }
    
55.             //if stuck, swich two pins and continue
    
56.             swap(nums,le, ge);
    
57.             le++;
    
58.             ge--;
    
59.             
    
60. 
    
61.         }
    
62. 
    
63.         //put the pivot in right position
    
64.         swap(nums,left, ge);
    
65.         return ge;
    
66. 
    
67.     }
    
68. 
    
69.     private void swap(int[] nums, int a , int b){
    
70.         int tmp = nums[a];
    
71.         nums[a] = nums[b];
    
72.         nums[b] = tmp;
    
73.     }
    
74. 
    
75. }

复制代码

2022-07-14打卡
79 单词搜索
Link：https://leetcode-cn.com/problems/word-search/
题解：https://gitee.com/vincentmliu/Al ... 0079WordSearch.java

DFS
笔记：

• DFS遍历，一每个board中的字母为起始点开始查找。
• 记录一个当前已经match的字母数nowIndex， nowIndex == wordLength既最后一个字母都match的时候表示match，开始用founded剪枝
• visited标识要在递归返回时置为false，仅在本次使用时标记为true，表示不能重复使用。
• 时间复杂度：最坏情况，每个字母为首，每次遍历wordlength = l 遍历几乎全部的board，那就是 l * n * m = O(l * n * m)
• 空间复杂度： 要维护一个visited数组，O(m*n)
  

2022-07-15打卡
1306    跳跃游戏 III
Link：https://leetcode-cn.com/problems/jump-game-iii/
题解：https://gitee.com/vincentmliu/Al ... 306JumpGameIii.java
耗时： 18min


DFS
笔记：
1. DFS遍历，每一个点都有左跳右跳两种选择。
2. 左跳条件下标>=0, 右跳下标 < arr.length;
3. 重点！！必须有一个visited数组，防止成环，如果该点被遍历过，那说明此路不通，不必再遍历。
4. 时间复杂度：有可能每个点都遍历一圈，最后发现此路不通。所以O(n)
5. 空间复杂度，需要一个boolean[]， 所以也是O(n)

2022-07-15打卡
752    打开转盘锁
Link：https://leetcode-cn.com/problems/open-the-lock/
题解：https://gitee.com/vincentmliu/Al ... 752OpenTheLock.java
耗时： 60min


BFS
笔记：
1. BFS遍历， 一个set存放deadEnd，另一个存放visited
2. Queue保存每个possibleStep
3. 注意分层，每个step循环所有的possibleStep
4. 每个possibleStep枚举所有可能的下一步，非deadEnd，非visited
5. 枚举的possibleStep添加到queue中的时候判断是否reach target，reach了就直接返回step
6. 时间复杂度：可能所有可能都要遍历，O(n),n是所有组合数
7. 空间复杂度：需要连两个set存储所有可能性，所以也是O(n)

2022-07-18打卡
Interview 17.22    单词转换
Link：https://leetcode-cn.com/problems/word-transformer-lcci/
题解：https://gitee.com/vincentmliu/Al ... ransformerLcci.java
耗时： 60min


回溯解法：
1. 首先创建个邻接表，存储每一位字母可以转变的可选列表；比如： 第0位 --> {h : {hot, hit, hug}}
2. 依次遍历beginWord的每一位，如果满足 （beginWord的第[i]个char ！= 第[i]位的可选列表 && wordSet.contains(第i位转换后的新单词)）。-----往下递归
3. 重点！！往下递归前要删掉wordSet中的该新单词，表示该单词已经转变过，避免成环。
4. 时间复杂度：创建邻接表，需要n*h, n为单词位数，h为wordSet的长度。递归需要遍历每一步的可能性，最差的可能性就是所有字母26*n ，wordSet中包含所有字母的所有可能性，省去常数就是n。最终复杂度是O(n*h)
5. 空间复杂度：每一位都要保存一个邻接表，每一位邻接表包含wordSet中的所有单词，所以也是O(n*h)

BFS:
1. 首先wordSet， 如果wordSet不包含endWord，就返回空集；
2. 一个visited数组记录是否访问过该单词，如果访问过就标记true
3. 遍历wordList, 判断是否可以从当前单词跳到该单词，如果能跳，且没有遍历过，就添加到Queue中；
4. 用一个HashMap<String, Stirng>记录下一跳单词的前一个单词（也就是poll出来的当前单词）；
5. 返回List的时候，递归到beginWord.equals(prevWord),然后逐层添加进pathList。

2022-07-19打卡
今天超级忙，做个简单的为了打卡😂

344    反转字符串
Link：https://leetcode.cn/problems/reverse-string/
题解：https://gitee.com/vincentmliu/Al ... r/src/com/xixi/easy
耗时： 3min


笔记：
1.双指针，终止条件是i>=j
时间复杂度 O(n)
空间复杂度 O(1)

2022-07-20打卡
今天超级忙，做个简单的为了打卡😂

offer 58 I    翻转单词顺序
Link：https://leetcode.cn/problems/rev ... string/submissions/
题解：https://gitee.com/vincentmliu/Al ... anCiShunXuLcof.java
耗时： 8min


笔记：
1. split数组时，要用\\s+,预防出现多个空格的情况
时间复杂度 O(n)，因为要全部遍历，n是单词数量
空间复杂度 O(n), 因为要一个buffer保存所有单词

2022-07-21打卡

125        验证回文串
Link：https://leetcode.cn/problems/valid-palindrome/
题解：https://gitee.com/vincentmliu/Al ... alidPalindrome.java
耗时： 5min


笔记：
1.Character.isLetterOrDigit（char） 方法可以判断字符是否符合要求
2.要避免用s.length() - 1 因为开头如果是空格，trim之后会数组越界；
时间复杂度 O(n)
空间复杂度 O(1)

2022-07-22打卡

Interview 17.07        婴儿名字
Link：https://leetcode-cn.com/problems/baby-names-lcci/
题解：https://gitee.com/vincentmliu/Al ... _BabyNamesLcci.java
耗时： 60min


笔记：
1. 通过names初始化并查集元素，names中的名字不一定包含在synonyms中，循环names，时间n
2. 遍历synonyms，合并并查集元素。比较每一组synonym， compareTo 小的就放到value里面，当爹。时间s + logs(find爹，理论上是logs，最差情况是s)
3. 注意！synonyms中的名字不一定包含在names中，所以每个synonym中的名字也要检查是否存在，并且初始化。conner case
4. 遍历names，将所有root的计数合并保存在map中，时间n
5. 遍历map，输出结果，最坏时间n
6. find中可以将非初始化的名字对进行合并
时间复杂度 3*n + s * logs
空间复杂度 需要保存一个，最差s+n的map