1545 找出第N个二进制字符串的第K位 #分治

题目链接

题意

给定正整数n(≤20)n(\leq 20)与kk，二进制串SnS_n形成规则有：

  • S1=“0”S_1 = “0”

  • 当i>1i>1时，Si=Si−1+“1”+reverse(invert(Si−1))S_i = S_{i-1}+“1”+reverse(invert(S_{i-1}))

    其中reverse(x)reverse(x)表示左右反转字符串x，invert(x)invert(x)表示翻转x中的每一位(0->1，1->0)

现要返回SnS_n的第kk位字符。

如：n=3,k=1n=3,k=1，可以得到S3=“0111001”S_3=“0111001”，其第一位为"0"，故返回"0"

分析

本来想打表，但最后的串实在是长。我们不必从n=1一步步模拟整个过程，而是自顶而下深入递归，只关心第kk位属于上一步形成的01串的哪个位置哪个字符。

我们容易推出，对于SnS_n形成的串为2n−12^n-1长度的01串，我们比较kk与2n−12^{n-1}的大小：

  • 如果k=2n−1k=2^{n-1}，它在串最中间，字符为"1"，直接返回即可
  • 如果k<2n−1k<2^{n-1}，它在当前串的左部分，由串的形成规则可知，串左部分是经上一轮的串直接复制得到的，那么递归n−1n-1次操作的第kk位即可
  • 如果k>2n−1k>2^{n-1}，由串的形成规则，串右部分是经过上一轮串的反转+翻转得到的，那么当前的第k位是由上一轮的2n−1−k+12^n-1-k+1位置得到的，当然别忘了对返回结果的字符进行取反操作！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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));
        }
    }
};

1546 和为目标值的最大数目不重叠非空子数组数目 #前缀和 #哈希表 #线性DP

题目链接

题意

给定数组 nums(长度不大于1e51e5) 和一个整数 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>0i>0显然dp[0] = 0；当i>0i>0时，有两种情况：

  • 存在这样的pos(≤i)st.sum[i]−sum[pos]==targetpos(\leq i) st.sum[i]-sum[pos]==target，

    • 我们找到[pos,i][pos, i]的合法子数组，于是dp[i] 可以由dp[pos]+1转移
    • [pos, i]的子数组长度可能太长，以至于覆盖了该区间的几个合法子数组，那么dp[i]也可以由dp[i-1]转移

    即得到转移方程：dp[i]=max(dp[i−1],dp[pos]+1)dp[i] = max(dp[i-1], dp[pos]+1)

  • 不存在这样的pospos，显然转移方程只能为dp[i]=dp[i−1]dp[i] = dp[i-1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
private:
    int dp[100005] = {0};
public:
    int maxNonOverlapping(vector<int>& nums, int target) {
        map<int, int> mymap;
        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()];
    }
};

1547 切棍子的最小成本 #区间DP

题目链接

题意

给定长度为nn个单位的木棍，及记录你要将棍子切开的位置数组cuts[i]cuts[i]，现要你按cuts[i]cuts[i]记录的位置按一定顺序切割木棍，使得成本最小，并求其值。其中每次切割的成本是当前要切割的棍子的长度。

分析

显然是石子合并的变式，区间DP题，不过我们需要预处理下每个切割位置之间的长度(该位置的序号-前一位置的序号)，同时将代价数组sum[]从1计数，便于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
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];
    }
};