一趟结束后能够确定一个元素的最终位置的排序方法有： 简单选择排序、快速排序、冒泡排序、堆排序
稳定性定义：排序前后两个相等的数相对位置不变，则算法稳定。
数据结构 search insert delete
数组 O(n)，有序数组折半查找是O(lgn) O(n) O(n)
双向链表 O(n) O(1) O(1)
排序二叉树 O(lgn) O(lgn) O(lgn)
哈希表（n与槽数m成正比）O(1) O(1) O(1)-
快速排序算法:
public static int[] qsort(int arr[],int start,int end) { int pivot = arr[start]; int i = start; int j = end; while (i<j) { while ((i<j)&&(arr[j]>pivot)) { j--; } while ((i<j)&&(arr[i]<pivot)) { i++; } if ((arr[i]==arr[j])&&(i<j)) { i++; } else { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } if (i-1>start) arr=qsort(arr,start,i-1); if (j+1<end) arr=qsort(arr,j+1,end); return arr; }
-
归并排序(左右分治)：
/** * 归并排序 * * @param arr */ public static void mergeSort(int[] arr) { process(arr, 0, arr.length - 1); } /** * 对lr范围内进行左右分别排序，使中点左右两边都有序 * * @param arr * @param l * @param r */ public static void process(int[] arr, int l, int r) { if (l == r) return; int mid = (l + r) / 2; process(arr, l, mid); process(arr, mid + 1, r); merge(arr, l, r); } /** * 使用辅助数组对已经左右拍好序的数组进行整体排序 * * @param arr * @param l * @param r */ public static void merge(int[] arr, int l, int r) { int[] helpArr = new int[r - l + 1]; int mid = (r + l) / 2; int p = l; int q = mid + 1; int index = 0; while (p <= mid && q <= r) { helpArr[index++] = arr[p] < arr[q] ? arr[p++] : arr[q++]; } //左右一定有一个越界 while (p <= mid) { helpArr[index++] = arr[p++]; } while (q <= r) { helpArr[index++] = arr[q++]; } if (helpArr.length >= 0) System.arraycopy(helpArr, 0, arr, l, helpArr.length); }归并排序的*Master公式=T(N)=a*T(N/b)+O(N^d)==T(N)=2T(N/2)+O(N) **
大顶堆：(根节点的关键字既大于等于左子树的关键字值，同时也大于等于右子树的关键字值)
小顶堆：(根结点的键值是所有堆结点键值中最小者)
典例
-
4的幂：
这个题和“2的幂”“3的幂”一样，有不用循环和递归就能直接判断的方法，同样十分巧妙，属于二进制/位运算的应用。 4的幂的数，都是这样的数：100、10000、1000000……（4、16、64） 观察规律，可以发现 4的幂 需要满足以下条件： 最高位是 1，其余都为 0； 最高位的 1 应该在奇数位上，比如：100 的 1 在 第三位上； 那么对应的判断方法为： 用 num & (num-1) 可以判断条件1，比如：100(4) & 011(3) == 0，结果为 0 说明符合条件1； 是否在奇数位可以用 0xaaaaaaaa 判断，16 进制的 a 是 1010，比如：0100(4) & 1010(a) == 0，结果为 0 说明最高位 1 在奇数位上； public boolean isPowerOfFour(int n) { return n > 0 && (n & (n - 1)) == 0 && ((n & 0x55555555) == n); // if (n<0) return false; // if ((n&(n-1))!=0) return false; 判断是否位2的幂次方 // return (n & 0x55555555) == n; 判断1是否在奇数位上 }
-
两个数相乘：
public static String multiply2(String num1, String num2) { int len1 = num1.length(); int len2 = num2.length(); int[] res = new int[len1 + len2]; for (int i = len1 - 1; i >= 0; i--) { for (int j = len2 - 1; j >= 0; j--) { int LowPos = i + j + 1; int highPos = i + j; int temp = (num1.charAt(i) - '0') * (num2.charAt(j) - '0') + res[LowPos]; res[LowPos] = (temp) % 10; res[highPos] += temp / 10; //这里高位不要取mod } } StringBuilder sb = new StringBuilder(); for (int i : res) { if (!(sb.length() == 0) && i == 0) sb.append(i); } return sb.length() == 0 ? "0" : sb.toString(); }
-
二叉树的公共祖先：
-
最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
[图片上传失败...(image-2faa57-1585194160478)]
-
class Solution { /* 算法思想,当递归到的节点为p1或p2时候,则将该节点向上传递, 使其父节点变成其本身,如果一个节点下方没有p1/p2,则向上传递null,使父节点为null, 当左右节点分别是p1,p2时则说明该节点是目标节点，向上传递, 该目标节点对应的兄弟节点经过递归后一定为null(因为兄弟节点的子节点中不存在p1/p2只能向上传递null), 最终目标顶点传递至根节点。 */ public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p1, TreeNode p2) { if (root == null || root == p1 || root == p2) return root; TreeNode left = lowestCommonAncestor(root.left, p1, p2); TreeNode right = lowestCommonAncestor(root.right, p1, p2); if (left == null && right == null) return null; if (left == null || right == null) return left == null ? right : left; return root; } }-
括号生成
-
给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
例如，给出 n = 3，生成结果为：
[ "((()))",
"(()())",
"(())()",
"()(())",
"()()()"] public List<String> generateParenthesis(int n) { List<String> res = new ArrayList<>(); generate(res, "", 0, 0, n); return res; } //count1统计“(”的个数，count2统计“)”的个数 public void generate(List<String> res, String ans, int count1, int count2, int n) { if (count1 > n || count2 > n) return; if (count1 == n && count2 == n) res.add(ans); /*核心点: count1>=count2 , 从左往右添加,只有满足左边括号数量>=右边括号时候, 才能够满足题意,否则会出现括号不匹配的情况 */ if (count1 >= count2) { generate(res, ans + "(", count1 + 1, count2, n); generate(res, ans + ")", count1, count2 + 1, n); } }
-
-
BFS:
- [图片上传失败...(image-26fb97-1585194160478)]
# 广度遍历 graph = { "A": ["B", "C"], "B": ["A", "C", "D"], "C": ["A", "B", "D", "E"], "D": ["B", "C", "E", "F"], "E": ["C", "D"], "F": ["D"] } def BFS(graph, s): queue = [] # 使用动态数组作队列 queue.append(s) seen = set() while (len(queue) > 0): vertex = queue.pop(0) # 每次取队列中的第一个再进行添加 seen.add(s) nodes = graph[vertex] for w in nodes: if w not in seen: queue.append(w) seen.add(w) print(vertex) BFS(graph, "A") -
DFS
# 深度遍历 graph = { "A": ["B", "C"], "B": ["A", "C", "D"], "C": ["A", "B", "D", "E"], "D": ["B", "C", "E", "F"], "E": ["C", "D"], "F": ["D"] } def DFS(graph, s): queue = [] # 使用动态数组作栈 queue.append(s) seen = set() seen.add(s) parent = {s: None} # <子节点:父节点> while (len(queue) > 0): vertex = queue.pop() nodes = graph[vertex] for w in nodes: if w not in seen: parent[w] = vertex queue.append(w) seen.add(w) print(vertex) return parent if __name__ == "__main__": print (DFS(graph,"A"))
-
使用BFS求最短路径(Dijkstra)：
[图片上传失败...(image-a1078d-1585194160478)]
import heapq # 权限比队列 import math graph = { "A": {"B": 5, "C": 1}, "B": {"A": 5, "C": 2}, "C": {"A": 1, "B": 2, "D": 4}, "D": {"B": 1, "C": 4, "E": 3, "F": 6}, "E": {"C": 8, "D": 3}, "F": {"D": 6} } def init_distance(graph, s): distance = {s: 0} for vertex in graph.keys(): if vertex != s: distance[vertex] = math.inf return distance def dijkstra(graph, s): pqueue = [] # prorityqueue 具有权重比的队列，权重高的排前面 heapq.heappush(pqueue, (0, s)) seen = set() parent = {s: None} distance = init_distance(graph, s) while(len(pqueue) > 0): pair = heapq.heappop(pqueue) dist = pair[0] # 取出来的点到s的距离 vertex = pair[1] seen.add(vertex) nodes = graph[vertex].keys() for w in nodes: if w not in seen: if dist+graph[vertex][w] < distance[w]: distance[w] = dist+graph[vertex][w] heapq.heappush(pqueue, (dist+graph[vertex][w], w)) parent[w] = vertex return parent, distance parent, distance = dijkstra(graph, "A") print(parent) print(distance)-
两个数之间的所有数相与：
public static int rangeBitwiseAnd(int m, int n) { int count = 0; while (n != m) { n >>= 1; m >>= 1; count++; } return n << count; }
-
最大正方形
-
在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
示例:输入:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0输出: 4
//dp[i][j]为以[i][j]为右下角坐标的最长正方形边长 class Solution { public int maximalSquare(char[][] matrix) { if (matrix==null||matrix.length==0) return 0; int m = matrix.length; int n = matrix[0].length; int[][] dp = new int[m][n]; int res = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (matrix[i][j] == '1' && (i == 0 || j == 0)) { dp[i][j] = 1; }else if (matrix[i][j] == '1') { dp[i][j] = 1 + Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])); } res = Math.max(dp[i][j] * dp[i][j], res); } } return res; } }
-
LeetCode 395题：至少有K个重复字符的最长子串
找到给定字符串（由小写字符组成）中的最长子串 T ， 要求 T 中的每一字符出现次数都不少于 k 。输出 T 的长度。 示例 1: 输入: s = "aaabb", k = 3 输出: 3 最长子串为 "aaa" ，其中 'a' 重复了 3 次。 示例 2: 输入: s = "ababbc", k = 2 输出: 5 最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。题解(递归+分治)：
class Solution {
public int longestSubstring(String s, int k) {
if (s.length() < k) return 0;
return countLongestSubstring(s.toCharArray(), 0, s.length() - 1, k);
}
private int countLongestSubstring(char[] chars, int l, int r, int k) {
int[] count = new int[26];
for (int i = l; i <= r; i++) {
count[chars[i] - 'a']++;
}
//使得左右指针所在位置的字符满足条件(两指针之间仍然可能存在不满足条件的字符)
while (r - l + 1 >= k && count[chars[l] - 'a'] < k) l++;
while (r - l + 1 >= k && count[chars[r] - 'a'] < k) r--;
//当筛选完毕后如果长度不满足K则返回0
if (r - l + 1 < k) return 0;
//对初筛满足条件的子串进行遍历，出现不满足条件的字符，以字符为分割，左右继续递归查询，直到满足所有的count[chars[i] - 'a']都>=K则 返回 r - l + 1
for (int i = l; i < r; i++) {
if (count[chars[i] - 'a'] < k) {
return Math.max(countLongestSubstring(chars, l, i - 1, k), countLongestSubstring(chars, i + 1, r, k));
}
}
return r - l + 1;
}
}
计算完全二叉树的节点个数并且且时间复杂度小于O(N)
[图片上传失败...(image-86a6b8-1585194160478)]
-
lcs 最长公共子串：
[图片上传失败...(image-9fb531-1585194160478)]
-
//lrc 最长公共子串 public int longestCommonSubsequence(String text1, String text2) { int[][] dp = new int[text1.length()][text2.length()]; for (int i = 0; i < text1.length(); i++) { for (int j = 0; j < text2.length(); j++) { boolean b = text1.charAt(i) == text2.charAt(j); if (i != 0 && j != 0) { if (b) dp[i][j] = dp[i - 1][j - 1] + 1; else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); } else { if (b) dp[i][j] = 1; else { if (i == 0 && j == 0) continue; if (i == 0) dp[i][j] = dp[i][j - 1]; else dp[i][j] = dp[i - 1][j]; } } } } return dp[text1.length() - 1][text2.length() - 1]; }更优解法：
public int longestCommonSubsequence(String text1, String text2) { int n1 = text1.length(), n2 = text2.length(); int[][] dp = new int[n1 + 1][n2 + 1]; for (int i = 1; i <= n1; i++) { for (int j = 1; j <= n2; j++) { if (text1.charAt(i - 1) == text2.charAt(j - 1)) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[n1][n2]; }LIS 最长上升子序列：
//给定一个无序的整数数组，找到其中最长上升子序列的长度。 class Solution { public int lengthOfLIS(int[] nums) { if (nums.length == 0) return 0; int[] dp = new int[nums.length]; dp[0] = 1; for (int i = 1; i < nums.length; i++) { int tempMax = 0; for (int j = i - 1; j >= 0; j--) { if (nums[i] > nums[j]) { tempMax = Math.max(tempMax, dp[j]); } } dp[i] = tempMax + 1; } int res = 0; for (int i : dp) { if (i > res) res = i; } return res; } }
lcs 712 两个字符串的最小ascll删除和：
//最大公共子串 且 要求这些公共子串的 ascii 值最大。 public int minimumDeleteSum(String s1, String s2) { int sum = 0; for (int i = 0; i < s1.length(); i++) sum += s1.charAt(i); for (int i = 0; i < s2.length(); i++) sum += s2.charAt(i); if (s1.length() == 0 || s2.length() == 0) return sum; int[][] dp = new int[s1.length() + 1][s2.length() + 1]; int max_lcs_sum = 0; for (int i = 1; i <= s1.length(); i++) { for (int j = 1; j <= s2.length(); j++) { if (s1.charAt(i - 1) == s2.charAt(j - 1)) { dp[i][j] = dp[i - 1][j - 1] + s1.charAt(i - 1); } else { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); } max_lcs_sum = Math.max(dp[i][j], max_lcs_sum); } } return sum - 2 * max_lcs_sum; }-
279 完全平方数:
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。 示例 1: 输入: n = 12 输出: 3 解释: 12 = 4 + 4 + 4.//最小值公式f(n)=常数i+j*j (需要满足条件i-j*j>=0,不能越界) //而f(j*j)=1 //所以f(n)=f(i)+f(j*j)=f(i)+1 //bfs遍历所有可能的i j组合 //取每次遍历的最小值情况 //dp[i]=Math.min(dp[i],dp[i-j*j]+dp[j*j]); public int numSquares(int n) { int[] dp = new int[n + 1]; for (int i = 0; i <= n; i++) { //默认的每个数都是由全部1组成 dp[i] = i; //bfs操作 for (int j = 0; i - j * j >= 0; j++) { dp[i] = Math.min(dp[i], dp[i - j * j] + 1); } } return dp[n]; }
-
376,摆动序列（线性DP）
public int wiggleMaxLength(int[] nums) { if(nums.length<2) return nums.length; int low = 1; int high = 1; for (int i = 1; i < nums.length; i++) { //起始位高低位都为1. //保证了在连续上升/下降的情况下 high/low 不会重复递增， //在上升情况中，只要没有发生坡度中断，则high对应的low不会发生改变。那么high位就不会发生改变。 if (nums[i] > nums[i - 1]) high = low+1; if (nums[i] < nums[i - 1]) low = high+1; } return Math.max(low, high); }
-
汉诺塔问题(每次移动顶部的，并且不能大压小)
public void hanoti(int N,String from,String to,String help){ if(N==1) System.out.println("Move 1 from" + from + "to" +to ); else{ hanoti(N-1,from,help,to); System.out.println("Move"+N+"from" + from + "to" +to ); hanoti(N-1,help,to,from); } }
-
502题IPO
public int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) { IpoNode[] ipoNodes = new IpoNode[Profits.length]; PriorityQueue<IpoNode> MinCostHeap = new PriorityQueue<>(comparingInt(o -> o.cost)); PriorityQueue<IpoNode> MaxProfitHeap = new PriorityQueue<>(comparingInt(o -> -o.profit)); for (int i = 0; i < ipoNodes.length; i++) { ipoNodes[i] = new IpoNode(Capital[i], Profits[i]); MinCostHeap.add(ipoNodes[i]); } for (int i = 0; i < k; i++) { while (MinCostHeap.size() > 0 && MinCostHeap.peek().cost <= W) MaxProfitHeap.add(MinCostHeap.poll()); if (MaxProfitHeap.size() > 0) W += MaxProfitHeap.poll().profit; } return W; } class IpoNode { public int cost; public int profit; public IpoNode(int cost, int profit) { this.cost = cost; this.profit = profit; } }
-
1277 统计全为1的正方形子矩阵：
-
核心在于加上每次的边长 因为当出现长的边长,说明以该右下角为正方形几个新的小正方形也同时出现了, 比如3, res+3意味着加了边长为3和边长为2和边长为1这三个正方形。class Solution { public int countSquares(int[][] matrix) { if (matrix == null || matrix.length == 0) return 0; int m = matrix.length; int n = matrix[0].length; int[][] dp = new int[m][n]; int res = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (matrix[i][j] == 1 && (i == 0 || j == 0)) { dp[i][j] = 1; } else if (matrix[i][j] == 1) { dp[i][j] = 1 + Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])); } //直接将每一个正方形的边长加上来 res += dp[i][j]; } } return res; } }
-
-
894,所有可能的满二叉树
public List<TreeNode> allPossibleFBT(int N) { List<TreeNode> res = new ArrayList<TreeNode>(); if(N % 2 == 0){ return res; } if(N == 1){ res.add(new TreeNode(0)); return res; } //对每个奇数 //一个奇数拆成两个奇数+1 for(int i = 1; i < N; i += 2){ List<TreeNode> lt = allPossibleFBT(i); List<TreeNode> rt = allPossibleFBT(N - 1 - i); //每种可能性都加进来 for(TreeNode l : lt){ for(TreeNode r : rt){ TreeNode root = new TreeNode(0); root.left = l; root.right = r; res.add(root); } } } return res; }
-
1079 活字印刷：
你有一套活字字模 tiles，其中每个字模上都刻有一个字母 tiles[i]。返回你可以印出的非空字母序列的数目。 示例 1： 输入："AAB" 输出：8 解释：可能的序列为 "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA"。
分而治之
-
23 合并K个排序链表
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 输入: [ 1->4->5, 1->3->4, 2->6 ] 输出: 1->1->2->3->4->4->5->6public ListNode mergeKLists(ListNode[] lists) { if (lists == null || lists.length == 0) return null; if (lists.length == 1) return lists[0]; if (lists.length == 2) return mergeTwoListNode(lists[0], lists[1]); int mid = lists.length / 2; ListNode[] leftArr = new ListNode[mid]; ListNode[] rightArr = new ListNode[lists.length - mid]; for (int i = 0; i < lists.length; i++) { if (i < mid) { leftArr[i] = lists[i]; } else { rightArr[i - mid] = lists[i]; } } //左右分治，最终变成两个listNode合并 return mergeTwoListNode(mergeKLists(leftArr), mergeKLists(rightArr)); } //递归合并两个ListNode public ListNode mergeTwoListNode(ListNode l1, ListNode l2) { if (l1 == null) return l2; if (l2 == null) return l1; ListNode cur; if (l1.val < l2.val) { cur = l1; cur.next = mergeTwoListNode(l1.next, l2); } else { cur = l2; cur.next = mergeTwoListNode(l1, l2.next); } return cur; }-
不用加减乘除做加法：
a+b==> (a&b)<<1+a^b
(异或就相当于没有进位的加法，而&就是寻找进位，<<1左移动1是表明与的值为进位在二进制加法中向前一位)
//当a==0的时候说明没有进位 public int add(int a, int b) { if(a==0) return b; return add((a&b)<<1,b^a); }
动态规划
-
lc 264 丑数 三指针：
public int nthUglyNumber(int n) { if (n == 0) return 1; int[] dp = new int[n]; dp[0] = 1; int l_2 = 0, l_3 = 0, l_5 = 0; for (int i = 1; i < n; i++) { dp[i] = Math.min(dp[l_2] * 2, Math.min(dp[l_3] * 3, dp[l_5] * 5)); if (dp[i] == dp[l_2] * 2) l_2++; if (dp[i] == dp[l_3] * 3) l_3++; if (dp[i] == dp[l_5] * 5) l_5++; } return dp[n - 1]; }
-
lc 309 最佳买卖股票世纪含冷冻期：
# sold rest hold 分别表示在该price 所持有的收益 class Solution: def maxProfit(self, prices: List[int]) -> int: sold=0 rest=0 hold=-2147383648 for price in prices: pre_sold=sold # 今天卖出的的收益 sold=hold+price # 当天是否买入，前一天的持有与之前的冷冻期收益减掉price hold = max(hold, rest - price); #当天冷冻,取之前的冷冻的那天值和前一天pre_sold的比较值,保证了冷冻一定是在上次销售之后 rest = max(rest, pre_sold); return max(sold,rest)
-
lc123 最佳买卖股票，次数限制：
public int maxProfit(int[] prices) { if (prices == null || prices.length < 2) return 0; int[][][] dp = new int[prices.length+1][3][2]; //base case for (int i = 0; i < 3; i++) { dp[0][i][0] = 0; dp[0][i][1] = Integer.MIN_VALUE; } for (int i = 1; i <= prices.length; i++) { for (int j = 1; j < 3; j++) { dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i-1]); dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j-1][0] - prices[i-1]); } } return dp[prices.length][2][0]; } -
lc309 股票买卖，含冷冻期：
public int maxProfit(int[] prices) { if(prices==null||prices.length==0) return 0; int[][] dp = new int[prices.length][2]; dp[0][0] = 0; dp[0][1] = -prices[0]; for (int i = 1; i < prices.length; i++) { if (i == 1) dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]); //-2表示相邻那天不能交易 else dp[i][1] = Math.max(dp[i - 1][1], dp[i - 2][0] - prices[i]); dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]); } return dp[prices.length - 1][0]; } -
迭代实现中序遍历：
public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); while (root != null || !stack.isEmpty()) { if (root != null) { stack.push(root); root = root.left; } else { root = stack.pop(); res.add(root.val); root = root.right; } } return res; }
