迫于找工作,不得不一边鄙视自己的智商,一边硬着头皮刷 LeetCode。既然开始刷题,那顺便做个笔记,以便日后温习。

因为顺序是乱的,所以请善用 CTRL-F

217. Contains Duplicate

Example:

1
2
3
4
5
Input: nums = [1,2,3,1]
Output: true

Input: nums = [1,2,3,4]
Output: false
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public boolean containsDuplicate(int[] nums) {
if (nums == null || nums.length == 0) {
return false;
}

HashSet<Integer> hashSet = new HashSet<>();
for (int i : nums) {
// 看见一个数字就去hashSet里面查,
// 查到就说明重复过了
if (hashSet.contains(i)) {
return true;
}

hashSet.add(i);
}

return false;
}
}

242. Valid Anagram

Example:

1
2
3
4
5
Input: s = "anagram", t = "nagaram"
Output: true

Input: s = "rat", t = "car"
Output: false
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}

// 字符串s中各个字符出现的次数
Map<Character, Integer> countS = new HashMap<>();

// 字符串t中各个字符出现的次数
Map<Character, Integer> countT = new HashMap<>();

for (int i = 0; i < s.length(); i++) {
countS.put(
s.charAt(i),
countS.getOrDefault(s.charAt(i), 0) + 1);
}

for (int i = 0; i < t.length(); i++) {
countT.put(
t.charAt(i),
countT.getOrDefault(t.charAt(i), 0) + 1);
}

// Map#equals比较的是两个map中的键值对
// 键值对相同,说明两串字符都用了相同的字母,每个字母出现的次数也一样
// 即同字母异序词
return countS.equals(countT);
}
}

1299. Replace Elements with Greatest Element on Right Side

Example:

1
2
3
4
5
6
7
8
9
Input: arr = [17,18,5,4,6,1]
Output: [18,6,6,6,1,-1]
Explanation:
- index 0 --> the greatest element to the right of index 0 is index 1 (18).
- index 1 --> the greatest element to the right of index 1 is index 4 (6).
- index 2 --> the greatest element to the right of index 2 is index 4 (6).
- index 3 --> the greatest element to the right of index 3 is index 4 (6).
- index 4 --> the greatest element to the right of index 4 is index 5 (1).
- index 5 --> there are no elements to the right of index 5, so we put -1.
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public int[] replaceElements(int[] arr) {
int max = -1;
for (int i = arr.length - 1; i >= 0; i--) {
int a = arr[i];
arr[i] = max;
max = Math.max(max, a);
}

return arr;
}
}

解题思路就是把 explanation 反过来看,既然要找元素右边最大的数,那么就从最右开始,这样找到的最大的数必定适用于 arr[i] ~ arr[length - 1] 这个范围。

392. Is Subsequence

Example:

1
2
3
4
5
6
7
8
9
10
11
Input: s = "abc", t = "ahbgdc"
Output: true

Input: s = "axc", t = "ahbgdc"
Output: false

Input: s = "acb", t = "ahbgdc"
Output: false

Input: s = "aaaaaa", t = "bbaaaa"
Output: false
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public boolean isSubsequence(String s, String t) {
if (s.equals(t) || s.length() == 0) {
return true;
}

if (t.length() == 0) {
return false;
}

int sIndex = 0;
for (int i = 0; i < t.length(); i++) {
if (t.charAt(i) == s.charAt(sIndex)) {
sIndex++;
if (sIndex >= s.length()) {
return true;
}
}
}

return false;
}
}

解题思路就是整两个指针,sIndex 指向 s 的各个字符,在循环里面逐个取 t 的字符跟 s[sIndex] 对比,匹配到的话 sIndex 就往下走一步,如果 sIndex 能走到头,就说明 st 的子序列。

58. Length of Last Word

Example:

1
2
3
4
5
6
7
Input: s = "Hello World"
Output: 5
Explanation: The last word is "World" with length 5.

Input: s = " fly me to the moon "
Output: 4
Explanation: The last word is "moon" with length 4.
1
2
3
4
5
6
class Solution {
public int lengthOfLastWord(String s) {
String[] strs = s.split(" ");
return strs[strs.length - 1].length();
}
}

我的评价是,这道题不应该出现在 LeetCode,应该出现在大学 Java 课程的作业里。

14. Longest Common Prefix

Example:

1
2
Input: strs = ["flower","flow","flight"]
Output: "fl"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs.length == 0) {
return "";
}

// 拿第一个字符串当模版,匹配剩下几个字符串
String commonPrefix = strs[0];
for (int i = 1; i < strs.length; i++) {
// 如果commonPrefix在strs[i]的下标不是0
// 那么就去掉commonPrefix的最后一个字母,直到下标为0
// 如果没有common prefix,那么commonPrefix会被砍成空字符串
while (strs[i].indexOf(commonPrefix) != 0) {
commonPrefix = commonPrefix.substring(0, commonPrefix.length() - 1);
}
}

return commonPrefix;
}
}

计算过程:(语言描述太费劲,直接拿 Replit 放示意图算了)

49. Group Anagrams

Example:

1
2
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new LinkedHashMap<>();

for (String str: strs) {
// 取一个字符串,打散成字符数组,把字符数组排序后得到一个新字符串
// 比如eat-> aet,tea->aet
// 这个作为map的key
char[] charArray = str.toCharArray();
Arrays.sort(charArray);
String newStr = new String(charArray);

if (!map.containsKey(newStr)) {
map.put(newStr, new ArrayList<>());
}
// 把重排序后结果相同的字符串放在同一个key下面的List里面
map.get(newStr).add(str);
}

List<List<String>> result = new ArrayList(map.values());
return result;
}
}

计算过程语言不好描述…… 但是代码挺易懂的吧,实在看不明白的话自己 debug 一下就清楚了。

118. Pascal’s Triangle

Example:

1
2
3
4
5
Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Input: numRows = 1
Output: [[1]]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public List<List<Integer>> generate(int numRows) {
// 需要单独处理只有一行的情况
// 否则会因为下面预设前两行数据的代码而返回错误的数据
if (numRows == 1) {
return List.of(List.of(1));
}

List<List<Integer>> result = new ArrayList<>(numRows);

// 前两行的内容是固定的
result.add(List.of(1));
result.add(List.of(1,1));

for (int row = 2; row < numRows; row++) {
List<Integer> list = new ArrayList<>(row + 1);
// 这一行最左边肯定是1
list.add(1);

// 两个两个取上一行的各个数,两两相加,得到当前格子的数字
// 因为要取上一行的第i和第i+1个元素,所以循环结束条件得是上一行的个数减一
// 否则就下标越界了
int previousRow = row - 1;
for (int i = 0; i < result.get(previousRow).size() - 1; i++) {
int sum = result.get(previousRow).get(i) + result.get(previousRow).get(i + 1);
list.add(sum);
}

// 最右边也肯定是1
list.add(1);

result.add(list);
}

return result;
}
}

27. Remove Element

Example:

1
2
3
4
Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,_,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 2.
It does not matter what you leave beyond the returned k (hence they are underscores).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public int removeElement(int[] nums, int val) {
// 不等于val的数字的个数,同时当作nums的一个指针
int count = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != val) {
nums[count] = nums[i];
count++;
}
}

return count;
}
}

929. Unique Email Addresses

Example:

1
2
3
Input: emails = ["test.email+alex@leetcode.com","test.e.mail+bob.cathy@leetcode.com","testemail+david@lee.tcode.com"]
Output: 2
Explanation: "testemail@leetcode.com" and "testemail@lee.tcode.com" actually receive mails.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public int numUniqueEmails(String[] emails) {
HashSet<String> uniqueEmails = new HashSet<>();

for (String email : emails) {
String sanitizedEmail = "";
int indexOfPlusSign = email.indexOf("+");
int indexOfAtSign = email.indexOf("@");

if (indexOfPlusSign > 0) {
// 按题目要求,第一个加号及其以后的用户名部分都会被忽略
sanitizedEmail += email.substring(0, indexOfPlusSign);
} else {
sanitizedEmail += email.substring(0, indexOfAtSign);
}

// 按题目要求,用户名部分的点都会被忽略
sanitizedEmail = sanitizedEmail.replace(".", "");

// 处理完了用户名部分,把域名部分拼上去
sanitizedEmail += email.substring(indexOfAtSign);

// 全处理完之后,扔进HashSet里面,顺便去重
uniqueEmails.add(sanitizedEmail);
}

return uniqueEmails.size();
}
}

205. Isomorphic Strings

Example:

1
2
3
4
5
Input: s = "paper", t = "title"
Output: true

Input: s = "foo", t = "bar"
Output: false
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public boolean isIsomorphic(String s, String t) {
// 俩字符串长度都不一样,那必然不同形
if (s.length() != t.length()) {
return false;
}

// 建立s中每个字符与t中同位置字符的映射关系
// 如 egg -> add
// e -> a, g -> d
HashMap<Character, Character> map = new HashMap(s.length());
for (int i = 0; i < t.length(); i++) {
if (map.containsValue(t.charAt(i))) {
continue;
}

map.put(s.charAt(i), t.charAt(i));
}

// 然后从map里面,按照s的每个字母,取出映射过的字符
// 拼在StringBuilder里面
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
Character ch = map.get(s.charAt(i));
sb.append(ch);
}

// 检查用映射拼出来的字符串与t是否相同
return sb.toString().equals(t);
}
}

347. Top K Frequent Elements

Example:

1
2
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public int[] topKFrequent(int[] nums, int k) {
if (nums.length == k) {
return nums;
}

return Arrays
.stream(nums)
// int -> Integer
.boxed()
// 收集到一个map中,key是数字,value是出现的次数
.collect(Collectors.groupingBy(num -> num, Collectors.summingInt(num -> 1)))
.entrySet()
.stream()
// 把entry set按照value降序排列
.sorted(Map.Entry.comparingByValue((a, b) -> Integer.compare(b, a)))
// 取前k个
.limit(k)
// 把key取出来,unbox成int
.mapToInt(e -> e.getKey())
// 最后造个数组出来返回掉
.toArray();
}
}

还写 (chao) 了一个不用 stream,纯手工拿 entry set 做比较的解法,因过于丑陋,就不贴在这了,submission这里

128. Longest Consecutive Sequence

Example:

1
2
3
4
5
6
7
Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9
Explanation: The longest consecutive elements sequence is [0, 1, 2, 3, 4, 5, 6, 7, 8]. Therefore its length is 9.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public int longestConsecutive(int[] nums) {
if (nums.length == 0) {
return 0;
}

Arrays.sort(nums);

int longestStreak = 1;
int currentStreak = 1;

for (int i = 1; i < nums.length; i++) {
// 因为当前数字已经记入了一个“连击”
// 所以当这个数字跟上一个数字重复的时候,直接跳到下一个数字
if (nums[i] != nums[i - 1]) {
// 既然连续,那么当前数字跟上一个数字肯定差1
if (nums[i] == nums[i - 1] + 1) {
currentStreak++;
} else {
// 如果不连续了,记下来最大的连击数,当前连击数重置
longestStreak = Math.max(longestStreak, currentStreak);
currentStreak = 1;
}
}
}

// 最后取最大的连击数,这个不用多说吧
return Math.max(longestStreak, currentStreak);
}
}

125. Valid Palindrome

Example:

1
2
3
4
5
6
7
8
Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public boolean isPalindrome(String s) {
// 把不是字母和数字的字符剔出去,然后转小写,方便比较
String str = s.replaceAll("[\\W]|_", "");
str = str.toLowerCase();

String reversed = new StringBuilder(str).reverse().toString();

return str.equals(reversed);
}
}

但是很显然,这个偷鸡解法并不是 two pointers 这个分类想要的,所以另一个解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public boolean isPalindrome(String s) {
// 把不是字母和数字的字符剔出去,然后转小写,方便比较
String str = s.replaceAll("[\\W]|_", "");
str = str.toLowerCase();

char[] chars = str.toCharArray();

int middle = chars.length / 2;
int head = 0;
int tail = chars.length - 1;

// head和tail两个指针逐步向middle逼近
// 一边走,一边比较两个指针指向的字母是不是一样
while (head < middle) {
if (chars[head] != chars[tail]) {
// 不一样的话,那自然就不是回文字符串了
return false;
}

head++;
tail--;
}

return true;
}
}

1. Two Sum

Example:

1
2
3
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public int[] twoSum(int[] nums, int target) {
// key是数字本身,value是数字所在下标
Map<Integer, Integer> map = new HashMap<>();

for (int i = 0; i < nums.length; i++) {
// 算一下target与当前下标的差
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[] { map.get(complement), i };
}
map.put(nums[i], i);
}

throw new IllegalArgumentException("No solution found");
}
}

计算过程:

  • i = 0nums[i] = 2complement = 9 - 2 = 7,map 的 key 里面找不到 7,所以 map.put(2, 0)
  • i = 1nums[i] = 7complement = 9 - 7 = 2,map 的 key 里面有 2,即 nums[i] + nums[map.get(2)] = 9,返回 [map.get(2), nums[i]][0, 1]

167. Two Sum II - Input Array Is Sorted

Example:

1
2
3
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public int[] twoSum(int[] numbers, int target) {
// 两个指针
// 一个从头往尾走,一个从尾往头走
int low = 0;
int high = numbers.length - 1;

while (low < high) {
// 要求是计算两个数字之和是否等于target
// 同时因为数组已经按升序排列
// 那么如果加的结果大于target,就让尾指针往前,取更小的数
// 如果结果小于target,就让头指针往后,取更大的数
// 结果要么找到合适的两个数,要么两个指针相遇,即没有合适的数字
int sum = numbers[low] + numbers[high];
if (sum == target) {
return new int[] {low + 1, high + 1};
} else if (sum < target) {
++low;
} else {
--high;
}
}

return new int[] {-1, -1};
}
}

15. 3Sum

Example:

1
2
3
4
5
6
7
8
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

一种解法是,类似 Two Sum II,取一个基准数,然后用 Two Sum II 的方法找基准数右边符合要求的两个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
// 先把nums排序,让这个数组符合Two Sum II的要求
Arrays.sort(nums);

List<List<Integer>> result = new ArrayList<>();

// 从头到尾遍历nums,取一个数字作为基准
for (int i = 0; i < nums.length && nums[i] <= 0; ++i) {
// 这里的条件是为了不重复计算相同的数字,
// 即只在当前数字不跟上一个数字重复的时候才计算
if (i == 0 || nums[i - 1] != nums[i]) {
twoSumII(nums, i, result);
}
}

return result;
}

private void twoSumII(int[] nums, int i, List<List<Integer>> result) {
// 取nums[i]右边的数组作为子数组
// 左指针指向子数组第一个元素
int low = i + 1;
// 右指针指向最后一个元素
int high = nums.length - 1;

while (low < high) {
// 基准数 + 左指针 + 右指针
int sum = nums[i] + nums[low] + nums[high];
if (sum < 0) {
// 结果小于零,那么左指针往右走,取更大的一个数
++low;
} else if (sum > 0) {
// 结果大于零,那么右指针往左走,取更小的一个数
--high;
} else {
// 等于零,那么这三个数就是我们想要的
result.add(Arrays.asList(nums[i], nums[low], nums[high]));

// 继续缩小范围
low++;
high--;

// 并且当low指向相同数字时,继续向右走
// 然后重新在上一层循环里面继续找符合要求的数字
// 毕竟区间内可能有多组符合条件的数字
while (low < high && nums[low] == nums[low - 1]) {
++low;
}
}
}
}
}

但是,如果题目不允许改变 nums 数组呢?那么可以这样解,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Set<List<Integer>> result = new HashSet<>();
Set<Integer> duplicates = new HashSet<>();
Map<Integer, Integer> seen = new HashMap<>();

for (int i = 0; i < nums.length; i++) {
if (!duplicates.add(nums[i])) {
continue;
}

for (int j = i + 1; j < nums.length; j++) {
int complement = -(nums[i] + nums[j]);
// 如果在seen这个map里面找到了曾经计算过的complement
// 那么说明complement存在于nums数组中
// 即找到了三个和为零的数字,nums[i],nums[j],complement
if (seen.containsKey(complement) && seen.get(complement) == i) {
List<Integer> triplet = Arrays.asList(nums[i], nums[j], complement);
// 排序之后再放进set,避免插入内容相同位置不同的结果
Collections.sort(triplet);
result.add(triplet);
}

// 记录nums[j]可以作为nums[i]的补充(complement)
seen.put(nums[j], i);
}
}

return new ArrayList<>(result);
}
}

11. Container With Most Water

Example:

1
2
3
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public int maxArea(int[] height) {
int max = 0;

int left = 0;
int right = height.length - 1;

while (left < right) {
// 取容器最短的那个板子,木桶原理嘛
int ht = Math.min(height[left], height[right]);
// 板子左右有几格水
int water = right - left;
// 水的体积,也就是蓝色正方形的面积,底*高
int volume = ht * water;
// 记录最大的体积
max = Math.max(max, volume);

// 既然要找最大的体积,当然哪个板子短就换哪个
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}

return max;
}
}

121. Best Time to Buy and Sell Stock

Example:

1
2
3
4
Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public int maxProfit(int[] prices) {
if (prices.length < 2) {
return 0;
}

int buyPrice = Integer.MAX_VALUE;
int overallProfit = 0;
int profitIfSoldToday = 0;

for (int i = 0; i < prices.length; i++) {
// 让buyPrice保存最小的价格
if (prices[i] < buyPrice) {
buyPrice = prices[i];
}

// 计算今日价格与买入价的差
profitIfSoldToday = prices[i] - buyPrice;

// overallProfit记录最大的总利润
if (overallProfit < profitIfSoldToday) {
overallProfit = profitIfSoldToday;
}
}

return overallProfit;
}
}

108. Convert Sorted Array to Binary Search Tree

Example:

1
2
Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return builder(nums, 0, nums.length - 1);
}

private TreeNode builder(int[] nums, int left, int right) {
if (left > right) {
return null;
}

// 从中间将nums二分
// 比如在第一层递归中,
// [-10,-3,0,5,9] -> [-10,-3,0] [5,9]
int middle = (left + right) / 2;

// 中间的数字作为二叉搜索树的根节点
TreeNode rootNode = new TreeNode(nums[middle]);
// 第一层递归中[-10, -3]拿去构造左边的子节点
rootNode.left = builder(nums, left, middle - 1);
// 第一层递归中[5,9]拿去构造右边的子节点
rootNode.right = builder(nums, middle + 1, right);

return rootNode;
}
}

思路就是递归 + 二分,或许还有些分治思想?先找见根节点,然后把数组左右分成两半,在递归里面再重复这样的操作,直到只有一个根节点,也就是最下面的叶子节点。最后往上组装。
数据怎么跑的 debug 一下看看吧,用语言描述肯定要乱死。

146. LRU Cache

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1); // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2); // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1); // return -1 (not found)
lRUCache.get(3); // return 3
lRUCache.get(4); // return 4

解题思路:

LRU Cache,即 Least Recently Used Cache,其运作机理是,如果在 cache 已满的时候添加新的记录,那么要先删掉其中最不常用的记录,然后添加新的记录。

我们可以用双向链表来实现这个效果,越靠近链表头,就代表这个元素越常被用到;反之越靠近链表尾,这个元素就越不常用,链表尾的前一个元素也将是在 cache 满了之后被删掉的那个元素。

那么首先需要创建一个类 Node,代表双向链表中的节点。

1
2
3
4
5
6
7
8
9
10
11
12
public class Node {
Node next;
Node prev;

int key;
int value;

public Node(int key, int value) {
this.key = key;
this.value = value;
}
}

这时候就可以初始化 LRUCache 这个类的结构了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class LRUCache {
// 链表头节点,永远不动
private final Node head = new Node(0, 0);
// 链表尾节点,永远不动
private final Node tail = new Node(0, 0);
// 存储key与Node的映射,get的时候实际上是从这取值
private final Map<Integer, Node> map = new HashMap<>();
// cache容量
private final int capacity;

public LRUCache(int capacity) {
this.capacity = capacity;
// 双向链表头尾相连
head.next = tail;
tail.prev = head;
}
}

接下来先实现 get 方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 当一个节点被get
// 那么就把它提到双向链表的头部位置
public int get(int key) {
// 根据题目要求,key不存在就返回-1
if (!map.containsKey(key)) {
return -1;
}

Node node = map.get(key);
Node nodeNext = node.next;
Node nodePrev = node.prev;

// 先把这个node从当前位置抹去
nodePrev.next = nodeNext;
nodeNext.prev = nodePrev;

// 然后插入到头部
Node headNext = head.next;
node.next = headNext;
node.prev = head;
headNext.prev = node;
head.next = node;

return node.value;
}

接下来实现 put 方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public void put(int key, int value) {
// 如果key已经存在
// 那么put相当于更新value,同时刷新在LRU Cache中的位置
// 所以先把已有的这个node删掉
if (map.containsKey(key)) {
Node node = map.remove(key);

Node nodeNext = node.next;
Node nodePrev = node.prev;
nodePrev.next = nodeNext;
nodeNext.prev = nodePrev;
}

// 如果cache满了,就要先删掉末尾的节点(末位淘汰制?
if (map.size() == capacity) {
Node leastRecentUsedNode = tail.prev;
map.remove(leastRecentUsedNode.key);

leastRecentUsedNode.prev = tail;
tail.prev = leastRecentUsedNode.prev;
}

Node newNode = new Node(key, value);
map.put(key, newNode);

// 把这个新建的node塞到head和headNext之间
Node headNext = head.next;
newNode.prev = head;
newNode.next = headNext;
headNext.prev = newNode;
head.next = newNode;
}

可见新增节点和删除节点操作的代码是经常重复的,所以抽成两个单独的方法。最后完整的解题代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
class LRUCache {
private final Node head = new Node(0, 0);
private final Node tail = new Node(0, 0);
private final Map<Integer, Node> map = new HashMap<>();

private final int capacity;

public LRUCache(int capacity) {
this.capacity = capacity;
head.next = tail;
tail.prev = head;
}

public int get(int key) {
if (!map.containsKey(key)) {
return -1;
}

Node node = map.get(key);
remove(node);
insert(node);

return node.value;
}

public void put(int key, int value) {
if (map.containsKey(key)) {
remove(map.get(key));
}

if (map.size() == capacity) {
remove(tail.prev);
}

insert(new Node(key, value));
}

private void remove(Node node) {
map.remove(node.key);
node.prev.next = node.next;
node.next.prev = node.prev;
}

private void insert(Node node) {
map.put(node.key, node);

Node headNext = head.next;
node.prev = head;
node.next = headNext;
headNext.prev = node;
head.next = node;
}

public class Node {
Node next;
Node prev;

int key;
int value;

public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
}

/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/

9. Palindrome number

Example:

1
2
3
Input: x = 121
Output: true
Explanation: 121 reads as 121 from left to right and from right to left.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public boolean isPalindrome(int x) {
if (x < 0) {
return false;
}

int input = x;

int reversedNum = 0;

// x从低位往高位取数字,然后从高位到低位填给reversedNum
// 即把x反转
while (x != 0) {
// reversedNum乘10,加上x除以10的余数,即当前x的末位数
reversedNum = reversedNum * 10 + x % 10;
// x除以10,抛掉当前的末位数
x = x / 10;
}

if (reversedNum > Integer.MAX_VALUE || reversedNum < Integer.MIN_VALUE) {
return false;
}

return input == reversedNum;
}
}

计算过程:

  • x = 121reversedNum = 0reversedNum = reversedNum * 10 + x % 10 = 0 + 1 = 1x = x / 10 = 121 / 10 = 12
  • x = 12reversedNum = 1reversedNum = reversedNum * 10 + x % 10 = 10 + 2 = 12x = x / 10 = 12 / 10 = 1
  • x = 1reversedNum = 12reversedNum = reversedNum * 10 + x % 10 = 120 + 1 = 121x = x / 10 = 1 / 10 = 0
  • input == reversedNum => 121 == 121 => true

写到这想到还有个粗暴解法,把数字当成字符串,翻转一下然后比较两个字符串是不是一样不就行了,做什么数学题?

1
2
3
4
5
6
7
8
class Solution {
public boolean isPalindrome(int x) {
String inputString = Integer.toString(x);
String reversedString = new StringBuilder(inputString).reverse().toString();

return inputString.equals(reversedString);
}
}

多清爽,三行完事还不烧脑子。

13. Roman to Integer

Example:

1
2
3
Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public int romanToInt(String s) {
// 基本罗马数字
final HashMap<Character, Integer> map = new HashMap<>(7);
map.put('I', 1);
map.put('V', 5);
map.put('X', 10);
map.put('L', 50);
map.put('C', 100);
map.put('D', 500);
map.put('M', 1000);

// IV这种左减格式的数字收拾起来太麻烦,
// 直接转成连续的基本数字
final String sanitized = s
.replace("IV", "IIII")
.replace("IX", "VIIII")
.replace("XL", "XXXX")
.replace("XC", "LXXXX")
.replace("CD", "CCCC")
.replace("CM", "DCCCC");

final char[] chars = sanitized.toCharArray();

int result = 0;
for (char aChar : chars) {
result += map.get(aChar);
}

return result;
}
}

计算过程:

  • MCMXCIV(1994) => M CM XC IV(1000 900 90 4) => M DCCC LXXXX IIII
  • 从头到尾遍历 MDCCCLXXXXIIII 中每个字符,去 map 里面找对应的阿拉伯数字,加起来就完事了

一开始做的时候愁死我了,没有左减格式的数字没啥难度,想破脑袋也没想到怎么处理左减,抄答案发现还能这么玩,属实打开思路了。

252. Meeting Rooms

Given an array of meeting time intervals where intervals[i] = [starti, endi], determine if a person could attend all meetings.

Example:

1
2
Input: intervals = [[0,30],[5,10],[15,20]]
Output: false

Easy 级别的题,思路很简单,先把会议安排按照开始时间升序排列,然后比较下一场会议的开始时间是否小于上一场会议的结束时间,是的话就说明这个人无法参加全部会议。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public boolean canAttendMeetings(int[][] intervals) {
if (intervals.length <= 1) {
return true;
}

// Sort with the meeting start time
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

int lastEndTime = intervals[0][1];

for (int i = 1; i < intervals.length; i++) {
int currentBeginTime = intervals[i][0];

if (currentBeginTime < lastEndTime) {
return false;
}

lastEndTime = intervals[i][1];
}

return true;
}
}

253. Meeting Rooms II

Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.

Example:

1
2
Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2

这道题要用到优先队列,具体算法见注释。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public int minMeetingRooms(int[][] intervals) {
if (intervals.length <= 1) {
return intervals.length;
}

// 定义一个优先队列,存储会议的结束时间,按升序排列
// 因为会议结束,下一场会议才能占用这个会议室
// 所以只需要比较当前会议的开始时间与上一场会议的结束时间
PriorityQueue<Integer> allocator = new PriorityQueue<>(
intervals.length,
(a, b) -> a - b
);

// 重新排序intervals,按照会议的开始时间升序排列
Arrays.sort(
intervals,
(a, b) -> a[0] - b[0]);

// 第一场会议占用一个会议室
allocator.add(intervals[0][1]);

for (int i = 1; i < intervals.length; i++) {
// 从第二场会议开始检查
if (intervals[i][0] >= allocator.peek()) {
// 如果第二场会议在开始的时候,上一场会议已经结束
// 那么释放掉上一场会议的会议室
// 也就是删除掉优先队列的第一个元素
allocator.poll();
}

// 当前会议肯定要占一个会议室
allocator.add(intervals[i][1]);
}

return allocator.size();
}
}

655. Print Binary Tree

抄答案 Java Easy Solution - shawonnirob16

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<String>> printTree(TreeNode root) {
List<List<String>> result = new ArrayList<>();

int height = getHeight(root);
int row = height + 1;
int column = (int) Math.pow(2, height + 1) - 1;

// 先全部填充空字符串
for (int k = 0; k < row; k++) {
List<String> list = new ArrayList<>();
for (int i = 0; i < column; i++) {
list.add("");
}

result.add(list);
}

int left = 0;
int right = column - 1;
int level = 0;
fill(result, left, right, level, root);

return result;
}

// 递归整个树,每层高度加一,计算树的高度
private int getHeight(TreeNode root) {
if (root == null) {
return -1;
}

int left = getHeight(root.left);
int right = getHeight(root.right);

return 1 + Math.max(left, right);
}

private void fill(
List<List<String>> result,
int left,
int right,
int level,
TreeNode root
) {
if (root == null) {
return;
}

// 计算list的中间位置的下标
int middle = left + (right - left) / 2;
// 在中间位置填入当前节点的值
result.get(level).set(middle, String.valueOf(root.val));

fill(result, left, middle - 1, level + 1, root.left);
fill(result, middle + 1, right, level + 1, root.right);
}
}