LeetCode笔记(Array:原地哈希)

189 - 299 - 41。

189. 旋转数组

LeetCode笔记(Array:原地哈希)

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. 猜数字游戏

LeetCode笔记(Array:原地哈希)
其实可以有更简单的想法,就是我们可以遍历一次很简单地就得到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. 缺失的第一个正数

LeetCode笔记(Array:原地哈希)
原地哈希,直接把每个元素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;
    }
};
上一篇:Python代码实现猜数字游戏


下一篇:C语言练习题~猜数字游戏