189 - 299 - 41。
189. 旋转数组
class Solution {
public:
void rotate(vector<int>& nums, int k) {
if(nums.empty() || !(k % nums.size())) return ;
k = k % nums.size();
reverse(nums.begin(), nums.end());
reverse(nums.begin(), nums.begin()+k);
reverse(nums.begin()+k, nums.end());
return ;
}
};
299. 猜数字游戏
其实可以有更简单的想法,就是我们可以遍历一次很简单地就得到A(数字相同且位置相同),然后通过计算所有数字相同的情况减去A,就得到了数字相同但位置不同的B,这种思考过程更有逻辑,自己的做法有点混乱
(参考 windliang)
// 20.08
// 20.26
class Solution {
public:
string getHint(string secret, string guess) {
if(secret.empty() || guess.empty()) return "";
int a, b; a = b = 0;
vector<int> vec(350, 0);
for(int i = 0; i < guess.size(); i++) {
if(guess[i] == secret[i]) {
guess[i] = 'a';
a++;
}
else vec[secret[i]]++;
}
for(int i = 0; i < guess.size(); i++) {
if(vec[guess[i]]) {
if(guess[i] == secret[i]) {
vec[guess[i]]--;
a++;
} else {
vec[guess[i]]--;
b++;
}
}
}
return to_string(a) + "A" + to_string(b) + "B";
}
};
41. 缺失的第一个正数
原地哈希,直接把每个元素nums[i],排到数组中正确的位置nums[nums[i]-1]
// 20.45
// 21.10
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
if(nums.empty()) return 1;
int min, max;
for(int i = 0; i < nums.size(); i++) {
if(nums[i] > 0 && nums[i] <= nums.size() && i != nums[i] - 1 && nums[nums[i]-1] != nums[i])
swap(nums[i], nums[nums[i--] - 1]);
}
for(int i = 0; i < nums.size(); i++) {
if(i+1 != nums[i]) return i+1;
}
return nums.size()+1;
}
};