leetcode150题

刷了 10 多天,刷了 leetcode 上前面 150 题。

因为很多题以前做过,所以做的还是比较快的。因为想熟悉一下 Java ,所以全部都用 Java 写的。leetcode 很多都是面试题,所以题目都是基本,没有什么特别难的题目,几道 hard 也没有特别难的。但是很多题目很经典,而且社区很活跃,Discuss 里很多神仙。有几道题目真的让我感觉到“还有这种操作?”的感受,因为思路太秀了。

之所以特地现在做一个中断,是因为前面 150 道比较经典,虽然很多类型的题目还没出现过,但是最新的题目我做过一些,有凸包,有最短路径什么的,而且 150-200 题之前很多 easy 和 medium,太水了,我懒得做了。我大概浏览了一下 150-200 的 hard,知道了基本的思路,然后就打算先这样中断一下,不打算最近撸了,之后如果没什么特别需要的地方,可能就每周做一下 Contest 吧。

因为有几道题目很帅,所以特地记录一下,有空可以在做一遍这几道。

leetcode32

leetcode32. Longest Valid Parentheses

可以用 DP ,也可以用栈来做。我用了 DP 。官方 Solution 很详细了。

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 longestValidParentheses(String s) {
int len = s.length();
int[] dp = new int[len];
int res = 0;

for(int i = 0; i < len; i++)
{
if(i - 1 >= 0 && s.charAt(i) == ')')
{
if(s.charAt(i - 1) == '(')
{
if(i >= 2) dp[i] = dp[i - 2] + 2;
else dp[i] = 2;
}
else if(s.charAt(i - 1) == ')')
{
if(i - 1 - dp[i - 1] >= 0 && s.charAt(i - 1 - dp[i - 1]) == '(')
{
dp[i] = dp[i - 1] + 2;
if(i - 2 - dp[i - 1] >= 0) dp[i] += dp[i - 2 - dp[i - 1]];
}
}
res = Math.max(res, dp[i]);
}
}

return res;
}
}

leetcode42

leetcode42. Trapping Rain Water

用两个指针向中间收敛来维护一个变量。官方的 Solution 也很详细。也可以用 DP 或者栈来做。

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
class Solution {
public int trap(int[] height) {
if(height.length <= 2) return 0;
int left = 0, right = height.length - 1;
int res = 0, level = Math.min(height[left], height[right]);

while(left < right)
{
if(height[left] <= height[right])
{
left++;
if(height[left] > level)
{
level = Math.min(height[left], height[right]);
}
else
{
res += level - height[left];
}
}
else
{
right--;
if(height[right] > level)
{
level = Math.min(height[left], height[right]);
}
else
{
res += level - height[right];
}
}
}
return res;
}
}

leetcode69

leetcode69. Sqrt(x)

题目贴的 tag 是 binary search,想考查的是二分查找,用二分查找可以。但是一般标准库里用的是 sqrt() 用的是牛顿迭代法。

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
/**
* 1. 二分查找
*/
class Solution {
public int mySqrt(int x) {
if (x == 0)
return 0;
int left = 1, right = Integer.MAX_VALUE;
while (true) {
int mid = left + (right - left)/2;
if (mid > x/mid) {
right = mid - 1;
} else {
if (mid + 1 > x/(mid + 1))
return mid;
left = mid + 1;
}
}
}
}


/**
* 2. 牛顿迭代法
*/
class Solution {
public int mySqrt(int x) {
long r = x;
while (r*r > x)
r = (r + x/r) / 2;
return (int) r;
}
}

leetcode84

leetcode84. Largest Rectangle in Histogram

可以转化成最大01矩阵问题,但是会超时。当然用栈来模拟。

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 largestRectangleArea(int[] heights) {
Stack<Integer> st = new Stack<>();
int res = 0, cnt = 0;
for(int i = 0; i < heights.length; i++)
{
if(st.empty() || heights[i] >= st.peek())
{
st.push(heights[i]);
}
else
{
cnt = 0;
while(!st.empty() && heights[i] < st.peek())
{
res = Math.max(res, ++cnt * st.pop());
}
while(cnt-- >= 0) st.push(heights[i]);
}
}
cnt = 0;
while(!st.empty())
{
res = Math.max(res, ++cnt * st.pop());
}
return res;
}
}

leetcode132

leetcode132. Palindrome Partitioning II

两种DP。

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
class Solution {
public int minCut(String s) {
boolean[][] isPalindrome = new boolean[s.length()][s.length()];
int[] dp = new int[s.length() + 1];
for(int i = 0; i <= s.length(); i++) dp[i] = s.length() - i - 1;

for(int i = s.length() - 1; i >= 0; i --)
{
isPalindrome[i][i] = true;
dp[i] = dp[i + 1] + 1;
for(int j = i + 1; j < s.length(); j++)
{
if(s.charAt(i) == s.charAt(j) && (i + 1 == j || isPalindrome[i + 1][j - 1]))
{
isPalindrome[i][j] = true;
if(dp[j + 1] + 1 < dp[i])
{
dp[i] = dp[j + 1] + 1;
}
}
}
}
return dp[0];
}
}

class Solution {
public int minCut(String s) {
int[] dp = new int[s.length() + 1];
for(int i = 0; i <= s.length(); i++) dp[i] = i - 1;

for(int i = 0; i < s.length(); i++)
{
for(int j = 0; i - j >= 0 && i + j < s.length() && s.charAt(i - j) == s.charAt(i + j); j++) // odd
dp[i + j + 1] = Math.min(dp[i + j + 1], dp[i - j] + 1);
for(int j = 0; i - j - 1 >= 0 && i + j < s.length() && s.charAt(i - j - 1) == s.charAt(i + j); j++) // even
dp[i + j + 1] = Math.min(dp[i + j + 1], dp[i - j - 1] + 1);
}
return dp[s.length()];
}
}

leetcode137

leetcode137. Single Number II

感受到布尔代数的魅力了。一波位运算毁天灭地。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public int singleNumber(int[] nums) {
int one = 0, two = 0;
for(int num : nums)
{
one = (one ^ num) & ~two;
two = (two ^ num) & ~one;
}
return one;
}
}

leetcode146

leetcode146. LRU Cache

实现一个 LRU(Least Recently Used) 的 cache 类。突然感受了一下学操作系统学到的东西,这个看起来很简单的东西,实现起来还是有点秀的。用双向链表和哈希表来实现,让查询和插入都为O(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
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
class LRUCache {

class DLinkedNode {
int key;
int value;
DLinkedNode pre;
DLinkedNode post;
}

/**
* Always add the new node right after head;
*/
private void addNode(DLinkedNode node){
node.pre = head;
node.post = head.post;

head.post.pre = node;
head.post = node;
}

/**
* Remove an existing node from the linked list.
*/
private void removeNode(DLinkedNode node){
DLinkedNode pre = node.pre;
DLinkedNode post = node.post;

pre.post = post;
post.pre = pre;
}

/**
* Move certain node in between to the head.
*/
private void moveToHead(DLinkedNode node){
this.removeNode(node);
this.addNode(node);
}

// pop the current tail.
private DLinkedNode popTail(){
DLinkedNode res = tail.pre;
this.removeNode(res);
return res;
}

private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();
private int count;
private int capacity;
private DLinkedNode head, tail;

public LRUCache(int capacity) {
this.count = 0;
this.capacity = capacity;

head = new DLinkedNode();
head.pre = null;

tail = new DLinkedNode();
tail.post = null;

head.post = tail;
tail.pre = head;
}

public int get(int key) {

DLinkedNode node = cache.get(key);
if(node == null){
return -1; // should raise exception here.
}

// move the accessed node to the head;
this.moveToHead(node);

return node.value;
}


public void put(int key, int value) {
DLinkedNode node = cache.get(key);

if(node == null){

DLinkedNode newNode = new DLinkedNode();
newNode.key = key;
newNode.value = value;

this.cache.put(key, newNode);
this.addNode(newNode);

++count;

if(count > capacity){
// pop the tail
DLinkedNode tail = this.popTail();
this.cache.remove(tail.key);
--count;
}
}else{
// update the value.
node.value = value;
this.moveToHead(node);
}

}
}

/**
* 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);
*/

leetcode166

leetcode166. Fraction to Recurring Decimal

写一个除法生成分数。比较难的用无线循环小数的时候,用哈希表存储余数,key存储余数,value存储起始的位置。如果重复就在起始位置插入’(‘。

leetcode187

leetcode187. Repeated DNA Sequences

用三位就可以表示 A,C,G,T。10个的话用 30 位表示一个序列保存到哈希表中。

总结

这几道是真的很秀。我这几天的代码全在这里了。

放一张图片。

leetcode150