# interview **Repository Path**: seekerrc/interview ## Basic Information - **Project Name**: interview - **Description**: No description available - **Primary Language**: Java - **License**: Not specified - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2022-01-17 - **Last Updated**: 2022-08-19 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README ### 链表 #### [206. 反转链表](https://leetcode-cn.com/problems/reverse-linked-list/) **数据结构：链表节点** **算法：双指针** pre, cur。tmp存储下一个节点用于迭代 #### [19. 删除链表的倒数第 N 个结点](https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/) **数据结构：链表节点** **算法：快慢指针** pre设置为dummy，应对删除head的情况。快指针移动n步。这样快指针移动到倒数第一个节点时，慢指针移动到倒数n+1个节点，即可删除第n个。 #### [23. 合并K个升序链表](https://leetcode-cn.com/problems/merge-k-sorted-lists/) **数据结构：链表节点数组** **算法：归并排序** divide为递归，merge为合并函数，就是合并两个升序链表的接口（用到了dummy pre指针） #### [141. 环形链表](https://leetcode-cn.com/problems/linked-list-cycle/) **数据结构：链表节点** **算法：快慢指针** 快指针到链表尾部，退出循环否则一致循环到双指针相遇 #### [142. 环形链表 II](https://leetcode-cn.com/problems/linked-list-cycle-ii/) 快慢指针相遇时退出循环，将fast重置为head，双指针再次相遇即为入口 ### 查找、排序 #### [581. 最短无序连续子数组](https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/) ``` UnsortedSubarray ``` **数据结构：数组指针** **算法：找规律** 从左到右循环，记录最大值为 max，若 nums[i] < max, 则表明位置 i 需要调整, 循环结束，记录需要调整的最大位置 i 为 high; 同理，从右到左循环，记录最小值为 min, 若 nums[i] > min, 则表明位置 i 需要调整，循环结束，记录需要调整的最小位置 i 为 low. #### [215. 数组中的第K个最大元素](https://leetcode-cn.com/problems/kth-largest-element-in-an-array/) **数据结构：数组** **算法：快排，堆排序** ```java PriorityQueue minHeap = new PriorityQueue<>(k, (x, y) -> x - y); public int quickSort(int[] arr, int begin, int end) ``` #### [912. 排序数组](https://leetcode-cn.com/problems/sort-an-array/) **数据结构：数组** **算法：归并排序** 注意点：需要辅助数组，每次将nums数组的对应部分拷贝到tmp，利用tmp比较后覆盖nums ```java public void mergeSort(int[] arr, int left, int right, int[] temp) public void merge(int[] nums, int left, int mid, int right, int[] temp){ System.arraycopy(nums, left, temp, left, right + 1 - left); ... } ``` #### [33. 搜索旋转排序数组](https://leetcode-cn.com/problems/search-in-rotated-sorted-array/) **数据结构：数组** **算法：二分查找** 根据mid和right大小比较，总能确定有序的那一半，根据有序的一半提供的边界判断target的搜索范围 #### [704. 二分查找](https://leetcode-cn.com/problems/binary-search/) 最简单的二分查找 ```java public int search(int[] nums, int target) { int len = nums.length; if(len == 0){ return -1; } int left = 0, right = len - 1; while(left <= right){ int mid = left + (right - left) / 2; if(nums[mid] < target){ left = mid + 1; }else if(nums[mid] > target){ right = mid - 1; }else if(nums[mid] == target){ return mid; } } return -1; } ``` #### [35. 搜索插入位置](https://leetcode-cn.com/problems/search-insert-position/) **二分查找，插入位置模板！！！** ```java public int searchInsert(int[] nums, int target) { // 找到第一个等于或者大于target的索引 int len = nums.length; if(target > nums[len - 1]){ return len; } int left = 0, right = len - 1; while(left < right){ int mid = (left + right) / 2; if(nums[mid] < target){ left = mid + 1; }else{ // 大于等于target的时候，当前mid索引可能就是答案 right = mid; } } return left; } ``` #### [34. 在排序数组中查找元素的第一个和最后一个位置](https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/) 背一下模板，插入位置模板找的是左边界 ```java public int[] searchRange(int[] nums, int target) { if(nums.length == 0) { return new int[]{-1,-1}; } int l = 0, r = nums.length - 1; //二分范围 while(l < r) //查找元素的开始位置 { int mid = (l + r) / 2; if(nums[mid] >= target) { r = mid; }else{ l = mid + 1; } } if(nums[r] != target) { return new int[]{-1,-1}; //查找失败 } int L = r; l = 0; r = nums.length - 1; //二分范围 while( l < r) //查找元素的结束位置 { // 这是个模板，+1的操作背下来 int mid = (l + r + 1)/2; if(nums[mid] <= target) { l = mid; }else{ r = mid - 1; } } return new int[]{L,r}; } ``` ### 二叉树 #### [530. 二叉搜索树的最小绝对差](https://leetcode-cn.com/problems/minimum-absolute-difference-in-bst/) ```java MinimumDifference ``` **数据结构：二叉树** **算法：中序遍历** DFS，将pre节点和res存为成员变量 ### 堆、栈、队列 #### [155. 最小栈](https://leetcode-cn.com/problems/min-stack/) **数据结构：栈** **算法：双栈或者单栈** 双栈：正常栈、单调不增的栈（保证min取得的复杂度是常数级）单栈：min作为成员变量，每次来新的最小值（或者等于最小值）时，先把当前的min入栈便于后续恢复 ### 哈希 #### [1. 两数之和](https://leetcode-cn.com/problems/two-sum/) **数据结构：hashmap** **算法：遍历查找待匹配元素** ### 字符串 #### [415. 字符串相加](https://leetcode-cn.com/problems/add-strings/) **数据结构：字符串、StringBuilder** **算法：右对齐相加，进位** 所谓右对齐：从len - 1开始遍历字符串，越界则设置为0 注：调用StringBuilder的reverse方法翻转顺序 ### 递归回溯 #### [46. 全排列](https://leetcode-cn.com/problems/permutations/) **数据结构：List和visited布尔数组** **算法：DFS** 因为是全排列，DFS中开始的索引是0，用布尔数组去重 ### 动态规划 #### [42. 接雨水](https://leetcode-cn.com/problems/trapping-rain-water/) 数据结构：数组算法：DP 找左右最长板，比较当前索引高度，确定能否盛水 ```java leftMax[i] = Math.max(leftMax[i - 1], height[i - 1]); ``` ### 双指针、滑动窗口 #### [剑指 Offer 48. 最长不含重复字符的子字符串](https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/) ```java LongestSubstring ``` **数据结构：HashMap** key为字符，value为下标索引 **算法：双指针滑动窗口** 如果map中已经存在当前字符，更新最后一个重复字符的索引，子串长度为当前下标-最后一个重复的下标 #### [15. 三数之和](https://leetcode-cn.com/problems/3sum/) **数据结构：排序数组Arrays.sort** **算法：双指针** 根据sum与目标值大小关系，调整双指针位置 **注意点：剪枝、去重** #### [5. 最长回文子串](https://leetcode-cn.com/problems/longest-palindromic-substring/) **数据结构：字符串** **算法：双指针，中心扩散** 两种中心：单一中心、相邻中心，分别求中心扩散的长度如果长度超过当前存储的start和end索引，就更新，注意更新的时候是由中心i和长度len算的，要考虑奇偶，更新公式，不然不能ac #### [3. 无重复字符的最长子串](https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/) **数据结构：hashmap存字符及其索引** **算法：滑动窗口** 双指针：start end，其中start存最后一个重复字符的索引，用Math.max更新 ### 贪心算法 #### [670. 最大交换](https://leetcode-cn.com/problems/maximum-swap/) ```java MaximumSwap ``` **数据结构：数组** 字符数组 **算法：贪心算法** 用一个数组从后往前记录比当前索引更大的数的索引，这样交换的数尽可能靠右；然后从前往后遍历，交换小的数，这样交换的数尽可能靠左； ### 设计 #### [146. LRU 缓存](https://leetcode-cn.com/problems/lru-cache/) ``` LRUCache ``` **数据结构：双向链表（自己写节点）+hashmap** hashmap实现CRUD的常量复杂度，双向链表实现节点的排序 hashmap的key为key，value为包装键值对的node **算法：同步修改** #### [1195. 交替打印字符串](https://leetcode-cn.com/problems/fizz-buzz-multithreaded/) ``` CyclicBarrier ReentrantLock ``` #### [1116. 打印零与奇偶数](https://leetcode-cn.com/problems/print-zero-even-odd/) ``` Semaphore ReentrantLock ```