8000 20200829 · BoscoSuen/leetcode@3d36b1e · GitHub
[go: up one dir, main page]
Skip to content

Commit 3d36b1e

Browse files
BoscoSuenBoscoSuen
committed
20200829
1 parent ffbe037 commit 3d36b1e

6 files changed

+186
-0
lines changed

‎Java/115.distinct-subsequences.java

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
/*
2+
* @lc app=leetcode id=115 lang=java
3+
*
4+
* [115] Distinct Subsequences
5+
*/
6+
7+
// @lc code=start
8+
class Solution {
9+
/*
10+
DP dp[i][j] : t的(1,i)部分和s的(1,j)部分相等的subsequences数
11+
padding : dp[0][*] = 1 t为""，s中有一个subsequence""和之匹配
12+
if t[i] = s[j] dp[i][j] = dp[i- 1][j - 1] # t[i]和s[j]在subsequence中匹配
13+
+ dp[i][j - 1] # s[j]不在subsequence中，和s(0, j-1)结果相同
14+
else dp[i][j] = dp[i][j - 1] # s多加一个j不会改变subsequences数
15+
*/
16+
public int numDistinct(String s, String t) {
17+
// t.size() < s.size()
18+
int m = t.length(), n = s.length();
19+
int[][] dp = new int[m + 1][n + 1];
20+
Arrays.fill(dp[0], 1);
21+
for (int i = 1; i <= m; ++i) {
22+
for (int j = 1; j <= n; ++j) {
23+
if (t.charAt(i - 1) == s.charAt(j - 1)) {
24+
dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1];
25+
} else {
26+
dp[i][j] = dp[i][j - 1];
27+
}
28+
}
29+
}
30+
return dp[m][n];
31+
}
32+
}
33+
// @lc code=end
34+

‎Java/188.best-time-to-buy-and-sell-stock-iv.java

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
/*
2+
* @lc app=leetcode id=188 lang=java
3+
*
4+
* [188] Best Time to Buy and Sell Stock IV
5+
*/
6+
7+
// @lc code=start
8+
class Solution {
9+
/*
10+
如果k >= prices.length / 2, 则视为可以无限次交易
11+
我们定义local[i][j]为在到达第i天时最多可进行j次交易并且最后一次交易在最后一天卖出的最大利润，此为局部最优。然后我们定义global[i][j]为在到达第i天时最多可进行j次交易的最大利润，此为全局最优。它们的递推式为：
12+
local[i][j] = max(global[i - 1][j - 1] + max(diff, 0), local[i - 1][j] + diff)
13+
global[i][j] = max(local[i][j], global[i - 1][j])
14+
time: O(kn)
15+
space: O(k)
16+
*/
17+
public int maxProfit(int k, int[] prices) {
18+
if (prices == null || prices.length == 0) return 0;
19+
if (k >= prices.length / 2) return unlimitedProfit(prices);
20+
int[] local = new int[k + 1];
21+
int[] global = new int[k + 1];
22+
for (int i = 0; i < prices.length - 1; ++i) {
23+
int diff = prices[i + 1] - prices[i];
24+
for (int j = k; j >= 1; --j) {
25+
local[j] = Math.max(global[j - 1] + Math.max(diff, 0), local[j] + diff);
26+
global[j] = Math.max(global[j], local[j]);
27+
}
28+
}
29+
return global[k];
30+
}
31+
32+
private int unlimitedProfit(int[] prices) {
33+
int res = 0;
34+
for (int i = 0; i < prices.length - 1; ++i) {
35+
if (prices[i + 1] - prices[i] > 0) {
36+
res += prices[i + 1] - prices[i];
37+
}
38+
}
39+
return res;
40+
}
41+
}
42+
// @lc code=end
43+

‎Java/435.non-overlapping-intervals.java

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
/*
2+
* @lc app=leetcode id=435 lang=java
3+
*
4+
* [435] Non-overlapping Intervals
5+
*/
6+
7+
// @lc code=start
8+
class Solution {
9+
/*
10+
因为是比较end,所以按照end排序
11+
找到排序之后最多有多少non overlapping
12+
time: O(nlogn)
13+
space: O(1)
14+
*/
15+
public int eraseOverlapIntervals(int[][] intervals) {
16+
if (intervals == null || intervals.length == 0) return 0;
17+
Arrays.sort(intervals, (a, b) -> (a[1] - b[1]));
18+
int count = 1;
19+
int end = intervals[0][1];
20+
for (int i = 1; i < intervals.length; ++i) {
21+
if (intervals[i][0] >= end) {
22+
end = intervals[i][1];
23+
count++;
24+
}
25+
}
26+
return intervals.length - count;
27+
}
28+
}
29+
// @lc code=end
30+

‎Java/470.implement-rand-10-using-rand-7.java

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
/*
2+
* @lc app=leetcode id=470 lang=java
3+
*
4+
* [470] Implement Rand10() Using Rand7()
5+
*/
6+
7+
// @lc code=start
8+
/**
9+
* The rand7() API is already defined in the parent class SolBase.
10+
* public int rand7();
11+
* @return a random integer in the range 1 to 7
12+
*/
13+
class Solution extends SolBase {
14+
/*
15+
rand7() will get random 1 ~ 7
16+
(rand7() - 1) * 7 + rand7() - 1 will get random 0 ~ 48
17+
We discard 40 ~ 48, now we have rand40 equals to random 0 ~ 39.
18+
We just need to return rand40 % 10 + 1 and we get random 1 ~ 10.
19+
20+
In 9/49 cases, we need to start over again.
21+
In 40/49 cases, we call rand7() two times.
22+
23+
Overall, we need 49/40*2 = 2.45 calls of rand7() per rand10().
24+
*/
25+
public int rand10() {
26+
int rand40 = 40;
27+
while (rand40 >= 40) {
28+
rand40 = (rand7() - 1) * 7 + (rand7() - 1);
29+
}
30+
return rand40 % 10 + 1;
31+
}
32+
}
33+
// @lc code=end
34+

‎Java/767.reorganize-string.java

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
/*
2+
* @lc app=leetcode id=767 lang=java
3+
*
4+
* [767] Reorganize String
5+
*/
6+
7+
// @lc code=start
8+
class Solution {
9+
/*
10+
先放频率最高的字符，再按位置插入
11+
time: O(n)
12+
space: O(1)
13+
*/
14+
public String reorganizeString(String S) {
15+
int[] freq = new int[26];
16+
char maxChar = 'a';
17+
int maxFreq = 0;
18+
for (char c : S.toCharArray()) {
19+
freq[c - 'a']++;
20+
if (freq[c - 'a'] > maxFreq) {
21+
maxChar = c;
22+
maxFreq = freq[c - 'a'];
23+
}
24+
}
25+
if (maxFreq > (S.length() + 1) / 2) return ""; // "aba"
26+
char[] res = new char[S.length()];
27+
int i = 0;
28+
while (freq[maxChar - 'a']-- > 0) {
29+
res[i] = maxChar;
30+
i += 2;
31+
}
32+
for (char c = 'a'; c <= 'z'; ++c) {
33+
while (freq[c - 'a']-- > 0) {
34+
if (i >= S.length()) i = 1;
35+
res[i] = c;
36+
i += 2;
37+
}
38+
}
39+
return new String(res);
40+
}
41+
}
42+
// @lc code=end
43+

‎README.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -38,6 +38,7 @@
3838
[42. trapping rain water](https://leetcode.com/problems/trapping-rain-water/) | [DP优化为two pointer](https://github.com/Yukinichi/leetcode/blob/master/Java/42.trapping-rain-water.java)
3939
[72. Edit Distance](https://leetcode.com/problems/edit-distance/) | [Solution](https://github.com/Yukinichi/leetcode/blob/master/Java/72.edit-distance.java)
4040
[96. Unique Binary Search Trees](https://leetcode.com/problems/unique-binary-search-trees/) | [Solution](https://github.com/Yukinichi/leetcode/blob/master/Java/96.unique-binary-search-trees.java)
41+
[188. Best Time to Buy and Sell Stock IV](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/) | [局部最优vs全局最优](https://github.com/Yukinichi/leetcode/blob/master/Java/188.best-time-to-buy-and-sell-stock-iv.java)
4142
[300. Longest Increasing Subsequence(LIS)](https://leetcode.com/problems/longest-increasing-subsequence/) | [DP + binary search(C++)](https://github.com/Yukinichi/leetcode/blob/master/Cpp/300.longest-increasing-subsequence.cpp)
4243
[368. Largest Divisible Subset](https://leetcode.com/problems/largest-divisible-subset/) | [LIS问题变种](https://github.com/Yukinichi/leetcode/blob/master/Java/368.largest-divisible-subset.java)
4344
[354. Russian Doll Envelopes](https://leetcode.com/problems/russian-doll-envelopes/)|[Binary Search+DP(思路同lc300)](https://github.com/Yukinichi/leetcode/blob/master/Java/354.russian-doll-envelopes.java)
@@ -122,6 +123,7 @@
122123
:- | :-:
123124
[528. Random Pick with Weight](https://leetcode.com/problems/random-pick-with-weight/) | [Random + binarySeach](https://github.com/Yukinichi/leetcode/blob/master/Java/528.random-pick-with-weight.java)
124125
[384. Shuffle an Array](https://leetcode.com/problems/shuffle-an-array/) | [inside-out shuffle](https://github.com/Yukinichi/leetcode/blob/master/Java/384.shuffle-an-array.java)
126+
[470. Implement Rand10() Using Rand7()](https://leetcode.com/problems/implement-rand10-using-rand7/) | [Solution](https://github.com/Yukinichi/leetcode/blob/master/Java/470.implement-rand-10-using-rand-7.java)
125127

126128
## Search
127129
| Problem | Solution

0 commit comments

Comments
 (0)
0