LeetCode数据结构基础---2021/8/29（完结）

痛定思痛。 2022-09-09 04:44 127阅读 0赞

### 目录 ###

*  找到小镇的法官
 *  可以到达所有点的最少点数目
 *  钥匙和房间
 *  数组中的第K个最大元素
 *  前K个高频元素
 *  根据字符出现频率排序
 *  最接近原点的K个点

# 找到小镇的法官 #

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQ3lyaWxfS0k_size_20_color_FFFFFF_t_70_g_se_x_16]  
分析：  
  循环判断即可。  
代码：

class Solution { 
    public:
        int findJudge(int n, vector<vector<int>>& trust) { 
            for(int i = 1; i <= n; i++) { 
                int cnt = 0, flag = 0;
                for(vector<int>& x : trust) { 
                    if(x[0] == i) { 
                        flag = 1;
                        break;  //不满足条件1
                    }
                    if(x[1] == i) { 
                        cnt++;
                    }
                }
                if(cnt == n - 1 && flag == 0) { 
                    return i;
                }
            }
            return -1;
        }
    };

# 可以到达所有点的最少点数目 #

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQ3lyaWxfS0k_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
分析：  
  由于入度为0的结点只能从自身出发才能被访问到，所以集合中必须包含所有入度为0的结点。又由于是有向无环图，所以从所有入度为0的结点出发必然能访问到所有结点，所以答案就是入度为0的结点的集合。  
代码：

class Solution { 
    public:
        vector<int> findSmallestSetOfVertices(int n, vector<vector<int>>& edges) { 
            vector<int> res;
            vector<int> du(n);
            for(vector<int>& x : edges) { 
                du[x[1]]++;
            }
            for(int i = 0; i < n; i++) { 
                if(du[i] == 0) { 
                    res.push_back(i);
                }
            }
            return res;
        }
    };

# 钥匙和房间 #

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQ3lyaWxfS0k_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
方法一：  
  dfs：判断从0出发是否能到达所有结点。  
代码：

方法二：  
  bfs。  
代码：

class Solution { 
    public:
        vector<int> visited;
        int cnt = 0;
        void dfs(vector<vector<int>>& rooms, int x) { 
            cnt++;
            visited[x] = 1;
            for(int y : rooms[x]) { 
                if(!visited[y]) { 
                    dfs(rooms, y);
                }
            }
        }
        bool canVisitAllRooms(vector<vector<int>>& rooms) { 
            int n = rooms.size();
            visited.resize(n);
            queue<int> que;
            que.push(0);
            visited[0] = 1;
            while(!que.empty()) { 
                int t = que.front();
                cnt++;
                que.pop();
                for(int x : rooms[t]) { 
                    if(!visited[x]) { 
                        visited[x] = 1;
                        que.push(x);
                    }
                }
            }
            return cnt == n;
        }
    };

# 数组中的第K个最大元素 #

[数组中的第K个最大元素][K]

# 前K个高频元素 #

[前K个高频元素][K 1]

# 根据字符出现频率排序 #

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQ3lyaWxfS0k_size_20_color_FFFFFF_t_70_g_se_x_16 3]  
分析：  
  统计出每个字符出现的频率，然后排序再累加。  
代码：

class Solution { 
    public:
        static bool cmp(const pair<char, int>& x, const pair<char, int>& y) { 
            return x.second > y.second;
        }
        string frequencySort(string s) { 
            unordered_map<char, int> mp;
            for(char x : s) { 
                mp[x]++;
            }
            vector<pair<char, int>> temp(mp.begin(), mp.end());
            sort(temp.begin(), temp.end(), cmp);
            string res = "";
            for(auto& x : temp) { 
                for(int i = 0; i < x.second; i++) { 
                    res += x.first;
                }
            }
            return res;
        }
    };

# 最接近原点的K个点 #

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQ3lyaWxfS0k_size_20_color_FFFFFF_t_70_g_se_x_16 4]  
分析：  
  按到原点的距离对所有点进行排序，然后返回前k个。  
代码：

class Solution { 
    public:
        static bool cmp(const vector<int>& x, const vector<int>& y) { 
            return x[0] * x[0] + x[1] * x[1] < y[0] * y[0] + y[1] * y[1];
        }
        vector<vector<int>> kClosest(vector<vector<int>>& points, int k) { 
            sort(points.begin(), points.end(), cmp);
            points.resize(k);
            return points;
        }
    };

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQ3lyaWxfS0k_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/fe538ce76e0440698f47434576a2f3b8.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQ3lyaWxfS0k_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/e95b022c51964ad6849b2a0a65acc59f.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQ3lyaWxfS0k_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220829/cb13547d58c64d50a0a380ce823b4296.png
[K]: https://blog.csdn.net/Cyril_KI/article/details/119345922
[K 1]: https://blog.csdn.net/Cyril_KI/article/details/119377098
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQ3lyaWxfS0k_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220829/de3f98c2373a49e18dc46ac9a4f84a4b.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQ3lyaWxfS0k_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220829/d60c71dd40cb4066a9ee8d0e71aedf59.png