算法思想
貪心思想
貪心思想保證每次操作都是局部最優(yōu)的择诈，并且最后得到的結(jié)果是全局最優(yōu)的拧烦。
分配餅干
Input: [1,2], [1,2,3]
Output: 2
Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2.
You have 3 cookies and their sizes are big enough to gratify all of the children,
You need to output 2.
題目描述：每個(gè)孩子都有一個(gè)滿足度军掂，每個(gè)餅干都有一個(gè)大小，只有餅干的大小大于等于一個(gè)孩子的滿足度枷莉，該孩子才會(huì)獲得滿足。求解最多可以獲得滿足的孩子數(shù)量。
因?yàn)樽钚〉暮⒆幼钊菀椎玫綕M足卷谈，因此先滿足最小孩子。給一個(gè)孩子的餅干應(yīng)當(dāng)盡量小又能滿足該孩子霞篡，這樣大餅干就能拿來給滿足度比較大的孩子世蔗。因此貪心策略
證明：假設(shè)在某次選擇中，貪心策略選擇給當(dāng)前滿足度最小的孩子分配第 m 個(gè)餅干朗兵，第 m 個(gè)餅干為可以滿足該孩子的最小餅干污淋。假設(shè)存在一種最優(yōu)策略，給該孩子分配第 n 個(gè)餅干余掖，并且 m < n寸爆。我們可以發(fā)現(xiàn)，經(jīng)過這一輪分配盐欺，貪心策略分配后剩下的餅干一定有一個(gè)比最優(yōu)策略來得大赁豆。因此在后續(xù)的分配中，貪心策略一定能滿足更多的孩子冗美。也就是說不存在比貪心策略更優(yōu)的策略魔种，即貪心策略就是最優(yōu)策略。
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int gi = 0, si = 0;
while (gi < g.length && si < s.length) {
if (g[gi] <= s[si]) {
gi++;
}
si++;
}
return gi;
}
不重疊的區(qū)間個(gè)數(shù)
435. Non-overlapping Intervals (Medium)
Input: [ [1,2], [1,2], [1,2] ]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapping.
Input: [ [1,2], [2,3] ]
Output: 0
Explanation: You don't need to remove any of the intervals since they're already non-overlapping.
題目描述：計(jì)算讓一組區(qū)間不重疊所需要移除的區(qū)間個(gè)數(shù)粉洼。
計(jì)算最多能組成的不重疊區(qū)間個(gè)數(shù)节预，然后用區(qū)間總個(gè)數(shù)減去不重疊區(qū)間的個(gè)數(shù)。
在每次選擇中属韧，區(qū)間的結(jié)尾最為重要心铃，選擇的區(qū)間結(jié)尾越小，留給后面的區(qū)間的空間越大挫剑，那么后面能夠選擇的區(qū)間個(gè)數(shù)也就越大去扣。
按區(qū)間的結(jié)尾進(jìn)行排序，每次選擇結(jié)尾最小樊破，并且和前一個(gè)區(qū)間不重疊的區(qū)間愉棱。
public int eraseOverlapIntervals(Interval[] intervals) {
if (intervals.length == 0) {
return 0;
}
Arrays.sort(intervals, Comparator.comparingInt(o -> o.end));
int cnt = 1;
int end = intervals[0].end;
for (int i = 1; i < intervals.length; i++) {
if (intervals[i].start < end) {
continue;
}
end = intervals[i].end;
cnt++;
}
return intervals.length - cnt;
}
使用 lambda 表示式創(chuàng)建 Comparator 會(huì)導(dǎo)致算法運(yùn)行時(shí)間過長，如果注重運(yùn)行時(shí)間哲戚，可以修改為普通創(chuàng)建 Comparator 語句：
Arrays.sort(intervals, new Comparator<Interval>() {
@Override
public int compare(Interval o1, Interval o2) {
return o1.end - o2.end;
}
});
投飛鏢刺破氣球
452. Minimum Number of Arrows to Burst Balloons (Medium)
Input:
[[10,16], [2,8], [1,6], [7,12]]
Output:
2
題目描述：氣球在一個(gè)水平數(shù)軸上擺放奔滑，可以重疊，飛鏢垂直投向坐標(biāo)軸顺少，使得路徑上的氣球都會(huì)刺破朋其。求解最小的投飛鏢次數(shù)使所有氣球都被刺破王浴。
也是計(jì)算不重疊的區(qū)間個(gè)數(shù)，不過和 Non-overlapping Intervals 的區(qū)別在于梅猿，[1, 2] 和 [2, 3] 在本題中算是重疊區(qū)間氓辣。
public int findMinArrowShots(int[][] points) {
if (points.length == 0) {
return 0;
}
Arrays.sort(points, Comparator.comparingInt(o -> o[1]));
int cnt = 1, end = points[0][1];
for (int i = 1; i < points.length; i++) {
if (points[i][0] <= end) {
continue;
}
cnt++;
end = points[i][1];
}
return cnt;
}
根據(jù)身高和序號(hào)重組隊(duì)列
406. Queue Reconstruction by Height(Medium)
Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
題目描述：一個(gè)學(xué)生用兩個(gè)分量 (h, k) 描述，h 表示身高袱蚓，k 表示排在前面的有 k 個(gè)學(xué)生的身高比他高或者和他一樣高钞啸。
為了在每次插入操作時(shí)不影響后續(xù)的操作，身高較高的學(xué)生應(yīng)該先做插入操作喇潘，否則身高較小的學(xué)生原先正確插入第 k 個(gè)位置可能會(huì)變成第 k+1 個(gè)位置体斩。
身高降序、k 值升序颖低，然后按排好序的順序插入隊(duì)列的第 k 個(gè)位置中絮吵。
public int[][] reconstructQueue(int[][] people) {
if (people == null || people.length == 0 || people[0].length == 0) {
return new int[0][0];
}
Arrays.sort(people, (a, b) -> (a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]));
List<int[]> queue = new ArrayList<>();
for (int[] p : people) {
queue.add(p[1], p);
}
return queue.toArray(new int[queue.size()][]);
}
分隔字符串使同種字符出現(xiàn)在一起
763. Partition Labels (Medium)
Input: S = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation:
The partition is "ababcbaca", "defegde", "hijhklij".
This is a partition so that each letter appears in at most one part.
A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts.
public List<Integer> partitionLabels(String S) {
int[] lastIndexsOfChar = new int[26];
for (int i = 0; i < S.length(); i++) {
lastIndexsOfChar[char2Index(S.charAt(i))] = i;
}
List<Integer> partitions = new ArrayList<>();
int firstIndex = 0;
while (firstIndex < S.length()) {
int lastIndex = firstIndex;
for (int i = firstIndex; i < S.length() && i <= lastIndex; i++) {
int index = lastIndexsOfChar[char2Index(S.charAt(i))];
if (index > lastIndex) {
lastIndex = index;
}
}
partitions.add(lastIndex - firstIndex + 1);
firstIndex = lastIndex + 1;
}
return partitions;
}
private int char2Index(char c) {
return c - 'a';
}
種植花朵
Input: flowerbed = [1,0,0,0,1], n = 1
Output: True
題目描述：花朵之間至少需要一個(gè)單位的間隔，求解是否能種下 n 朵花忱屑。
public boolean canPlaceFlowers(int[] flowerbed, int n) {
int len = flowerbed.length;
int cnt = 0;
for (int i = 0; i < len && cnt < n; i++) {
if (flowerbed[i] == 1) {
continue;
}
int pre = i == 0 ? 0 : flowerbed[i - 1];
int next = i == len - 1 ? 0 : flowerbed[i + 1];
if (pre == 0 && next == 0) {
cnt++;
flowerbed[i] = 1;
}
}
return cnt >= n;
}
判斷是否為子串
s = "abc", t = "ahbgdc"
Return true.
public boolean isSubsequence(String s, String t) {
int index = -1;
for (char c : s.toCharArray()) {
index = t.indexOf(c, index + 1);
if (index == -1) {
return false;
}
}
return true;
}
修改一個(gè)數(shù)成為非遞減數(shù)組
665. Non-decreasing Array (Easy)
Input: [4,2,3]
Output: True
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.
題目描述：判斷一個(gè)數(shù)組能不能只修改一個(gè)數(shù)就成為非遞減數(shù)組蹬敲。
在出現(xiàn) nums[i] < nums[i - 1] 時(shí)，需要考慮的是應(yīng)該修改數(shù)組的哪個(gè)數(shù)想幻，使得本次修改能使 i 之前的數(shù)組成為非遞減數(shù)組，并且 不影響后續(xù)的操作 话浇。優(yōu)先考慮令 nums[i - 1] = nums[i]脏毯，因?yàn)槿绻薷?nums[i] = nums[i - 1] 的話，那么 nums[i] 這個(gè)數(shù)會(huì)變大幔崖，就有可能比 nums[i + 1] 大食店，從而影響了后續(xù)操作。還有一個(gè)比較特別的情況就是 nums[i] < nums[i - 2]赏寇，只修改 nums[i - 1] = nums[i] 不能使數(shù)組成為非遞減數(shù)組吉嫩，只能修改 nums[i] = nums[i - 1]。
public boolean checkPossibility(int[] nums) {
int cnt = 0;
for (int i = 1; i < nums.length && cnt < 2; i++) {
if (nums[i] >= nums[i - 1]) {
continue;
}
cnt++;
if (i - 2 >= 0 && nums[i - 2] > nums[i]) {
nums[i] = nums[i - 1];
} else {
nums[i - 1] = nums[i];
}
}
return cnt <= 1;
}
股票的最大收益
122. Best Time to Buy and Sell Stock II (Easy)
題目描述：一次股票交易包含買入和賣出嗅定，多個(gè)交易之間不能交叉進(jìn)行自娩。
對(duì)于 [a, b, c, d]，如果有 a <= b <= c <= d 渠退，那么最大收益為 d - a忙迁。而 d - a = (d - c) + (c - b) + (b - a) ，因此當(dāng)訪問到一個(gè) prices[i] 且 prices[i] - prices[i-1] > 0碎乃，那么就把 prices[i] - prices[i-1] 添加到收益中姊扔，從而在局部最優(yōu)的情況下也保證全局最優(yōu)。
public int maxProfit(int[] prices) {
int profit = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1]) {
profit += (prices[i] - prices[i - 1]);
}
}
return profit;
}
雙指針
雙指針主要用于遍歷數(shù)組梅誓，兩個(gè)指針指向不同的元素恰梢，從而協(xié)同完成任務(wù)佛南。
有序數(shù)組的 Two Sum
Leetcode ：167. Two Sum II - Input array is sorted (Easy)
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
題目描述：在有序數(shù)組中找出兩個(gè)數(shù)，使它們的和為 target嵌言。
使用雙指針嗅回，一個(gè)指針指向值較小的元素，一個(gè)指針指向值較大的元素呀页。指向較小元素的指針從頭向尾遍歷妈拌，指向較大元素的指針從尾向頭遍歷。
如果兩個(gè)指針指向元素的和 sum == target蓬蝶，那么得到要求的結(jié)果尘分；如果 sum > target，移動(dòng)較大的元素丸氛，使 sum 變小一些培愁；如果 sum < target，移動(dòng)較小的元素缓窜，使 sum 變大一些定续。
public int[] twoSum(int[] numbers, int target) {
int i = 0, j = numbers.length - 1;
while (i < j) {
int sum = numbers[i] + numbers[j];
if (sum == target) {
return new int[]{i + 1, j + 1};
} else if (sum < target) {
i++;
} else {
j--;
}
}
return null;
}
兩數(shù)平方和
633. Sum of Square Numbers (Easy)
Input: 5
Output: True
Explanation: 1 * 1 + 2 * 2 = 5
題目描述：判斷一個(gè)數(shù)是否為兩個(gè)數(shù)的平方和，例如 5 = 12 + 22禾锤。
public boolean judgeSquareSum(int c) {
int i = 0, j = (int) Math.sqrt(c);
while (i <= j) {
int powSum = i * i + j * j;
if (powSum == c) {
return true;
} else if (powSum > c) {
j--;
} else {
i++;
}
}
return false;
}
反轉(zhuǎn)字符串中的元音字符
345. Reverse Vowels of a String (Easy)
Given s = "leetcode", return "leotcede".
使用雙指針私股，指向待反轉(zhuǎn)的兩個(gè)元音字符，一個(gè)指針從頭向尾遍歷恩掷，一個(gè)指針從尾到頭遍歷倡鲸。
private final static HashSet<Character> vowels = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'));
public String reverseVowels(String s) {
int i = 0, j = s.length() - 1;
char[] result = new char[s.length()];
while (i <= j) {
char ci = s.charAt(i);
char cj = s.charAt(j);
if (!vowels.contains(ci)) {
result[i++] = ci;
} else if (!vowels.contains(cj)) {
result[j--] = cj;
} else {
result[i++] = cj;
result[j--] = ci;
}
}
return new String(result);
}
回文字符串
680. Valid Palindrome II (Easy)
Input: "abca"
Output: True
Explanation: You could delete the character 'c'.
題目描述：可以刪除一個(gè)字符，判斷是否能構(gòu)成回文字符串黄娘。
public boolean validPalindrome(String s) {
int i = -1, j = s.length();
while (++i < --j) {
if (s.charAt(i) != s.charAt(j)) {
return isPalindrome(s, i, j - 1) || isPalindrome(s, i + 1, j);
}
}
return true;
}
private boolean isPalindrome(String s, int i, int j) {
while (i < j) {
if (s.charAt(i++) != s.charAt(j--)) {
return false;
}
}
return true;
}
歸并兩個(gè)有序數(shù)組
Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
題目描述：把歸并結(jié)果存到第一個(gè)數(shù)組上峭状。
需要從尾開始遍歷，否則在 nums1 上歸并得到的值會(huì)覆蓋還未進(jìn)行歸并比較的值
public void merge(int[] nums1, int m, int[] nums2, int n) {
int index1 = m - 1, index2 = n - 1;
int indexMerge = m + n - 1;
while (index1 >= 0 || index2 >= 0) {
if (index1 < 0) {
nums1[indexMerge--] = nums2[index2--];
} else if (index2 < 0) {
nums1[indexMerge--] = nums1[index1--];
} else if (nums1[index1] > nums2[index2]) {
nums1[indexMerge--] = nums1[index1--];
} else {
nums1[indexMerge--] = nums2[index2--];
}
}
}
判斷鏈表是否存在環(huán)
使用雙指針逼争，一個(gè)指針每次移動(dòng)一個(gè)節(jié)點(diǎn)优床，一個(gè)指針每次移動(dòng)兩個(gè)節(jié)點(diǎn)，如果存在環(huán)誓焦，那么這兩個(gè)指針一定會(huì)相遇胆敞。
public boolean hasCycle(ListNode head) {
if (head == null) {
return false;
}
ListNode l1 = head, l2 = head.next;
while (l1 != null && l2 != null && l2.next != null) {
if (l1 == l2) {
return true;
}
l1 = l1.next;
l2 = l2.next.next;
}
return false;
}
最長子序列
524. Longest Word in Dictionary through Deleting (Medium)
Input:
s = "abpcplea", d = ["ale","apple","monkey","plea"]
Output:
"apple"
題目描述：刪除 s 中的一些字符怀酷，使得它構(gòu)成字符串列表 d 中的一個(gè)字符串论悴，找出能構(gòu)成的最長字符串。如果有多個(gè)相同長度的結(jié)果蚌卤，返回按字典序排序的最大字符串稿壁。
public String findLongestWord(String s, List<String> d) {
String longestWord = "";
for (String target : d) {
int l1 = longestWord.length(), l2 = target.length();
if (l1 > l2 || (l1 == l2 && longestWord.compareTo(target) < 0)) {
continue;
}
if (isValid(s, target)) {
longestWord = target;
}
}
return longestWord;
}
private boolean isValid(String s, String target) {
int i = 0, j = 0;
while (i < s.length() && j < target.length()) {
if (s.charAt(i) == target.charAt(j)) {
j++;
}
i++;
}
return j == target.length();
}
排序
快速選擇
一般用于求解 Kth Element 問題幽钢，可以在 O(N) 時(shí)間復(fù)雜度，O(1) 空間復(fù)雜度完成求解工作傅是。
與快速排序一樣匪燕，快速選擇一般需要先打亂數(shù)組蕾羊，否則最壞情況下時(shí)間復(fù)雜度為 O(N2)。
堆排序
堆排序用于求解 TopK Elements 問題帽驯，通過維護(hù)一個(gè)大小為 K 的堆龟再，堆中的元素就是 TopK Elements。當(dāng)然它也可以用于求解 Kth Element 問題尼变，堆頂元素就是 Kth Element利凑。快速選擇也可以求解 TopK Elements 問題嫌术，因?yàn)檎业?Kth Element 之后哀澈，再遍歷一次數(shù)組，所有小于等于 Kth Element 的元素都是 TopK Elements度气「畎矗可以看到，快速選擇和堆排序都可以求解 Kth Element 和 TopK Elements 問題磷籍。
Kth Element
215. Kth Largest Element in an Array (Medium)
排序 ：時(shí)間復(fù)雜度 O(NlogN)适荣，空間復(fù)雜度 O(1)
public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length - k];
}
堆排序 ：時(shí)間復(fù)雜度 O(NlogK)，空間復(fù)雜度 O(K)院领。
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>(); // 小頂堆
for (int val : nums) {
pq.add(val);
if (pq.size() > k) // 維護(hù)堆的大小為 K
pq.poll();
}
return pq.peek();
}
快速選擇 ：時(shí)間復(fù)雜度 O(N)弛矛，空間復(fù)雜度 O(1)
public int findKthLargest(int[] nums, int k) {
k = nums.length - k;
int l = 0, h = nums.length - 1;
while (l < h) {
int j = partition(nums, l, h);
if (j == k) {
break;
} else if (j < k) {
l = j + 1;
} else {
h = j - 1;
}
}
return nums[k];
}
private int partition(int[] a, int l, int h) {
int i = l, j = h + 1;
while (true) {
while (a[++i] < a[l] && i < h) ;
while (a[--j] > a[l] && j > l) ;
if (i >= j) {
break;
}
swap(a, i, j);
}
swap(a, l, j);
return j;
}
private void swap(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
桶排序
出現(xiàn)頻率最多的 k 個(gè)數(shù)
347. Top K Frequent Elements (Medium)
Given [1,1,1,2,2,3] and k = 2, return [1,2].
設(shè)置若干個(gè)桶，每個(gè)桶存儲(chǔ)出現(xiàn)頻率相同的數(shù)比然，并且桶的下標(biāo)代表桶中數(shù)出現(xiàn)的頻率丈氓，即第 i 個(gè)桶中存儲(chǔ)的數(shù)出現(xiàn)的頻率為 i。把數(shù)都放到桶之后谈秫，從后向前遍歷桶扒寄，最先得到的 k 個(gè)數(shù)就是出現(xiàn)頻率最多的的 k 個(gè)數(shù)鱼鼓。
public List<Integer> topKFrequent(int[] nums, int k) {
Map<Integer, Integer> frequencyForNum = new HashMap<>();
for (int num : nums) {
frequencyForNum.put(num, frequencyForNum.getOrDefault(num, 0) + 1);
}
List<Integer>[] buckets = new ArrayList[nums.length + 1];
for (int key : frequencyForNum.keySet()) {
int frequency = frequencyForNum.get(key);
if (buckets[frequency] == null) {
buckets[frequency] = new ArrayList<>();
}
buckets[frequency].add(key);
}
List<Integer> topK = new ArrayList<>();
for (int i = buckets.length - 1; i >= 0 && topK.size() < k; i--) {
if (buckets[i] != null) {
topK.addAll(buckets[i]);
}
}
return topK;
}
按照字符出現(xiàn)次數(shù)對(duì)字符串排序
451. Sort Characters By Frequency (Medium)
Input:
"tree"
Output:
"eert"
Explanation:
'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.
public String frequencySort(String s) {
Map<Character, Integer> frequencyForNum = new HashMap<>();
for (char c : s.toCharArray())
frequencyForNum.put(c, frequencyForNum.getOrDefault(c, 0) + 1);
List<Character>[] frequencyBucket = new ArrayList[s.length() + 1];
for (char c : frequencyForNum.keySet()) {
int f = frequencyForNum.get(c);
if (frequencyBucket[f] == null) {
frequencyBucket[f] = new ArrayList<>();
}
frequencyBucket[f].add(c);
}
StringBuilder str = new StringBuilder();
for (int i = frequencyBucket.length - 1; i >= 0; i--) {
if (frequencyBucket[i] == null) {
continue;
}
for (char c : frequencyBucket[i]) {
for (int j = 0; j < i; j++) {
str.append(c);
}
}
}
return str.toString();
}
荷蘭國旗問題
荷蘭國旗包含三種顏色：紅拟烫、白、藍(lán)迄本。有這三種顏色的球硕淑，算法的目標(biāo)是將這三種球按顏色順序正確地排列。
它其實(shí)是三向切分快速排序的一種變種嘉赎，在三向切分快速排序中置媳，每次切分都將數(shù)組分成三個(gè)區(qū)間：小于切分元素、等于切分元素公条、大于切分元素拇囊，而該算法是將數(shù)組分成三個(gè)區(qū)間：等于紅色、等于白色靶橱、等于藍(lán)色寥袭。
<div align="center"> <img src="../pics//3b49dd67-2c40-4b81-8ad2-7bbb1fe2fcbd.png"/> </div>
按顏色進(jìn)行排序
Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
題目描述：只有 0/1/2 三種顏色路捧。
public void sortColors(int[] nums) {
int zero = -1, one = 0, two = nums.length;
while (one < two) {
if (nums[one] == 0) {
swap(nums, ++zero, one++);
} else if (nums[one] == 2) {
swap(nums, --two, one);
} else {
++one;
}
}
}
private void swap(int[] nums, int i, int j) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
二分查找
正常實(shí)現(xiàn)
public int binarySearch(int[] nums, int key) {
int l = 0, h = nums.length - 1;
while (l <= h) {
int m = l + (h - l) / 2;
if (nums[m] == key) {
return m;
} else if (nums[m] > key) {
h = m - 1;
} else {
l = m + 1;
}
}
return -1;
}
時(shí)間復(fù)雜度
二分查找也稱為折半查找，每次都能將查找區(qū)間減半传黄，這種折半特性的算法時(shí)間復(fù)雜度都為 O(logN)杰扫。
m 計(jì)算
有兩種計(jì)算中值 m 的方式：
- m = (l + h) / 2
- m = l + (h - l) / 2
l + h 可能出現(xiàn)加法溢出，最好使用第二種方式膘掰。
返回值
循環(huán)退出時(shí)如果仍然沒有查找到 key章姓，那么表示查找失敗∈堵瘢可以有兩種返回值：
- -1：以一個(gè)錯(cuò)誤碼表示沒有查找到 key
- l：將 key 插入到 nums 中的正確位置
變種
二分查找可以有很多變種凡伊，變種實(shí)現(xiàn)要注意邊界值的判斷。例如在一個(gè)有重復(fù)元素的數(shù)組中查找 key 的最左位置的實(shí)現(xiàn)如下：
public int binarySearch(int[] nums, int key) {
int l = 0, h = nums.length - 1;
while (l < h) {
int m = l + (h - l) / 2;
if (nums[m] >= key) {
h = m;
} else {
l = m + 1;
}
}
return l;
}
該實(shí)現(xiàn)和正常實(shí)現(xiàn)有以下不同：
- 循環(huán)條件為 l < h
- h 的賦值表達(dá)式為 h = m
- 最后返回 l 而不是 -1
在 nums[m] >= key 的情況下惭聂，可以推導(dǎo)出最左 key 位于 [l, m] 區(qū)間中窗声，這是一個(gè)閉區(qū)間。h 的賦值表達(dá)式為 h = m辜纲，因?yàn)?m 位置也可能是解笨觅。
在 h 的賦值表達(dá)式為 h = mid 的情況下，如果循環(huán)條件為 l <= h耕腾，那么會(huì)出現(xiàn)循環(huán)無法退出的情況见剩，因此循環(huán)條件只能是 l < h。以下演示了循環(huán)條件為 l <= h 時(shí)循環(huán)無法退出的情況：
nums = {0, 1, 2}, key = 1
l m h
0 1 2 nums[m] >= key
0 0 1 nums[m] < key
1 1 1 nums[m] >= key
1 1 1 nums[m] >= key
...
當(dāng)循環(huán)體退出時(shí)扫俺，不表示沒有查找到 key苍苞，因此最后返回的結(jié)果不應(yīng)該為 -1。為了驗(yàn)證有沒有查找到狼纬，需要在調(diào)用端判斷一下返回位置上的值和 key 是否相等羹呵。
求開方
Input: 4
Output: 2
Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we want to return an integer, the decimal part will be truncated.
一個(gè)數(shù) x 的開方 sqrt 一定在 0 ~ x 之間，并且滿足 sqrt == x / sqrt疗琉「曰叮可以利用二分查找在 0 ~ x 之間查找 sqrt。
對(duì)于 x = 8盈简，它的開方是 2.82842...凑耻，最后應(yīng)該返回 2 而不是 3。在循環(huán)條件為 l <= h 并且循環(huán)退出時(shí)柠贤，h 總是比 l 小 1香浩，也就是說 h = 2，l = 3臼勉，因此最后的返回值應(yīng)該為 h 而不是 l邻吭。
public int mySqrt(int x) {
if (x <= 1) {
return x;
}
int l = 1, h = x;
while (l <= h) {
int mid = l + (h - l) / 2;
int sqrt = x / mid;
if (sqrt == mid) {
return mid;
} else if (mid > sqrt) {
h = mid - 1;
} else {
l = mid + 1;
}
}
return h;
}
大于給定元素的最小元素
744. Find Smallest Letter Greater Than Target (Easy)
Input:
letters = ["c", "f", "j"]
target = "d"
Output: "f"
Input:
letters = ["c", "f", "j"]
target = "k"
Output: "c"
題目描述：給定一個(gè)有序的字符數(shù)組 letters 和一個(gè)字符 target，要求找出 letters 中大于 target 的最小字符宴霸，如果找不到就返回第 1 個(gè)字符囱晴。
public char nextGreatestLetter(char[] letters, char target) {
int n = letters.length;
int l = 0, h = n - 1;
while (l <= h) {
int m = l + (h - l) / 2;
if (letters[m] <= target) {
l = m + 1;
} else {
h = m - 1;
}
}
return l < n ? letters[l] : letters[0];
}
有序數(shù)組的 Single Element
540. Single Element in a Sorted Array (Medium)
Input: [1,1,2,3,3,4,4,8,8]
Output: 2
題目描述：一個(gè)有序數(shù)組只有一個(gè)數(shù)不出現(xiàn)兩次岸裙，找出這個(gè)數(shù)。要求以 O(logN) 時(shí)間復(fù)雜度進(jìn)行求解速缆。
令 index 為 Single Element 在數(shù)組中的位置降允。如果 m 為偶數(shù)，并且 m + 1 < index艺糜，那么 nums[m] == nums[m + 1]剧董；m + 1 >= index，那么 nums[m] != nums[m + 1]破停。
從上面的規(guī)律可以知道翅楼，如果 nums[m] == nums[m + 1]，那么 index 所在的數(shù)組位置為 [m + 2, h]真慢，此時(shí)令 l = m + 2毅臊；如果 nums[m] != nums[m + 1]，那么 index 所在的數(shù)組位置為 [l, m]黑界，此時(shí)令 h = m管嬉。
因?yàn)?h 的賦值表達(dá)式為 h = m，那么循環(huán)條件也就只能使用 l < h 這種形式朗鸠。
public int singleNonDuplicate(int[] nums) {
int l = 0, h = nums.length - 1;
while (l < h) {
int m = l + (h - l) / 2;
if (m % 2 == 1) {
m--; // 保證 l/h/m 都在偶數(shù)位蚯撩，使得查找區(qū)間大小一直都是奇數(shù)
}
if (nums[m] == nums[m + 1]) {
l = m + 2;
} else {
h = m;
}
}
return nums[l];
}
第一個(gè)錯(cuò)誤的版本
題目描述：給定一個(gè)元素 n 代表有 [1, 2, ..., n] 版本，可以調(diào)用 isBadVersion(int x) 知道某個(gè)版本是否錯(cuò)誤烛占，要求找到第一個(gè)錯(cuò)誤的版本胎挎。
如果第 m 個(gè)版本出錯(cuò)，則表示第一個(gè)錯(cuò)誤的版本在 [l, m] 之間忆家，令 h = m犹菇；否則第一個(gè)錯(cuò)誤的版本在 [m + 1, h] 之間，令 l = m + 1芽卿。
因?yàn)?h 的賦值表達(dá)式為 h = m揭芍，因此循環(huán)條件為 l < h。
public int firstBadVersion(int n) {
int l = 1, h = n;
while (l < h) {
int mid = l + (h - l) / 2;
if (isBadVersion(mid)) {
h = mid;
} else {
l = mid + 1;
}
}
return l;
}
旋轉(zhuǎn)數(shù)組的最小數(shù)字
153. Find Minimum in Rotated Sorted Array (Medium)
Input: [3,4,5,1,2],
Output: 1
public int findMin(int[] nums) {
int l = 0, h = nums.length - 1;
while (l < h) {
int m = l + (h - l) / 2;
if (nums[m] <= nums[h]) {
h = m;
} else {
l = m + 1;
}
}
return nums[l];
}
查找區(qū)間
34. Search for a Range (Medium)
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
public int[] searchRange(int[] nums, int target) {
int first = binarySearch(nums, target);
int last = binarySearch(nums, target + 1) - 1;
if (first == nums.length || nums[first] != target) {
return new int[]{-1, -1};
} else {
return new int[]{first, Math.max(first, last)};
}
}
private int binarySearch(int[] nums, int target) {
int l = 0, h = nums.length; // 注意 h 的初始值
while (l < h) {
int m = l + (h - l) / 2;
if (nums[m] >= target) {
h = m;
} else {
l = m + 1;
}
}
return l;
}
搜索
深度優(yōu)先搜索和廣度優(yōu)先搜索廣泛運(yùn)用于樹和圖中蹬竖，但是它們的應(yīng)用遠(yuǎn)遠(yuǎn)不止如此沼沈。
BFS
<div align="center"> <img src="../pics//4ff355cf-9a7f-4468-af43-e5b02038facc.jpg"/> </div>
廣度優(yōu)先搜索的搜索過程有點(diǎn)像一層一層地進(jìn)行遍歷，每層遍歷都以上一層遍歷的結(jié)果作為起點(diǎn)，遍歷一個(gè)距離能訪問到的所有節(jié)點(diǎn)俐芯。需要注意的是蔑穴，遍歷過的節(jié)點(diǎn)不能再次被遍歷。
第一層：
- 0 -> {6,2,1,5};
第二層：
- 6 -> {4}
- 2 -> {}
- 1 -> {}
- 5 -> {3}
第三層：
- 4 -> {}
- 3 -> {}
可以看到泥栖，每一層遍歷的節(jié)點(diǎn)都與根節(jié)點(diǎn)距離相同。設(shè) di 表示第 i 個(gè)節(jié)點(diǎn)與根節(jié)點(diǎn)的距離，推導(dǎo)出一個(gè)結(jié)論：對(duì)于先遍歷的節(jié)點(diǎn) i 與后遍歷的節(jié)點(diǎn) j阴绢，有 di<=dj店乐。利用這個(gè)結(jié)論，可以求解最短路徑等 最優(yōu)解 問題：第一次遍歷到目的節(jié)點(diǎn)呻袭，其所經(jīng)過的路徑為最短路徑眨八。應(yīng)該注意的是，使用 BFS 只能求解無權(quán)圖的最短路徑左电。
在程序?qū)崿F(xiàn) BFS 時(shí)需要考慮以下問題：
- 隊(duì)列：用來存儲(chǔ)每一輪遍歷得到的節(jié)點(diǎn)廉侧；
- 標(biāo)記：對(duì)于遍歷過的節(jié)點(diǎn)，應(yīng)該將它標(biāo)記篓足，防止重復(fù)遍歷段誊。
計(jì)算在網(wǎng)格中從原點(diǎn)到特定點(diǎn)的最短路徑長度
[[1,1,0,1],
[1,0,1,0],
[1,1,1,1],
[1,0,1,1]]
1 表示可以經(jīng)過某個(gè)位置，求解從 (0, 0) 位置到 (tr, tc) 位置的最短路徑長度栈拖。
public int minPathLength(int[][] grids, int tr, int tc) {
final int[][] direction = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
final int m = grids.length, n = grids[0].length;
Queue<Pair<Integer, Integer>> queue = new LinkedList<>();
queue.add(new Pair<>(0, 0));
int pathLength = 0;
while (!queue.isEmpty()) {
int size = queue.size();
pathLength++;
while (size-- > 0) {
Pair<Integer, Integer> cur = queue.poll();
for (int[] d : direction) {
int nr = cur.getKey() + d[0], nc = cur.getValue() + d[1];
Pair<Integer, Integer> next = new Pair<>(nr, nc);
if (next.getKey() < 0 || next.getValue() >= m
|| next.getKey() < 0 || next.getValue() >= n) {
continue;
}
grids[next.getKey()][next.getValue()] = 0; // 標(biāo)記
if (next.getKey() == tr && next.getValue() == tc) {
return pathLength;
}
queue.add(next);
}
}
}
return -1;
}
組成整數(shù)的最小平方數(shù)數(shù)量
For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.
可以將每個(gè)整數(shù)看成圖中的一個(gè)節(jié)點(diǎn)连舍，如果兩個(gè)整數(shù)之差為一個(gè)平方數(shù)，那么這兩個(gè)整數(shù)所在的節(jié)點(diǎn)就有一條邊涩哟。
要求解最小的平方數(shù)數(shù)量索赏，就是求解從節(jié)點(diǎn) n 到節(jié)點(diǎn) 0 的最短路徑。
本題也可以用動(dòng)態(tài)規(guī)劃求解贴彼，在之后動(dòng)態(tài)規(guī)劃部分中會(huì)再次出現(xiàn)参滴。
public int numSquares(int n) {
List<Integer> squares = generateSquares(n);
Queue<Integer> queue = new LinkedList<>();
boolean[] marked = new boolean[n + 1];
queue.add(n);
marked[n] = true;
int level = 0;
while (!queue.isEmpty()) {
int size = queue.size();
level++;
while (size-- > 0) {
int cur = queue.poll();
for (int s : squares) {
int next = cur - s;
if (next < 0) {
break;
}
if (next == 0) {
return level;
}
if (marked[next]) {
continue;
}
marked[next] = true;
queue.add(cur - s);
}
}
}
return n;
}
/**
* 生成小于 n 的平方數(shù)序列
* @return 1,4,9,...
*/
private List<Integer> generateSquares(int n) {
List<Integer> squares = new ArrayList<>();
int square = 1;``
int diff = 3;
while (square <= n) {
squares.add(square);
square += diff;
diff += 2;
}
return squares;
}
最短單詞路徑
Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.
找出一條從 beginWord 到 endWord 的最短路徑，每次移動(dòng)規(guī)定為改變一個(gè)字符锻弓，并且改變之后的字符串必須在 wordList 中砾赔。
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
wordList.add(beginWord);
int N = wordList.size();
int start = N - 1;
int end = 0;
while (end < N && !wordList.get(end).equals(endWord)) {
end++;
}
if (end == N) {
return 0;
}
List<Integer>[] graphic = buildGraphic(wordList);
return getShortestPath(graphic, start, end);
}
private List<Integer>[] buildGraphic(List<String> wordList) {
int N = wordList.size();
List<Integer>[] graphic = new List[N];
for (int i = 0; i < N; i++) {
graphic[i] = new ArrayList<>();
for (int j = 0; j < N; j++) {
if (isConnect(wordList.get(i), wordList.get(j))) {
graphic[i].add(j);
}
}
}
return graphic;
}
private boolean isConnect(String s1, String s2) {
int diffCnt = 0;
for (int i = 0; i < s1.length() && diffCnt <= 1; i++) {
if (s1.charAt(i) != s2.charAt(i)) {
diffCnt++;
}
}
return diffCnt == 1;
}
private int getShortestPath(List<Integer>[] graphic, int start, int end) {
Queue<Integer> queue = new LinkedList<>();
boolean[] marked = new boolean[graphic.length];
queue.add(start);
marked[start] = true;
int path = 1;
while (!queue.isEmpty()) {
int size = queue.size();
path++;
while (size-- > 0) {
int cur = queue.poll();
for (int next : graphic[cur]) {
if (next == end) {
return path;
}
if (marked[next]) {
continue;
}
marked[next] = true;
queue.add(next);
}
}
}
return 0;
}
DFS
<div align="center"> <img src="../pics//f7f7e3e5-7dd4-4173-9999-576b9e2ac0a2.png"/> </div>
廣度優(yōu)先搜索一層一層遍歷，每一層得到的所有新節(jié)點(diǎn)青灼，要用隊(duì)列存儲(chǔ)起來以備下一層遍歷的時(shí)候再遍歷暴心。
而深度優(yōu)先搜索在得到一個(gè)新節(jié)點(diǎn)時(shí)立馬對(duì)新節(jié)點(diǎn)進(jìn)行遍歷：從節(jié)點(diǎn) 0 出發(fā)開始遍歷，得到到新節(jié)點(diǎn) 6 時(shí)杂拨，立馬對(duì)新節(jié)點(diǎn) 6 進(jìn)行遍歷专普，得到新節(jié)點(diǎn) 4；如此反復(fù)以這種方式遍歷新節(jié)點(diǎn)弹沽，直到?jīng)]有新節(jié)點(diǎn)了檀夹，此時(shí)返回。返回到根節(jié)點(diǎn) 0 的情況是策橘，繼續(xù)對(duì)根節(jié)點(diǎn) 0 進(jìn)行遍歷炸渡，得到新節(jié)點(diǎn) 2，然后繼續(xù)以上步驟丽已。
從一個(gè)節(jié)點(diǎn)出發(fā)蚌堵，使用 DFS 對(duì)一個(gè)圖進(jìn)行遍歷時(shí)，能夠遍歷到的節(jié)點(diǎn)都是從初始節(jié)點(diǎn)可達(dá)的，DFS 常用來求解這種 可達(dá)性 問題吼畏。
在程序?qū)崿F(xiàn) DFS 時(shí)需要考慮以下問題：
- 棧：用棧來保存當(dāng)前節(jié)點(diǎn)信息督赤，當(dāng)遍歷新節(jié)點(diǎn)返回時(shí)能夠繼續(xù)遍歷當(dāng)前節(jié)點(diǎn)⌒何茫可以使用遞歸棧躲舌。
- 標(biāo)記：和 BFS 一樣同樣需要對(duì)已經(jīng)遍歷過的節(jié)點(diǎn)進(jìn)行標(biāo)記。
查找最大的連通面積
695. Max Area of Island (Easy)
[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]
private int m, n;
private int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
public int maxAreaOfIsland(int[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
m = grid.length;
n = grid[0].length;
int maxArea = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
maxArea = Math.max(maxArea, dfs(grid, i, j));
}
}
return maxArea;
}
private int dfs(int[][] grid, int r, int c) {
if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] == 0) {
return 0;
}
grid[r][c] = 0;
int area = 1;
for (int[] d : direction) {
area += dfs(grid, r + d[0], c + d[1]);
}
return area;
}
矩陣中的連通分量數(shù)目
200. Number of Islands (Medium)
Input:
11000
11000
00100
00011
Output: 3
可以將矩陣表示看成一張有向圖性雄。
private int m, n;
private int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
m = grid.length;
n = grid[0].length;
int islandsNum = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] != '0') {
dfs(grid, i, j);
islandsNum++;
}
}
}
return islandsNum;
}
private void dfs(char[][] grid, int i, int j) {
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == '0') {
return;
}
grid[i][j] = '0';
for (int[] d : direction) {
dfs(grid, i + d[0], j + d[1]);
}
}
好友關(guān)系的連通分量數(shù)目
Input:
[[1,1,0],
[1,1,0],
[0,0,1]]
Output: 2
Explanation:The 0th and 1st students are direct friends, so they are in a friend circle.
The 2nd student himself is in a friend circle. So return 2.
好友關(guān)系可以看成是一個(gè)無向圖孽糖，例如第 0 個(gè)人與第 1 個(gè)人是好友，那么 M[0][1] 和 M[1][0] 的值都為 1毅贮。
private int n;
public int findCircleNum(int[][] M) {
n = M.length;
int circleNum = 0;
boolean[] hasVisited = new boolean[n];
for (int i = 0; i < n; i++) {
if (!hasVisited[i]) {
dfs(M, i, hasVisited);
circleNum++;
}
}
return circleNum;
}
private void dfs(int[][] M, int i, boolean[] hasVisited) {
hasVisited[i] = true;
for (int k = 0; k < n; k++) {
if (M[i][k] == 1 && !hasVisited[k]) {
dfs(M, k, hasVisited);
}
}
}
填充封閉區(qū)域
130. Surrounded Regions (Medium)
For example,
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:
X X X X
X X X X
X X X X
X O X X
使被 'X' 包圍的 'O' 轉(zhuǎn)換為 'X'办悟。
先填充最外側(cè)，剩下的就是里側(cè)了滩褥。
private int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
private int m, n;
public void solve(char[][] board) {
if (board == null || board.length == 0) {
return;
}
m = board.length;
n = board[0].length;
for (int i = 0; i < m; i++) {
dfs(board, i, 0);
dfs(board, i, n - 1);
}
for (int i = 0; i < n; i++) {
dfs(board, 0, i);
dfs(board, m - 1, i);
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 'T') {
board[i][j] = 'O';
} else if (board[i][j] == 'O') {
board[i][j] = 'X';
}
}
}
}
private void dfs(char[][] board, int r, int c) {
if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] != 'O') {
return;
}
board[r][c] = 'T';
for (int[] d : direction) {
dfs(board, r + d[0], c + d[1]);
}
}
能到達(dá)的太平洋和大西洋的區(qū)域
417. Pacific Atlantic Water Flow (Medium)
Given the following 5x5 matrix:
Pacific ~ ~ ~ ~ ~
~ 1 2 2 3 (5) *
~ 3 2 3 (4) (4) *
~ 2 4 (5) 3 1 *
~ (6) (7) 1 4 5 *
~ (5) 1 1 2 4 *
* * * * * Atlantic
Return:
[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).
左邊和上邊是太平洋病蛉，右邊和下邊是大西洋，內(nèi)部的數(shù)字代表海拔瑰煎，海拔高的地方的水能夠流到低的地方铺然，求解水能夠流到太平洋和大西洋的所有位置。
private int m, n;
private int[][] matrix;
private int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
public List<int[]> pacificAtlantic(int[][] matrix) {
List<int[]> ret = new ArrayList<>();
if (matrix == null || matrix.length == 0) {
return ret;
}
m = matrix.length;
n = matrix[0].length;
this.matrix = matrix;
boolean[][] canReachP = new boolean[m][n];
boolean[][] canReachA = new boolean[m][n];
for (int i = 0; i < m; i++) {
dfs(i, 0, canReachP);
dfs(i, n - 1, canReachA);
}
for (int i = 0; i < n; i++) {
dfs(0, i, canReachP);
dfs(m - 1, i, canReachA);
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (canReachP[i][j] && canReachA[i][j]) {
ret.add(new int[]{i, j});
}
}
}
return ret;
}
private void dfs(int r, int c, boolean[][] canReach) {
if (canReach[r][c]) {
return;
}
canReach[r][c] = true;
for (int[] d : direction) {
int nextR = d[0] + r;
int nextC = d[1] + c;
if (nextR < 0 || nextR >= m || nextC < 0 || nextC >= n
|| matrix[r][c] > matrix[nextR][nextC]) {
continue;
}
dfs(nextR, nextC, canReach);
}
}
Backtracking
Backtracking（回溯）屬于 DFS酒甸。
- 普通 DFS 主要用在 可達(dá)性問題 魄健，這種問題只需要執(zhí)行到特點(diǎn)的位置然后返回即可。
- 而 Backtracking 主要用于求解 排列組合 問題插勤，例如有 { 'a','b','c' } 三個(gè)字符沽瘦，求解所有由這三個(gè)字符排列得到的字符串，這種問題在執(zhí)行到特定的位置返回之后還會(huì)繼續(xù)執(zhí)行求解過程农尖。
因?yàn)?Backtracking 不是立即就返回析恋，而要繼續(xù)求解，因此在程序?qū)崿F(xiàn)時(shí)盛卡，需要注意對(duì)元素的標(biāo)記問題：
- 在訪問一個(gè)新元素進(jìn)入新的遞歸調(diào)用時(shí)助隧，需要將新元素標(biāo)記為已經(jīng)訪問，這樣才能在繼續(xù)遞歸調(diào)用時(shí)不用重復(fù)訪問該元素滑沧；
- 但是在遞歸返回時(shí)并村，需要將元素標(biāo)記為未訪問，因?yàn)橹恍枰ＷC在一個(gè)遞歸鏈中不同時(shí)訪問一個(gè)元素滓技，可以訪問已經(jīng)訪問過但是不在當(dāng)前遞歸鏈中的元素哩牍。
數(shù)字鍵盤組合
17. Letter Combinations of a Phone Number (Medium)
<div align="center"> <img src="../pics//a3f34241-bb80-4879-8ec9-dff2d81b514e.jpg"/> </div>
Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
private static final String[] KEYS = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
public List<String> letterCombinations(String digits) {
List<String> combinations = new ArrayList<>();
if (digits == null || digits.length() == 0) {
return combinations;
}
doCombination(new StringBuilder(), combinations, digits);
return combinations;
}
private void doCombination(StringBuilder prefix, List<String> combinations, final String digits) {
if (prefix.length() == digits.length()) {
combinations.add(prefix.toString());
return;
}
int curDigits = digits.charAt(prefix.length()) - '0';
String letters = KEYS[curDigits];
for (char c : letters.toCharArray()) {
prefix.append(c); // 添加
doCombination(prefix, combinations, digits);
prefix.deleteCharAt(prefix.length() - 1); // 刪除
}
}
IP 地址劃分
93. Restore IP Addresses(Medium)
Given "25525511135",
return ["255.255.11.135", "255.255.111.35"].
public List<String> restoreIpAddresses(String s) {
List<String> addresses = new ArrayList<>();
StringBuilder tempAddress = new StringBuilder();
doRestore(0, tempAddress, addresses, s);
return addresses;
}
private void doRestore(int k, StringBuilder tempAddress, List<String> addresses, String s) {
if (k == 4 || s.length() == 0) {
if (k == 4 && s.length() == 0) {
addresses.add(tempAddress.toString());
}
return;
}
for (int i = 0; i < s.length() && i <= 2; i++) {
if (i != 0 && s.charAt(0) == '0') {
break;
}
String part = s.substring(0, i + 1);
if (Integer.valueOf(part) <= 255) {
if (tempAddress.length() != 0) {
part = "." + part;
}
tempAddress.append(part);
doRestore(k + 1, tempAddress, addresses, s.substring(i + 1));
tempAddress.delete(tempAddress.length() - part.length(), tempAddress.length());
}
}
}
在矩陣中尋找字符串
For example,
Given board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.
private final static int[][] direction = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
private int m;
private int n;
public boolean exist(char[][] board, String word) {
if (word == null || word.length() == 0) {
return true;
}
if (board == null || board.length == 0 || board[0].length == 0) {
return false;
}
m = board.length;
n = board[0].length;
boolean[][] hasVisited = new boolean[m][n];
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (backtracking(0, r, c, hasVisited, board, word)) {
return true;
}
}
}
return false;
}
private boolean backtracking(int curLen, int r, int c, boolean[][] visited, final char[][] board, final String word) {
if (curLen == word.length()) {
return true;
}
if (r < 0 || r >= m || c < 0 || c >= n
|| board[r][c] != word.charAt(curLen) || visited[r][c]) {
return false;
}
visited[r][c] = true;
for (int[] d : direction) {
if (backtracking(curLen + 1, r + d[0], c + d[1], visited, board, word)) {
return true;
}
}
visited[r][c] = false;
return false;
}
輸出二叉樹中所有從根到葉子的路徑
1
/ \
2 3
\
5
["1->2->5", "1->3"]
public List<String> binaryTreePaths(TreeNode root) {
List<String> paths = new ArrayList<>();
if (root == null) {
return paths;
}
List<Integer> values = new ArrayList<>();
backtracking(root, values, paths);
return paths;
}
private void backtracking(TreeNode node, List<Integer> values, List<String> paths) {
if (node == null) {
return;
}
values.add(node.val);
if (isLeaf(node)) {
paths.add(buildPath(values));
} else {
backtracking(node.left, values, paths);
backtracking(node.right, values, paths);
}
values.remove(values.size() - 1);
}
private boolean isLeaf(TreeNode node) {
return node.left == null && node.right == null;
}
private String buildPath(List<Integer> values) {
StringBuilder str = new StringBuilder();
for (int i = 0; i < values.size(); i++) {
str.append(values.get(i));
if (i != values.size() - 1) {
str.append("->");
}
}
return str.toString();
}
排列
[1,2,3] have the following permutations:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> permutes = new ArrayList<>();
List<Integer> permuteList = new ArrayList<>();
boolean[] hasVisited = new boolean[nums.length];
backtracking(permuteList, permutes, hasVisited, nums);
return permutes;
}
private void backtracking(List<Integer> permuteList, List<List<Integer>> permutes, boolean[] visited, final int[] nums) {
if (permuteList.size() == nums.length) {
permutes.add(new ArrayList<>(permuteList)); // 重新構(gòu)造一個(gè) List
return;
}
for (int i = 0; i < visited.length; i++) {
if (visited[i]) {
continue;
}
visited[i] = true;
permuteList.add(nums[i]);
backtracking(permuteList, permutes, visited, nums);
permuteList.remove(permuteList.size() - 1);
visited[i] = false;
}
}
含有相同元素求排列
[1,1,2] have the following unique permutations:
[[1,1,2], [1,2,1], [2,1,1]]
數(shù)組元素可能含有相同的元素，進(jìn)行排列時(shí)就有可能出現(xiàn)重復(fù)的排列殖属，要求重復(fù)的排列只返回一個(gè)姐叁。
在實(shí)現(xiàn)上瓦盛，和 Permutations 不同的是要先排序洗显，然后在添加一個(gè)元素時(shí)外潜，判斷這個(gè)元素是否等于前一個(gè)元素，如果等于挠唆，并且前一個(gè)元素還未訪問处窥，那么就跳過這個(gè)元素。
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> permutes = new ArrayList<>();
List<Integer> permuteList = new ArrayList<>();
Arrays.sort(nums); // 排序
boolean[] hasVisited = new boolean[nums.length];
backtracking(permuteList, permutes, hasVisited, nums);
return permutes;
}
private void backtracking(List<Integer> permuteList, List<List<Integer>> permutes, boolean[] visited, final int[] nums) {
if (permuteList.size() == nums.length) {
permutes.add(new ArrayList<>(permuteList));
return;
}
for (int i = 0; i < visited.length; i++) {
if (i != 0 && nums[i] == nums[i - 1] && !visited[i - 1]) {
continue; // 防止重復(fù)
}
if (visited[i]){
continue;
}
visited[i] = true;
permuteList.add(nums[i]);
backtracking(permuteList, permutes, visited, nums);
permuteList.remove(permuteList.size() - 1);
visited[i] = false;
}
}
組合
If n = 4 and k = 2, a solution is:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> combinations = new ArrayList<>();
List<Integer> combineList = new ArrayList<>();
backtracking(combineList, combinations, 1, k, n);
return combinations;
}
private void backtracking(List<Integer> combineList, List<List<Integer>> combinations, int start, int k, final int n) {
if (k == 0) {
combinations.add(new ArrayList<>(combineList));
return;
}
for (int i = start; i <= n - k + 1; i++) { // 剪枝
combineList.add(i);
backtracking(combineList, combinations, i + 1, k - 1, n);
combineList.remove(combineList.size() - 1);
}
}
組合求和
given candidate set [2, 3, 6, 7] and target 7,
A solution set is:
[[7],[2, 2, 3]]
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> combinations = new ArrayList<>();
backtracking(new ArrayList<>(), combinations, 0, target, candidates);
return combinations;
}
private void backtracking(List<Integer> tempCombination, List<List<Integer>> combinations,
int start, int target, final int[] candidates) {
if (target == 0) {
combinations.add(new ArrayList<>(tempCombination));
return;
}
for (int i = start; i < candidates.length; i++) {
if (candidates[i] <= target) {
tempCombination.add(candidates[i]);
backtracking(tempCombination, combinations, i, target - candidates[i], candidates);
tempCombination.remove(tempCombination.size() - 1);
}
}
}
含有相同元素的求組合求和
40. Combination Sum II (Medium)
For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> combinations = new ArrayList<>();
Arrays.sort(candidates);
backtracking(new ArrayList<>(), combinations, new boolean[candidates.length], 0, target, candidates);
return combinations;
}
private void backtracking(List<Integer> tempCombination, List<List<Integer>> combinations,
boolean[] hasVisited, int start, int target, final int[] candidates) {
if (target == 0) {
combinations.add(new ArrayList<>(tempCombination));
return;
}
for (int i = start; i < candidates.length; i++) {
if (i != 0 && candidates[i] == candidates[i - 1] && !hasVisited[i - 1]) {
continue;
}
if (candidates[i] <= target) {
tempCombination.add(candidates[i]);
hasVisited[i] = true;
backtracking(tempCombination, combinations, hasVisited, i + 1, target - candidates[i], candidates);
hasVisited[i] = false;
tempCombination.remove(tempCombination.size() - 1);
}
}
}
1-9 數(shù)字的組合求和
216. Combination Sum III (Medium)
Input: k = 3, n = 9
Output:
[[1,2,6], [1,3,5], [2,3,4]]
從 1-9 數(shù)字中選出 k 個(gè)數(shù)不重復(fù)的數(shù)玄组，使得它們的和為 n滔驾。
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> combinations = new ArrayList<>();
List<Integer> path = new ArrayList<>();
backtracking(k, n, 1, path, combinations);
return combinations;
}
private void backtracking(int k, int n, int start,
List<Integer> tempCombination, List<List<Integer>> combinations) {
if (k == 0 && n == 0) {
combinations.add(new ArrayList<>(tempCombination));
return;
}
if (k == 0 || n == 0) {
return;
}
for (int i = start; i <= 9; i++) {
tempCombination.add(i);
backtracking(k - 1, n - i, i + 1, tempCombination, combinations);
tempCombination.remove(tempCombination.size() - 1);
}
}
子集
找出集合的所有子集，子集不能重復(fù)俄讹，[1, 2] 和 [2, 1] 這種子集算重復(fù)
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> subsets = new ArrayList<>();
List<Integer> tempSubset = new ArrayList<>();
for (int size = 0; size <= nums.length; size++) {
backtracking(0, tempSubset, subsets, size, nums); // 不同的子集大小
}
return subsets;
}
private void backtracking(int start, List<Integer> tempSubset, List<List<Integer>> subsets,
final int size, final int[] nums) {
if (tempSubset.size() == size) {
subsets.add(new ArrayList<>(tempSubset));
return;
}
for (int i = start; i < nums.length; i++) {
tempSubset.add(nums[i]);
backtracking(i + 1, tempSubset, subsets, size, nums);
tempSubset.remove(tempSubset.size() - 1);
}
}
含有相同元素求子集
For example,
If nums = [1,2,2], a solution is:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> subsets = new ArrayList<>();
List<Integer> tempSubset = new ArrayList<>();
boolean[] hasVisited = new boolean[nums.length];
for (int size = 0; size <= nums.length; size++) {
backtracking(0, tempSubset, subsets, hasVisited, size, nums); // 不同的子集大小
}
return subsets;
}
private void backtracking(int start, List<Integer> tempSubset, List<List<Integer>> subsets, boolean[] hasVisited,
final int size, final int[] nums) {
if (tempSubset.size() == size) {
subsets.add(new ArrayList<>(tempSubset));
return;
}
for (int i = start; i < nums.length; i++) {
if (i != 0 && nums[i] == nums[i - 1] && !hasVisited[i - 1]) {
continue;
}
tempSubset.add(nums[i]);
hasVisited[i] = true;
backtracking(i + 1, tempSubset, subsets, hasVisited, size, nums);
hasVisited[i] = false;
tempSubset.remove(tempSubset.size() - 1);
}
}
分割字符串使得每個(gè)部分都是回文數(shù)
131. Palindrome Partitioning (Medium)
For example, given s = "aab",
Return
[
["aa","b"],
["a","a","b"]
]
public List<List<String>> partition(String s) {
List<List<String>> partitions = new ArrayList<>();
List<String> tempPartition = new ArrayList<>();
doPartition(s, partitions, tempPartition);
return partitions;
}
private void doPartition(String s, List<List<String>> partitions, List<String> tempPartition) {
if (s.length() == 0) {
partitions.add(new ArrayList<>(tempPartition));
return;
}
for (int i = 0; i < s.length(); i++) {
if (isPalindrome(s, 0, i)) {
tempPartition.add(s.substring(0, i + 1));
doPartition(s.substring(i + 1), partitions, tempPartition);
tempPartition.remove(tempPartition.size() - 1);
}
}
}
private boolean isPalindrome(String s, int begin, int end) {
while (begin < end) {
if (s.charAt(begin++) != s.charAt(end--)) {
return false;
}
}
return true;
}
數(shù)獨(dú)
<div align="center"> <img src="../pics//1ca52246-c443-48ae-b1f8-1cafc09ec75c.png"/> </div>
private boolean[][] rowsUsed = new boolean[9][10];
private boolean[][] colsUsed = new boolean[9][10];
private boolean[][] cubesUsed = new boolean[9][10];
private char[][] board;
public void solveSudoku(char[][] board) {
this.board = board;
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++) {
if (board[i][j] == '.') {
continue;
}
int num = board[i][j] - '0';
rowsUsed[i][num] = true;
colsUsed[j][num] = true;
cubesUsed[cubeNum(i, j)][num] = true;
}
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
backtracking(i, j);
}
}
}
private boolean backtracking(int row, int col) {
while (row < 9 && board[row][col] != '.') {
row = col == 8 ? row + 1 : row;
col = col == 8 ? 0 : col + 1;
}
if (row == 9) {
return true;
}
for (int num = 1; num <= 9; num++) {
if (rowsUsed[row][num] || colsUsed[col][num] || cubesUsed[cubeNum(row, col)][num]) {
continue;
}
rowsUsed[row][num] = colsUsed[col][num] = cubesUsed[cubeNum(row, col)][num] = true;
board[row][col] = (char) (num + '0');
if (backtracking(row, col)) {
return true;
}
board[row][col] = '.';
rowsUsed[row][num] = colsUsed[col][num] = cubesUsed[cubeNum(row, col)][num] = false;
}
return false;
}
private int cubeNum(int i, int j) {
int r = i / 3;
int c = j / 3;
return r * 3 + c;
}
N 皇后
<div align="center"> <img src="../pics//1f080e53-4758-406c-bb5f-dbedf89b63ce.jpg"/> </div>
在 n*n 的矩陣中擺放 n 個(gè)皇后哆致，并且每個(gè)皇后不能在同一行，同一列患膛，同一對(duì)角線上摊阀，求所有的 n 皇后的解。
一行一行地?cái)[放踪蹬，在確定一行中的那個(gè)皇后應(yīng)該擺在哪一列時(shí)胞此，需要用三個(gè)標(biāo)記數(shù)組來確定某一列是否合法，這三個(gè)標(biāo)記數(shù)組分別為：列標(biāo)記數(shù)組跃捣、45 度對(duì)角線標(biāo)記數(shù)組和 135 度對(duì)角線標(biāo)記數(shù)組漱牵。
45 度對(duì)角線標(biāo)記數(shù)組的維度為 2 * n - 1，通過下圖可以明確 (r, c) 的位置所在的數(shù)組下標(biāo)為 r + c疚漆。
<div align="center"> <img src="../pics//85583359-1b45-45f2-9811-4f7bb9a64db7.jpg"/> </div>
135 度對(duì)角線標(biāo)記數(shù)組的維度也是 2 * n - 1酣胀，(r, c) 的位置所在的數(shù)組下標(biāo)為 n - 1 - (r - c)。
<div align="center"> <img src="../pics//9e80f75a-b12b-4344-80c8-1f9ccc2d5246.jpg"/> </div>
private List<List<String>> solutions;
private char[][] nQueens;
private boolean[] colUsed;
private boolean[] diagonals45Used;
private boolean[] diagonals135Used;
private int n;
public List<List<String>> solveNQueens(int n) {
solutions = new ArrayList<>();
nQueens = new char[n][n];
for (int i = 0; i < n; i++) {
Arrays.fill(nQueens[i], '.');
}
colUsed = new boolean[n];
diagonals45Used = new boolean[2 * n - 1];
diagonals135Used = new boolean[2 * n - 1];
this.n = n;
backtracking(0);
return solutions;
}
private void backtracking(int row) {
if (row == n) {
List<String> list = new ArrayList<>();
for (char[] chars : nQueens) {
list.add(new String(chars));
}
solutions.add(list);
return;
}
for (int col = 0; col < n; col++) {
int diagonals45Idx = row + col;
int diagonals135Idx = n - 1 - (row - col);
if (colUsed[col] || diagonals45Used[diagonals45Idx] || diagonals135Used[diagonals135Idx]) {
continue;
}
nQueens[row][col] = 'Q';
colUsed[col] = diagonals45Used[diagonals45Idx] = diagonals135Used[diagonals135Idx] = true;
backtracking(row + 1);
colUsed[col] = diagonals45Used[diagonals45Idx] = diagonals135Used[diagonals135Idx] = false;
nQueens[row][col] = '.';
}
}
分治
給表達(dá)式加括號(hào)
241. Different Ways to Add Parentheses (Medium)
Input: "2-1-1".
((2-1)-1) = 0
(2-(1-1)) = 2
Output : [0, 2]
public List<Integer> diffWaysToCompute(String input) {
List<Integer> ways = new ArrayList<>();
for (int i = 0; i < input.length(); i++) {
char c = input.charAt(i);
if (c == '+' || c == '-' || c == '*') {
List<Integer> left = diffWaysToCompute(input.substring(0, i));
List<Integer> right = diffWaysToCompute(input.substring(i + 1));
for (int l : left) {
for (int r : right) {
switch (c) {
case '+':
ways.add(l + r);
break;
case '-':
ways.add(l - r);
break;
case '*':
ways.add(l * r);
break;
}
}
}
}
}
if (ways.size() == 0) {
ways.add(Integer.valueOf(input));
}
return ways;
}
動(dòng)態(tài)規(guī)劃
遞歸和動(dòng)態(tài)規(guī)劃都是將原問題拆成多個(gè)子問題然后求解娶聘，他們之間最本質(zhì)的區(qū)別是灵临，動(dòng)態(tài)規(guī)劃保存了子問題的解，避免重復(fù)計(jì)算趴荸。
斐波那契數(shù)列
爬樓梯
題目描述：有 N 階樓梯儒溉，每次可以上一階或者兩階，求有多少種上樓梯的方法发钝。
定義一個(gè)數(shù)組 dp 存儲(chǔ)上樓梯的方法數(shù)（為了方便討論顿涣，數(shù)組下標(biāo)從 1 開始），dp[i] 表示走到第 i 個(gè)樓梯的方法數(shù)目酝豪。第 i 個(gè)樓梯可以從第 i-1 和 i-2 個(gè)樓梯再走一步到達(dá)涛碑，走到第 i 個(gè)樓梯的方法數(shù)為走到第 i-1 和第 i-2 個(gè)樓梯的方法數(shù)之和。
<div align="center"><img src="https://latex.codecogs.com/gif.latex?dp[i]=dp[i-1]+dp[i-2]"/></div>
dp[N] 即為所求孵淘。
考慮到 dp[i] 只與 dp[i - 1] 和 dp[i - 2] 有關(guān)蒲障，因此可以只用兩個(gè)變量來存儲(chǔ) dp[i - 1] 和 dp[i - 2]引瀑，使得原來的 O(N) 空間復(fù)雜度優(yōu)化為 O(1) 復(fù)雜度。
public int climbStairs(int n) {
if (n <= 2) {
return n;
}
int pre2 = 1, pre1 = 2;
for (int i = 2; i < n; i++) {
int cur = pre1 + pre2;
pre2 = pre1;
pre1 = cur;
}
return pre1;
}
強(qiáng)盜搶劫
題目描述：搶劫一排住戶栅螟，但是不能搶鄰近的住戶蚂维，求最大搶劫量。
定義 dp 數(shù)組用來存儲(chǔ)最大的搶劫量毙籽，其中 dp[i] 表示搶到第 i 個(gè)住戶時(shí)的最大搶劫量洞斯。由于不能搶劫鄰近住戶，因此如果搶劫了第 i 個(gè)住戶那么只能搶劫 i - 2 或者 i - 3 的住戶坑赡，所以
<div align="center"><img src="https://latex.codecogs.com/gif.latex?dp[i]=max(dp[i-2],dp[i-3])+nums[i]"/></div>
public int rob(int[] nums) {
int n = nums.length;
if (n == 0) {
return 0;
}
if (n == 1) {
return nums[0];
}
int pre3 = 0, pre2 = 0, pre1 = 0;
for (int i = 0; i < n; i++) {
int cur = Math.max(pre2, pre3) + nums[i];
pre3 = pre2;
pre2 = pre1;
pre1 = cur;
}
return Math.max(pre1, pre2);
}
強(qiáng)盜在環(huán)形街區(qū)搶劫
public int rob(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int n = nums.length;
if (n == 1) {
return nums[0];
}
return Math.max(rob(nums, 0, n - 2), rob(nums, 1, n - 1));
}
private int rob(int[] nums, int first, int last) {
int pre3 = 0, pre2 = 0, pre1 = 0;
for (int i = first; i <= last; i++) {
int cur = Math.max(pre3, pre2) + nums[i];
pre3 = pre2;
pre2 = pre1;
pre1 = cur;
}
return Math.max(pre2, pre1);
}
母牛生產(chǎn)
題目描述：假設(shè)農(nóng)場中成熟的母牛每年都會(huì)生 1 頭小母牛烙如，并且永遠(yuǎn)不會(huì)死。第一年有 1 只小母牛毅否，從第二年開始亚铁，母牛開始生小母牛。每只小母牛 3 年之后成熟又可以生小母牛螟加。給定整數(shù) N刀闷，求 N 年后牛的數(shù)量。
第 i 年成熟的牛的數(shù)量為：
<div align="center"><img src="https://latex.codecogs.com/gif.latex?dp[i]=dp[i-1]+dp[i-3]"/></div>
信件錯(cuò)排
題目描述：有 N 個(gè) 信 和 信封仰迁，它們被打亂甸昏，求錯(cuò)誤裝信方式的數(shù)量。
定義一個(gè)數(shù)組 dp 存儲(chǔ)錯(cuò)誤方式數(shù)量徐许，dp[i] 表示前 i 個(gè)信和信封的錯(cuò)誤方式數(shù)量施蜜。假設(shè)第 i 個(gè)信裝到第 j 個(gè)信封里面，而第 j 個(gè)信裝到第 k 個(gè)信封里面雌隅。根據(jù) i 和 k 是否相等翻默，有兩種情況：
- i==k，交換 i 和 k 的信后恰起，它們的信和信封在正確的位置修械，但是其余 i-2 封信有 dp[i-2] 種錯(cuò)誤裝信的方式。由于 j 有 i-1 種取值检盼，因此共有 (i-1)*dp[i-2] 種錯(cuò)誤裝信方式肯污。
- i != k，交換 i 和 j 的信后吨枉，第 i 個(gè)信和信封在正確的位置蹦渣，其余 i-1 封信有 dp[i-1] 種錯(cuò)誤裝信方式。由于 j 有 i-1 種取值貌亭，因此共有 (i-1)*dp[i-1] 種錯(cuò)誤裝信方式柬唯。
綜上所述，錯(cuò)誤裝信數(shù)量方式數(shù)量為：
<div align="center"><img src="https://latex.codecogs.com/gif.latex?dp[i]=(i-1)dp[i-2]+(i-1)dp[i-1]"/></div>
dp[N] 即為所求圃庭。
矩陣路徑
矩陣的最小路徑和
[[1,3,1],
[1,5,1],
[4,2,1]]
Given the above grid map, return 7. Because the path 1→3→1→1→1 minimizes the sum.
題目描述：求從矩陣的左上角到右下角的最小路徑和锄奢，每次只能向右和向下移動(dòng)失晴。
public int minPathSum(int[][] grid) {
if (grid.length == 0 || grid[0].length == 0) {
return 0;
}
int m = grid.length, n = grid[0].length;
int[] dp = new int[n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (j == 0) {
dp[j] = dp[j]; // 只能從上側(cè)走到該位置
} else if (i == 0) {
dp[j] = dp[j - 1]; // 只能從左側(cè)走到該位置
} else {
dp[j] = Math.min(dp[j - 1], dp[j]);
}
dp[j] += grid[i][j];
}
}
return dp[n - 1];
}
矩陣的總路徑數(shù)
題目描述：統(tǒng)計(jì)從矩陣左上角到右下角的路徑總數(shù)，每次只能向右或者向下移動(dòng)拘央。
<div align="center"> <img src="../pics//7c98e1b6-c446-4cde-8513-5c11b9f52aea.jpg"/> </div>
public int uniquePaths(int m, int n) {
int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[j] = dp[j] + dp[j - 1];
}
}
return dp[n - 1];
}
也可以直接用數(shù)學(xué)公式求解涂屁，這是一個(gè)組合問題。機(jī)器人總共移動(dòng)的次數(shù) S=m+n-2堪滨，向下移動(dòng)的次數(shù) D=m-1胯陋，那么問題可以看成從 S 從取出 D 個(gè)位置的組合數(shù)量蕊温，這個(gè)問題的解為 C(S, D)袱箱。
public int uniquePaths(int m, int n) {
int S = m + n - 2; // 總共的移動(dòng)次數(shù)
int D = m - 1; // 向下的移動(dòng)次數(shù)
long ret = 1;
for (int i = 1; i <= D; i++) {
ret = ret * (S - D + i) / i;
}
return (int) ret;
}
數(shù)組區(qū)間
數(shù)組區(qū)間和
303. Range Sum Query - Immutable (Easy)
Given nums = [-2, 0, 3, -5, 2, -1]
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
求區(qū)間 i ~ j 的和，可以轉(zhuǎn)換為 sum[j] - sum[i-1]义矛，其中 sum[i] 為 0 ~ i 的和发笔。
class NumArray {
private int[] sums;
public NumArray(int[] nums) {
sums = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
sums[i] = i == 0 ? nums[0] : sums[i - 1] + nums[i];
}
}
public int sumRange(int i, int j) {
return i == 0 ? sums[j] : sums[j] - sums[i - 1];
}
}
子數(shù)組最大的和
For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.
public int maxSubArray(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int preSum = nums[0];
int maxSum = preSum;
for (int i = 1; i < nums.length; i++) {
preSum = preSum > 0 ? preSum + nums[i] : nums[i];
maxSum = Math.max(maxSum, preSum);
}
return maxSum;
}
數(shù)組中等差遞增子區(qū)間的個(gè)數(shù)
413. Arithmetic Slices (Medium)
A = [1, 2, 3, 4]
return: 3, for 3 arithmetic slices in A: [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.
dp[i] 表示以 A[i] 為結(jié)尾的等差遞增子區(qū)間的個(gè)數(shù)。
如果 A[i] - A[i - 1] == A[i - 1] - A[i - 2]凉翻，表示 [A[i - 2], A[i - 1], A[i]] 是一個(gè)等差遞增子區(qū)間了讨。如果 [A[i - 3], A[i - 2], A[i - 1]] 是一個(gè)等差遞增子區(qū)間，那么 [A[i - 3], A[i - 2], A[i - 1], A[i]] 也是制轰。因此在這個(gè)條件下前计，dp[i] = dp[i-1] + 1。
public int numberOfArithmeticSlices(int[] A) {
if (A == null || A.length == 0) {
return 0;
}
int n = A.length;
int[] dp = new int[n];
for (int i = 2; i < n; i++) {
if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
dp[i] = dp[i - 1] + 1;
}
}
int total = 0;
for (int cnt : dp) {
total += cnt;
}
return total;
}
分割整數(shù)
分割整數(shù)的最大乘積
題目描述：For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).
public int integerBreak(int n) {
int[] dp = new int[n + 1];
dp[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i - 1; j++) {
dp[i] = Math.max(dp[i], Math.max(j * dp[i - j], j * (i - j)));
}
}
return dp[n];
}
按平方數(shù)來分割整數(shù)
題目描述：For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.
public int numSquares(int n) {
List<Integer> squareList = generateSquareList(n);
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++) {
int min = Integer.MAX_VALUE;
for (int square : squareList) {
if (square > i) {
break;
}
min = Math.min(min, dp[i - square] + 1);
}
dp[i] = min;
}
return dp[n];
}
private List<Integer> generateSquareList(int n) {
List<Integer> squareList = new ArrayList<>();
int diff = 3;
int square = 1;
while (square <= n) {
squareList.add(square);
square += diff;
diff += 2;
}
return squareList;
}
分割整數(shù)構(gòu)成字母字符串
題目描述：Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).
public int numDecodings(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int n = s.length();
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = s.charAt(0) == '0' ? 0 : 1;
for (int i = 2; i <= n; i++) {
int one = Integer.valueOf(s.substring(i - 1, i));
if (one != 0) {
dp[i] += dp[i - 1];
}
if (s.charAt(i - 2) == '0') {
continue;
}
int two = Integer.valueOf(s.substring(i - 2, i));
if (two <= 26) {
dp[i] += dp[i - 2];
}
}
return dp[n];
}
最長遞增子序列
已知一個(gè)序列 {S1, S2,...,Sn} 垃杖，取出若干數(shù)組成新的序列 {Si1, Si2,..., Sim}男杈，其中 i1、i2 ... im 保持遞增调俘，即新序列中各個(gè)數(shù)仍然保持原數(shù)列中的先后順序伶棒，稱新序列為原序列的一個(gè) 子序列 。
如果在子序列中彩库，當(dāng)下標(biāo) ix > iy 時(shí)肤无，Six > Siy，稱子序列為原序列的一個(gè) 遞增子序列 骇钦。
定義一個(gè)數(shù)組 dp 存儲(chǔ)最長遞增子序列的長度宛渐，dp[n] 表示以 Sn 結(jié)尾的序列的最長遞增子序列長度。對(duì)于一個(gè)遞增子序列 {Si1, Si2,...,Sim}眯搭，如果 im < n 并且 Sim < Sn 皇忿，此時(shí) {Si1, Si2,..., Sim, Sn} 為一個(gè)遞增子序列，遞增子序列的長度增加 1坦仍。滿足上述條件的遞增子序列中鳍烁，長度最長的那個(gè)遞增子序列就是要找的，在長度最長的遞增子序列上加上 Sn 就構(gòu)成了以 Sn 為結(jié)尾的最長遞增子序列繁扎。因此 dp[n] = max{ dp[i]+1 | Si < Sn && i < n} 幔荒。
因?yàn)樵谇?dp[n] 時(shí)可能無法找到一個(gè)滿足條件的遞增子序列糊闽，此時(shí) {Sn} 就構(gòu)成了遞增子序列，需要對(duì)前面的求解方程做修改爹梁，令 dp[n] 最小為 1右犹，即：
<div align="center"><img src="https://latex.codecogs.com/gif.latex?dp[n]=max{1,dp[i]+1|S_i<S_n&&i<n}"/></div>
對(duì)于一個(gè)長度為 N 的序列，最長遞增子序列并不一定會(huì)以 SN 為結(jié)尾姚垃，因此 dp[N] 不是序列的最長遞增子序列的長度念链，需要遍歷 dp 數(shù)組找出最大值才是所要的結(jié)果，即 max{ dp[i] | 1 <= i <= N} 即為所求积糯。
最長遞增子序列
300. Longest Increasing Subsequence (Medium)
public int lengthOfLIS(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
for (int i = 0; i < n; i++) {
int max = 1;
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
max = Math.max(max, dp[j] + 1);
}
}
dp[i] = max;
}
return Arrays.stream(dp).max().orElse(0);
}
使用 Stream 求最大值會(huì)導(dǎo)致運(yùn)行時(shí)間過長掂墓，可以改成以下形式：
int ret = 0;
for (int i = 0; i < n; i++) {
ret = Math.max(ret, dp[i]);
}
return ret;
以上解法的時(shí)間復(fù)雜度為 O(N2) ，可以使用二分查找將時(shí)間復(fù)雜度降低為 O(NlogN)看成。
定義一個(gè) tails 數(shù)組君编，其中 tails[i] 存儲(chǔ)長度為 i + 1 的最長遞增子序列的最后一個(gè)元素。對(duì)于一個(gè)元素 x川慌，
- 如果它大于 tails 數(shù)組所有的值吃嘿，那么把它添加到 tails 后面，表示最長遞增子序列長度加 1梦重；
- 如果 tails[i-1] < x <= tails[i]兑燥，那么更新 tails[i-1] = x。
例如對(duì)于數(shù)組 [4,3,6,5]琴拧，有：
tails len num
[] 0 4
[4] 1 3
[3] 1 6
[3,6] 2 5
[3,5] 2 null
可以看出 tails 數(shù)組保持有序降瞳，因此在查找 Si 位于 tails 數(shù)組的位置時(shí)就可以使用二分查找。
public int lengthOfLIS(int[] nums) {
int n = nums.length;
int[] tails = new int[n];
int len = 0;
for (int num : nums) {
int index = binarySearch(tails, len, num);
tails[index] = num;
if (index == len) {
len++;
}
}
return len;
}
private int binarySearch(int[] tails, int len, int key) {
int l = 0, h = len;
while (l < h) {
int mid = l + (h - l) / 2;
if (tails[mid] == key) {
return mid;
} else if (tails[mid] > key) {
h = mid;
} else {
l = mid + 1;
}
}
return l;
}
一組整數(shù)對(duì)能夠構(gòu)成的最長鏈
646. Maximum Length of Pair Chain (Medium)
Input: [[1,2], [2,3], [3,4]]
Output: 2
Explanation: The longest chain is [1,2] -> [3,4]
題目描述：對(duì)于 (a, b) 和 (c, d) 艾蓝，如果 b < c力崇，則它們可以構(gòu)成一條鏈。
public int findLongestChain(int[][] pairs) {
if (pairs == null || pairs.length == 0) {
return 0;
}
Arrays.sort(pairs, (a, b) -> (a[0] - b[0]));
int n = pairs.length;
int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (pairs[j][1] < pairs[i][0]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
return Arrays.stream(dp).max().orElse(0);
}
最長擺動(dòng)子序列
376. Wiggle Subsequence (Medium)
Input: [1,7,4,9,2,5]
Output: 6
The entire sequence is a wiggle sequence.
Input: [1,17,5,10,13,15,10,5,16,8]
Output: 7
There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].
Input: [1,2,3,4,5,6,7,8,9]
Output: 2
要求：使用 O(N) 時(shí)間復(fù)雜度求解赢织。
public int wiggleMaxLength(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int up = 1, down = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] > nums[i - 1]) {
up = down + 1;
} else if (nums[i] < nums[i - 1]) {
down = up + 1;
}
}
return Math.max(up, down);
}
最長公共子序列
對(duì)于兩個(gè)子序列 S1 和 S2亮靴，找出它們最長的公共子序列。
定義一個(gè)二維數(shù)組 dp 用來存儲(chǔ)最長公共子序列的長度于置，其中 dp[i][j] 表示 S1 的前 i 個(gè)字符與 S2 的前 j 個(gè)字符最長公共子序列的長度茧吊。考慮 S1i 與 S2j 值是否相等八毯，分為兩種情況：
- 當(dāng) S1i==S2j 時(shí)搓侄，那么就能在 S1 的前 i-1 個(gè)字符與 S2 的前 j-1 個(gè)字符最長公共子序列的基礎(chǔ)上再加上 S1i 這個(gè)值，最長公共子序列長度加 1 话速，即 dp[i][j] = dp[i-1][j-1] + 1讶踪。
- 當(dāng) S1i != S2j 時(shí)，此時(shí)最長公共子序列為 S1 的前 i-1 個(gè)字符和 S2 的前 j 個(gè)字符最長公共子序列泊交，與 S1 的前 i 個(gè)字符和 S2 的前 j-1 個(gè)字符最長公共子序列乳讥，它們的最大者柱查，即 dp[i][j] = max{ dp[i-1][j], dp[i][j-1] }。
綜上云石，最長公共子序列的狀態(tài)轉(zhuǎn)移方程為：
<div align="center"><img src="https://latex.codecogs.com/gif.latex?dp[i][j]=\left{\begin{array}{rcl}dp[i-1][j-1]&&{S1_i==S2_j}\max(dp[i-1][j],dp[i][j-1])&&{S1_i<>S2_j}\end{array}\right."/></div>
對(duì)于長度為 N 的序列 S1 和 長度為 M 的序列 S2唉工，dp[N][M] 就是序列 S1 和序列 S2 的最長公共子序列長度。
與最長遞增子序列相比汹忠，最長公共子序列有以下不同點(diǎn)：
- 針對(duì)的是兩個(gè)序列淋硝，求它們的最長公共子序列。
- 在最長遞增子序列中宽菜，dp[i] 表示以 Si 為結(jié)尾的最長遞增子序列長度谣膳，子序列必須包含 Si ；在最長公共子序列中赋焕，dp[i][j] 表示 S1 中前 i 個(gè)字符與 S2 中前 j 個(gè)字符的最長公共子序列長度参歹，不一定包含 S1i 和 S2j 仰楚。
- 在求最終解時(shí)隆判，最長公共子序列中 dp[N][M] 就是最終解友绝，而最長遞增子序列中 dp[N] 不是最終解度迂，因?yàn)橐?SN 為結(jié)尾的最長遞增子序列不一定是整個(gè)序列最長遞增子序列，需要遍歷一遍 dp 數(shù)組找到最大者八匠。
public int lengthOfLCS(int[] nums1, int[] nums2) {
int n1 = nums1.length, n2 = nums2.length;
int[][] dp = new int[n1 + 1][n2 + 1];
for (int i = 1; i <= n1; i++) {
for (int j = 1; j <= n2; j++) {
if (nums1[i - 1] == nums2[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];
}
最大連續(xù)子數(shù)組
題目描述：給定一個(gè)數(shù)組arr捂襟，數(shù)組中的元素有整數(shù)也有負(fù)數(shù)咬腕，數(shù)組中的一個(gè)或者連續(xù)多個(gè)數(shù)組成一個(gè)子數(shù)組。
求所有子數(shù)組里面的最大和葬荷。例如現(xiàn)在有數(shù)組 {1 涨共， -2 ， 3 宠漩， 10 举反， -4 ， 7 扒吁， 2 火鼻， -5 }。
public static int maxsubarr(int[] array)
{
if(array == null || array.length == 0)
return 0;
int sumMax = array[0];
int currentMax = array[0];//保存子數(shù)組相加之和
//從頭開始遍歷相加數(shù)組中的元素
for (int i = 1; i < array.length; i++)
{
//若是相加之和一旦小于零雕崩，子數(shù)組從新開始魁索，否則相加
currentMax=currentMax < 0? array[i]:currentMax + array[i];
//sumMax保存最大的子數(shù)組的和
sumMax=Math.max(sumMax,currentMax);
}
return sumMax;
}
0-1 背包
有一個(gè)容量為 N 的背包，要用這個(gè)背包裝下物品的價(jià)值最大盼铁，這些物品有兩個(gè)屬性：體積 w 和價(jià)值 v粗蔚。
定義一個(gè)二維數(shù)組 dp 存儲(chǔ)最大價(jià)值，其中 dp[i][j] 表示前 i 件物品體積不超過 j 的情況下能達(dá)到的最大價(jià)值饶火。設(shè)第 i 件物品體積為 w鹏控，價(jià)值為 v冬念，根據(jù)第 i 件物品是否添加到背包中，可以分兩種情況討論：
- 第 i 件物品沒添加到背包牧挣，總體積不超過 j 的前 i 件物品的最大價(jià)值就是總體積不超過 j 的前 i-1 件物品的最大價(jià)值急前，dp[i][j] = dp[i-1][j]。
- 第 i 件物品添加到背包中瀑构，dp[i][j] = dp[i-1][j-w] + v裆针。
第 i 件物品可添加也可以不添加，取決于哪種情況下最大價(jià)值更大寺晌。
綜上世吨，0-1 背包的狀態(tài)轉(zhuǎn)移方程為：
<div align="center"><img src="https://latex.codecogs.com/gif.latex?dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v)"/></div>
public int knapsack(int W, int N, int[] weights, int[] values) {
int[][] dp = new int[N + 1][W + 1];
for (int i = 1; i <= N; i++) {
int w = weights[i - 1], v = values[i - 1];
for (int j = 1; j <= W; j++) {
if (j >= w) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w] + v);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[N][W];
}
空間優(yōu)化
在程序?qū)崿F(xiàn)時(shí)可以對(duì) 0-1 背包做優(yōu)化。觀察狀態(tài)轉(zhuǎn)移方程可以知道呻征，前 i 件物品的狀態(tài)僅由前 i-1 件物品的狀態(tài)有關(guān)耘婚，因此可以將 dp 定義為一維數(shù)組，其中 dp[j] 既可以表示 dp[i-1][j] 也可以表示 dp[i][j]陆赋。此時(shí)沐祷，
<div align="center"><img src="https://latex.codecogs.com/gif.latex?dp[j]=max(dp[j],dp[j-w]+v)"/></div>
因?yàn)?dp[j-w] 表示 dp[i-1][j-w]，因此不能先求 dp[i][j-w]攒岛，以防止將 dp[i-1][j-w] 覆蓋赖临。也就是說要先計(jì)算 dp[i][j] 再計(jì)算 dp[i][j-w]，在程序?qū)崿F(xiàn)時(shí)需要按倒序來循環(huán)求解灾锯。
public int knapsack(int W, int N, int[] weights, int[] values) {
int[] dp = new int[W + 1];
for (int i = 1; i <= N; i++) {
int w = weights[i - 1], v = values[i - 1];
for (int j = W; j >= 1; j--) {
if (j >= w) {
dp[j] = Math.max(dp[j], dp[j - w] + v);
}
}
}
return dp[W];
}
無法使用貪心算法的解釋
0-1 背包問題無法使用貪心算法來求解兢榨，也就是說不能按照先添加性價(jià)比最高的物品來達(dá)到最優(yōu)，這是因?yàn)檫@種方式可能造成背包空間的浪費(fèi)顺饮，從而無法達(dá)到最優(yōu)吵聪。考慮下面的物品和一個(gè)容量為 5 的背包兼雄，如果先添加物品 0 再添加物品 1吟逝，那么只能存放的價(jià)值為 16，浪費(fèi)了大小為 2 的空間君旦。最優(yōu)的方式是存放物品 1 和物品 2澎办，價(jià)值為 22.
| id | w | v | v/w |
|---|---|---|---|
| 0 | 1 | 6 | 6 |
| 1 | 2 | 10 | 5 |
| 2 | 3 | 12 | 4 |
變種
完全背包：物品數(shù)量為無限個(gè)
多重背包：物品數(shù)量有限制
多維費(fèi)用背包：物品不僅有重量，還有體積金砍，同時(shí)考慮這兩種限制
其它：物品之間相互約束或者依賴
劃分?jǐn)?shù)組為和相等的兩部分
416. Partition Equal Subset Sum (Medium)
Input: [1, 5, 11, 5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
可以看成一個(gè)背包大小為 sum/2 的 0-1 背包問題局蚀。
public boolean canPartition(int[] nums) {
int sum = computeArraySum(nums);
if (sum % 2 != 0) {
return false;
}
int W = sum / 2;
boolean[] dp = new boolean[W + 1];
dp[0] = true;
Arrays.sort(nums);
for (int num : nums) { // 0-1 背包一個(gè)物品只能用一次
for (int i = W; i >= num; i--) { // 從后往前，先計(jì)算 dp[i] 再計(jì)算 dp[i-num]
dp[i] = dp[i] || dp[i - num];
}
}
return dp[W];
}
private int computeArraySum(int[] nums) {
int sum = 0;
for (int num : nums) {
sum += num;
}
return sum;
}
改變一組數(shù)的正負(fù)號(hào)使得它們的和為一給定數(shù)
Input: nums is [1, 1, 1, 1, 1], S is 3.
Output: 5
Explanation:
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
There are 5 ways to assign symbols to make the sum of nums be target 3.
該問題可以轉(zhuǎn)換為 Subset Sum 問題恕稠，從而使用 0-1 背包的方法來求解琅绅。
可以將這組數(shù)看成兩部分，P 和 N鹅巍，其中 P 使用正號(hào)千扶，N 使用負(fù)號(hào)料祠，有以下推導(dǎo)：
sum(P) - sum(N) = target
sum(P) + sum(N) + sum(P) - sum(N) = target + sum(P) + sum(N)
2 * sum(P) = target + sum(nums)
因此只要找到一個(gè)子集，令它們都取正號(hào)澎羞，并且和等于 (target + sum(nums))/2髓绽，就證明存在解。
public int findTargetSumWays(int[] nums, int S) {
int sum = computeArraySum(nums);
if (sum < S || (sum + S) % 2 == 1) {
return 0;
}
int W = (sum + S) / 2;
int[] dp = new int[W + 1];
dp[0] = 1;
Arrays.sort(nums);
for (int num : nums) {
for (int i = W; i >= num; i--) {
dp[i] = dp[i] + dp[i - num];
}
}
return dp[W];
}
private int computeArraySum(int[] nums) {
int sum = 0;
for (int num : nums) {
sum += num;
}
return sum;
}
DFS 解法：
public int findTargetSumWays(int[] nums, int S) {
return findTargetSumWays(nums, 0, S);
}
private int findTargetSumWays(int[] nums, int start, int S) {
if (start == nums.length) {
return S == 0 ? 1 : 0;
}
return findTargetSumWays(nums, start + 1, S + nums[start])
+ findTargetSumWays(nums, start + 1, S - nums[start]);
}
字符串按單詞列表分割
s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".
dict 中的單詞沒有使用次數(shù)的限制妆绞，因此這是一個(gè)完全背包問題顺呕。
0-1 背包和完全背包在實(shí)現(xiàn)上的不同之處是，0-1 背包對(duì)物品的迭代是在最外層括饶，而完全背包對(duì)物品的迭代是在最里層株茶。
public boolean wordBreak(String s, List<String> wordDict) {
int n = s.length();
boolean[] dp = new boolean[n + 1];
dp[0] = true;
for (int i = 1; i <= n; i++) {
for (String word : wordDict) { // 完全一個(gè)物品可以使用多次
int len = word.length();
if (len <= i && word.equals(s.substring(i - len, i))) {
dp[i] = dp[i] || dp[i - len];
}
}
}
return dp[n];
}
01 字符構(gòu)成最多的字符串
Input: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
Output: 4
Explanation: There are totally 4 strings can be formed by the using of 5 0s and 3 1s, which are "10","0001","1","0"
這是一個(gè)多維費(fèi)用的 0-1 背包問題，有兩個(gè)背包大小图焰，0 的數(shù)量和 1 的數(shù)量启盛。
public int findMaxForm(String[] strs, int m, int n) {
if (strs == null || strs.length == 0) {
return 0;
}
int[][] dp = new int[m + 1][n + 1];
for (String s : strs) { // 每個(gè)字符串只能用一次
int ones = 0, zeros = 0;
for (char c : s.toCharArray()) {
if (c == '0') {
zeros++;
} else {
ones++;
}
}
for (int i = m; i >= zeros; i--) {
for (int j = n; j >= ones; j--) {
dp[i][j] = Math.max(dp[i][j], dp[i - zeros][j - ones] + 1);
}
}
}
return dp[m][n];
}
找零錢的方法數(shù)
Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)
Example 2:
coins = [2], amount = 3
return -1.
題目描述：給一些面額的硬幣，要求用這些硬幣來組成給定面額的錢數(shù)技羔，并且使得硬幣數(shù)量最少僵闯。硬幣可以重復(fù)使用。
- 物品：硬幣
- 物品大卸槔：面額
- 物品價(jià)值：數(shù)量
因?yàn)橛矌趴梢灾貜?fù)使用棍厂，因此這是一個(gè)完全背包問題颗味。
public int coinChange(int[] coins, int amount) {
if (coins == null || coins.length == 0) {
return 0;
}
int[] minimum = new int[amount + 1];
Arrays.fill(minimum, amount + 1);
minimum[0] = 0;
Arrays.sort(coins);
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.length && coins[j] <= i; j++) {
minimum[i] = Math.min(minimum[i], minimum[i - coins[j]] + 1);
}
}
return minimum[amount] > amount ? -1 : minimum[amount];
}
組合總和
377. Combination Sum IV (Medium)
nums = [1, 2, 3]
target = 4
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Note that different sequences are counted as different combinations.
Therefore the output is 7.
完全背包超陆。
public int combinationSum4(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return 0;
}
int[] maximum = new int[target + 1];
maximum[0] = 1;
Arrays.sort(nums);
for (int i = 1; i <= target; i++) {
for (int j = 0; j < nums.length && nums[j] <= i; j++) {
maximum[i] += maximum[i - nums[j]];
}
}
return maximum[target];
}
只能進(jìn)行 k 次的股票交易
188. Best Time to Buy and Sell Stock IV (Hard)
public int maxProfit(int k, int[] prices) {
int n = prices.length;
if (k >= n / 2) { // 這種情況下該問題退化為普通的股票交易問題
int maxProfit = 0;
for (int i = 1; i < n; i++) {
if (prices[i] > prices[i - 1]) {
maxProfit += prices[i] - prices[i - 1];
}
}
return maxProfit;
}
int[][] maxProfit = new int[k + 1][n];
for (int i = 1; i <= k; i++) {
int localMax = maxProfit[i - 1][0] - prices[0];
for (int j = 1; j < n; j++) {
maxProfit[i][j] = Math.max(maxProfit[i][j - 1], prices[j] + localMax);
localMax = Math.max(localMax, maxProfit[i - 1][j] - prices[j]);
}
}
return maxProfit[k][n - 1];
}
只能進(jìn)行兩次的股票交易
123. Best Time to Buy and Sell Stock III (Hard)
public int maxProfit(int[] prices) {
int firstBuy = Integer.MIN_VALUE, firstSell = 0;
int secondBuy = Integer.MIN_VALUE, secondSell = 0;
for (int curPrice : prices) {
if (firstBuy < -curPrice) {
firstBuy = -curPrice;
}
if (firstSell < firstBuy + curPrice) {
firstSell = firstBuy + curPrice;
}
if (secondBuy < firstSell - curPrice) {
secondBuy = firstSell - curPrice;
}
if (secondSell < secondBuy + curPrice) {
secondSell = secondBuy + curPrice;
}
}
return secondSell;
}
股票交易
需要冷卻期的股票交易
309. Best Time to Buy and Sell Stock with Cooldown(Medium)
題目描述：交易之后需要有一天的冷卻時(shí)間。
<div align="center"> <img src="../pics//a3da4342-078b-43e2-b748-7e71bec50dc4.png"/> </div>
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) {
return 0;
}
int N = prices.length;
int[] buy = new int[N];
int[] s1 = new int[N];
int[] sell = new int[N];
int[] s2 = new int[N];
s1[0] = buy[0] = -prices[0];
sell[0] = s2[0] = 0;
for (int i = 1; i < N; i++) {
buy[i] = s2[i - 1] - prices[i];
s1[i] = Math.max(buy[i - 1], s1[i - 1]);
sell[i] = Math.max(buy[i - 1], s1[i - 1]) + prices[i];
s2[i] = Math.max(s2[i - 1], sell[i - 1]);
}
return Math.max(sell[N - 1], s2[N - 1]);
}
需要交易費(fèi)用的股票交易
714. Best Time to Buy and Sell Stock with Transaction Fee (Medium)
Input: prices = [1, 3, 2, 8, 4, 9], fee = 2
Output: 8
Explanation: The maximum profit can be achieved by:
Buying at prices[0] = 1
Selling at prices[3] = 8
Buying at prices[4] = 4
Selling at prices[5] = 9
The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
題目描述：每交易一次浦马，都要支付一定的費(fèi)用时呀。
<div align="center"> <img src="../pics//61942711-45a0-4e11-bbc9-434e31436f33.png"/> </div>
public int maxProfit(int[] prices, int fee) {
int N = prices.length;
int[] buy = new int[N];
int[] s1 = new int[N];
int[] sell = new int[N];
int[] s2 = new int[N];
s1[0] = buy[0] = -prices[0];
sell[0] = s2[0] = 0;
for (int i = 1; i < N; i++) {
buy[i] = Math.max(sell[i - 1], s2[i - 1]) - prices[i];
s1[i] = Math.max(buy[i - 1], s1[i - 1]);
sell[i] = Math.max(buy[i - 1], s1[i - 1]) - fee + prices[i];
s2[i] = Math.max(s2[i - 1], sell[i - 1]);
}
return Math.max(sell[N - 1], s2[N - 1]);
}
買入和售出股票最大的收益
121. Best Time to Buy and Sell Stock (Easy)
題目描述：只進(jìn)行一次交易。
只要記錄前面的最小價(jià)格晶默，將這個(gè)最小價(jià)格作為買入價(jià)格谨娜，然后將當(dāng)前的價(jià)格作為售出價(jià)格，查看當(dāng)前收益是不是最大收益磺陡。
public int maxProfit(int[] prices) {
int n = prices.length;
if (n == 0) return 0;
int soFarMin = prices[0];
int max = 0;
for (int i = 1; i < n; i++) {
if (soFarMin > prices[i]) soFarMin = prices[i];
else max = Math.max(max, prices[i] - soFarMin);
}
return max;
}
字符串編輯
刪除兩個(gè)字符串的字符使它們相等
583. Delete Operation for Two Strings (Medium)
Input: "sea", "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".
可以轉(zhuǎn)換為求兩個(gè)字符串的最長公共子序列問題趴梢。
public int minDistance(String word1, String word2) {
int m = word1.length(), n = word2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0) {
continue;
}
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
}
}
}
return m + n - 2 * dp[m][n];
}
編輯距離
Example 1:
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')
Example 2:
Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation:
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')
題目描述：修改一個(gè)字符串成為另一個(gè)字符串，使得修改次數(shù)最少币他。一次修改操作包括：插入一個(gè)字符坞靶、刪除一個(gè)字符、替換一個(gè)字符蝴悉。
public int minDistance(String word1, String word2) {
if (word1 == null || word2 == null) {
return 0;
}
int m = word1.length(), n = word2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
dp[i][0] = i;
}
for (int i = 1; i <= n; i++) {
dp[0][i] = i;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j])) + 1;
}
}
}
return dp[m][n];
}
復(fù)制粘貼字符
題目描述：最開始只有一個(gè)字符 A彰阴，問需要多少次操作能夠得到 n 個(gè)字符 A，每次操作可以復(fù)制當(dāng)前所有的字符拍冠，或者粘貼尿这。
Input: 3
Output: 3
Explanation:
Intitally, we have one character 'A'.
In step 1, we use Copy All operation.
In step 2, we use Paste operation to get 'AA'.
In step 3, we use Paste operation to get 'AAA'.
public int minSteps(int n) {
if (n == 1) return 0;
for (int i = 2; i <= Math.sqrt(n); i++) {
if (n % i == 0) return i + minSteps(n / i);
}
return n;
}
public int minSteps(int n) {
int[] dp = new int[n + 1];
int h = (int) Math.sqrt(n);
for (int i = 2; i <= n; i++) {
dp[i] = i;
for (int j = 2; j <= h; j++) {
if (i % j == 0) {
dp[i] = dp[j] + dp[i / j];
break;
}
}
}
return dp[n];
}
數(shù)學(xué)
素?cái)?shù)
素?cái)?shù)分解
每一個(gè)數(shù)都可以分解成素?cái)?shù)的乘積簇抵，例如 84 = 22 * 31 * 50 * 71 * 110 * 130 * 170 * …
整除
令 x = 2m0 * 3m1 * 5m2 * 7m3 * 11m4 * …
令 y = 2n0 * 3n1 * 5n2 * 7n3 * 11n4 * …
如果 x 整除 y（y mod x == 0），則對(duì)于所有 i射众，mi <= ni碟摆。
最大公約數(shù)最小公倍數(shù)
x 和 y 的最大公約數(shù)為：gcd(x,y) = 2min(m0,n0) * 3min(m1,n1) * 5min(m2,n2) * ...
x 和 y 的最小公倍數(shù)為：lcm(x,y) = 2max(m0,n0) * 3max(m1,n1) * 5max(m2,n2) * ...
生成素?cái)?shù)序列
埃拉托斯特尼篩法在每次找到一個(gè)素?cái)?shù)時(shí)，將能被素?cái)?shù)整除的數(shù)排除掉叨橱。
public int countPrimes(int n) {
boolean[] notPrimes = new boolean[n + 1];
int count = 0;
for (int i = 2; i < n; i++) {
if (notPrimes[i]) {
continue;
}
count++;
// 從 i * i 開始焦履，因?yàn)槿绻?k < i，那么 k * i 在之前就已經(jīng)被去除過了
for (long j = (long) (i) * i; j < n; j += i) {
notPrimes[(int) j] = true;
}
}
return count;
}
最大公約數(shù)
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a% b);
}
最小公倍數(shù)為兩數(shù)的乘積除以最大公約數(shù)雏逾。
int lcm(int a, int b) {
return a * b / gcd(a, b);
}
使用位操作和減法求解最大公約數(shù)
對(duì)于 a 和 b 的最大公約數(shù) f(a, b)嘉裤，有：
- 如果 a 和 b 均為偶數(shù)，f(a, b) = 2*f(a/2, b/2);
- 如果 a 是偶數(shù) b 是奇數(shù)栖博，f(a, b) = f(a/2, b);
- 如果 b 是偶數(shù) a 是奇數(shù)屑宠，f(a, b) = f(a, b/2);
- 如果 a 和 b 均為奇數(shù)，f(a, b) = f(b, a-b);
乘 2 和除 2 都可以轉(zhuǎn)換為移位操作仇让。
public int gcd(int a, int b) {
if (a < b) {
return gcd(b, a);
}
if (b == 0) {
return a;
}
boolean isAEven = isEven(a), isBEven = isEven(b);
if (isAEven && isBEven) {
return 2 * gcd(a >> 1, b >> 1);
} else if (isAEven && !isBEven) {
return gcd(a >> 1, b);
} else if (!isAEven && isBEven) {
return gcd(a, b >> 1);
} else {
return gcd(b, a - b);
}
}
進(jìn)制轉(zhuǎn)換
7 進(jìn)制
public String convertToBase7(int num) {
if (num == 0) {
return "0";
}
StringBuilder sb = new StringBuilder();
boolean isNegative = num < 0;
if (isNegative) {
num = -num;
}
while (num > 0) {
sb.append(num % 7);
num /= 7;
}
String ret = sb.reverse().toString();
return isNegative ? "-" + ret : ret;
}
Java 中 static String toString(int num, int radix) 可以將一個(gè)整數(shù)轉(zhuǎn)換為 redix 進(jìn)制表示的字符串典奉。
public String convertToBase7(int num) {
return Integer.toString(num, 7);
}
16 進(jìn)制
405. Convert a Number to Hexadecimal (Easy)
Input:
26
Output:
"1a"
Input:
-1
Output:
"ffffffff"
負(fù)數(shù)要用它的補(bǔ)碼形式。
public String toHex(int num) {
char[] map = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};
if (num == 0) return "0";
StringBuilder sb = new StringBuilder();
while (num != 0) {
sb.append(map[num & 0b1111]);
num >>>= 4; // 因?yàn)榭紤]的是補(bǔ)碼形式丧叽，因此符號(hào)位就不能有特殊的意義卫玖，需要使用無符號(hào)右移，左邊填 0
}
return sb.reverse().toString();
}
26 進(jìn)制
168. Excel Sheet Column Title (Easy)
1 -> A
2 -> B
3 -> C
...
26 -> Z
27 -> AA
28 -> AB
因?yàn)槭菑?1 開始計(jì)算的踊淳，而不是從 0 開始假瞬，因此需要對(duì) n 執(zhí)行 -1 操作。
public String convertToTitle(int n) {
if (n == 0) {
return "";
}
n--;
return convertToTitle(n / 26) + (char) (n % 26 + 'A');
}
階乘
統(tǒng)計(jì)階乘尾部有多少個(gè) 0
172. Factorial Trailing Zeroes (Easy)
尾部的 0 由 2 * 5 得來迂尝，2 的數(shù)量明顯多于 5 的數(shù)量脱茉，因此只要統(tǒng)計(jì)有多少個(gè) 5 即可。
對(duì)于一個(gè)數(shù) N垄开，它所包含 5 的個(gè)數(shù)為：N/5 + N/52 + N/53 + ...琴许，其中 N/5 表示不大于 N 的數(shù)中 5 的倍數(shù)貢獻(xiàn)一個(gè) 5，N/52 表示不大于 N 的數(shù)中 52 的倍數(shù)再貢獻(xiàn)一個(gè) 5 ...溉躲。
public int trailingZeroes(int n) {
return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5);
}
如果統(tǒng)計(jì)的是 N! 的二進(jìn)制表示中最低位 1 的位置榜田，只要統(tǒng)計(jì)有多少個(gè) 2 即可，該題目出自 編程之美：2.2 锻梳。和求解有多少個(gè) 5 一樣箭券，2 的個(gè)數(shù)為 N/2 + N/22 + N/23 + ...
字符串加法減法
二進(jìn)制加法
a = "11"
b = "1"
Return "100".
public String addBinary(String a, String b) {
int i = a.length() - 1, j = b.length() - 1, carry = 0;
StringBuilder str = new StringBuilder();
while (carry == 1 || i >= 0 || j >= 0) {
if (i >= 0 && a.charAt(i--) == '1') {
carry++;
}
if (j >= 0 && b.charAt(j--) == '1') {
carry++;
}
str.append(carry % 2);
carry /= 2;
}
return str.reverse().toString();
}
字符串加法
字符串的值為非負(fù)整數(shù)。
public String addStrings(String num1, String num2) {
StringBuilder str = new StringBuilder();
int carry = 0, i = num1.length() - 1, j = num2.length() - 1;
while (carry == 1 || i >= 0 || j >= 0) {
int x = i < 0 ? 0 : num1.charAt(i--) - '0';
int y = j < 0 ? 0 : num2.charAt(j--) - '0';
str.append((x + y + carry) % 10);
carry = (x + y + carry) / 10;
}
return str.reverse().toString();
}
相遇問題
改變數(shù)組元素使所有的數(shù)組元素都相等
462. Minimum Moves to Equal Array Elements II (Medium)
Input:
[1,2,3]
Output:
2
Explanation:
Only two moves are needed (remember each move increments or decrements one element):
[1,2,3] => [2,2,3] => [2,2,2]
每次可以對(duì)一個(gè)數(shù)組元素加一或者減一唱蒸，求最小的改變次數(shù)邦鲫。
這是個(gè)典型的相遇問題谒兄，移動(dòng)距離最小的方式是所有元素都移動(dòng)到中位數(shù)妄壶。理由如下：
設(shè) m 為中位數(shù)。a 和 b 是 m 兩邊的兩個(gè)元素，且 b > a糠亩。要使 a 和 b 相等秆撮，它們總共移動(dòng)的次數(shù)為 b - a收壕，這個(gè)值等于 (b - m) + (m - a)歼捐，也就是把這兩個(gè)數(shù)移動(dòng)到中位數(shù)的移動(dòng)次數(shù)。
設(shè)數(shù)組長度為 N你画，則可以找到 N/2 對(duì) a 和 b 的組合抵碟，使它們都移動(dòng)到 m 的位置。
解法 1
先排序坏匪，時(shí)間復(fù)雜度：O(NlogN)
public int minMoves2(int[] nums) {
Arrays.sort(nums);
int move = 0;
int l = 0, h = nums.length - 1;
while (l <= h) {
move += nums[h] - nums[l];
l++;
h--;
}
return move;
}
解法 2
使用快速選擇找到中位數(shù)拟逮，時(shí)間復(fù)雜度 O(N)
public int minMoves2(int[] nums) {
int move = 0;
int median = findKthSmallest(nums, nums.length / 2);
for (int num : nums) {
move += Math.abs(num - median);
}
return move;
}
private int findKthSmallest(int[] nums, int k) {
int l = 0, h = nums.length - 1;
while (l < h) {
int j = partition(nums, l, h);
if (j == k) {
break;
}
if (j < k) {
l = j + 1;
} else {
h = j - 1;
}
}
return nums[k];
}
private int partition(int[] nums, int l, int h) {
int i = l, j = h + 1;
while (true) {
while (nums[++i] < nums[l] && i < h) ;
while (nums[--j] > nums[l] && j > l) ;
if (i >= j) {
break;
}
swap(nums, i, j);
}
swap(nums, l, j);
return j;
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
多數(shù)投票問題
數(shù)組中出現(xiàn)次數(shù)多于 n / 2 的元素
先對(duì)數(shù)組排序，最中間那個(gè)數(shù)出現(xiàn)次數(shù)一定多于 n / 2适滓。
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length / 2];
}
可以利用 Boyer-Moore Majority Vote Algorithm 來解決這個(gè)問題敦迄，使得時(shí)間復(fù)雜度為 O(N)∑炯＃可以這么理解該算法：使用 cnt 來統(tǒng)計(jì)一個(gè)元素出現(xiàn)的次數(shù)罚屋，當(dāng)遍歷到的元素和統(tǒng)計(jì)元素不相等時(shí)，令 cnt--嗅绸。如果前面查找了 i 個(gè)元素脾猛，且 cnt == 0，說明前 i 個(gè)元素沒有 majority鱼鸠，或者有 majority猛拴，但是出現(xiàn)的次數(shù)少于 i / 2，因?yàn)槿绻嘤?i / 2 的話 cnt 就一定不會(huì)為 0瞧柔。此時(shí)剩下的 n - i 個(gè)元素中漆弄，majority 的數(shù)目依然多于 (n - i) / 2，因此繼續(xù)查找就能找出 majority造锅。
public int majorityElement(int[] nums) {
int cnt = 0, majority = nums[0];
for (int num : nums) {
majority = (cnt == 0) ? num : majority;
cnt = (majority == num) ? cnt + 1 : cnt - 1;
}
return majority;
}
其它
平方數(shù)
367. Valid Perfect Square (Easy)
Input: 16
Returns: True
平方序列：1,4,9,16,..
間隔：3,5,7,...
間隔為等差數(shù)列，使用這個(gè)特性可以得到從 1 開始的平方序列廉邑。
public boolean isPerfectSquare(int num) {
int subNum = 1;
while (num > 0) {
num -= subNum;
subNum += 2;
}
return num == 0;
}
3 的 n 次方
public boolean isPowerOfThree(int n) {
return n > 0 && (1162261467 % n == 0);
}
乘積數(shù)組
238. Product of Array Except Self (Medium)
For example, given [1,2,3,4], return [24,12,8,6].
給定一個(gè)數(shù)組哥蔚，創(chuàng)建一個(gè)新數(shù)組，新數(shù)組的每個(gè)元素為原始數(shù)組中除了該位置上的元素之外所有元素的乘積蛛蒙。
要求時(shí)間復(fù)雜度為 O(N)糙箍，并且不能使用除法。
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] products = new int[n];
Arrays.fill(products, 1);
int left = 1;
for (int i = 1; i < n; i++) {
left *= nums[i - 1];
products[i] *= left;
}
int right = 1;
for (int i = n - 2; i >= 0; i--) {
right *= nums[i + 1];
products[i] *= right;
}
return products;
}
找出數(shù)組中的乘積最大的三個(gè)數(shù)
628. Maximum Product of Three Numbers (Easy)
Input: [1,2,3,4]
Output: 24
public int maximumProduct(int[] nums) {
int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE, min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
for (int n : nums) {
if (n > max1) {
max3 = max2;
max2 = max1;
max1 = n;
} else if (n > max2) {
max3 = max2;
max2 = n;
} else if (n > max3) {
max3 = n;
}
if (n < min1) {
min2 = min1;
min1 = n;
} else if (n < min2) {
min2 = n;
}
}
return Math.max(max1*max2*max3, max1*min1*min2);
}
數(shù)據(jù)結(jié)構(gòu)相關(guān)
棧和隊(duì)列
用棧實(shí)現(xiàn)隊(duì)列
232. Implement Queue using Stacks (Easy)
class MyQueue {
private Stack<Integer> in = new Stack<>();
private Stack<Integer> out = new Stack<>();
public void push(int x) {
in.push(x);
}
public int pop() {
in2out();
return out.pop();
}
public int peek() {
in2out();
return out.peek();
}
private void in2out() {
if (out.isEmpty()) {
while (!in.isEmpty()) {
out.push(in.pop());
}
}
}
public boolean empty() {
return in.isEmpty() && out.isEmpty();
}
}
用隊(duì)列實(shí)現(xiàn)棧
225. Implement Stack using Queues (Easy)
在將一個(gè)元素 x 插入隊(duì)列時(shí)牵祟，需要讓除了 x 之外的所有元素出隊(duì)列深夯，再入隊(duì)列。此時(shí) x 在隊(duì)首，第一個(gè)出隊(duì)列咕晋，實(shí)現(xiàn)了后進(jìn)先出順序雹拄。
class MyStack {
private Queue<Integer> queue;
public MyStack() {
queue = new LinkedList<>();
}
public void push(int x) {
queue.add(x);
int cnt = queue.size();
while (cnt-- > 1) {
queue.add(queue.poll());
}
}
public int pop() {
return queue.remove();
}
public int top() {
return queue.peek();
}
public boolean empty() {
return queue.isEmpty();
}
}
最小值棧
class MinStack {
private Stack<Integer> dataStack;
private Stack<Integer> minStack;
private int min;
public MinStack() {
dataStack = new Stack<>();
minStack = new Stack<>();
min = Integer.MAX_VALUE;
}
public void push(int x) {
dataStack.add(x);
min = Math.min(min, x);
minStack.add(min);
}
public void pop() {
dataStack.pop();
minStack.pop();
min = minStack.isEmpty() ? Integer.MAX_VALUE : minStack.peek();
}
public int top() {
return dataStack.peek();
}
public int getMin() {
return minStack.peek();
}
}
對(duì)于實(shí)現(xiàn)最小值隊(duì)列問題，可以先將隊(duì)列使用棧來實(shí)現(xiàn)掌呜，然后就將問題轉(zhuǎn)換為最小值棧滓玖，這個(gè)問題出現(xiàn)在 編程之美：3.7。
用棧實(shí)現(xiàn)括號(hào)匹配
"()[]{}"
Output : true
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c == '(' || c == '{' || c == '[') {
stack.push(c);
} else {
if (stack.isEmpty()) {
return false;
}
char cStack = stack.pop();
boolean b1 = c == ')' && cStack != '(';
boolean b2 = c == ']' && cStack != '[';
boolean b3 = c == '}' && cStack != '{';
if (b1 || b2 || b3) {
return false;
}
}
}
return stack.isEmpty();
}
數(shù)組中元素與下一個(gè)比它大的元素之間的距離
739. Daily Temperatures (Medium)
Input: [73, 74, 75, 71, 69, 72, 76, 73]
Output: [1, 1, 4, 2, 1, 1, 0, 0]
在遍歷數(shù)組時(shí)用 Stack 把數(shù)組中的數(shù)存起來质蕉，如果當(dāng)前遍歷的數(shù)比棧頂元素來的大势篡，說明棧頂元素的下一個(gè)比它大的數(shù)就是當(dāng)前元素。
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] dist = new int[n];
Stack<Integer> indexs = new Stack<>();
for (int curIndex = 0; curIndex < n; curIndex++) {
while (!indexs.isEmpty() && temperatures[curIndex] > temperatures[indexs.peek()]) {
int preIndex = indexs.pop();
dist[preIndex] = curIndex - preIndex;
}
indexs.add(curIndex);
}
return dist;
}
循環(huán)數(shù)組中比當(dāng)前元素大的下一個(gè)元素
503. Next Greater Element II (Medium)
Input: [1,2,1]
Output: [2,-1,2]
Explanation: The first 1's next greater number is 2;
The number 2 can't find next greater number;
The second 1's next greater number needs to search circularly, which is also 2.
與 739. Daily Temperatures (Medium) 不同的是模暗，數(shù)組是循環(huán)數(shù)組禁悠，并且最后要求的不是距離而是下一個(gè)元素。
public int[] nextGreaterElements(int[] nums) {
int n = nums.length;
int[] next = new int[n];
Arrays.fill(next, -1);
Stack<Integer> pre = new Stack<>();
for (int i = 0; i < n * 2; i++) {
int num = nums[i % n];
while (!pre.isEmpty() && nums[pre.peek()] < num) {
next[pre.pop()] = num;
}
if (i < n){
pre.push(i);
}
}
return next;
}
哈希表
哈希表使用 O(N) 空間復(fù)雜度存儲(chǔ)數(shù)據(jù)兑宇，從而能夠以 O(1) 時(shí)間復(fù)雜度求解問題绷蹲。
Java 中的 HashSet 用于存儲(chǔ)一個(gè)集合，可以查找元素是否在集合中顾孽。
如果元素有窮祝钢，并且范圍不大，那么可以用一個(gè)布爾數(shù)組來存儲(chǔ)一個(gè)元素是否存在若厚。例如對(duì)于只有小寫字符的元素拦英，就可以用一個(gè)長度為 26 的布爾數(shù)組來存儲(chǔ)一個(gè)字符集合，使得空間復(fù)雜度降低為 O(1)测秸。
Java 中的 HashMap 主要用于映射關(guān)系疤估，從而把兩個(gè)元素聯(lián)系起來。
在對(duì)一個(gè)內(nèi)容進(jìn)行壓縮或者其它轉(zhuǎn)換時(shí)霎冯，利用 HashMap 可以把原始內(nèi)容和轉(zhuǎn)換后的內(nèi)容聯(lián)系起來铃拇。例如在一個(gè)簡化 url 的系統(tǒng)中Leetcdoe : 535. Encode and Decode TinyURL (Medium)，利用 HashMap 就可以存儲(chǔ)精簡后的 url 到原始 url 的映射沈撞，使得不僅可以顯示簡化的 url慷荔，也可以根據(jù)簡化的 url 得到原始 url 從而定位到正確的資源。
HashMap 也可以用來對(duì)元素進(jìn)行計(jì)數(shù)統(tǒng)計(jì)缠俺，此時(shí)鍵為元素显晶，值為計(jì)數(shù)。和 HashSet 類似壹士，如果元素有窮并且范圍不大磷雇，可以用整型數(shù)組來進(jìn)行統(tǒng)計(jì)。
數(shù)組中的兩個(gè)數(shù)和為給定值
可以先對(duì)數(shù)組進(jìn)行排序躏救，然后使用雙指針方法或者二分查找方法唯笙。這樣做的時(shí)間復(fù)雜度為 O(NlogN)，空間復(fù)雜度為 O(1)。
用 HashMap 存儲(chǔ)數(shù)組元素和索引的映射崩掘，在訪問到 nums[i] 時(shí)七嫌，判斷 HashMap 中是否存在 target - nums[i]，如果存在說明 target - nums[i] 所在的索引和 i 就是要找的兩個(gè)數(shù)呢堰。該方法的時(shí)間復(fù)雜度為 O(N)抄瑟，空間復(fù)雜度為 O(N)，使用空間來換取時(shí)間枉疼。
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> indexForNum = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (indexForNum.containsKey(target - nums[i])) {
return new int[]{indexForNum.get(target - nums[i]), i};
} else {
indexForNum.put(nums[i], i);
}
}
return null;
}
判斷數(shù)組是否含有重復(fù)元素
217. Contains Duplicate (Easy)
public boolean containsDuplicate(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int num : nums) {
set.add(num);
}
return set.size() < nums.length;
}
最長和諧序列
594. Longest Harmonious Subsequence (Easy)
Input: [1,3,2,2,5,2,3,7]
Output: 5
Explanation: The longest harmonious subsequence is [3,2,2,2,3].
和諧序列中最大數(shù)和最小數(shù)只差正好為 1皮假，應(yīng)該注意的是序列的元素不一定是數(shù)組的連續(xù)元素。
public int findLHS(int[] nums) {
Map<Integer, Integer> countForNum = new HashMap<>();
for (int num : nums) {
countForNum.put(num, countForNum.getOrDefault(num, 0) + 1);
}
int longest = 0;
for (int num : countForNum.keySet()) {
if (countForNum.containsKey(num + 1)) {
longest = Math.max(longest, countForNum.get(num + 1) + countForNum.get(num));
}
}
return longest;
}
最長連續(xù)序列
128. Longest Consecutive Sequence (Hard)
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
要求以 O(N) 的時(shí)間復(fù)雜度求解骂维。
public int longestConsecutive(int[] nums) {
Map<Integer, Integer> countForNum = new HashMap<>();
for (int num : nums) {
countForNum.put(num, 1);
}
for (int num : nums) {
forward(countForNum, num);
}
return maxCount(countForNum);
}
private int forward(Map<Integer, Integer> countForNum, int num) {
if (!countForNum.containsKey(num)) {
return 0;
}
int cnt = countForNum.get(num);
if (cnt > 1) {
return cnt;
}
cnt = forward(countForNum, num + 1) + 1;
countForNum.put(num, cnt);
return cnt;
}
private int maxCount(Map<Integer, Integer> countForNum) {
int max = 0;
for (int num : countForNum.keySet()) {
max = Math.max(max, countForNum.get(num));
}
return max;
}
字符串
兩個(gè)字符串包含的字符是否完全相同
s = "anagram", t = "nagaram", return true.
s = "rat", t = "car", return false.
字符串只包含小寫字符惹资，總共有 26 個(gè)小寫字符『焦耄可以用 HashMap 來映射字符與出現(xiàn)次數(shù)褪测。因?yàn)殒I的范圍很小，因此可以使用長度為 26 的整型數(shù)組對(duì)字符串出現(xiàn)的字符進(jìn)行統(tǒng)計(jì)潦刃，然后比較兩個(gè)字符串出現(xiàn)的字符數(shù)量是否相同侮措。
public boolean isAnagram(String s, String t) {
int[] cnts = new int[26];
for (char c : s.toCharArray()) {
cnts[c - 'a']++;
}
for (char c : t.toCharArray()) {
cnts[c - 'a']--;
}
for (int cnt : cnts) {
if (cnt != 0) {
return false;
}
}
return true;
}
計(jì)算一組字符集合可以組成的回文字符串的最大長度
409. Longest Palindrome (Easy)
Input : "abccccdd"
Output : 7
Explanation : One longest palindrome that can be built is "dccaccd", whose length is 7.
使用長度為 256 的整型數(shù)組來統(tǒng)計(jì)每個(gè)字符出現(xiàn)的個(gè)數(shù)，每個(gè)字符有偶數(shù)個(gè)可以用來構(gòu)成回文字符串乖杠。
因?yàn)榛匚淖址钪虚g的那個(gè)字符可以單獨(dú)出現(xiàn)分扎，所以如果有單獨(dú)的字符就把它放到最中間。
public int longestPalindrome(String s) {
int[] cnts = new int[256];
for (char c : s.toCharArray()) {
cnts[c]++;
}
int palindrome = 0;
for (int cnt : cnts) {
palindrome += (cnt / 2) * 2;
}
if (palindrome < s.length()) {
palindrome++; // 這個(gè)條件下 s 中一定有單個(gè)未使用的字符存在胧洒，可以把這個(gè)字符放到回文的最中間
}
return palindrome;
}
字符串同構(gòu)
205. Isomorphic Strings (Easy)
Given "egg", "add", return true.
Given "foo", "bar", return false.
Given "paper", "title", return true.
記錄一個(gè)字符上次出現(xiàn)的位置畏吓，如果兩個(gè)字符串中的字符上次出現(xiàn)的位置一樣，那么就屬于同構(gòu)卫漫。
public boolean isIsomorphic(String s, String t) {
int[] preIndexOfS = new int[256];
int[] preIndexOfT = new int[256];
for (int i = 0; i < s.length(); i++) {
char sc = s.charAt(i), tc = t.charAt(i);
if (preIndexOfS[sc] != preIndexOfT[tc]) {
return false;
}
preIndexOfS[sc] = i + 1;
preIndexOfT[tc] = i + 1;
}
return true;
}
回文子字符串
647. Palindromic Substrings (Medium)
Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".
從字符串的某一位開始菲饼，嘗試著去擴(kuò)展子字符串。
private int cnt = 0;
public int countSubstrings(String s) {
for (int i = 0; i < s.length(); i++) {
extendSubstrings(s, i, i); // 奇數(shù)長度
extendSubstrings(s, i, i + 1); // 偶數(shù)長度
}
return cnt;
}
private void extendSubstrings(String s, int start, int end) {
while (start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)) {
start--;
end++;
cnt++;
}
}
判斷一個(gè)整數(shù)是否是回文數(shù)
要求不能使用額外空間列赎，也就不能將整數(shù)轉(zhuǎn)換為字符串進(jìn)行判斷宏悦。
將整數(shù)分成左右兩部分，右邊那部分需要轉(zhuǎn)置粥谬，然后判斷這兩部分是否相等肛根。
public boolean isPalindrome(int x) {
if (x == 0) {
return true;
}
if (x < 0 || x % 10 == 0) {
return false;
}
int right = 0;
while (x > right) {
right = right * 10 + x % 10;
x /= 10;
}
return x == right || x == right / 10;
}
統(tǒng)計(jì)二進(jìn)制字符串中連續(xù) 1 和連續(xù) 0 數(shù)量相同的子字符串個(gè)數(shù)
696. Count Binary Substrings (Easy)
Input: "00110011"
Output: 6
Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01".
public int countBinarySubstrings(String s) {
int preLen = 0, curLen = 1, count = 0;
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == s.charAt(i - 1)) {
curLen++;
} else {
preLen = curLen;
curLen = 1;
}
if (preLen >= curLen) {
count++;
}
}
return count;
}
字符串循環(huán)移位包含
s1 = AABCD, s2 = CDAA
Return : true
給定兩個(gè)字符串 s1 和 s2，要求判定 s2 是否能夠被 s1 做循環(huán)移位得到的字符串包含漏策。
s1 進(jìn)行循環(huán)移位的結(jié)果是 s1s1 的子字符串，因此只要判斷 s2 是否是 s1s1 的子字符串即可臼氨。
字符串循環(huán)移位
s = "abcd123" k = 3
Return "123abcd"
將字符串向右循環(huán)移動(dòng) k 位掺喻。
將 abcd123 中的 abcd 和 123 單獨(dú)逆序，得到 dcba321，然后對(duì)整個(gè)字符串進(jìn)行逆序感耙，得到 123abcd褂乍。
字符串中單詞的翻轉(zhuǎn)
s = "I am a student"
return "student a am I"
將每個(gè)單詞逆序，然后將整個(gè)字符串逆序即硼。
數(shù)組與矩陣
把數(shù)組中的 0 移到末尾
For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].
public void moveZeroes(int[] nums) {
int idx = 0;
for (int num : nums) {
if (num != 0) {
nums[idx++] = num;
}
}
while (idx < nums.length) {
nums[idx++] = 0;
}
}
改變矩陣維度
566. Reshape the Matrix (Easy)
Input:
nums =
[[1,2],
[3,4]]
r = 1, c = 4
Output:
[[1,2,3,4]]
Explanation:
The row-traversing of nums is [1,2,3,4]. The new reshaped matrix is a 1 * 4 matrix, fill it row by row by using the previous list.
public int[][] matrixReshape(int[][] nums, int r, int c) {
int m = nums.length, n = nums[0].length;
if (m * n != r * c) {
return nums;
}
int[][] reshapedNums = new int[r][c];
int index = 0;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
reshapedNums[i][j] = nums[index / n][index % n];
index++;
}
}
return reshapedNums;
}
找出數(shù)組中最長的連續(xù) 1
485. Max Consecutive Ones (Easy)
public int findMaxConsecutiveOnes(int[] nums) {
int max = 0, cur = 0;
for (int x : nums) {
cur = x == 0 ? 0 : cur + 1;
max = Math.max(max, cur);
}
return max;
}
一個(gè)數(shù)組元素在 [1, n] 之間逃片，其中一個(gè)數(shù)被替換為另一個(gè)數(shù)，找出重復(fù)的數(shù)和丟失的數(shù)
Input: nums = [1,2,2,4]
Output: [2,3]
Input: nums = [1,2,2,4]
Output: [2,3]
最直接的方法是先對(duì)數(shù)組進(jìn)行排序只酥，這種方法時(shí)間復(fù)雜度為 O(NlogN)褥实。本題可以以 O(N) 的時(shí)間復(fù)雜度、O(1) 空間復(fù)雜度來求解裂允。
主要思想是通過交換數(shù)組元素损离，使得數(shù)組上的元素在正確的位置上。遍歷數(shù)組绝编，如果第 i 位上的元素不是 i + 1僻澎，那么一直交換第 i 位和 nums[i] - 1 位置上的元素。
public int[] findErrorNums(int[] nums) {
for (int i = 0; i < nums.length; i++) {
while (nums[i] != i + 1 && nums[nums[i] - 1] != nums[i]) {
swap(nums, i, nums[i] - 1);
}
}
for (int i = 0; i < nums.length; i++) {
if (nums[i] != i + 1) {
return new int[]{nums[i], i + 1};
}
}
return null;
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
類似題目：
- 448. Find All Numbers Disappeared in an Array (Easy)十饥，尋找所有丟失的元素
- 442. Find All Duplicates in an Array (Medium)窟勃，尋找所有重復(fù)的元素。
找出數(shù)組中重復(fù)的數(shù)逗堵，數(shù)組值在 [1, n] 之間
287. Find the Duplicate Number (Medium)
要求不能修改數(shù)組秉氧，也不能使用額外的空間。
二分查找解法：
public int findDuplicate(int[] nums) {
int l = 1, h = nums.length - 1;
while (l <= h) {
int mid = l + (h - l) / 2;
int cnt = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] <= mid) cnt++;
}
if (cnt > mid) h = mid - 1;
else l = mid + 1;
}
return l;
}
雙指針解法砸捏，類似于有環(huán)鏈表中找出環(huán)的入口：
public int findDuplicate(int[] nums) {
int slow = nums[0], fast = nums[nums[0]];
while (slow != fast) {
slow = nums[slow];
fast = nums[nums[fast]];
}
fast = 0;
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
有序矩陣查找
240. Search a 2D Matrix II (Medium)
[
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
]
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
int m = matrix.length, n = matrix[0].length;
int row = 0, col = n - 1;
while (row < m && col >= 0) {
if (target == matrix[row][col]) return true;
else if (target < matrix[row][col]) col--;
else row++;
}
return false;
}
有序矩陣的 Kth Element
378. Kth Smallest Element in a Sorted Matrix ((Medium))
matrix = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,
return 13.
解題參考：Share my thoughts and Clean Java Code
二分查找解法：
public int kthSmallest(int[][] matrix, int k) {
int m = matrix.length, n = matrix[0].length;
int lo = matrix[0][0], hi = matrix[m - 1][n - 1];
while(lo <= hi) {
int mid = lo + (hi - lo) / 2;
int cnt = 0;
for(int i = 0; i < m; i++) {
for(int j = 0; j < n && matrix[i][j] <= mid; j++) {
cnt++;
}
}
if(cnt < k) lo = mid + 1;
else hi = mid - 1;
}
return lo;
}
堆解法：
public int kthSmallest(int[][] matrix, int k) {
int m = matrix.length, n = matrix[0].length;
PriorityQueue<Tuple> pq = new PriorityQueue<Tuple>();
for(int j = 0; j < n; j++) pq.offer(new Tuple(0, j, matrix[0][j]));
for(int i = 0; i < k - 1; i++) { // 小根堆谬运，去掉 k - 1 個(gè)堆頂元素，此時(shí)堆頂元素就是第 k 的數(shù)
Tuple t = pq.poll();
if(t.x == m - 1) continue;
pq.offer(new Tuple(t.x + 1, t.y, matrix[t.x + 1][t.y]));
}
return pq.poll().val;
}
class Tuple implements Comparable<Tuple> {
int x, y, val;
public Tuple(int x, int y, int val) {
this.x = x; this.y = y; this.val = val;
}
@Override
public int compareTo(Tuple that) {
return this.val - that.val;
}
}
數(shù)組相鄰差值的個(gè)數(shù)
667. Beautiful Arrangement II (Medium)
Input: n = 3, k = 2
Output: [1, 3, 2]
Explanation: The [1, 3, 2] has three different positive integers ranging from 1 to 3, and the [2, 1] has exactly 2 distinct integers: 1 and 2.
題目描述：數(shù)組元素為 1~n 的整數(shù)垦藏，要求構(gòu)建數(shù)組梆暖，使得相鄰元素的差值不相同的個(gè)數(shù)為 k。
讓前 k+1 個(gè)元素構(gòu)建出 k 個(gè)不相同的差值掂骏，序列為：1 k+1 2 k 3 k-1 ... k/2 k/2+1.
public int[] constructArray(int n, int k) {
int[] ret = new int[n];
ret[0] = 1;
for (int i = 1, interval = k; i <= k; i++, interval--) {
ret[i] = i % 2 == 1 ? ret[i - 1] + interval : ret[i - 1] - interval;
}
for (int i = k + 1; i < n; i++) {
ret[i] = i + 1;
}
return ret;
}
數(shù)組的度
697. Degree of an Array (Easy)
Input: [1,2,2,3,1,4,2]
Output: 6
題目描述：數(shù)組的度定義為元素出現(xiàn)的最高頻率轰驳，例如上面的數(shù)組度為 3。要求找到一個(gè)最小的子數(shù)組弟灼，這個(gè)子數(shù)組的度和原數(shù)組一樣级解。
public int findShortestSubArray(int[] nums) {
Map<Integer, Integer> numsCnt = new HashMap<>();
Map<Integer, Integer> numsLastIndex = new HashMap<>();
Map<Integer, Integer> numsFirstIndex = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int num = nums[i];
numsCnt.put(num, numsCnt.getOrDefault(num, 0) + 1);
numsLastIndex.put(num, i);
if (!numsFirstIndex.containsKey(num)) {
numsFirstIndex.put(num, i);
}
}
int maxCnt = 0;
for (int num : nums) {
maxCnt = Math.max(maxCnt, numsCnt.get(num));
}
int ret = nums.length;
for (int i = 0; i < nums.length; i++) {
int num = nums[i];
int cnt = numsCnt.get(num);
if (cnt != maxCnt) continue;
ret = Math.min(ret, numsLastIndex.get(num) - numsFirstIndex.get(num) + 1);
}
return ret;
}
對(duì)角元素相等的矩陣
1234
5123
9512
In the above grid, the diagonals are "[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]", and in each diagonal all elements are the same, so the answer is True.
public boolean isToeplitzMatrix(int[][] matrix) {
for (int i = 0; i < matrix[0].length; i++) {
if (!check(matrix, matrix[0][i], 0, i)) {
return false;
}
}
for (int i = 0; i < matrix.length; i++) {
if (!check(matrix, matrix[i][0], i, 0)) {
return false;
}
}
return true;
}
private boolean check(int[][] matrix, int expectValue, int row, int col) {
if (row >= matrix.length || col >= matrix[0].length) {
return true;
}
if (matrix[row][col] != expectValue) {
return false;
}
return check(matrix, expectValue, row + 1, col + 1);
}
嵌套數(shù)組
Input: A = [5,4,0,3,1,6,2]
Output: 4
Explanation:
A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.
One of the longest S[K]:
S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}
題目描述：S[i] 表示一個(gè)集合锈锤，集合的第一個(gè)元素是 A[i]劈狐，第二個(gè)元素是 A[A[i]]，如此嵌套下去疏叨。求最大的 S[i]掩驱。
public int arrayNesting(int[] nums) {
int max = 0;
for (int i = 0; i < nums.length; i++) {
int cnt = 0;
for (int j = i; nums[j] != -1; ) {
cnt++;
int t = nums[j];
nums[j] = -1; // 標(biāo)記該位置已經(jīng)被訪問
j = t;
}
max = Math.max(max, cnt);
}
return max;
}
分隔數(shù)組
769. Max Chunks To Make Sorted (Medium)
Input: arr = [1,0,2,3,4]
Output: 4
Explanation:
We can split into two chunks, such as [1, 0], [2, 3, 4].
However, splitting into [1, 0], [2], [3], [4] is the highest number of chunks possible.
題目描述：分隔數(shù)組芒划，使得對(duì)每部分排序后數(shù)組就為有序冬竟。
public int maxChunksToSorted(int[] arr) {
if (arr == null) return 0;
int ret = 0;
int right = arr[0];
for (int i = 0; i < arr.length; i++) {
right = Math.max(right, arr[i]);
if (right == i) ret++;
}
return ret;
}
鏈表
鏈表是空節(jié)點(diǎn)，或者有一個(gè)值和一個(gè)指向下一個(gè)鏈表的指針民逼，因此很多鏈表問題可以用遞歸來處理泵殴。
找出兩個(gè)鏈表的交點(diǎn)
160. Intersection of Two Linked Lists (Easy)
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
要求：時(shí)間復(fù)雜度為 O(N)，空間復(fù)雜度為 O(1)
設(shè) A 的長度為 a + c拼苍，B 的長度為 b + c笑诅，其中 c 為尾部公共部分長度，可知 a + c + b = b + c + a疮鲫。
當(dāng)訪問 A 鏈表的指針訪問到鏈表尾部時(shí)吆你，令它從鏈表 B 的頭部開始訪問鏈表 B；同樣地棚点，當(dāng)訪問 B 鏈表的指針訪問到鏈表尾部時(shí)早处，令它從鏈表 A 的頭部開始訪問鏈表 A。這樣就能控制訪問 A 和 B 兩個(gè)鏈表的指針能同時(shí)訪問到交點(diǎn)瘫析。
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode l1 = headA, l2 = headB;
while (l1 != l2) {
l1 = (l1 == null) ? headB : l1.next;
l2 = (l2 == null) ? headA : l2.next;
}
return l1;
}
如果只是判斷是否存在交點(diǎn)砌梆，那么就是另一個(gè)問題，即 編程之美：3.6 的問題贬循。有兩種解法：把第一個(gè)鏈表的結(jié)尾連接到第二個(gè)鏈表的開頭咸包，看第二個(gè)鏈表是否存在環(huán)；或者直接比較兩個(gè)鏈表的最后一個(gè)節(jié)點(diǎn)是否相同杖虾。
鏈表反轉(zhuǎn)
206. Reverse Linked List (Easy)
遞歸
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode next = head.next;
ListNode newHead = reverseList(next);
next.next = head;
head.next = null;
return newHead;
}
頭插法
public ListNode reverseList(ListNode head) {
ListNode newHead = new ListNode(-1);
while (head != null) {
ListNode next = head.next;
head.next = newHead.next;
newHead.next = head;
head = next;
}
return newHead.next;
}
歸并兩個(gè)有序的鏈表
21. Merge Two Sorted Lists (Easy)
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
從有序鏈表中刪除重復(fù)節(jié)點(diǎn)
83. Remove Duplicates from Sorted List (Easy)
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.
public ListNode deleteDuplicates(ListNode head) {
if(head == null || head.next == null) return head;
head.next = deleteDuplicates(head.next);
return head.val == head.next.val ? head.next : head;
}
刪除鏈表的倒數(shù)第 n 個(gè)節(jié)點(diǎn)
19. Remove Nth Node From End of List (Medium)
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode fast = head;
while (n-- > 0) {
fast = fast.next;
}
if (fast == null) return head.next;
ListNode slow = head;
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return head;
}
交換鏈表中的相鄰結(jié)點(diǎn)
24. Swap Nodes in Pairs (Medium)
Given 1->2->3->4, you should return the list as 2->1->4->3.
題目要求：不能修改結(jié)點(diǎn)的 val 值烂瘫，O(1) 空間復(fù)雜度。
public ListNode swapPairs(ListNode head) {
ListNode node = new ListNode(-1);
node.next = head;
ListNode pre = node;
while (pre.next != null && pre.next.next != null) {
ListNode l1 = pre.next, l2 = pre.next.next;
ListNode next = l2.next;
l1.next = next;
l2.next = l1;
pre.next = l2;
pre = l1;
}
return node.next;
}
鏈表求和
445. Add Two Numbers II (Medium)
Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7
題目要求：不能修改原始鏈表奇适。
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Stack<Integer> l1Stack = buildStack(l1);
Stack<Integer> l2Stack = buildStack(l2);
ListNode head = new ListNode(-1);
int carry = 0;
while (!l1Stack.isEmpty() || !l2Stack.isEmpty() || carry != 0) {
int x = l1Stack.isEmpty() ? 0 : l1Stack.pop();
int y = l2Stack.isEmpty() ? 0 : l2Stack.pop();
int sum = x + y + carry;
ListNode node = new ListNode(sum % 10);
node.next = head.next;
head.next = node;
carry = sum / 10;
}
return head.next;
}
private Stack<Integer> buildStack(ListNode l) {
Stack<Integer> stack = new Stack<>();
while (l != null) {
stack.push(l.val);
l = l.next;
}
return stack;
}
回文鏈表
234. Palindrome Linked List (Easy)
題目要求：以 O(1) 的空間復(fù)雜度來求解坟比。
切成兩半，把后半段反轉(zhuǎn)嚷往，然后比較兩半是否相等葛账。
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) return true;
ListNode slow = head, fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
if (fast != null) slow = slow.next; // 偶數(shù)節(jié)點(diǎn)，讓 slow 指向下一個(gè)節(jié)點(diǎn)
cut(head, slow); // 切成兩個(gè)鏈表
return isEqual(head, reverse(slow));
}
private void cut(ListNode head, ListNode cutNode) {
while (head.next != cutNode) {
head = head.next;
}
head.next = null;
}
private ListNode reverse(ListNode head) {
ListNode newHead = null;
while (head != null) {
ListNode nextNode = head.next;
head.next = newHead;
newHead = head;
head = nextNode;
}
return newHead;
}
private boolean isEqual(ListNode l1, ListNode l2) {
while (l1 != null && l2 != null) {
if (l1.val != l2.val) return false;
l1 = l1.next;
l2 = l2.next;
}
return true;
}
分隔鏈表
725. Split Linked List in Parts(Medium)
Input:
root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
Output: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
Explanation:
The input has been split into consecutive parts with size difference at most 1, and earlier parts are a larger size than the later parts.
題目描述：把鏈表分隔成 k 部分皮仁，每部分的長度都應(yīng)該盡可能相同籍琳，排在前面的長度應(yīng)該大于等于后面的。
public ListNode[] splitListToParts(ListNode root, int k) {
int N = 0;
ListNode cur = root;
while (cur != null) {
N++;
cur = cur.next;
}
int mod = N % k;
int size = N / k;
ListNode[] ret = new ListNode[k];
cur = root;
for (int i = 0; cur != null && i < k; i++) {
ret[i] = cur;
int curSize = size + (mod-- > 0 ? 1 : 0);
for (int j = 0; j < curSize - 1; j++) {
cur = cur.next;
}
ListNode next = cur.next;
cur.next = null;
cur = next;
}
return ret;
}
鏈表元素按奇偶聚集
328. Odd Even Linked List (Medium)
Example:
Given 1->2->3->4->5->NULL,
return 1->3->5->2->4->NULL.
public ListNode oddEvenList(ListNode head) {
if (head == null) {
return head;
}
ListNode odd = head, even = head.next, evenHead = even;
while (even != null && even.next != null) {
odd.next = odd.next.next;
odd = odd.next;
even.next = even.next.next;
even = even.next;
}
odd.next = evenHead;
return head;
}
樹
遞歸
一棵樹要么是空樹贷祈，要么有兩個(gè)指針趋急，每個(gè)指針指向一棵樹。樹是一種遞歸結(jié)構(gòu)势誊，很多樹的問題可以使用遞歸來處理呜达。
樹的高度
104. Maximum Depth of Binary Tree (Easy)
public int maxDepth(TreeNode root) {
if (root == null) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
平衡樹
110. Balanced Binary Tree (Easy)
3
/ \
9 20
/ \
15 7
平衡樹左右子樹高度差都小于等于 1
private boolean result = true;
public boolean isBalanced(TreeNode root) {
maxDepth(root);
return result;
}
public int maxDepth(TreeNode root) {
if (root == null) return 0;
int l = maxDepth(root.left);
int r = maxDepth(root.right);
if (Math.abs(l - r) > 1) result = false;
return 1 + Math.max(l, r);
}
兩節(jié)點(diǎn)的最長路徑
543. Diameter of Binary Tree (Easy)
Input:
1
/ \
2 3
/ \
4 5
Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].
private int max = 0;
public int diameterOfBinaryTree(TreeNode root) {
depth(root);
return max;
}
private int depth(TreeNode root) {
if (root == null) return 0;
int leftDepth = depth(root.left);
int rightDepth = depth(root.right);
max = Math.max(max, leftDepth + rightDepth);
return Math.max(leftDepth, rightDepth) + 1;
}
翻轉(zhuǎn)樹
226. Invert Binary Tree (Easy)
public TreeNode invertTree(TreeNode root) {
if (root == null) return null;
TreeNode left = root.left; // 后面的操作會(huì)改變 left 指針，因此先保存下來
root.left = invertTree(root.right);
root.right = invertTree(left);
return root;
}
歸并兩棵樹
617. Merge Two Binary Trees (Easy)
Input:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
Output:
Merged tree:
3
/ \
4 5
/ \ \
5 4 7
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) return null;
if (t1 == null) return t2;
if (t2 == null) return t1;
TreeNode root = new TreeNode(t1.val + t2.val);
root.left = mergeTrees(t1.left, t2.left);
root.right = mergeTrees(t1.right, t2.right);
return root;
}
判斷路徑和是否等于一個(gè)數(shù)
Leetcdoe : 112. Path Sum (Easy)
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
路徑和定義為從 root 到 leaf 的所有節(jié)點(diǎn)的和
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) return false;
if (root.left == null && root.right == null && root.val == sum) return true;
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}
統(tǒng)計(jì)路徑和等于一個(gè)數(shù)的路徑數(shù)量
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
Return 3. The paths that sum to 8 are:
1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11
路徑不一定以 root 開頭粟耻，也不一定以 leaf 結(jié)尾闻丑，但是必須連續(xù)漩怎。
public int pathSum(TreeNode root, int sum) {
if (root == null) return 0;
int ret = pathSumStartWithRoot(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
return ret;
}
private int pathSumStartWithRoot(TreeNode root, int sum) {
if (root == null) return 0;
int ret = 0;
if (root.val == sum) ret++;
ret += pathSumStartWithRoot(root.left, sum - root.val) + pathSumStartWithRoot(root.right, sum - root.val);
return ret;
}
子樹
572. Subtree of Another Tree (Easy)
Given tree s:
3
/ \
4 5
/ \
1 2
Given tree t:
4
/ \
1 2
Return true, because t has the same structure and node values with a subtree of s.
Given tree s:
3
/ \
4 5
/ \
1 2
/
0
Given tree t:
4
/ \
1 2
Return false.
public boolean isSubtree(TreeNode s, TreeNode t) {
if (s == null) return false;
return isSubtreeWithRoot(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
}
private boolean isSubtreeWithRoot(TreeNode s, TreeNode t) {
if (t == null && s == null) return true;
if (t == null || s == null) return false;
if (t.val != s.val) return false;
return isSubtreeWithRoot(s.left, t.left) && isSubtreeWithRoot(s.right, t.right);
}
樹的對(duì)稱
1
/ \
2 2
/ \ / \
3 4 4 3
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
return isSymmetric(root.left, root.right);
}
private boolean isSymmetric(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) return true;
if (t1 == null || t2 == null) return false;
if (t1.val != t2.val) return false;
return isSymmetric(t1.left, t2.right) && isSymmetric(t1.right, t2.left);
}
最小路徑
111. Minimum Depth of Binary Tree (Easy)
樹的根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的最小路徑長度
public int minDepth(TreeNode root) {
if (root == null) return 0;
int left = minDepth(root.left);
int right = minDepth(root.right);
if (left == 0 || right == 0) return left + right + 1;
return Math.min(left, right) + 1;
}
統(tǒng)計(jì)左葉子節(jié)點(diǎn)的和
404. Sum of Left Leaves (Easy)
3
/ \
9 20
/ \
15 7
There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.
public int sumOfLeftLeaves(TreeNode root) {
if (root == null) return 0;
if (isLeaf(root.left)) return root.left.val + sumOfLeftLeaves(root.right);
return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
}
private boolean isLeaf(TreeNode node){
if (node == null) return false;
return node.left == null && node.right == null;
}
相同節(jié)點(diǎn)值的最大路徑長度
687. Longest Univalue Path (Easy)
1
/ \
4 5
/ \ \
4 4 5
Output : 2
private int path = 0;
public int longestUnivaluePath(TreeNode root) {
dfs(root);
return path;
}
private int dfs(TreeNode root){
if (root == null) return 0;
int left = dfs(root.left);
int right = dfs(root.right);
int leftPath = root.left != null && root.left.val == root.val ? left + 1 : 0;
int rightPath = root.right != null && root.right.val == root.val ? right + 1 : 0;
path = Math.max(path, leftPath + rightPath);
return Math.max(leftPath, rightPath);
}
間隔遍歷
337. House Robber III (Medium)
3
/ \
2 3
\ \
3 1
Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
public int rob(TreeNode root) {
if (root == null) return 0;
int val1 = root.val;
if (root.left != null) val1 += rob(root.left.left) + rob(root.left.right);
if (root.right != null) val1 += rob(root.right.left) + rob(root.right.right);
int val2 = rob(root.left) + rob(root.right);
return Math.max(val1, val2);
}
找出二叉樹中第二小的節(jié)點(diǎn)
671. Second Minimum Node In a Binary Tree (Easy)
Input:
2
/ \
2 5
/ \
5 7
Output: 5
一個(gè)節(jié)點(diǎn)要么具有 0 個(gè)或 2 個(gè)子節(jié)點(diǎn)勋颖，如果有子節(jié)點(diǎn)嗦嗡，那么根節(jié)點(diǎn)是最小的節(jié)點(diǎn)。
public int findSecondMinimumValue(TreeNode root) {
if (root == null) return -1;
if (root.left == null && root.right == null) return -1;
int leftVal = root.left.val;
int rightVal = root.right.val;
if (leftVal == root.val) leftVal = findSecondMinimumValue(root.left);
if (rightVal == root.val) rightVal = findSecondMinimumValue(root.right);
if (leftVal != -1 && rightVal != -1) return Math.min(leftVal, rightVal);
if (leftVal != -1) return leftVal;
return rightVal;
}
層次遍歷
使用 BFS 進(jìn)行層次遍歷饭玲。不需要使用兩個(gè)隊(duì)列來分別存儲(chǔ)當(dāng)前層的節(jié)點(diǎn)和下一層的節(jié)點(diǎn)侥祭，因?yàn)樵陂_始遍歷一層的節(jié)點(diǎn)時(shí)，當(dāng)前隊(duì)列中的節(jié)點(diǎn)數(shù)就是當(dāng)前層的節(jié)點(diǎn)數(shù)茄厘，只要控制遍歷這么多節(jié)點(diǎn)數(shù)矮冬，就能保證這次遍歷的都是當(dāng)前層的節(jié)點(diǎn)。
一棵樹每層節(jié)點(diǎn)的平均數(shù)
637. Average of Levels in Binary Tree (Easy)
public List<Double> averageOfLevels(TreeNode root) {
List<Double> ret = new ArrayList<>();
if (root == null) return ret;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()){
int cnt = queue.size();
double sum = 0;
for (int i = 0; i < cnt; i++){
TreeNode node = queue.poll();
sum += node.val;
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
ret.add(sum / cnt);
}
return ret;
}
得到左下角的節(jié)點(diǎn)
513. Find Bottom Left Tree Value (Easy)
Input:
1
/ \
2 3
/ / \
4 5 6
/
7
Output:
7
public int findBottomLeftValue(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()){
root = queue.poll();
if (root.right != null) queue.add(root.right);
if (root.left != null) queue.add(root.left);
}
return root.val;
}
前中后序遍歷
1
/ \
2 3
/ \ \
4 5 6
層次遍歷順序：[1 2 3 4 5 6]
前序遍歷順序：[1 2 4 5 3 6]
中序遍歷順序：[4 2 5 1 3 6]
后序遍歷順序：[4 5 2 6 3 1]
層次遍歷使用 BFS 實(shí)現(xiàn)次哈，利用的就是 BFS 一層一層遍歷的特性胎署；而前序、中序窑滞、后序遍歷利用了 DFS 實(shí)現(xiàn)琼牧。
前序、中序哀卫、后序遍只是在對(duì)節(jié)點(diǎn)訪問的順序有一點(diǎn)不同巨坊，其它都相同。
① 前序
void dfs(TreeNode root){
visit(root);
dfs(root.left);
dfs(root.right);
}
② 中序
void dfs(TreeNode root){
dfs(root.left);
visit(root);
dfs(root.right);
}
③ 后序
void dfs(TreeNode root){
dfs(root.left);
dfs(root.right);
visit(root);
}
非遞歸實(shí)現(xiàn)二叉樹的前序遍歷
144. Binary Tree Preorder Traversal (Medium)
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node == null) continue;
ret.add(node.val);
stack.push(node.right); // 先右后左此改，保證左子樹先遍歷
stack.push(node.left);
}
return ret;
}
非遞歸實(shí)現(xiàn)二叉樹的后序遍歷
145. Binary Tree Postorder Traversal (Medium)
前序遍歷為 root -> left -> right趾撵，后序遍歷為 left -> right -> root，可以修改前序遍歷成為 root -> right -> left共啃，那么這個(gè)順序就和后序遍歷正好相反占调。
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node == null) continue;
ret.add(node.val);
stack.push(node.left);
stack.push(node.right);
}
Collections.reverse(ret);
return ret;
}
非遞歸實(shí)現(xiàn)二叉樹的中序遍歷
94. Binary Tree Inorder Traversal (Medium)
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
if (root == null) return ret;
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
TreeNode node = stack.pop();
ret.add(node.val);
cur = node.right;
}
return ret;
}
BST
二叉查找樹（BST）：根節(jié)點(diǎn)大于等于左子樹所有節(jié)點(diǎn)，小于等于右子樹所有節(jié)點(diǎn)移剪。
二叉查找樹中序遍歷有序究珊。
修剪二叉查找樹
669. Trim a Binary Search Tree (Easy)
Input:
3
/ \
0 4
\
2
/
1
L = 1
R = 3
Output:
3
/
2
/
1
只保留值在 L ~ R 之間的節(jié)點(diǎn)
public TreeNode trimBST(TreeNode root, int L, int R) {
if (root == null) return null;
if (root.val > R) return trimBST(root.left, L, R);
if (root.val < L) return trimBST(root.right, L, R);
root.left = trimBST(root.left, L, R);
root.right = trimBST(root.right, L, R);
return root;
}
尋找二叉查找樹的第 k 個(gè)元素
230. Kth Smallest Element in a BST (Medium)
中序遍歷解法：
private int cnt = 0;
private int val;
public int kthSmallest(TreeNode root, int k) {
inOrder(root, k);
return val;
}
private void inOrder(TreeNode node, int k) {
if (node == null) return;
inOrder(node.left, k);
cnt++;
if (cnt == k) {
val = node.val;
return;
}
inOrder(node.right, k);
}
遞歸解法：
public int kthSmallest(TreeNode root, int k) {
int leftCnt = count(root.left);
if (leftCnt == k - 1) return root.val;
if (leftCnt > k - 1) return kthSmallest(root.left, k);
return kthSmallest(root.right, k - leftCnt - 1);
}
private int count(TreeNode node) {
if (node == null) return 0;
return 1 + count(node.left) + count(node.right);
}
把二叉查找樹每個(gè)節(jié)點(diǎn)的值都加上比它大的節(jié)點(diǎn)的值
Convert BST to Greater Tree (Easy)
Input: The root of a Binary Search Tree like this:
5
/ \
2 13
Output: The root of a Greater Tree like this:
18
/ \
20 13
先遍歷右子樹。
private int sum = 0;
public TreeNode convertBST(TreeNode root) {
traver(root);
return root;
}
private void traver(TreeNode root) {
if (root == null) return;
if (root.right != null) traver(root.right);
sum += root.val;
root.val = sum;
if (root.left != null) traver(root.left);
}
二叉查找樹的最近公共祖先
235. Lowest Common Ancestor of a Binary Search Tree (Easy)
_______6______
/ \
___2__ ___8__
/ \ / \
0 4 7 9
/ \
3 5
For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q);
if (root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q);
return root;
}
二叉樹的最近公共祖先
236. Lowest Common Ancestor of a Binary Tree (Medium)
_______3______
/ \
___5__ ___1__
/ \ / \
6 2 0 8
/ \
7 4
For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
return left == null ? right : right == null ? left : root;
}
從有序數(shù)組中構(gòu)造二叉查找樹
108. Convert Sorted Array to Binary Search Tree (Easy)
public TreeNode sortedArrayToBST(int[] nums) {
return toBST(nums, 0, nums.length - 1);
}
private TreeNode toBST(int[] nums, int sIdx, int eIdx){
if (sIdx > eIdx) return null;
int mIdx = (sIdx + eIdx) / 2;
TreeNode root = new TreeNode(nums[mIdx]);
root.left = toBST(nums, sIdx, mIdx - 1);
root.right = toBST(nums, mIdx + 1, eIdx);
return root;
}
根據(jù)有序鏈表構(gòu)造平衡的二叉查找樹
109. Convert Sorted List to Binary Search Tree (Medium)
Given the sorted linked list: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
0
/ \
-3 9
/ /
-10 5
public TreeNode sortedListToBST(ListNode head) {
if (head == null) return null;
int size = size(head);
if (size == 1) return new TreeNode(head.val);
ListNode pre = head, mid = pre.next;
int step = 2;
while (step <= size / 2) {
pre = mid;
mid = mid.next;
step++;
}
pre.next = null;
TreeNode t = new TreeNode(mid.val);
t.left = sortedListToBST(head);
t.right = sortedListToBST(mid.next);
return t;
}
private int size(ListNode node) {
int size = 0;
while (node != null) {
size++;
node = node.next;
}
return size;
}
在二叉查找樹中尋找兩個(gè)節(jié)點(diǎn)挂滓，使它們的和為一個(gè)給定值
653. Two Sum IV - Input is a BST (Easy)
Input:
5
/ \
3 6
/ \ \
2 4 7
Target = 9
Output: True
使用中序遍歷得到有序數(shù)組之后苦银，再利用雙指針對(duì)數(shù)組進(jìn)行查找。
應(yīng)該注意到赶站，這一題不能用分別在左右子樹兩部分來處理這種思想幔虏，因?yàn)閮蓚€(gè)待求的節(jié)點(diǎn)可能分別在左右子樹中。
public boolean findTarget(TreeNode root, int k) {
List<Integer> nums = new ArrayList<>();
inOrder(root, nums);
int i = 0, j = nums.size() - 1;
while (i < j) {
int sum = nums.get(i) + nums.get(j);
if (sum == k) return true;
if (sum < k) i++;
else j--;
}
return false;
}
private void inOrder(TreeNode root, List<Integer> nums) {
if (root == null) return;
inOrder(root.left, nums);
nums.add(root.val);
inOrder(root.right, nums);
}
在二叉查找樹中查找兩個(gè)節(jié)點(diǎn)之差的最小絕對(duì)值
530. Minimum Absolute Difference in BST (Easy)
Input:
1
\
3
/
2
Output:
1
利用二叉查找樹的中序遍歷為有序的性質(zhì)贝椿，計(jì)算中序遍歷中臨近的兩個(gè)節(jié)點(diǎn)之差的絕對(duì)值想括，取最小值。
private int minDiff = Integer.MAX_VALUE;
private TreeNode preNode = null;
public int getMinimumDifference(TreeNode root) {
inOrder(root);
return minDiff;
}
private void inOrder(TreeNode node) {
if (node == null) return;
inOrder(node.left);
if (preNode != null) minDiff = Math.min(minDiff, Math.abs(node.val - preNode.val));
preNode = node;
inOrder(node.right);
}
尋找二叉查找樹中出現(xiàn)次數(shù)最多的值
501. Find Mode in Binary Search Tree (Easy)
1
\
2
/
2
return [2].
答案可能不止一個(gè)烙博，也就是有多個(gè)值出現(xiàn)的次數(shù)一樣多瑟蜈，并且是最大的烟逊。
private int curCnt = 1;
private int maxCnt = 1;
private TreeNode preNode = null;
public int[] findMode(TreeNode root) {
List<Integer> maxCntNums = new ArrayList<>();
inOrder(root, maxCntNums);
int[] ret = new int[maxCntNums.size()];
int idx = 0;
for (int num : maxCntNums) {
ret[idx++] = num;
}
return ret;
}
private void inOrder(TreeNode node, List<Integer> nums) {
if (node == null) return;
inOrder(node.left, nums);
if (preNode != null) {
if (preNode.val == node.val) curCnt++;
else curCnt = 1;
}
if (curCnt > maxCnt) {
maxCnt = curCnt;
nums.clear();
nums.add(node.val);
} else if (curCnt == maxCnt) {
nums.add(node.val);
}
preNode = node;
inOrder(node.right, nums);
}
Trie
<div align="center"> <img src="../pics//5c638d59-d4ae-4ba4-ad44-80bdc30f38dd.jpg"/> </div>
Trie，又稱前綴樹或字典樹铺根，用于判斷字符串是否存在或者是否具有某種字符串前綴宪躯。
實(shí)現(xiàn)一個(gè) Trie
208. Implement Trie (Prefix Tree) (Medium)
class Trie {
private class Node {
Node[] childs = new Node[26];
boolean isLeaf;
}
private Node root = new Node();
public Trie() {
}
public void insert(String word) {
insert(word, root);
}
private void insert(String word, Node node) {
if (node == null) return;
if (word.length() == 0) {
node.isLeaf = true;
return;
}
int index = indexForChar(word.charAt(0));
if (node.childs[index] == null) {
node.childs[index] = new Node();
}
insert(word.substring(1), node.childs[index]);
}
public boolean search(String word) {
return search(word, root);
}
private boolean search(String word, Node node) {
if (node == null) return false;
if (word.length() == 0) return node.isLeaf;
int index = indexForChar(word.charAt(0));
return search(word.substring(1), node.childs[index]);
}
public boolean startsWith(String prefix) {
return startWith(prefix, root);
}
private boolean startWith(String prefix, Node node) {
if (node == null) return false;
if (prefix.length() == 0) return true;
int index = indexForChar(prefix.charAt(0));
return startWith(prefix.substring(1), node.childs[index]);
}
private int indexForChar(char c) {
return c - 'a';
}
}
實(shí)現(xiàn)一個(gè) Trie，用來求前綴和
Input: insert("apple", 3), Output: Null
Input: sum("ap"), Output: 3
Input: insert("app", 2), Output: Null
Input: sum("ap"), Output: 5
class MapSum {
private class Node {
Node[] child = new Node[26];
int value;
}
private Node root = new Node();
public MapSum() {
}
public void insert(String key, int val) {
insert(key, root, val);
}
private void insert(String key, Node node, int val) {
if (node == null) return;
if (key.length() == 0) {
node.value = val;
return;
}
int index = indexForChar(key.charAt(0));
if (node.child[index] == null) {
node.child[index] = new Node();
}
insert(key.substring(1), node.child[index], val);
}
public int sum(String prefix) {
return sum(prefix, root);
}
private int sum(String prefix, Node node) {
if (node == null) return 0;
if (prefix.length() != 0) {
int index = indexForChar(prefix.charAt(0));
return sum(prefix.substring(1), node.child[index]);
}
int sum = node.value;
for (Node child : node.child) {
sum += sum(prefix, child);
}
return sum;
}
private int indexForChar(char c) {
return c - 'a';
}
}
圖
二分圖
如果可以用兩種顏色對(duì)圖中的節(jié)點(diǎn)進(jìn)行著色位迂，并且保證相鄰的節(jié)點(diǎn)顏色不同访雪，那么這個(gè)圖就是二分圖。
判斷是否為二分圖
785. Is Graph Bipartite? (Medium)
Input: [[1,3], [0,2], [1,3], [0,2]]
Output: true
Explanation:
The graph looks like this:
0----1
| |
| |
3----2
We can divide the vertices into two groups: {0, 2} and {1, 3}.
Example 2:
Input: [[1,2,3], [0,2], [0,1,3], [0,2]]
Output: false
Explanation:
The graph looks like this:
0----1
| \ |
| \ |
3----2
We cannot find a way to divide the set of nodes into two independent subsets.
public boolean isBipartite(int[][] graph) {
int[] colors = new int[graph.length];
Arrays.fill(colors, -1);
for (int i = 0; i < graph.length; i++) { // 處理圖不是連通的情況
if (colors[i] == -1 && !isBipartite(i, 0, colors, graph)) {
return false;
}
}
return true;
}
private boolean isBipartite(int curNode, int curColor, int[] colors, int[][] graph) {
if (colors[curNode] != -1) {
return colors[curNode] == curColor;
}
colors[curNode] = curColor;
for (int nextNode : graph[curNode]) {
if (!isBipartite(nextNode, 1 - curColor, colors, graph)) {
return false;
}
}
return true;
}
拓?fù)渑判?/h3>
常用于在具有先序關(guān)系的任務(wù)規(guī)劃中掂林。
課程安排的合法性
2, [[1,0]]
return true
2, [[1,0],[0,1]]
return false
題目描述：一個(gè)課程可能會(huì)先修課程臣缀，判斷給定的先修課程規(guī)定是否合法。
本題不需要使用拓?fù)渑判蛐喊铮恍枰獧z測有向圖是否存在環(huán)即可精置。
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<Integer>[] graphic = new List[numCourses];
for (int i = 0; i < numCourses; i++) {
graphic[i] = new ArrayList<>();
}
for (int[] pre : prerequisites) {
graphic[pre[0]].add(pre[1]);
}
boolean[] globalMarked = new boolean[numCourses];
boolean[] localMarked = new boolean[numCourses];
for (int i = 0; i < numCourses; i++) {
if (hasCycle(globalMarked, localMarked, graphic, i)) {
return false;
}
}
return true;
}
private boolean hasCycle(boolean[] globalMarked, boolean[] localMarked,
List<Integer>[] graphic, int curNode) {
if (localMarked[curNode]) {
return true;
}
if (globalMarked[curNode]) {
return false;
}
globalMarked[curNode] = true;
localMarked[curNode] = true;
for (int nextNode : graphic[curNode]) {
if (hasCycle(globalMarked, localMarked, graphic, nextNode)) {
return true;
}
}
localMarked[curNode] = false;
return false;
}
課程安排的順序
210. Course Schedule II (Medium)
4, [[1,0],[2,0],[3,1],[3,2]]
There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].
使用 DFS 來實(shí)現(xiàn)拓?fù)渑判颍褂靡粋€(gè)棧存儲(chǔ)后序遍歷結(jié)果锣杂，這個(gè)棧的逆序結(jié)果就是拓?fù)渑判蚪Y(jié)果脂倦。
證明：對(duì)于任何先序關(guān)系：v->w，后序遍歷結(jié)果可以保證 w 先進(jìn)入棧中蹲堂，因此棧的逆序結(jié)果中 v 會(huì)在 w 之前狼讨。
public int[] findOrder(int numCourses, int[][] prerequisites) {
List<Integer>[] graphic = new List[numCourses];
for (int i = 0; i < numCourses; i++) {
graphic[i] = new ArrayList<>();
}
for (int[] pre : prerequisites) {
graphic[pre[0]].add(pre[1]);
}
Stack<Integer> postOrder = new Stack<>();
boolean[] globalMarked = new boolean[numCourses];
boolean[] localMarked = new boolean[numCourses];
for (int i = 0; i < numCourses; i++) {
if (hasCycle(globalMarked, localMarked, graphic, i, postOrder)) {
return new int[0];
}
}
int[] orders = new int[numCourses];
for (int i = numCourses - 1; i >= 0; i--) {
orders[i] = postOrder.pop();
}
return orders;
}
private boolean hasCycle(boolean[] globalMarked, boolean[] localMarked, List<Integer>[] graphic,
int curNode, Stack<Integer> postOrder) {
if (localMarked[curNode]) {
return true;
}
if (globalMarked[curNode]) {
return false;
}
globalMarked[curNode] = true;
localMarked[curNode] = true;
for (int nextNode : graphic[curNode]) {
if (hasCycle(globalMarked, localMarked, graphic, nextNode, postOrder)) {
return true;
}
}
localMarked[curNode] = false;
postOrder.push(curNode);
return false;
}
并查集
并查集可以動(dòng)態(tài)地連通兩個(gè)點(diǎn)，并且可以非称饩海快速地判斷兩個(gè)點(diǎn)是否連通政供。
冗余連接
684. Redundant Connection (Medium)
Input: [[1,2], [1,3], [2,3]]
Output: [2,3]
Explanation: The given undirected graph will be like this:
1
/ \
2 - 3
題目描述：有一系列的邊連成的圖，找出一條邊朽基，移除它之后該圖能夠成為一棵樹布隔。
public int[] findRedundantConnection(int[][] edges) {
int N = edges.length;
UF uf = new UF(N);
for (int[] e : edges) {
int u = e[0], v = e[1];
if (uf.connect(u, v)) {
return e;
}
uf.union(u, v);
}
return new int[]{-1, -1};
}
private class UF {
private int[] id;
UF(int N) {
id = new int[N + 1];
for (int i = 0; i < id.length; i++) {
id[i] = i;
}
}
void union(int u, int v) {
int uID = find(u);
int vID = find(v);
if (uID == vID) {
return;
}
for (int i = 0; i < id.length; i++) {
if (id[i] == uID) {
id[i] = vID;
}
}
}
int find(int p) {
return id[p];
}
boolean connect(int u, int v) {
return find(u) == find(v);
}
}
位運(yùn)算
1. 基本原理
0s 表示一串 0，1s 表示一串 1稼虎。
x ^ 0s = x x & 0s = 0 x | 0s = x
x ^ 1s = ~x x & 1s = x x | 1s = 1s
x ^ x = 0 x & x = x x | x = x
- 利用 x ^ 1s = ~x 的特點(diǎn)衅檀，可以將位級(jí)表示翻轉(zhuǎn)；利用 x ^ x = 0 的特點(diǎn)霎俩，可以將三個(gè)數(shù)中重復(fù)的兩個(gè)數(shù)去除哀军，只留下另一個(gè)數(shù)。
- 利用 x & 0s = 0 和 x & 1s = x 的特點(diǎn)打却，可以實(shí)現(xiàn)掩碼操作杉适。一個(gè)數(shù) num 與 mask ：00111100 進(jìn)行位與操作，只保留 num 中與 mask 的 1 部分相對(duì)應(yīng)的位柳击。
- 利用 x | 0s = x 和 x | 1s = 1s 的特點(diǎn)猿推，可以實(shí)現(xiàn)設(shè)值操作。一個(gè)數(shù) num 與 mask：00111100 進(jìn)行位或操作捌肴，將 num 中與 mask 的 1 部分相對(duì)應(yīng)的位都設(shè)置為 1蹬叭。
位與運(yùn)算技巧：
- n&(n-1) 去除 n 的位級(jí)表示中最低的那一位藕咏。例如對(duì)于二進(jìn)制表示 10110 100 ，減去 1 得到 10110011秽五，這兩個(gè)數(shù)相與得到 10110000孽查。
- n&(-n) 得到 n 的位級(jí)表示中最低的那一位。-n 得到 n 的反碼加 1筝蚕，對(duì)于二進(jìn)制表示 10110 100 卦碾，-n 得到 01001100，相與得到 00000100起宽。
- n-n&(~n+1) 去除 n 的位級(jí)表示中最高的那一位。
移位運(yùn)算：
- >> n 為算術(shù)右移济榨，相當(dāng)于除以 2n坯沪；
- >>> n 為無符號(hào)右移，左邊會(huì)補(bǔ)上 0擒滑。
- << n 為算術(shù)左移腐晾，相當(dāng)于乘以 2n。
2. mask 計(jì)算
要獲取 111111111丐一，將 0 取反即可藻糖，~0。
要得到只有第 i 位為 1 的 mask库车，將 1 向左移動(dòng) i-1 位即可巨柒，1<<(i-1) 。例如 1<<4 得到只有第 5 位為 1 的 mask ：00010000柠衍。
要得到 1 到 i 位為 1 的 mask洋满，1<<(i+1)-1 即可，例如將 1<<(4+1)-1 = 00010000-1 = 00001111珍坊。
要得到 1 到 i 位為 0 的 mask牺勾，只需將 1 到 i 位為 1 的 mask 取反，即 ~(1<<(i+1)-1)阵漏。
3. Java 中的位操作
static int Integer.bitCount(); // 統(tǒng)計(jì) 1 的數(shù)量
static int Integer.highestOneBit(); // 獲得最高位
static String toBinaryString(int i); // 轉(zhuǎn)換為二進(jìn)制表示的字符串
統(tǒng)計(jì)兩個(gè)數(shù)的二進(jìn)制表示有多少位不同
Input: x = 1, y = 4
Output: 2
Explanation:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑
The above arrows point to positions where the corresponding bits are different.
對(duì)兩個(gè)數(shù)進(jìn)行異或操作驻民，位級(jí)表示不同的那一位為 1，統(tǒng)計(jì)有多少個(gè) 1 即可履怯。
public int hammingDistance(int x, int y) {
int z = x ^ y;
int cnt = 0;
while(z != 0) {
if ((z & 1) == 1) cnt++;
z = z >> 1;
}
return cnt;
}
使用 z&(z-1) 去除 z 位級(jí)表示最低的那一位回还。
public int hammingDistance(int x, int y) {
int z = x ^ y;
int cnt = 0;
while (z != 0) {
z &= (z - 1);
cnt++;
}
return cnt;
}
可以使用 Integer.bitcount() 來統(tǒng)計(jì) 1 個(gè)的個(gè)數(shù)。
public int hammingDistance(int x, int y) {
return Integer.bitCount(x ^ y);
}
數(shù)組中唯一一個(gè)不重復(fù)的元素
Input: [4,1,2,1,2]
Output: 4
兩個(gè)相同的數(shù)異或的結(jié)果為 0虑乖，對(duì)所有數(shù)進(jìn)行異或操作懦趋，最后的結(jié)果就是單獨(dú)出現(xiàn)的那個(gè)數(shù)。
public int singleNumber(int[] nums) {
int ret = 0;
for (int n : nums) ret = ret ^ n;
return ret;
}
找出數(shù)組中缺失的那個(gè)數(shù)
Input: [3,0,1]
Output: 2
題目描述：數(shù)組元素在 0-n 之間疹味，但是有一個(gè)數(shù)是缺失的仅叫，要求找到這個(gè)缺失的數(shù)帜篇。
public int missingNumber(int[] nums) {
int ret = 0;
for (int i = 0; i < nums.length; i++) {
ret = ret ^ i ^ nums[i];
}
return ret ^ nums.length;
}
數(shù)組中不重復(fù)的兩個(gè)元素
260. Single Number III (Medium)
兩個(gè)不相等的元素在位級(jí)表示上必定會(huì)有一位存在不同。
將數(shù)組的所有元素異或得到的結(jié)果為不存在重復(fù)的兩個(gè)元素異或的結(jié)果诫咱。
diff &= -diff 得到出 diff 最右側(cè)不為 0 的位笙隙，也就是不存在重復(fù)的兩個(gè)元素在位級(jí)表示上最右側(cè)不同的那一位挥唠，利用這一位就可以將兩個(gè)元素區(qū)分開來仇穗。
public int[] singleNumber(int[] nums) {
int diff = 0;
for (int num : nums) diff ^= num;
diff &= -diff; // 得到最右一位
int[] ret = new int[2];
for (int num : nums) {
if ((num & diff) == 0) ret[0] ^= num;
else ret[1] ^= num;
}
return ret;
}
翻轉(zhuǎn)一個(gè)數(shù)的比特位
public int reverseBits(int n) {
int ret = 0;
for (int i = 0; i < 32; i++) {
ret <<= 1;
ret |= (n & 1);
n >>>= 1;
}
return ret;
}
如果該函數(shù)需要被調(diào)用很多次妇智，可以將 int 拆成 4 個(gè) byte茉盏，然后緩存 byte 對(duì)應(yīng)的比特位翻轉(zhuǎn)垃它，最后再拼接起來筷黔。
private static Map<Byte, Integer> cache = new HashMap<>();
public int reverseBits(int n) {
int ret = 0;
for (int i = 0; i < 4; i++) {
ret <<= 8;
ret |= reverseByte((byte) (n & 0b11111111));
n >>= 8;
}
return ret;
}
private int reverseByte(byte b) {
if (cache.containsKey(b)) return cache.get(b);
int ret = 0;
byte t = b;
for (int i = 0; i < 8; i++) {
ret <<= 1;
ret |= t & 1;
t >>= 1;
}
cache.put(b, ret);
return ret;
}
不用額外變量交換兩個(gè)整數(shù)
a = a ^ b;
b = a ^ b;
a = a ^ b;
判斷一個(gè)數(shù)是不是 2 的 n 次方
二進(jìn)制表示只有一個(gè) 1 存在草巡。
public boolean isPowerOfTwo(int n) {
return n > 0 && Integer.bitCount(n) == 1;
}
利用 1000 & 0111 == 0 這種性質(zhì)唯卖，得到以下解法：
public boolean isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
判斷一個(gè)數(shù)是不是 4 的 n 次方
這種數(shù)在二進(jìn)制表示中有且只有一個(gè)奇數(shù)位為 1憎夷，例如 16（10000）莽鸿。
public boolean isPowerOfFour(int num) {
return num > 0 && (num & (num - 1)) == 0 && (num & 0b01010101010101010101010101010101) != 0;
}
也可以使用正則表達(dá)式進(jìn)行匹配。
public boolean isPowerOfFour(int num) {
return Integer.toString(num, 4).matches("10*");
}
判斷一個(gè)數(shù)的位級(jí)表示是否不會(huì)出現(xiàn)連續(xù)的 0 和 1
693. Binary Number with Alternating Bits (Easy)
Input: 10
Output: True
Explanation:
The binary representation of 10 is: 1010.
Input: 11
Output: False
Explanation:
The binary representation of 11 is: 1011.
對(duì)于 1010 這種位級(jí)表示的數(shù)拾给，把它向右移動(dòng) 1 位得到 101祥得，這兩個(gè)數(shù)每個(gè)位都不同，因此異或得到的結(jié)果為 1111蒋得。
public boolean hasAlternatingBits(int n) {
int a = (n ^ (n >> 1));
return (a & (a + 1)) == 0;
}
求一個(gè)數(shù)的補(bǔ)碼
Input: 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.
題目描述：不考慮二進(jìn)制表示中的首 0 部分级及。
對(duì)于 00000101，要求補(bǔ)碼可以將它與 00000111 進(jìn)行異或操作额衙。那么問題就轉(zhuǎn)換為求掩碼 00000111饮焦。
public int findComplement(int num) {
if (num == 0) return 1;
int mask = 1 << 30;
while ((num & mask) == 0) mask >>= 1;
mask = (mask << 1) - 1;
return num ^ mask;
}
可以利用 Java 的 Integer.highestOneBit() 方法來獲得含有首 1 的數(shù)。
public int findComplement(int num) {
if (num == 0) return 1;
int mask = Integer.highestOneBit(num);
mask = (mask << 1) - 1;
return num ^ mask;
}
對(duì)于 10000000 這樣的數(shù)要擴(kuò)展成 11111111入偷，可以利用以下方法：
mask |= mask >> 1 11000000
mask |= mask >> 2 11110000
mask |= mask >> 4 11111111
public int findComplement(int num) {
int mask = num;
mask |= mask >> 1;
mask |= mask >> 2;
mask |= mask >> 4;
mask |= mask >> 8;
mask |= mask >> 16;
return (mask ^ num);
}
實(shí)現(xiàn)整數(shù)的加法
371. Sum of Two Integers (Easy)
a ^ b 表示沒有考慮進(jìn)位的情況下兩數(shù)的和追驴，(a & b) << 1 就是進(jìn)位。
遞歸會(huì)終止的原因是 (a & b) << 1 最右邊會(huì)多一個(gè) 0疏之，那么繼續(xù)遞歸殿雪，進(jìn)位最右邊的 0 會(huì)慢慢增多，最后進(jìn)位會(huì)變?yōu)?0锋爪，遞歸終止丙曙。
public int getSum(int a, int b) {
return b == 0 ? a : getSum((a ^ b), (a & b) << 1);
}
字符串?dāng)?shù)組最大乘積
318. Maximum Product of Word Lengths (Medium)
Given ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
Return 16
The two words can be "abcw", "xtfn".
題目描述：字符串?dāng)?shù)組的字符串只含有小寫字符。求解字符串?dāng)?shù)組中兩個(gè)字符串長度的最大乘積其骄，要求這兩個(gè)字符串不能含有相同字符亏镰。
本題主要問題是判斷兩個(gè)字符串是否含相同字符，由于字符串只含有小寫字符拯爽，總共 26 位索抓，因此可以用一個(gè) 32 位的整數(shù)來存儲(chǔ)每個(gè)字符是否出現(xiàn)過。
public int maxProduct(String[] words) {
int n = words.length;
int[] val = new int[n];
for (int i = 0; i < n; i++) {
for (char c : words[i].toCharArray()) {
val[i] |= 1 << (c - 'a');
}
}
int ret = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if ((val[i] & val[j]) == 0) {
ret = Math.max(ret, words[i].length() * words[j].length());
}
}
}
return ret;
}
統(tǒng)計(jì)從 0 ~ n 每個(gè)數(shù)的二進(jìn)制表示中 1 的個(gè)數(shù)
對(duì)于數(shù)字 6(110)，它可以看成是 4(100) 再加一個(gè) 2(10)逼肯，因此 dp[i] = dp[i&(i-1)] + 1;
public int[] countBits(int num) {
int[] ret = new int[num + 1];
for(int i = 1; i <= num; i++){
ret[i] = ret[i&(i-1)] + 1;
}
return ret;
}
參考資料
- Leetcode
- Weiss M A, 馮舜璽. 數(shù)據(jù)結(jié)構(gòu)與算法分析——C 語言描述[J]. 2004.
- Sedgewick R. Algorithms[M]. Pearson Education India, 1988.
- 何海濤, 軟件工程師. 劍指 Offer: 名企面試官精講典型編程題[M]. 電子工業(yè)出版社, 2014.
- 《編程之美》小組. 編程之美[M]. 電子工業(yè)出版社, 2008.
- 左程云. 程序員代碼面試指南[M]. 電子工業(yè)出版社, 2015.
