给定正整数\(n(\leq 20)\)与\(k\),二进制串\(S_n\)形成规则有:
\(S_1 = “0”\)
当\(i>1\)时,\(S_i = S_{i-1}+“1”+reverse(invert(S_{i-1}))\)
其中\(reverse(x)\)表示左右反转字符串x
,\(invert(x)\)表示翻转x中的每一位(0->1,1->0)
现要返回\(S_n\)的第\(k\)位字符。
如:\(n=3,k=1\),可以得到\(S_3=“0111001”\),其第一位为"0",故返回"0"
本来想打表,但最后的串实在是长。我们不必从n=1一步步模拟整个过程,而是自顶而下深入递归,只关心第\(k\)位属于上一步形成的01串的哪个位置哪个字符。
我们容易推出,对于\(S_n\)形成的串为\(2^n-1\)长度的01串,我们比较\(k\)与\(2^{n-1}\)的大小:
如果\(k=2^{n-1}\),它在串最中间,字符为"1",直接返回即可
如果\(k<2^{n-1}\),它在当前串的左部分,由串的形成规则可知,串左部分是经上一轮的串直接复制得到的,那么递归\(n-1\)次操作的第\(k\)位即可
如果\(k>2^{n-1}\),由串的形成规则,串右部分是经过上一轮串的反转+翻转得到的,那么当前的第k位是由上一轮的\(2^n-1-k+1\)位置得到的,当然别忘了对返回结果的字符进行取反操作!
class Solution {
public:
char Trans(char now) {
return (now == '1') ? '0' : '1';
}
char findKthBit(int n, int k) {
if (n == 1) return '0';
int len = 1 << (n - 1);
if (k == len) return '1';
else if (k < len) return findKthBit(n - 1, k);
else {
return Trans(findKthBit(n - 1, (len << 1) - k));
}
}
};
给定数组 nums
(长度不大于\(1e5\)) 和一个整数 target
。现要返回 非空不重叠 子数组的最大数目,且每个子数组中数字和都为 target
。
nums = [-1,3,5,1,4,2,-9], target = 6
,总共有 3 个子数组和为 6 。 $([5,1], [4,2], [3,5,1,4,2,-9]) $但只有前 2 个是不重叠的。
dp[i]
表示前i
位满足要求的子数组个数;sum
表示[1, size]
的前缀和(先假定从1计数)
当\(i>0\)显然dp[0] = 0
;当\(i>0\)时,有两种情况:
存在这样的\(pos(\leq i) st.sum[i]-sum[pos]==target\),
dp[i]
可以由dp[pos]+1
转移[pos, i]
的子数组长度可能太长,以至于覆盖了该区间的几个合法子数组,那么dp[i]
也可以由dp[i-1]
转移即得到转移方程:\(dp[i] = max(dp[i-1], dp[pos]+1)\)
不存在这样的\(pos\),显然转移方程只能为\(dp[i] = dp[i-1]\)
class Solution {
private:
int dp[100005] = {0};
public:
int maxNonOverlapping(vector
map
int sum = 0; mymap[0] = 0;
for (int i = 1; i <= nums.size(); i++) {
sum += nums[i - 1];
if (mymap.count(sum - target)) { //是否存在sum[pos]满足sum[i]-sum[pos]=target
int pos = mymap[sum - target];
dp[i] = max(dp[i - 1], dp[pos] + 1);
}
else {
dp[i] = dp[i - 1];
}
mymap[sum] = i; //记录前缀和sum的最新位置
}
return dp[nums.size()];
}
};
给定长度为\(n\)个单位的木棍,及记录你要将棍子切开的位置数组\(cuts[i]\),现要你按\(cuts[i]\)记录的位置按一定顺序切割木棍,使得成本最小,并求其值。其中每次切割的成本是当前要切割的棍子的长度。
显然是石子合并的变式,区间DP题,不过我们需要预处理下每个切割位置之间的长度(该位置的序号-前一位置的序号),同时将代价数组sum[]
从1计数,便于DP
class Solution {
private:
int sum[105] = { 0 };
int dp[105][105];
public:
int cost(int lo, int hi) {
return sum[hi] - sum[lo];
}
void Init(int maxlen, vector<int>& cuts, int n) {
sort(cuts.begin(), cuts.end());
for (int i = 1; i <= maxlen; i++)
for (int j = 1; j <= maxlen; j++)
dp[i][j] = 0x3f3f3f3f;
sum[1] = cuts[0]; dp[1][1] = dp[maxlen][maxlen] = 0;
for (int i = 2; i <= cuts.size(); i++) {
dp[i][i] = 0;
sum[i] = sum[i - 1] + cuts[i - 1] - cuts[i - 2];
}
sum[maxlen] = sum[maxlen - 1] + n - cuts[cuts.size() - 1];
}
int minCost(int n, vector<int>& cuts) {
int maxlen = cuts.size() + 1;
Init(maxlen, cuts, n);
for (int len = 2; len <= maxlen; len++) {
for (int i = 1; i + len - 1 <= maxlen; i++) {
int j = i + len - 1;
for (int k = i; k < j; k++)
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + cost(i - 1, j));
}
}
return dp[1][maxlen];
}
};
手机扫一扫
移动阅读更方便
你可能感兴趣的文章