總結下，從奇虎的兩次測試來看，數組的變相二分查找，以及利用map與數組，結合dp，可以有效的解決很多問題。
掃描線這塊要放上pair。
The skyline problem ：是将起始位置的height置位負的，将結束位置的高不變。
放上一個int數組，構成一組pair
Arrays.fill(arr, 0)；将整個數組元素填充為0
// 求最大公約數
lic int findGcd(int a, int b){
return (a == || b == ) ? a + b : findGcd(b, a % b);
}
之前聽課的時候老師也說過分治法就像一個女王大人，處于root的位置，然後派了兩位青蛙大臣去處理一些事物，女王大人隻需要管好自己的val是多少，然後把兩個大臣的回報直接加起來就可以了。個人認為分治法算是比較接近普通人思維的一種方法了。
實作一個帶括号的電腦
思路：1.處理括号，徐兆第一個反括号，計算
2.計算， 得到+-*/的四個不同的index，不存在傳回str.length();
3.對于加減，進行stack1，stack2緩存，對于乘除，直接計算。
2給定字元串，輸出包含偶數個字元的子串的個數
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
int cur = ;
Map map = new HashMap();
map.put(, );//回到初始狀态也要先加上1
int resu = ;
char[] ch = str.toCharArray();
for (int i = ; i < ch.length; i++) {
int temp = ch[i] - 'a';
cur = cur ^ ( << temp);//此處注意是亦或
if (map.containsKey(cur)) {
resu += (int)map.get(cur);
map.put(cur, (int)map.get(cur) + );
} else {
map.put(cur, );
}
}
System.out.println(resu);
}
3清單任務與臨時任務
輸入 清單任務個數 N 臨時任務個數 M
輸入N個數，表示清單任務執行的時刻
輸入M個數，表示臨時任務執行的熟客
輸出M個數，表示臨時任務執行時間
思路：1.這個主要是利用第一個輸入數組作為區間标定，M數組總的時刻t，在N數組中找出大于t的有效時間間隔。可以用TreeSet來緩存有效時間段開始時刻（不包含端點），對于最大的值，TreeSet應該并入max+ 1到正無窮，用用Map來緩存有效時間結束的時刻，每次來了資料，先找lower的值，在找到結束的值，如果包含，就輸出val的值，否則輸出higher的值。
2.吧清單任務用數組進行緩存，lower_bound函數傳回大于等于該元素的下表，如果傳回值不等于，那麼直接輸出，如果等于，那麼進行二分查找，找到下一個大于等于的值，并且後面不連續的值。很巧妙的方法。
int solve(int left, int right) {
int idx;
int start = left;
while (left <= right) {
int mid = (left + right) >> ;
if (a[mid] - a[start] == mid - start) {
left = mid + ;
idx = mid;
}
else {
right = mid - ;
}
}
return a[idx] + ;
}
幼稚園小朋友排隊,轉化為數組逆序對的問題
public static int reseversepairs(int nums[]) {
int[] res = new int[nums.length];
return mergeSort(nums, res, , nums.length - );
}
public static int mergeSort(int[] nums,int[] res, int left, int right) {
if (left >= right) {
return ;
}
int mid = left + ((right - left) >> );
int numl = mergeSort(nums, res, left, mid);
int numr = mergeSort(nums, res, mid + , right);
int merm = merge(nums, res, left , mid, right);
return numl + numr + merm;
}
public static int merge(int[] nums, int[] res, int left, int mid, int right) {
int le = left, ri = mid + , idx = left;
int cnt = ;
while (le <= mid && ri <= right) {
if (nums[le] > nums[ri]) {
res[idx++] = nums[ri++];
cnt += mid - le + ;
} else {
res[idx++] = nums[le++];
}
}
while (le <= mid) {
res[idx++] = nums[le++];
}
while (ri <= right) {
res[idx++] = nums[ri++];
}
for (int k = left; k <= right; k++) {
nums[k] = res[k];
}
return cnt;
}
二分問題的一個小結
第一境界：會寫程式
Find First Position of Target
Find Last Position of Target
第二境界：找到第一個/最後一個滿足某個條件的位置/值
Search a 2D Matrix
Find Minimum in Rotated Sorted Array
第三境界：保留有解的那一半
Find Peak Element
找到第一個位置
public static int findFirstPo(int[] nums, int val) {
int left = ;
int right = nums.length - ;
int mid = ;
while (left < right) {
mid = (left + right) >> ;
if (nums[mid] > val) {
right = mid - ;
} else if (nums[mid] < val) {
left = mid + ;
} else {
right = mid;
}
}
return nums[left] == val ? left : -;//此處的mid具有一定的滞後性，故采用left
}
區間縮小-> 剩下兩個下标->判斷兩個下标
注：不要把縮小區間和得到答案放在一個循環裡面，容易出問題，增加難度
找到最後一個位置
因為除法存在下取整數的問題，是以第一個下标沒問題，第二個下标會出現問題
public static int findFirstPo(int[] nums, int val) {
int left = ;
int right = nums.length - ;
int mid = ;
while (left + < right) {// 此處更改
mid = (left + right) >> ;
if (nums[mid] > val) {
right = mid - ;
} else if (nums[mid] < val) {
left = mid + ;
} else {
left = mid;// 此處更改
}
}
return nums[right] == val ? right : nums[left] == val ? left ; -;//此處的mid具有一定的滞後性，故采用left
}
74. Search a 2D Matrix
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length < || matrix[].length < ) {
return false;
}
int left = , right = matrix.length - ;
int mid = ;
while (left + < right) {// find the first less than target
mid = (left + right) >> ;
if (matrix[mid][] > target) {
right = mid;
} else {
left = mid;
}
}
int index = matrix[right][] <= target ? right : left;
int left2 = , right2 = matrix[].length - ;
int mid2 = ;
while (left2 + < right2) {
mid2 = ((right2 - left2) >> ) + left2;
if (matrix[index][mid2] > target) {
right2 = mid2 - ;
} else if (matrix[index][mid2] < target) {
left2 = mid2 + ;
} else {
return true;
}
}
if (matrix[index][left2] == target) return true;
if (matrix[index][right2] == target) return true;
return false;
}
240. Search a 2D Matrix II
令x = 0， y = length；
然後進行周遊疊代，很巧妙的方法
153. Find Minimum in Rotated Sorted Array
找到旋轉數組的最小值,這個也是個很巧妙， 以後考慮每個二分采用left+ 1 < right ;
取target為數組的最後一個值，尋找到第一個小于等于這個值的數。
154. Find Minimum in Rotated Sorted Array II
旋轉數組中存在重複的元素如何改變
public class Solution {
public int findMin(int[] nums) {
int left = ;
int right = nums.length -;
int target = nums[right];
int mid = ;
while (left + < right) {
mid = left + ((right - left) >> );
if (nums[mid] < nums[right]) {
right = mid;
} else if (nums[mid] > nums[right]){
left = mid;
} else {
right--;// 相等就往下減
}
}
return Math.min(nums[left], nums[right]);
}
}
35. Search Insert Position
二分法取等号的時候的一個例子，在檢索要插入的位置，要傳回0或者nums.length。
173. Binary Search Tree Iterator
二叉樹疊代器，每次都傳回目前樹種最小的數值,要求hasnext（）以及next（）都是O(1)時間複雜度，空間複雜度為O（k），k為樹的深度。
分治法的一個結
一、概念
對于一個規模為n的問題，若該問題可以容易地解決（比如說規模n較小）則直接解決，否則将其分解為k個規模較小的子問題，這些子問題互相獨立且與原問題形式相同，遞歸地解決這些子問題，然後将各子問題的解合并得到原問題的解。這種算法設計政策叫做分治法。
二、分治法适用情況
1）問題的規模縮小到一定程度就可以容易解決
2）具有最子結構的性質（遞歸思想）
3）子問題的解可以合并為原問題的解（關鍵，否則為貪心法或者動态規劃法）
4）子問題是互相獨立的 ，子問題之間不包含公共的子子問題（重複解公共的子問題，一般用動态規劃法比較好）
三、分治法的步驟
step1 分解：将原問題分解為若幹個規模較小，互相獨立，與原問題形式相同的子問題
step2 解決：子問題規模較小而容易被解決則直接解決，否則遞歸地解各個子問題
step3 合并：将各個子問題的解合并為原問題的解
設計模式
Divide-and-Conquer(P)
if |P|<=N0 then return (ADHOC(P))
将P分解為較小的字問題P1,P2,…,Pk
for i<-1 to kß
do Yi <- Divide-and-Conquer(Pi) 遞歸解決Pi
T <- MERGE(Y1,Y2,…,Yk) 合并子問題
return (T)
連結清單這塊
outline：
Dummy Node in Linked List
Remove Duplicates from Sorted List II
Reverse Linked List II
Partition List
Basic Linked List Skills
Sort List
Reorder List
Two Pointers in Linked List (Fast-slow pointers)
Merge K Sorted Lists
82. Remove Duplicates from Sorted List II
删除重複的元素，這個是如果本身存在重複，一樣也得删除
dummy要放一個傀儡，作為連結清單的頭
// 需要朗讀并背誦的段落
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode dummpy = new ListNode();
dummpy.next = head;
head = dummpy;
int val = ;
while(head.next != null && head.next.next != null) {
if (head.next.val == head.next.next.val) {
val = head.next.val;
while (head.next != null && head.next.val == val) {
head.next = head.next.next;
}
} else {
head = head.next;
}
}
return dummpy.next;
}
92. Reverse Linked List II
實作連結清單部分反轉，dummy
public ListNode reverseBetween(ListNode head, int m, int n) {
if (head == null || head.next == null) {
return head;
}
ListNode dumpy = new ListNode();
dumpy.next = head;
head = dumpy;
for (int i = ; i < m; i++) {
head = head.next;
}
ListNode pre = head;// pre 以及 mnode這兩個節點都是要進行
ListNode mnode = head.next;
ListNode nnode = mnode;
ListNode post = mnode.next;
for (int j = m; j < n; j++) {
ListNode temp = post.next;
post.next = nnode;
nnode = post;
post = temp;
}
mnode.next = post;
pre.next = nnode;
return dumpy.next;
}
86 Partition List
dummy的典型使用，歸并排序的一個基礎, 給定一個值，小于這個值的排在大于這個值的前面
總結
因為連結清單算是比較基礎的内容了，是以也不需要太多的東西。大家就把幾個重要的trick掌握好就可以了，還是需要多多練習。
知識點如下：
1.dummy的使用
2.fast-slow pointer的使用
大家都懼怕的“動規”
三種類型的動态規劃，坐标動态規劃，單序列動态規劃，多序列動态規劃
動态規劃入門級文章 ： 背包九講 贊！
http://blog.csdn.net/ling_du/article/details/41594767
Outline:
了解動态規劃
Triangle
動态規劃的适用範圍
坐标型動态規劃
Minimum Path Sum
Climbing Stairs
Jump Game
Longest Increasing Subsequence
單序列動态規劃
Word Break
雙序列動态規劃
Longest Common Subsequence
總結
這裡也就引出了動态規劃和分治法的根本差別：動态規劃存在重複計算的部分，而分治法是沒有的，也就是說，由全局的問題分成子問題的時候，分治法的子問題是完全獨立的，互相之間沒有交集，而動态規劃的方法是有交叉部分的。
2.動态規劃的适用範圍
這個内容我個人認為對于面試是非常重要的，因為之前有面試官給我出過一個求出所有可行解的問題，當時我就是用dp來考慮，顯然最後就用一個三維動态規劃來解決了，這種就給了自己很大的麻煩。是以動态規劃在一定程度上很容易和DFS這樣的場景混淆。
滿足下面三個條件之一：
- 求最大值最小值
- 判斷是否可行
- 統計方案個數
則極有可能是使用動态規劃的方法來求解的。之前求所有解的話，肯定是要去周遊然後求出滿足情況的解的方法，而不是動态規劃這樣的模式。
以下情況是不使用動态規劃的情況：
- 求出所有具體的方案
- 輸入資料是一個集合而不是序列
- 暴力算法的複雜度已經是多項式級别
動态規劃擅長于優化指數級别的複雜度到多項式級别
動态規劃就是四個重要的要素：
- 狀态
- 方程
- 初始化
- 答案
64. Minimum Path Sum
采用的是二維動态規劃
120. Triangle
同上
45. Jump Game II
這個是給定一個數組，用最小的步數jump到數組尾部
可以采用動态規劃，trick，對于每一個i，先初始化其為最大值，然後從0開始進行dp的累加，一旦可達，更新dp[i],采用這個方法，會出現TLE
最優的思路是greedy，貪心
300. Longest Increasing Subsequence
兩種思路：思路1：dp緩存的是目前位置的最長遞增組序列的長度，初始化dp每個值都為1
思路2：dp緩存的是目前下标+1長度的最長遞增子序列的最小值，傳回size的值
139. Word Break
看這個字元串能否在拆分的過程中每一個子串都在詞典中
這個是單序列動态規劃問題，除了坐标動态規劃以外，一般都需要多定義一位，dp[i]緩存的是從0到i結點，能否被詞典中單詞完整分割
雙指針
80. Remove Duplicates from Sorted Array II
有序數組要求最多可以重複2個元素，可以删除多于的數組
這個問題可以擴充為k個
public int removeDuplicates(int[] nums) {
int i = ;
for (int n : nums) {
if (i < || n > nums[i - ]) {
nums[i++] = n;
}
}
return i;
}
407. Trapping Rain Water II
存儲雨水，這個自己定義一個單元，存儲row，col以及height，利用優先隊列進行存儲，先将四周的資料引入到隊列中，然後向周圍進行擴散。定義出visited進行資料通路節點的标記
209. Minimum Size Subarray Sum
滿足累加和大于某個數的最小的子數組,這個用滑動視窗來做，注意while的使用
還有一個用二分的方法，比較trick
30. Substring with Concatenation of All Words
給定一個字元串，給定一個字元串清單，求出字元串中連續包含字元串清單的子串的起始位置。
這個是滑動視窗的變，采用兩個map來實作。
無AC原因， left += j + m;寫錯了
public class Solution {
public List<Integer> findSubstring(String s, String[] words) {
// 采用map作為滑動視窗，
List<Integer> list = new LinkedList<Integer>();
if (s.length() < || words.length < ) {
return list;
}
Map<String, Integer> slide = new HashMap<String, Integer>();
for (int i = ; i < words.length; i++) {
slide.put(words[i], slide.getOrDefault(words[i], ) + );
}
int n = s.length();
int m = words[].length();
int num = words.length;
for (int i = ; i < m; i++) {
int count = , left = i;
Map<String, Integer> map = new HashMap<String, Integer>();
for (int j = i; j <= n - m; j+= m) {
String str = s.substring(j, j + m);
if (slide.containsKey(str)) {
map.put(str, map.getOrDefault(str, ) + );
if (map.get(str) <= slide.get(str)) {
count++;
} else {
while (map.get(str) > slide.get(str)) {
String str1 = s.substring(left, left + m);
map.put(str1, map.get(str1) - );
if (map.get(str1) < slide.get(str1))
count--;
left += m;
}
}
if (count == num) {
list.add(left);
map.put(s.substring(left, left + m), map.get(s.substring(left, left + m)) - );
count--;
left += m;
}
} else {
map.clear();
left = j + m;
count = ;
}
}
}
return list;
}
}
421. Maximum XOR of Two Numbers in an Array
數組中兩個數異或所能得到的最大的數
思路1：采用的是位操作的方法加上set存儲。依次采用mask取得前數組中前i位的prefix，用dummymax表示目前max的第i位變成1，如果dummymax^ 某個數在set中包含，則更新max的值。
思路2：利用單詞查找樹，先将數字依次插入到單詞查找樹中，周遊數組，每次取到存在與目前位置相反的進行下一次更新，同時xor更新xor
128. Longest Consecutive Sequence
給定數組，從中選取子序列，得到最長的增長子序列。
這個可以采用一個并查集的結構進行求解
// 兩個數組一個做父節點的映射，一個進行size的統計，利用一個map進行下标的映射關系。
public class Solution {
int[] parent;
int[] size;
public int longestConsecutive(int[] nums) {
if (nums.length < ) {
return nums.length;
}
parent = new int[nums.length];
size = new int[nums.length];
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = ; i < nums.length; i++) {
if (map.containsKey(nums[i])) {
continue;
}
map.put(nums[i], i);
parent[i] = i;
size[i] = ;
if (map.containsKey(nums[i] - )) {
union(map.get(nums[i] - ), i);
}
if (map.containsKey(nums[i] + )) {
union(i, map.get(nums[i] + ));
}
}
int max = ;
for (int i = ; i < nums.length; i++) {
max = Math.max(max, size[i]);
}
return max;
}
public int find (int x) {
if (parent[x] == x) {
return x;
}
parent[x] = find(parent[x]);
return parent[x];
}
public void union (int a, int b) {
int pa = find(a);
int pb = find(b);
if (pa != pb) {
if (size[pa] > size[pb]) {
parent[pb] = pa;
size[pa] += size[pb];
} else {
parent[pa] = pb;
size[pb] += size[pa];
}
}
}
}
賽碼網京東考試通過機率的dp問題
1.小明n個考試，通過60%以上算考試通過，n個考試的通過機率依次為輸入
定義dp[i][j]為i個題目中做對j各個的機率，最後再的加
2.石頭分堆問題（這個是數學問題）
圖
圖的初始化一個比較好的方式是利用Map
幾個sum的問題
1. Two Sum
要求：單個數組，輸出兩個數的和等于某個特定值得下标
思路：用map進行合理的緩存
167. Two Sum II - Input array is sorted
要求：單個數組，同上，但是已經是有序的，需要
思路：利用二分的方法
15. 3Sum
要求：單個數組，輸出3個下标，使得對應的和為0
思路：先排序，時間複雜度為O（n平方），從下标為0開始，用while循環進行嵌套
16. 3Sum Closest
要求：單個數組，數組有序第一時間考慮二分
思路：for’循環加上while’循環
18. 4Sum
要求：單個數組，傳回4個下标，得到合理的解
思路：時間複雜度為O（n三次方）
454. 4Sum II
要求：4個數組，傳回每個數組合理的下标
思路：一個map，緩存兩個數組，另外兩個，因為輸出的是個數，是以可以
![7大排序算法詳解+java實作[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)