转码野生老农刷题打卡

2023-03-10
剑指 Offer 03. 数组中重复的数字
这个都没一次过。。。疯了

2023-03-30
852. Peak Index in a Mountain Array
binary search经典题目

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. }

复制代码

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-04-04
剑指 Offer 59 - I. 滑动窗口的最大值
首先想到双端队列，就是忘了怎么写出来

2023-04-06
55. Jump Game
挨着跳，能跳的范围大于length-1了就说明ok了。

2023-04-07
剑指 Offer 58 - II. 左旋转字符串
过过过

2023-04-10
658. Find K Closest Elements
方法1:先二分找到最接近x的，然后双指针向两边找。
方法2:直接用compartor排序，离得近的放前面

2023-04-11
面试题 08.01. Three Steps Problem LCCI
动态玫瑰花

2023-04-12
153. Find Minimum in Rotated Sorted Array
二分，pivot就是nums[0],
记得要排除nums[0]是最小的情况