力扣习题笔记

781. 森林中的兔子

781. 森林中的兔子 - 力扣（LeetCode）

 代码

从数字相同，到 采用映射的存储结构，如：unordered_map<int,int>

class Solution {
public:
    int numRabbits(vector<int>& answers) {
        //两只相同颜色的兔子，看到其他相同颜色兔子数是相同的，相反，不同。
        unordered_map<int,int> count;
        for(int y : answers) {
            ++ count[y];
        }
        int ans = 0;
        for(auto &[y,x] : count) {
            ans += (x+y)/(y+1)*(y+1);
            // y+1就是回答y只其他相同颜色，加自身
            // x/y 的向上取整： (x+ y-1)/y  
            // x/(y+1) : (x + y)/(y+1)
        }
        return ans;
    }
};

868. 二进制间距

 代码

class Solution {
public:
    int binaryGap(int n) {
        int last = -1, ans = 0;
        for(int i = 0; n; i ++) {
            if(n&1) {//奇数
                if(last!=-1) { // 为了防止只有一个1
                    ans = max(ans, i - last);
                }
                last = i;
           }
            n >>= 1;
        }
        return ans;
    }
};

994. 腐烂的橘子

994. 腐烂的橘子 - 力扣（LeetCode）

代码

class Solution {
    int cnt; // 记录新鲜橘子数，为了判断是否还有新鲜橘子
    int dis[10][10]; // 标记时间，刚开始时间是-1，腐烂橘子时间标记为0，开始的意思
    int x[4] = {0,1,0,-1};
    int y[4] = {1,0,-1,0};
public:
    int orangesRotting(vector<vector<int>>& grid) {
        queue<pair<int,int>> q;
        memset(dis,-1,sizeof(dis));
        // ans 记录时间 ： 答案
        int n = grid.size(), m = grid[0].size(), ans = 0;
        for(int i = 0; i < n; i ++) {
            for(int j = 0; j < m; j ++) {
                if(grid[i][j] == 2) {  // 腐烂橘子
                    q.emplace(i,j); // 入队
                    dis[i][j] = 0; //第0分钟，初始腐烂橘子
                }
                else if(grid[i][j] == 1) { //新鲜橘子
                    cnt += 1;
                }
            }
        }

        while(!q.empty()) {
            auto [r,c] = q.front();
            q.pop();
            
            for(int i = 0 ; i < 4; i ++) {
                int tx = r + x[i], ty = c + y[i];
                //-1取反是0 : -1补码为全1
                //grid【tx】【ty】 为0时，代表没橘子
                //dis为-1 时 ： 代表不是腐烂的 ： 没橘子或者新鲜橘子
                //-1取反为0，不跳过，因为新鲜或者没橘子
                // 没橘子跳过， 腐烂橘子跳过， 只要新鲜橘子
                if(tx<0||tx>=n||ty<0||ty>=m||~dis[tx][ty]||!grid[tx][ty]) continue;

                dis[tx][ty] = dis[r][c] + 1; // 时间＋1
                q.emplace(tx, ty);
                // 新鲜橘子数更新， 答案更新（时间递推）
                cnt -= 1;
                ans = dis[tx][ty];
                if(!cnt) break; //没有新鲜橘子
                
            }
        }

        return cnt ? -1 : ans;
    }
};