Leetcode算法题701-800

701-710¶

704. 二分查找¶

class Solution {
public:
    int search(vector<int> &nums, int target) {
        int r = nums.size() - 1, l = 0, mid;
        while (l < r) {
            mid = l + r + 1 >> 1;
            if (nums[mid] <= target) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        if (nums[l] == target) return l;
        else return -1;
    }
};

¶

711-720¶

721-730¶

724. 寻找数组的中心下标¶

本题将题目抽象出来就是解题的代码。

class Solution {
public:
    int pivotIndex(vector<int> &nums) {
        int total=accumulate(nums.begin(),nums.end(),0);
        for(int i=0,s=0;i<nums.size();i++){
            if(s==total-nums[i]-s) return i;
            else s+=nums[i];
        }
        return -1;
    }
};

731-740¶

741-750¶

751-760¶

761-770¶

771-780¶

781-790¶

781. 森林中的兔子¶

这题的难点在于分析兔子的种类数量与同一种类中兔子的数量。因此分为两步计算：

假设有x只兔子说有y只兔子同色。

1. 计算兔子种类：
2. 计算同一种类兔子的数量：
3. 二者相乘就是本题答案

注意代码中公式的顺序，因为整数除法涉及小数舍去。

代码中通过实现。

下面证明 。

class Solution {
public:
    int numRabbits(vector<int>& answers) {
        unordered_map<int,int> cnt;
        for(auto itor : answers) cnt[itor]+=1;
        int res=0;
        for(auto [k,v]:cnt){
            res+=(v+k)/(k+1)*(k+1);
        }
        return res;
    }
};

785.判断二分图

class Solution {
public:
    vector<int> color;

    bool dfs(int index, int c, vector <vector<int>> &graph) {
        color[index] = c;
        for (auto i: graph[index]) {
            if (color[i] != -1) {
                if (color[i] == c) return false;
            } else if (!dfs(i, !c, graph)) {
                return false;
            }
        }
        return true;
    }

    bool isBipartite(vector <vector<int>> &graph) {
        color = vector<int>(graph.size(), -1);
        bool flag = true;
        for (int i = 0; i < graph.size(); ++i) {
            if (!~color[i]) {
                if (!dfs(i, 0, graph)) {
                    return false;
                }
            }
        }
        return true;
    }
};

791-800¶