数组处理

找出数组中重复的数字

题目来源： acwing 13

题目

给定一个长度为n的整数数组nums，数组中所有的数字都在0 ~ n - 1的范围内。

数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。

请找出数组中任意一个重复的数字。

注意： 如果某些数字不在0 ~ n - 1的范围内，或数组中不包含重复数字，则返回-1；

样例

给定 nums = [2, 3, 5, 4, 2, 6, 7]。

返回 2 或 3。

代码实现 1

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        int n = nums.size();
        bool *tags = new bool[n];
        memset(tags, false, sizeof(bool) * n);
        for(int i = 0; i < n; i++) {
            if(nums[i] < 0) return -1;
        }
        for(int i = 0; i < n; i++) {
            if(nums[i] < 0) return -1;
            if(tags[nums[i]]) {
                return nums[i];
            } else {
                tags[nums[i]] = true;
            }
        }  
        return -1;
    }
};

代码实现2

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        int n = nums.size();
        for(auto x : nums) {
            if(x < 0 || x >= n) {
                return -1;
            }
        }
        for(int i = 0; i < n; i++) {
            while(i != nums[i] && nums[nums[i]] != nums[i]) {
                swap(nums[i], nums[nums[i]]);
            }
            if(i != nums[i] && nums[i] == nums[nums[i]]) {
                return nums[i];
            }
        }
        return -1;
    }
};

不修改数组找出重复的数字

题目来源： acwing 14

题目

给定一个长度为n + 1 的数组nums，数组中所有的数均在1~n的范围内，其中n ≥ 1.

请找出数组中任意一个重复的数，但不能修改输入的数组。

样例

给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。

返回2 或 3。

思考题： 如果只能使用O(1)的额外空间，该怎么做呢？

代码实现

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        int l = 1, r = nums.size() - 1;
        while(l < r) {
            int mid = l + r >> 1;
            int count = 0;
            for(auto x : nums) {
                count += x >= l && x <= mid;
            }
            if(count > mid - l + 1) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
};

机器人的运动范围

题目来源： acwing 24

题目内容

地上有一个m行和n列的方格，横纵坐标范围分别是 0 ~ m - 1 和 0 ~ n - 1。

一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格。

但是不能进入行坐标和列坐标的数位之和大于k的格子。

请问该机器人能够达到多少个格子？

样例1

输入：k = 7, m = 4, n = 5

输出： 20

样例2

输入：k = 18, m = 40, n = 40

输出：1484

解释：当k为18时，机器人能够进入方格（35， 37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。

注意

1
2
3

0 <= m <= 50
0 <= n <= 50
0 <= k <= 100

代码实现（BFS）

class Solution {
public:
    int get_sum(int number) {
        int ans = number % 10;
        while(number / 10) {
            number = number / 10;
            ans += number % 10;
        }
        return ans;
    }
    int movingCount(int threshold, int rows, int cols)
    {
        if(!rows || !cols) return 0;
        vector<vector<bool>> matrix(cols, vector<bool>(rows, false));
        queue<pair<int, int>> q;
        q.push({0, 0});
        int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};
        int count = 0;
        matrix[0][0] = true;
        while(!q.empty()) {
            pair<int, int> cur = q.front();
            q.pop();
            if((get_sum(cur.first) + get_sum(cur.second)) > threshold) continue;
            count++;
            
            for(int i = 0; i < 4; i++) {
                int x = dx[i] + cur.first, y = dy[i] + cur.second;
                if(x >= 0 && x < cols && y >= 0 && y < rows && !matrix[x][y]) {
                    q.push({x ,y});
                    matrix[x][y] = true;
                }
            }
        }
        return count;
    }
};