464. 我能赢吗
在 “100 game” 这个游戏中，两名玩家轮流选择从 1 到 10 的任意整数，累计整数和，先使得累计整数和达到 100 的玩家，即为胜者。
如果我们将游戏规则改为 “玩家不能重复使用整数” 呢？
例如，两个玩家可以轮流从公共整数池中抽取从 1 到 15 的整数（不放回），直到累计整数和 >= 100。
给定一个整数 maxChoosableInteger （整数池中可选择的最大数）和另一个整数 desiredTotal（累计和），判断先出手的玩家是否能稳赢（假设两位玩家游戏时都表现最佳）？
你可以假设 maxChoosableInteger 不会大于 20， desiredTotal 不会大于 300。
示例：
1
2
3
4
5
6
7
8
9
10
11
12
13
| 输入：
maxChoosableInteger = 10
desiredTotal = 11
输出：
false
解释：
无论第一个玩家选择哪个整数，他都会失败。
第一个玩家可以选择从 1 到 10 的整数。
如果第一个玩家选择 1，那么第二个玩家只能选择从 2 到 10 的整数。
第二个玩家可以通过选择整数 10（那么累积和为 11 >= desiredTotal），从而取得胜利.
同样地，第一个玩家选择任意其他整数，第二个玩家都会赢。
|
暂时还不知道什么想法…
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
| class Solution {
public:
bool helper(int bits, int distance, int maxChoosableInteger, int dp[]) {
if(dp[bits] != 0) {
return dp[bits] == 1;
}
bool result = false;
for(int cur = maxChoosableInteger;cur > 0;cur--) {
int curBit = 1 << (cur - 1);
if((bits & curBit) == 0) {
if(cur >= distance || !helper(bits | curBit, distance - cur, maxChoosableInteger, dp)) {
result = true;
break;
}
}
}
dp[bits] = result ? 1 : 2;
return result;
}
bool canIWin(int maxChoosableInteger, int desiredTotal) {
int canReachTotal = (1 + maxChoosableInteger) * maxChoosableInteger / 2;
if(canReachTotal < desiredTotal) {
return false;
} else if(canReachTotal == desiredTotal) {
return (maxChoosableInteger & 1) == 1;
}
int dp[1 << maxChoosableInteger] = {0};
return helper(0, desiredTotal, maxChoosableInteger, dp);
}
};
|
410. 分割数组的最大值
给定一个非负整数数组和一个整数 m，你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。
注意:
数组长度 n 满足以下条件:
1 ≤ n ≤ 1000
1 ≤ m ≤ min(50, n)
示例:
1
2
3
4
5
6
7
8
9
10
11
| 输入:
nums = [7,2,5,10,8]
m = 2
输出:
18
解释:
一共有四种方法将nums分割为2个子数组。
其中最好的方式是将其分为[7,2,5] 和 [10,8]，
因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。
|
思路：
我们能够找到这个答案的一个性质：
如果我们找到了一种分割方案，使得最大的分割子数组和不超过x，那么我们也能找到一种分割方案使得最大的分割子数组和不超过y，其中y > x
对于值x，我们把这个性质定义为F(x)。如果F(x)为真，那就意味着我们一定可以找到一种分割方案使得最大分割的子数组和不超过x
我们让x的区间为负无穷大到无穷大，一旦我们找到一个值x0，使得所有的x < x0,F(x)都为假，所有的x > x0，F(x)都为真。那么显然，这个x0就是我们要的答案了。
算法描述：
- 找到一个数，把它作为分割后各个子数组的和的最大值
- 根据这个最大值，分割数组，使每个子数组的和都不超过这个最大值
- 如果不能将数组中所有数字都分割进子数组，即还没分割完，子数组数量就已经用完了。则表示这个最大值还不够大。寻找下一个数，循环步骤1-3
- 如果全部都分割进子数组，则返回这个最大值。
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 splitArray(vector<int>& nums, int m) {
long l = nums[0], h = 0;
for(auto i : nums) {
h += i;
l = max(l, long(i));
}
while(l < h) {
long mid = (l + h) / 2;
long temp = 0;
int cnt = 1;
for(auto i : nums) {
temp += i;
if(temp > mid) {
temp = i;
++cnt;
}
}
if(cnt > m) {
l = mid + 1;
} else {
h = mid;
}
}
return l;
}
};
|
467. 环绕字符串中唯一的字符串
把字符串 s 看作是“abcdefghijklmnopqrstuvwxyz”的无限环绕字符串，所以 s 看起来是这样的："…zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd…".
现在我们有了另一个字符串 p 。你需要的是找出 s 中有多少个唯一的 p 的非空子串，尤其是当你的输入是字符串 p ，你需要输出字符串 s 中 p 的不同的非空子串的数目。
注意: p 仅由小写的英文字母组成，p 的大小可能超过 10000。
示例 1:
1
2
3
| 输入: "a"
输出: 1
解释: 字符串 S 中只有一个"a"子字符。
|
示例 2:
1
2
3
| 输入: "cac"
输出: 2
解释: 字符串 S 中的字符串“cac”只有两个子串“a”、“c”。
|
示例 3:
1
2
3
| 输入: "zab"
输出: 6
解释: 在字符串 S 中有六个子串“z”、“a”、“b”、“za”、“ab”、“zab”。
|
思路：
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 findSubstringInWraproundString(string p) {
int n = p.length();
if(n == 0) {
return 0;
}
int len_string[26] = {0};
len_string[p[0] - 'a'] = 1;
int dp = 1, sum = 0;
for(int i = 1;i < n;i++) {
if(p[i] == p[i - 1] + 1 || (p[i - 1] == 'z' && p[i] == 'a')) {
dp += 1;
} else {
dp = 1;
}
len_string[p[i] - 'a'] = max(len_string[p[i] - 'a'], dp);
}
for(int i = 0;i < 26;i++) {
sum += len_string[i];
}
return sum;
}
};
|
516. 最长回文子序列
给定一个字符串s，找到其中最长的回文子序列。可以假设s的最大长度为1000。
示例 1:
1
2
3
4
5
| 输入:
"bbbab"
输出:
4
一个可能的最长回文子序列为 "bbbb"。
|
示例 2:
思路：
典型的动态规划。记dp[i][j]表示从i-j的最长回文子序列
如果s[i] == s[j]，则dp[i][j] = dp[i + 1][j - 1] + 2
否则dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
上Code：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
int longestPalindromeSubseq(string s) {
int maxLength = 1;
int n = s.length();
vector<vector<int>> dp(n, vector<int>(n ,0));
for(int i = n - 1;i >= 0;i--) {
dp[i][i] = 1;
for(int j = i + 1;j < n;j++) {
dp[i][j] = s[i] == s[j] ? dp[i + 1][j - 1] + 2 : max(dp[i + 1][j], dp[i][j - 1]);
maxLength = max(maxLength, dp[i][j]);
}
}
return maxLength;
}
};
|