近期的一些总结

野性酷女 2024-04-08 09:15 43阅读 0赞

![d1912bec423b4aaaab262859b8917cf1.png][]

public int lengthOfLongestSubstring(String s) {
            if (s.length() == 0){
                return 0;
            }
            HashMap<Character,Integer> map = new HashMap<>();
            int max  = 0;
            int left = 0;
            for (int i = 0; i < s.length(); i++){
                if (map.containsKey(s.charAt(i))){
                    left = Math.max(left,map.get(s.charAt(i)) + 1);
                }
                map.put(s.charAt(i),i);
                max = Math.max(max,i - left + 1);
            }
            return max;
        }

![07029c187fb9429da55a0a3529870732.png][]

![b85fb1f57d4046919fb1443c70b2dc60.png][]

class LRUCache {
        int cap;
        LinkedHashMap<Integer, Integer> cache = new LinkedHashMap<>();
        public LRUCache(int capacity) {
            this.cap = capacity;
        }
    
        public int get(int key) {
            if (!cache.containsKey(key)) {
                return -1;
            }
            // 将 key 变为最近使用
            makeRecently(key);
            return cache.get(key);
        }
    
        public void put(int key, int val) {
            if (cache.containsKey(key)) {
                // 修改 key 的值
                cache.put(key, val);
                // 将 key 变为最近使用
                makeRecently(key);
                return;
            }
    
            if (cache.size() >= this.cap) {
                // 链表头部就是最久未使用的 key
                int oldestKey = cache.keySet().iterator().next();
                cache.remove(oldestKey);
            }
            // 将新的 key 添加链表尾部
            cache.put(key, val);
        }
    
        private void makeRecently(int key) {
            int val = cache.get(key);
            // 删除 key，重新插入到队尾
            cache.remove(key);
            cache.put(key, val);
        }
    }

![1bacbe150a2242cfa9f665a37095ec34.png][]

public int findKth(int[] a, int n, int K) {
            quick(a,0,n-1);
            int res = a[n - K];
            return res;
        }
        public static int postion(int[] array,int low,int high){
            int tmp = array[low];
            while (low < high){
                while (low < high && tmp <= array[high]) {
                    high--;
                }
                array[low] = array[high];
                while (low < high && tmp >= array[low]){
                    low++;
                }
                array[high] = array[low];
            }
            array[low] = tmp;
            return low;
        }
     
        public static void quick(int[] array,int low,int high){
            if(low >= high){
                return;
            }
            int priot = postion(array,low,high);
            quick(array,low,priot-1);
            quick(array,priot+1,high);
        }

![458998f907c3487481517dfe9b2a3904.png][]

public ListNode reverseKGroup(ListNode head, int k) {
            if (head == null) return null;
            // 区间 [a, b) 包含 k 个待反转元素
            ListNode a, b;
            a = b = head;
            for (int i = 0; i < k; i++) {
                // 不足 k 个，不需要反转，base case
                if (b == null) return head;
                b = b.next;
            }
            // 反转前 k 个元素
            ListNode newHead = reverse(a, b);
            // 递归反转后续链表并连接起来
            a.next = reverseKGroup(b, k);
            return newHead;
        }
    
        /* 反转区间 [a, b) 的元素，注意是左闭右开 */
        ListNode reverse(ListNode a, ListNode b) {
            ListNode pre, cur, nxt;
            pre = null;
            cur = a;
            nxt = a;
            // while 终止的条件改一下就行了
            while (cur != b) {
                nxt = cur.next;
                cur.next = pre;
                pre = cur;
                cur = nxt;
            }
            // 返回反转后的头结点
            return pre;
        }

![f988e299b3474a7b8b3084f318720b32.png][]

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; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
                if(i > 0 && nums[i] == nums[i-1]) continue; // 去重
                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;
        }

![27693b391ffb4a3f82718cdf58826836.png][]

public int[] MySort (int[] arr) {
            quick(arr,0,arr.length-1);
            return arr;
        }
         
       public static void quicksort(int[] a){
            quick(a,0,a

[d1912bec423b4aaaab262859b8917cf1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/ff98c9d7d4de48259e31842b2db1cd42.png
[07029c187fb9429da55a0a3529870732.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/5448cc7070344d6f8e28c9f89374b473.png
[b85fb1f57d4046919fb1443c70b2dc60.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/3bd2545706314ed4a2293d1850cda930.png
[1bacbe150a2242cfa9f665a37095ec34.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/a16e31995bd34c06863716d1232a9278.png
[458998f907c3487481517dfe9b2a3904.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/017c8b349fde43eeb1b991e91c5ebf90.png
[f988e299b3474a7b8b3084f318720b32.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/7c352ac2dae74fdcbebc77a1bb49fc68.png
[27693b391ffb4a3f82718cdf58826836.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/59aac723d4cc4853a6f296ec085b34de.png