leetcode刷题总结 数据结构与算法代码实现
数组 联想关键词
排序 双指针、三指针 扫描方向（左->右、右->左）
1. 遍历时需要用到其余位置的值，或者该位置的值此前是否被访问过 可以考虑使用HashMap进行存储 （哈希表时间复杂度为1），key或者value进行存储值 ，map中没有则put进去，有的话就取出来使用。
Map<Integer,Integer> map = new HashMap<Integer, Integer>(); int length = nums.length;for (int i = 0 ; i < length; i++) { if (map.containsKey(value)) { } map.put(nums[i],i); }
2. 数组题，一般就是左到右或者右到左扫描，通常我们就需要使用双指针，甚至三指针 例如颜色分类排序中，head指针把将小的放前面，tail指针把大的放后面 ，cur指针从头到尾来扫描
int head = 0 ;int tail = nums.length - 1 ;int cur = head;while (cur <= tail) { if (nums[cur] == 0 ) { swap(nums, cur, head); head++; cur++; } else if (nums[cur] == 2 ) { swap(nums, cur, tail); tail--; } else { cur++; } }
3. 可以先排序，再进行求解 例如三数之和中，先排序，再依次找两个数相加，少了往右走，多了就往左走
for (int i = 0 ; i <= nums.length - 3 ; i++) { if (i > 0 && nums[i] == nums[i - 1 ]) { continue ; } int l = i + 1 ; int r = nums.length - 1 ; while (l < r) { int sum = nums[l] + nums[r]; if (sum == -nums[i]) { List<Integer> list = new ArrayList<>(); list.add(nums[i]); list.add(nums[l]); list.add(nums[r]); resultList.add(list); while (l < r && nums[l] == nums[l + 1 ]) l++; while (l < r && nums[r] == nums[r - 1 ]) r--; l++; r--; } else if (sum < -nums[i]) { l++; } else { r--; } } }
4. 求两个有序数组，有序合并后第k大个数
即使不是有序的，也可以先排序 这类题也跟中位数差不多，也是求第几个大的数
可以使用分治/或者说是二分 思想，使得时间复杂度到O(log (m+n))。
（1）找第k大数，两数组有序，则可以每次排除其中一个数组k / 2个数，或者整个数组 。
（2）如何确定排除哪个数组，则看边界上的值。
if (nums1[begin1 + mid - 1] <= nums2[begin2 + mid - 1])
如果数组临界k/2的值比另一个数组边界值要小一些，则前面的都要小，可以排除，begin往前走 。
if (m == 0 ) { return nums2[begin2 + k - 1 ]; } if (k == 1 ) { return Math.min(nums1[begin1], nums2[begin2]); } int mid = Math.min(m, k / 2 );if (nums1[begin1 + mid - 1 ] <= nums2[begin2 + mid - 1 ]) { begin1 = begin1 + mid; } else { begin2 = begin2 + mid; } return findKth(nums1, begin1, end1, nums2, begin2, end2, k - mid);
链表 链表结题技巧
虚拟头结点 快慢指针（求中间节点） 双指针 链表翻转 检验边界情况：头、尾，传入一个节点进来处理，处理全部的节点
1. 双链表长度不一需要对位比较或者处理 两个数用链表存储例如345（3->4->5）和6789（6->7->8->9）相加，则将短的链表高位空位置为0
例：345（0->3->4->5）
int x = l1 == null ? 0 : l1.val;int y = l2 == null ? 0 : l2.val;
并且虚拟头结点newHead保存结果链表的开头，newHead的next才开始存储数据，然后 return newHead.next; 或者newHead.next开始遍历
ListNode newHead = new ListNode(0 ); ListNode newTail = newHead; return newHead.next;
2. 链表分隔 以某一值x，来分割链表，所有小于 x 的节点排在大于或等于 x 的节点之前，链表中包含 x，x 只需出现在小于 x 的元素之后。
思路：只需要使用双指针，类似于荷兰国旗题，小的挂在左尾指针后，大的挂在右尾指针后，最后连接左右两条链表即可。
ListNode leftTail = leftHead; ListNode rightTail = rightHead;
连接左右两条链表
leftTail.next = rightHead.next; rightTail.next = null ;
3. 反转链表（默写）
思路：递归的思路很简单，就是把除了这个节点后面的反转后，然后指向这个节点，一直到最后一个节点，或者传进来就是null。
if (head == null || head.next == null ) { return head; } ListNode newHead = reverseList(head.next); head.next.next = head; head.next = null ; return newHead;
思路：只有一个head能用，所以就只能从head入手一个一个串起来，加一个指针newhead来实现。
ListNode newhead = null ; while (head != null ) { ListNode temp = head.next; head.next = newhead; newhead = head; head = temp; }
4. 快慢指针（解决有环、对称、中间节点的问题） 4.1 解决是否有环问题 顾名思义即一个走一步，而另一个走两步。low = low.next; fast = fast.next.next;
注意：
while (fast != null && fast.next != null)，在while条件是加个fast.next的判断，避免null.next情况出现 。开始最好设置low为一个head，而另一个fast为下一位，这样才能使我们low == fast只在有环时成立
if (head == null || head.next == null ) { return false ; } ListNode low = head; ListNode fast = head.next; while (fast != null && fast.next != null ) { if (low == fast) { return true ; } low = low.next; fast = fast.next.next; } return false ;
4.2 对称问题（求中间节点，默写） ListNode slow = head; ListNode fast = head.next; while (fast != null && fast.next != null ) { fast = fast.next.next; slow = slow.next; } return slow;
5. 遍历时该位置的值此前是否被访问过，或者需要用到其余位置的值 之前我们在数组时有这种思想采用hash表实现，时间复杂度为O（1）
判断链表是否有环，我们基本上能想到就是快慢指针，但是其实我们只需遍历一遍判断 某个位置的值此前被访问过 即可判断有环 ，因为链表没有索引，所以就用hash表实现的列表（无重复的值）HashSet。
Set<ListNode> set = new HashSet<>(); ListNode node = head; while (node.next != null ) { if (set.contains(node)) { return true ; } set.add(node); node = node.next; } return false ;
6. while循环遍历，条件是head.next != null 还是 head != null 主要是看后面循环体里面是否有head的next相关的赋值，保证没有null.next 。
例如：这里不仅有fast.next而且还有fast.next.next，所以就两个条件都要满足
while (fast != null && fast.next != null ) { ...... fast = fast.next.next; }
栈、队列 联想关键词
1. 栈实现二叉树非递归遍历 非递归进行前序、中序、后序遍历，条件为：一直向左走，访问左节点，然后回来访问根结点。 所以就可以用栈来实现
Node<E> node = root; Stack<Node<E>> stack = new Stack<>(); while (true ) { if (node != null ) { if (visit(node.element)) { return ; } if (node.right != null ) { stack.push(node.right); } node = node.left; } else if (stack.isEmpty()){ return ; } else { node = stack.pop(); } }
2. 单调栈实现某值左右（或者左右其中一个）第一个最值 要通过遍历，使得找到某值左右（或者左右其中一个）的第一个最值，可以使用单调栈
例如：找到最大二叉树的每个节点的父节点索引
Stack<Integer> stack = new Stack<>(); for (......) { if (!stack.isEmpty() && nums[i] < nums[stack.peek()]) { leftIndexes[i] = stack.peek(); } while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) { rightIndexes[stack.peek()] = i; } stack.push(i); }
3. 单调双端队列实现一段区间内的最大、最小值和排序 要通过遍历，使得比它大（小）的值在最前面取，小（大）的值删也是删前面的，添加都是放后面的，所以遍历就保证了单调递减（递增），从而找到这个队列区间的元素的最值。
例：滑动的窗口的最值问题
for (......) { while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i] ) { deque.pollLast(); } deque.offerLast(i); maxes[w] = nums[deque.peekFirst()]; }
字符串 1. Java语言方面 String是个字符对象，其引用时指向字符串常量池中的一个字符数组char数组，所以最好每次先把String转成char[]，并且长度附一个变量，不用每次都调用方法。例如：
int length = s.length();char [] chars = s.toCharArray();
2. 循环移位子串 某一部分相等，字符串的子串问题，且发现子串是循环移位且满足时钟周期的特点， 所以拼接多个时钟周期(比如两个原串)。
比如water -> aterw，waterwater中就出现了子串
3. 树找子树 树找子树，很显然就是遍历出来，找到子树（子串），就类似于字符串寻找子串的问题，所以只需将其序列化成字符串。
注意：树序列化过程中，例如 !3!4!1!#!#!2!#!#!5 里面找 !4!1!#!#!2!#!#
（1） 最好用特殊符号来表示null，并且用再用一个字符隔开，不然出现问题
（2） 就转换成了一个找子串的问题
二叉树 联想关键词 树的题目一般都是通过：
1. 完全二叉树性质 完全二叉树的n1要么是0，要么是1（节点按序号排列），则由通用性质：n = 2n0 + n1 - 1
n1为0，则n = 2n0 - 1，n为奇数，叶子节点n0 =（n + 1）/ 2，非叶子节点n1 + n2 = （n - 1）/ 2
n1为1，则n = 2n0，n为偶数，叶子结点n0 = n / 2，非叶子节点n1 + n2 = n / 2
2. 二叉树遍历应用
前序遍历：树状结构 的展示（注意左右子树的顺序）
中序遍历：二叉搜索树的中序遍历按升序或者降序处理节点 后序遍历：适用于一些先子后父的操作
层序遍历：计算二叉树的高度，判断一棵树是否为完全二叉树
3. 判断二叉树结构 可以采用序列化成字符串 ，即前、中、后序遍历成字符串，加上！和 # 来作为分隔和空节点 。再采用字符串的算法，进行匹配，相等。
4. 二叉搜索树BST 看到这个敏感词二叉搜索树，一般不出意外就要用到它的性质：中序遍历是个升序的序列，或者递归判断是否为BST树（左右是否为，根大于左，小于右）。
递归 + 回溯 1. 二叉树 一般链表或者二叉树的问题都可以使用递归的思想，因为链表和二叉树的结构，本身就是递归的结构，即二叉树里面还是二叉树。
**树的题都是递归 + 遍历解决。**例如：寻找最大的BST子树
public int largestBSTSubtree (TreeNode root) if (root == null ) { return 0 ; } if (isBST(root)) { return nodesCount(root); } return Math.max(largestBSTSubtree(root.left), largestBSTSubtree(root.right)); }
2. DFS DFS的递归题目：排列组合，解决方法：递归 + 回溯例如：求二叉树的路径总和等于某值时
public List<List<Integer>> pathSum(TreeNode root, int sum) { List<List<Integer>> list = new ArrayList<>(); if (root == null ) { return list; } dfs(root, sum, new ArrayList<>(), list); return list; } private void dfs (TreeNode node, int sum, List<Integer> result, List<List<Integer>> list) if (node == null ) { return ; } sum -= node.val; result.add(node.val); if (node.left == null && node.right == null ) { if (sum == 0 ) { list.add(new ArrayList<>(result)); } } else { dfs(node.left, sum, result, list); dfs(node.right, sum, result, list); } result.remove(result.size() - 1 ); }
3. 回溯 树和图的DFS就是典型的回溯，而且回溯本质就是使用递归来实现 ，例如八皇后和走迷宫。
经典N皇后问题优化 回溯 + 剪枝处理，剪枝即剪去肯定错误的位置时（同一列，在其对角线上），使用三个标记数组来实现。以空间换时间，不用每次都用O（n）复杂度
for (int col = 0 ; col < n; col++) { if (cols[col]) { continue ; } int leftIndex = n - 1 - col + row; int rightIndex = row + col; if (leftTop[leftIndex] || rightTop[rightIndex]) { continue ; } queens[row] = col; cols[col] = true ; leftTop[leftIndex] = true ; rightTop[rightIndex] = true ; place(row + 1 ); cols[col] = false ; leftTop[leftIndex] = false ; rightTop[rightIndex] = false ; }
针对特定的数值（例如八皇后）每一位只有两种结果，可以使用位运算来优化（存在为1，不存在为0）byte cols;short leftTop;short rightTop;if ((cols & (1 << col)) != 0 ) { continue ; } int leftIndex = n - 1 - col + row;int rightIndex = row + col;if ((leftTop & (1 << leftIndex)) != 0 || (rightTop & (1 << rightIndex)) != 0 ) { continue ; } cols = (byte )(cols | (1 << col)); leftTop = (byte )(leftTop | (1 << leftIndex)); rightTop = (byte )(rightTop | (1 << rightIndex)); cols = (byte )(cols & ~(1 << col)); leftTop = (byte )(leftTop & ~(1 << leftIndex)); rightTop = (byte )(rightTop & ~(1 << rightIndex));
4. 递归转迭代 递归是从大的值推出小的值，例如f（10）-> f（9），但是如果我们知道递推关系式，且初始值知道，就可以从小一层一层推出大的值，就可以迭代。例如斐波那契数列、约瑟夫环问题（递推公式法）。public int lastRemaining1 (int n, int m) if (n == 1 ) { return 0 ; } int result = 0 ; for (int i = 2 ; i <= n; i++) { result = (result + m) % i; } return result; }
动态规划 动态规划一般求解最优问题的一种算法策略，后面的解与前面的状态有关，步骤为三步：
定义dp[i]的含义
设置初始状态（边界）
确定状态转移方程：dp[i]与dp[i - 1]的关系
联想关键词
1. dp[i]对于数组、字符序列来说，一般定为以该值（nums[i]）结尾的满足条件的序列 例如：求最长上升（递增）子序列的长度，dp为以nums[i]结尾的...长度dp[0 ] = 1 ; int maxLength = 1 ;for (int i = 1 ; i < nums.length; i++) { dp[i] = 1 ; for (int j = i - 1 ; j >= 0 ; j--) { if (nums[i] > nums[j]) { dp[i] = Math.max(dp[i], dp[j] + 1 ); } } maxLength = Math.max(dp[i], maxLength); }
2. dp[i,j]还可以是多元的，例如两个数组序列的公共问题 int [][] dp = new int [2 ][nums2.length + 1 ];for (int i = 1 ; i <= nums1.length; i++) { int prevRow = (i - 1 ) & 1 ; int row = i & 1 ; for (int j = 1 ; j <= nums2.length; j++) { if (nums1[i - 1 ] == nums2[j - 1 ]) { dp[row][j] = dp[prevRow][j - 1 ] + 1 ; } else { dp[row][j] = Math.max(dp[prevRow][j], dp[row][j - 1 ]); } } }
3. 优化成一维数组 每行的值都是从左向右赋值的，可以将二维优化成一维数组for (int row = 1 ; row < rows; row++) { for (int col = 0 ; col < cols; col++) { if (col == 0 ) { dp[0 ] = 0 ; int j = row; while (j >= 0 ) { dp[col] += grid[j][0 ]; j--; } } else { dp[col] = Math.max(dp[col], dp[col - 1 ]) + grid[row][col]; } } }
排序 各种排序时间复杂度
1. 分割区间最好左闭右开[begin, end) 有利于计算区间长度`length = end - begin;`，保证了mid的取值。
例如归并排序中：int mid = (begin + end) >> 1 ;sort(begin,mid); sort(mid,end); merge(begin,mid,end);
2. 冒泡排序和插入排序优化 冒泡排序：加入endIndex记录**最后一次交换位置（后面的就不用去冒泡了）**，初始值为完全有序时的下标为，即1int endIndex = 1 ;for (int begin = 1 ; begin <= end; begin++) { if (cmp(begin,begin - 1 ) < 0 ) { swap(begin,begin - 1 ); endIndex = begin; } end = endIndex; }
插入排序（打扑克排序）：时间复杂度与**逆序对**个数成正比
优化：
（重点）先将待插入的数据备份，挪动前面的元素后，再插入 （进阶） 利用二分搜索，优化了比较的次数 ，但是挪动没变，时间复杂度没变
for (int begin = 1 ; begin < array.length; begin++) { int cur = begin; E element = array[begin]; while (cur > 0 && cmp(cur, cur - 1 ) < 0 ) { swap(cur, cur - 1 ); array[cur] = array[cur - 1 ]; cur--; } array[cur] = element; E element = array[begin]; int insertIndex = search(begin); for (int i = begin - 1 ; i >= insertIndex; i--) { array[i + 1 ] = array[i]; } array[insertIndex] = element; }
3. 归并排序合并时避免，讨论右结束时左全挪动情况 即`ri = re`时，仍然是左边数组进行搬运，如代码 else块 所示，`ri = re`时`array[ai] = leftArray[li];`for (int i = li; i < le; i++) { leftArray[i] = array[begin + i]; } while (li < le) { if (ri < re && cmp(leftArray[li], array[ri]) > 0 ) { array[ai] = array[ri]; ai++; ri++; } else { array[ai] = leftArray[li]; ai++; li++; } }
4. 快排轴点随机设置，优化算法避免两边不均匀 int length = end - begin;swap(begin,begin + (int ) (Math.random() * length)); E pivot = array[begin];
数学 1. 快速幂解决Pow(x, n) 3^21 = 3^(1*2^0 + 0*2^1 + 1*2^2 + 0*2^3 + 1*2^4)
= 3^2^0 * 3^2^2 * 3^2^4
public double myPow1 (double x, int n) double res = 1.0 ; long y = n; if (n < 0 ) { y = -((long )n); } while (y > 0 ) { if ((y & 1 ) == 1 ) { res *= x; } x = x * x; y = y >> 1 ; } return (n < 0 ) ? (1 / res) : res; }
2. 快速幂补充 x^y%z 可能x、y都是很大的整数，导致乘法就会溢出，则(a * b) % p = ((a % p) * (b % p)) % p
3. 约瑟夫环公式 公式推导：f(n, m) = (f(n - m, m) + m) % n
哈希 哈希表，不考虑顺序、不考虑 Key 的可比较性（指的是不需要元素之间有大小顺序，而不是不能判断相等与否） 。
数组实现，典型的空间换时间， HashMap底层的hash函数。
联想关键词
1. LRU：哈希表 + 双向链表 这是一种经典的数据结构，在jdk1.8之前，Java中的HashMap采取这种数据结构存储
LRU：最近最少使用，这种页面置换算法，我们可以采取哈希表 + 双向链表 实现，在Java中有LinkedHashMap ，就是这种结构。
哈希表（存储数据）：因为缓存中存储的不是个值，键值对key-value，所以需要二维的存储
双向链表（存储顺序）：使用双向链表的目的是（1）能够在头部插入节点 （2）删除能删除尾结点
public int get (int key) Node node = map.get(key); if (node == null ) { return -1 ; } removeNode(node); addAfterFirst(node); return node.value; } private void removeNode (Node node) node.prev.next = node.next; node.next.prev = node.prev; } private void addAfterFirst (Node node) node.next = first.next; first.next.prev = node; first.next = node; node.prev = first; } public void put (int key, int value) Node node = map.get(key); if (node != null ) { node.value = value; removeNode(node); addAfterFirst(node); } else { if (map.size() == capacity) { Node remove = map.remove(last.prev.key); removeNode(remove); } map.put(key, node = new Node(key, value)); addAfterFirst(node); } }
堆 堆，操作一个排序好的数据，例如最大值，最小值 ，O（1）级别，用数组存放，用二叉搜索树则杀鸡用牛刀。
1. 优先队列 优先队列，每次拿取一组数据的最值 （例如：最小的，最大的），所以就可以采用大顶堆、小顶堆 来实现。
Trie 字典树，对一堆不重复 字符串进行前缀搜索，效率只跟字符串长度有关 。
并查集 1. 尽量使用Quick Union基于路径分裂/路径减半 + 基于rank优化或者size优化 实质上：基于路径分裂/路径减半优化find、基于rank优化或者size优化union
（1）不使用路径压缩是因为虽然树高度降低离谱，但是成本很高，每个节点都要压缩 。
if (v != parents[v]) { int parent = parents[v]; parents[v] = parents[parent]; v = parent; } return v;if (v != parents[v]) { parents[v] = parents[parents[v]]; v = parents[v]; } return v;
（2）基于rank的优化更好一点，避免数过高
if (sizes[p1] < sizes[p2]) { parents[p1] = p2; sizes[p2] += sizes[p1]; } else { parents[p2] = p1; sizes[p1] += sizes[p2]; } if (ranks[p1] < ranks[p2]) { parents[p1] = p2; } else if (ranks[p1] > ranks[p2]){ parents[p2] = p1; } else { parents[p1] = p2; ranks[p2]++; }
贪心 分治 1. Pow(x, n) 使用递归分治 解决：x^n = x^(n/2) * x^(n/2)
陷阱：n可能为负数，负数分治到最后会到-1，而-1 >> 1还是-1，则-1需要直接返回
public double myPow (double x, int n) if (n == 0 ) { return 1 ; } if (n == -1 ) { return 1 / x; } boolean flag = (n & 1 ) == 1 ; double half = myPow(x, n >> 1 ); return flag ? half * half * x : half * half; }
