重复的DNA序列
所有 DNA 都由一系列缩写为 ‘A’，’C’，’G’ 和 ‘T’ 的核苷酸组成，例如：”ACGAATTCCG”。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。
编写一个函数来找出所有目标子串，目标子串的长度为 10，且在 DNA 字符串 s 中出现次数超过一次。
示例 1：
输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出：["AAAAACCCCC","CCCCCAAAAA"]
示例 2：
输入：s = "AAAAAAAAAAAAA"
输出：["AAAAAAAAAA"]
提示：
0 <= s.length <= 10^5
s[i] 为 'A'、'C'、'G' 或 'T'
解题思路：利用一个 set 将未出现过的长度为 10 的字符串存起来，如果是出现过的，则是 answer 选项。
class Solution {
public:
vector<string> findRepeatedDnaSequences(string s) {
unordered_set<string> ss;
unordered_set<string> ret;
for(int i = 0; i+9 < s.size(); ++i) {
string tmp = s.substr(i, 10);
auto it = ss.find(tmp);
if(it == ss.end()) {
ss.insert(tmp);
}else {
ret.insert(tmp);
}
}
vector<string> res(ret.begin(), ret.end());
return res;
}
};
买卖股票的最佳时机 IV
给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1：
输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
示例 2：
输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
提示：
0 <= k <= 100
0 <= prices.length <= 1000
0 <= prices[i] <= 1000
解题思路：有了之前几道题的经验，看到这道题想到的就是用动态规划。
首先定义状态，buy[j] 表示当天交易 j 次且手持一个股票的最大收益。sell[j] 表示当天交易 j 次且不持有股票的最大收益。
因为规定只能持有一个股票，也就是 buy 的状态要不保持，要不由 sell 购买股票所得， sell 的状态也同理。
所以可以得到状态转移：(p 为当天股票价格)
- buy[j] = max(bug[j], sell[j-1] - p);
- sell[j] = max(sell[j], buy[j] + p);
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
if (prices.empty()) {
return 0;
}
int n = prices.size();
k = min(k, n / 2);
vector<int> buy(k + 1, INT_MIN);
vector<int> sell(k + 1, 0);
for (int i = 0; i < n; ++i) {
for (int j = 1; j <= k; ++j) {
buy[j] = max(buy[j], sell[j - 1] - prices[i]);
sell[j] = max(sell[j], buy[j] + prices[i]);
}
}
return *max_element(sell.begin(), sell.end());
}
};
旋转数组
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
进阶：
- 尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
- 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？
示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]
示例 2:
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]
提示：
1 <= nums.length <= 2 * 10^4
-2^31 <= nums[i] <= 2^31 - 1
0 <= k <= 10^5
解题思路：想到的第一种方式就是在末尾直接插入数组前 k 个数字，然后截断前 k 个数字。但是空间复杂度明显不符合。
既然是要求空间复杂度为 O(1)，那么可以预想到解题是需要在原数组上面操作；
尝试一：可以按照示例中的解释步骤实现空间复杂度为 O(1) 的算法。实践发现超出时间限制。
尝试二：找到每个数字旋转后的位置。因为可能会出现旋转超过一圈，所以第 i 个位置旋转 k 次后的位置为 (i + k) % n; 这样的话可以做到每个元素被遍历一次，也是在原数组上面操作。
不过需要注意的是，这样的遍历要以什么为标志为结束？所以需要利用一个值来计数已经遍历的个数，当遍历的个数等于数组大小时，表面遍历完成。
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
int count = 0;
for(int start = 0; ; ++start) {
int pos = start;
int value = nums[start];
while(1) {
int next = (pos + k) % n;
int temp = nums[next];
nums[next] = value;
value = temp;
pos = next;
count++;
if(pos == start) break;
}
if(count == n) break;
}
}
};
颠倒二进制位
颠倒给定的 32 位无符号整数的二进制位。
提示：
- 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
- 在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的 示例 2 中，输入表示有符号整数 -3，输出表示有符号整数 -1073741825。
进阶:
- 如果多次调用这个函数，你将如何优化你的算法？
示例 1：
输入: 00000010100101000001111010011100
输出: 00111001011110000010100101000000
解释: 输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。
示例 2：
输入：11111111111111111111111111111101
输出：10111111111111111111111111111111
解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293，
因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111 。
示例 1：
输入：n = 00000010100101000001111010011100
输出：964176192 (00111001011110000010100101000000)
解释：输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。
示例 2：
输入：n = 11111111111111111111111111111101
输出：3221225471 (10111111111111111111111111111111)
解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293，
因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111 。
提示：
输入是一个长度为 32 的二进制字符串
| 解题思路：这道题的难点在于如何操作 uint32_t，对于二进制来说，常见的操作有：或( | )，与(&)，异或(^)，取反(~)，左移(«)，右移(»)。 |
解题方法可以是每次从 n 拿到最后一位，res 左移一位，然后放到 res 的末位，最后 n 右移一位。
但是这道题可以根据分治算法去解决，这道题其实可以类比于固定长度的字符串的翻转，那么利用分治算法。
恰好 32 是 2 的五次方，那么分治五次即可得到长度为 2 的字符串，然后将其翻转。
那么对于 32 的二进制字符串需要考虑的就是如何去实现，翻转本质是交换，那么就只需要拿到相应的位置然后交换即可得到翻转后的结果。
对于分治的最小长度 2 的操作，其实就是每两位交换一下。
比如 01101001，
- 先拿奇数位 01010101 得到 01000001， 然后再拿偶数位 00101000
- 然后奇数位和偶数位位置交换。即 (01000001 « 1) & (00101000 » 1) 得到 10010110
这样就完成长度为 2 翻转的结果，如果要得到全部的翻转结果，则还需要翻转长度为 4 的结果，最后翻转长度为 8 得到最终结果，其实这就是分治算法的思想。
class Solution {
public:
const uint32_t M1 = 0x55555555; // 01010101010101010101010101010101
const uint32_t M2 = 0x33333333; // 00110011001100110011001100110011
const uint32_t M4 = 0x0f0f0f0f; // 00001111000011110000111100001111
const uint32_t M8 = 0x00ff00ff; // 00000000111111110000000011111111
uint32_t reverseBits(uint32_t n) {
n = n >> 1 & M1 | (n & M1) << 1;
n = n >> 2 & M2 | (n & M2) << 2;
n = n >> 4 & M4 | (n & M4) << 4;
n = n >> 8 & M8 | (n & M8) << 8;
return n >> 16 | n << 16;
}
};
