Skip to main content

额外题目

（图论、查并集、模拟、位运算）​

841.钥匙和房间​

（深度优先搜索）

class Solution {
    vector<bool> visited;
    void deep_search(vector<vector<int>>& rooms ,int start)
    {
        if(visited[start]) return;
        visited[start] = true;
        for (int i = 0; i < rooms[start].size(); ++i) {
            deep_search(rooms ,rooms[start][i]);
        }
    }
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        visited.assign(rooms.size(), false);
        deep_search(rooms,0);
        return std::accumulate(visited.begin(), visited.end(),0) == visited.size();
    }
};

127. 单词接龙​

（广度优先搜索）

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> WordSet(wordList.begin(),wordList.end());
        if ( WordSet.find(endWord)==WordSet.end()) return 0;
        unordered_map<string,int> Setmap;
        Setmap[beginWord] = 1;
        queue<string> Que;
        Que.push(beginWord);
        while (!Que.empty())
        {
            int size = Que.size();
            while (size--)
            {
                string now = Que.front();
                Que.pop();
                //计算有多少个邻接节点,并把其加入队列
                for (int j = 0; j < now.size(); ++j) {
                    string temp = now;
                    for (char i = 'a'; i <= 'z'; ++i) {
                        temp[j] = i;
                        if (WordSet.find(temp)!=WordSet.end() && Setmap.find(temp) == Setmap.end())
                        {
                            Setmap[temp] = Setmap[now] + 1;
                            Que.push(temp);
                        }
                        if (temp == endWord) return Setmap[endWord];
                    }
                }

            }

        }
        return 0;
    }
};

684. 冗余连接​

题目说是无向图，返回一条可以删去的边，使得结果图是一个有着N个节点的树。

如果有多个答案，则返回二维数组中最后出现的边。

那么我们就可以从前向后遍历每一条边，边的两个节点如果不在同一个集合，就加入集合（即：同一个根节点）。

如果边的两个节点已经出现在同一个集合里，说明着边的两个节点已经连在一起了，如果再加入这条边一定就出现环了。

class Solution {
    const static int MAX_SIZE = 1005;
    int father[MAX_SIZE];
    //初始化并查集
    void init()
    {
        for (int i = 0; i < MAX_SIZE; ++i) {
            father[i] = i;
        }
    }
    //合并
    void unions(int x , int y)
    {
        int x_f = find(x);
        int y_f = find(y);
        if(x_f == y_f) return;
        father[x_f] = y_f;

    }

    //找到祖先+路径压缩
    int find(int x)
    {
        if (x == father[x]) return x;
        father[x] = find(father[x]);
        return father[x];
    }


public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        init();
        unions(edges[0][0] , edges[0][1]);
        for (int i = 1; i < edges.size(); ++i) {
            if (find(edges[i][0]) == find(edges[i][1])) return edges[i];
            unions(edges[i][0] , edges[i][1]);
        }
        return {};
    }
};

657. 机器人能否返回原点​

class Solution {
public:
    bool judgeCircle(string moves) {
        return (count(moves.begin(), moves.end(),'U')==count(moves.begin(), moves.end(),'D') &&
                count(moves.begin(), moves.end(),'L')==count(moves.begin(), moves.end(),'R'));
    }
};

31.下一个排列​

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        for (int i = nums.size()-1; i >=0 ; --i) {
            for (int j = nums.size()-1; j >i ; --j) {
                if (nums[j] > nums[i])
                {
                    //交换
                    int temp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = temp;
                    reverse(nums.begin()+i+1,nums.end());
                    return;
                }

            }
        }
        reverse(nums.begin(),nums.end());
    }
};

200. 岛屿数量​

class Solution {
    vector<vector<int>> choose;
    void select(vector<vector<char>>& grid,int k,int i ,int j)
    {
        if (choose[i][j] != 0 || grid[i][j] == '0') return;
        choose[i][j] = k;
        if (i > 0) select( grid, k, i -1, j);
        if (i < grid.size() -1) select( grid, k, i +1, j);
        if (j > 0) select( grid, k, i , j - 1);
        if (j  < grid[0].size() -1) select( grid, k, i , j + 1);
    }
public:
    int numIslands(vector<vector<char>>& grid) {
        int k = 1;
        choose.assign(grid.size(),vector<int>(grid[0].size(), 0));
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[0].size(); ++j) {
                if (grid[i][j] == '1' && choose[i][j] == 0) select( grid, k++, i , j);
            }
        }
        return k -1;
    }

};

463. 岛屿的周长​

class Solution {
    int calc(vector<vector<int>>& grid,int i ,int j)
    {
        int c = 0;
        if (i == 0 || grid[i-1][j] == 0) c++;
        if (i == grid.size() - 1 || grid[i+1][j] == 0) c++;
        if (j == 0 || grid[i][j-1] == 0) c++;
        if (j == grid[0].size() -1 || grid[i][j+1] == 0) c++;
        return c;
    }
public:
    int islandPerimeter(vector<vector<int>>& grid) {
        int row = grid.size() , col = grid[0].size();
        int count = 0;
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                if (grid[i][j] == 1)
                {
                    count += calc(grid,i,j);
                }
            }
        }
        return count;
    }
};

1356. 根据数字二进制下 1 的数目排序​

这种方法，只循环n的二进制中1的个数次，比方法一高效的多

class Solution {
public:
    static int cal_one_num(int n)
    {
        int count = 0;
        while(n)
        {
            n &= (n-1);
            count++;
        }
        return count;
    }
    static bool cmps(int a, int b)
    {
        int c = cal_one_num(a);
        int d = cal_one_num(b);
        if (c == d) return a < b;
        return c < d;
    }
    vector<int> sortByBits(vector<int>& arr) {

        std::sort(arr.begin(), arr.end(), cmps);
        return arr;
    }
};

前缀和与积分图​

303. 区域和检索 - 数组不可变​

class NumArray {
    vector<int> partial;
public:
    NumArray(vector<int>& nums):partial(nums) {
        //计算前缀和
        std::partial_sum(partial.begin(), partial.end(),partial.begin());
    }

    int sumRange(int left, int right) {
        if (left == 0) return partial[right];
        return partial[right] - partial[left - 1];
    }
};

304. 二维区域和检索 - 矩阵不可变​

class NumMatrix {
    vector<vector<int>> res;
public:
    NumMatrix(vector<vector<int>>& matrix){
        res= vector<vector<int>>(matrix.size() + 1, vector<int>(matrix[0].size() + 1, 0));
        for (int i = 1; i <= matrix.size(); ++i) {
            for (int j = 1; j <= matrix[0].size(); ++j) {
                res[i][j] = matrix[i - 1][j - 1] + res[i-1][j] + res[i][j-1] - res[i-1][j-1];
            }
        }

    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        return res[row2+1][col2+1] - res[row2+1][col1] -
                res[row1][col2+1] + res[row1][col1];
    }
};

560. 和为 K 的子数组​

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int res = 0, psum = 0;
        unordered_map<int,int> umap;
        umap[0] = 1;
        //记录相等前缀和的个数，若存在前缀和为psum - k说明有umap[psum - k]个连续
        for (int x:nums) {
            psum+=x;
            res += umap[psum - k];
            umap[psum]++;
        }
        return res;
    }
};

146. LRU 缓存（难-未完成）​

我们采用一个链表 list来储存信息的 key 和 value，链表的链接顺序即为最 近使用的新旧顺序，最新的信息在链表头节点。同时我们需要一个嵌套着链表的迭代器的 unordered_map 进行快速搜索，存迭代器的原因是方便调用链表的 splice 函数来直接更新查找成功（cash hit）时的信息，即把迭代器对应的节点移动为链表的头节 点。

list::splice实现list拼接的功能。将源list的内容部分或全部元素删除，拼插入到目的list。

函数有以下三种声明：

void list::splice( iterator pos, list rhs );
void list::splice( iterator pos, list rhs, iterator ix ); 
void list::splice( iterator pos, list rhs, iterator first, iterator last );

splice()把一个或一级元素从一个 list 移到另一个中去 它有三种形式

1、从positon开始，把一个 list 的全部元素搬移到另一个中去

2、从positon开始，把一个 list 中包含的一组元素搬移到另一个中去

3、从positon开始，把first 到 last 剪接到要操作的list对象中


class LRUCache{
    unordered_map<int, list<pair<int, int>>::iterator> hash;
    list<pair<int, int>> cache;
    int size;
public:
    LRUCache(int capacity):size(capacity) {}
    int get(int key) {
        auto it = hash.find(key);
        if (it == hash.end()) {
            return -1;
        }
        cache.splice(cache.begin(), cache, it->second);
        return it->second->second;
    }
    void put(int key, int value) {
        auto it = hash.find(key);
        if (it != hash.end()) {
            it->second->second = value;
            return cache.splice(cache.begin(), cache, it->second);
        }
        cache.insert(cache.begin(), make_pair(key, value));
        hash[key] = cache.begin();
        if (cache.size() > size) {
            hash.erase(cache.back().first);
            cache.pop_back();
        }
    }
};