/*******************************************************************************
避免洪水泛滥
//leetcode-cn.com/problems/avoid-flood-in-the-city/solution/avoid-flood-in-the-city-by-ikaruga/
rains : 1 0 2 0 2 1
*******************************************************************************/
class Solution {
public:
vector<int> avoidFlood(vector<int> &rains) {
vector<int> ans(rains.size(), 1);
unordered_map<int, int> water; //记录每个湖泊上一次下雨的日期
set<int> zero;
for (int i = 0; i < rains.size(); i++) {
int r = rains[i];
if (r == 0) {
//将晴天的日期记录到zero中,遇到晴天时，先不用管抽哪个湖
zero.insert(i);
continue;
}
if (water.count(r) != 0) { //当下雨时，湖泊已经水满时，可以查询上次下雨的日期
auto it = zero.lower_bound(water[r]); //通过上次下雨的日期，查找对应的晴天日期
if (it == zero.end()) { //如果没有找到，则无法使用那天抽水，发生洪水
return {};
}
ans[*it] = r; // 如果在晴天*it找到了对应的下雨日期，则记录抽干的湖泊
zero.erase(it); //删除当前的晴天记录
}
// water记录每个湖泊上一次下雨的日期
water[r] = i; //更新当前湖的下雨日期
ans[i] = -1;
}
return ans;
}
};
/*******************************************************************************
并查集
*******************************************************************************/
void join(int p, int q){
int rootP = find(p);
int rootQ = find(q);
if(rootP == rootQ){
return;
}
//将两棵树合并为一棵
parent[rootP] = rootQ;
return;
}
int find(int p){
while(p != parent[p]){ //如果P的父亲指针指向不是自己，说明P不是根元素
//在find查询中嵌入一个路径压缩 此处不懂，参考这里https://blog.csdn.net/qq_19782019/article/details/78919990
parent[p] = parent[parent[p]];
//p元素不再选择原来的父亲节点，而是选择父亲节点的父亲节点作为自己的新的一个父亲节点
p = parent[p];
}
//经过while循环后，p = parent[p], 一定是一个根节点，且不能够再进行压缩
return p;
}
/*******************************************************************************
1319. 连通网络的操作次数
//leetcode-cn.com/problems/number-of-operations-to-make-network-connected/
两种方法：并查集 和 深度优先探索
*******************************************************************************/
/*并查集*/
class Solution {
public:
int* parent;
int find(int p){
while(p != parent[p]){
parent[p] = parent[parent[p]];
p = parent[p];
}
return p;
}
void join(int x, int y){
int rootX = find(x);
int rootY = find(y);
if(rootX == rootY){
return;
}
parent[rootX] = rootY;
return;
}
int makeConnected(int n, vector<vector<int>>& connections) {
if(connections.size()<n-1) //不满足线缆数量
return -1;
parent = new int[n]; //申请n个空间
for(int i =0;i<n;i++){
parent[i] = i; //初始化
}
for(int i =0;i<connections.size();i++){
join(connections[i][0],connections[i][1]); //连接
}
set<int> pars;
for(int i =0;i<n;i++){ //计算连通分量数
pars.insert(find(i)); //每个节点的根节点插入pars，每个键都是唯一的，可以插入或删除但不能更改
}
return pars.size()-1;
}
};
class Solution {
private:
vector<int> fa;
public:
int find(int x){
return x == fa[x] ? x : fa[x] = find(fa[x]); // 这种是未压缩路径
// return x == fa[x] ? x : x = find(fa[x]);
}
int makeConnected(int n, vector<vector<int>>& connections){
if(connections.size() < n-1){
return -1;
}
fa.resize(n); //初始化
iota(fa.begin(), fa.end(), 0);
int part = n; //初始化共有n个连通分量数
for(auto&& c : connections){ //连接
int p = find(c[0]), q = find(c[1]);
if(p != q){
--part;
fa[p] = q;
}
}
return part - 1;
}
};
/*
邻接矩阵深度优先探索算法
*/
class Solution{
private:
vector<vector<int>> edges;
vector<bool> used;
public:
void dfs(int u){
used[u] = true; //将已访问的定点标记true
for(int v : edges[u]){ //对于顶点u的其他相邻的节点，进行继续深度优先探索
if(!used[v]){
dfs(v);
}
}
}
int makeConnected(int n, vector<vector<int>> & connections){
if(connections.size() < n-1){
return -1;
}
edges.resize(n);
for(auto&& c: connections){ //组合无向图
edges[c[0]].push_back(c[1]);
edges[c[1]].push_back(c[0]);
}
used.resize(n);
int part = 0;
for(int i = 0; i < n; i++){ //遍历所有顶点，计算连通数量
if(!used[i]){
++part;
dfs(i);
}
}
return part-1;
}
};
/*邻接矩阵的广度优先探索*/
class Solution {
public:
int makeConnected(int n, vector<vector<int>>& connections) {
if (connections.size() < (n-1)) {
return -1;
}
//将相连接的组合成一个无向图
unordered_map<int, unordered_set<int>> link_map;
for (auto &conn : connections) {
link_map[conn[0]].emplace(conn[1]);
link_map[conn[1]].emplace(conn[0]);
}
vector<int> mark(n, 0);
int num = 0;
for (int i = 0; i < n; ++i) {
if (mark[i]) continue;
num++;
queue<int> q;
q.push(i);
while (!q.empty()) {
int index = q.front();
q.pop();
if (link_map.count(index) == 0) {
continue;
}
for (auto mi : link_map[index]) {
if (mark[mi]) continue;
q.push(mi);
mark[mi] = 1;
}
}
}
return num-1;
}
};
/*******************************************************************************
邻接矩阵：深度优先遍历，广度优先遍历
深度优先遍历：不断地沿着顶点的深度方向遍历；顶点的深度方向：它的邻接点方向。
用visited[i]表示顶点i的访问情况。
广度优先遍历：先访问当前顶点的所有邻接点；先访问顶点的邻接点先于后访问顶点的邻接点被访问
*******************************************************************************/
//访问标志数组
int visited[MAX] = {0};
void DFS(M G, int v){
visited[v] = 1;
}
/*******************************************************************************
朋友圈
//leetcode-cn.com/problems/friend-circles/
*******************************************************************************/
class Solution {
public:
vector<int> fa;
int find(int p){
while(p != fa[p]){
fa[p] = fa[fa[p]];
p = fa[p];
}
return p;
}
void Union(int p, int q){
int rootP = find(p);
int rootQ = find(q);
if(rootP != rootQ){
fa[rootP] = rootQ;
}
return;
}
int findCircleNum(vector<vector<int>>& M) {
int n = M.size();
fa.resize(n); //申请n个空间
for(int i = 0; i < n; i++){ //初始化
fa[i] = i;
}
//连接
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
if(M[i][j]==1 && i!=j)
Union(fa[i], fa[j]);
}
}
//计算有多少个连通分量数
int count = 0;
for(int i = 0; i < n; i++){
if(fa[i] == i){
++count;
}
}
return count;
//计算有多少个连通分量数
// set<int> pars;
// for(int i =0;i<n;i++){
// pars.insert(find(i)); //每个节点的根节点插入pars，每个键都是唯一的，可以插入或删除但不能更改
// }
// return pars.size();
}
};
/*深度优先探索*/
//把矩阵 M 看成是图的邻接矩阵，则问题转化为求图的连通块数
class Solution {
private:
vector<bool> vis;
public:
int findCircleNum(vector<vector<int>>& M){
int n = M.size();
vis.resize(n);
int ans = 0;
for(int i = 0; i < n; i++){
if(vis[i] == false){
dfs(M, i);
ans++;
}
}
return ans;
}
void dfs(vector<vector<int>> M, int i){
int n = M.size();
for(int j = 0; j < n; j++){
if(M[i][j] == 1 && vis[j] == false){
vis[j] = true;
dfs(M, j);
}
}
}
};
/*广度优先探索*/
class Solution {
public:
int findCircleNum(vector<vector<int>>& M){
int n = M.size();
vector<int> visit(n, 0);
int count = 0, tmp;
queue<int> que;
for(int i = 0; i < n; i++){
if(!visit[i]){
count++;
que.push(i);
while(!que.empty()){
tmp = que.front();
que.pop();
visit[tmp] = 1;
for(int j = 0; j < n; j++){
if(M[tmp][j] == 1 && !visit[j]){
que.push(j);
}
}
}
}
}
return count;
}
};
/*******************************************************************************
820. 单词的压缩编码
//leetcode-cn.com/problems/short-encoding-of-words/
*******************************************************************************/
class Solution {
public:
int minimumLengthEncoding(vector<string>& words) {
//unordered_set<string> good(words.begin(), words.end());
unordered_set<string> origin;
for(auto& word : words){
origin.insert(word);
}
for (const string& word: words) {
for (int k = 1; k < word.size(); ++k) {
origin.erase(word.substr(k));
}
}
int ans = 0;
for (const string& word: origin) {
ans += word.size() + 1;
}
return ans;
}
};
/*******************************************************************************
LCP 08. 剧情触发时间
//leetcode-cn.com/problems/ju-qing-hong-fa-shi-jian/
*******************************************************************************/
#define col 3
class Solution {
public:
vector<int> getTriggerTime(vector<vector<int>>& increase, vector<vector<int>>& requirements) {
vector<int> res;
int row = increase.size();
cout << row << endl;
vector<vector<int>> sum(row+1, vector<int>(col,0));
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
sum[i+1][j] = sum[i][j] + increase[i][j];
}
}
for(auto v : requirements){
int l = 0, r = row;
while(l < r){
int m = (l + r) / 2;
if(sum[m][0] >= v[0] && sum[m][1] >= v[1] && sum[m][2] >= v[2]){
r = m;
} else {
l = m + 1;
}
}
if(sum[l][0] >= v[0] && sum[l][1] >= v[1] && sum[l][2] >= v[2]){
res.push_back(l);
} else {
res.push_back(-1);
}
}
return res;
}
};
class Solution{
public:
vector<int> getTriggerTime(vector<vector<int>>& increase, vectoro<vector<int>>& requirements){
vector<int> C(increase.size()+1, 0);
vector<int> R(increase.size()+1, 0);
vector<int> H(increase.size()+1, 0);
for(int i = 0; i < inrease.size(); ++i){
C[i+1] = C[i] + increase[i][0];
R[i+1] = R[i] + increase[i][1];
H[i+1] = H[i] + increase[i][2];
}
vector<int> res;
int maxLen = C.size();
for(int i = 0; i < requirements.size(); i++){
int lc = lower_bound(C.begin(), C.end(), requirements[i][0]) - C.begin();
int lr = lower_bound(R.begin(), R.end(), requirements[i][1]) - R.begin();
int lh = lower_bound(H.begin(), H.end(), requirements[i][2]) - H.begin();
if(lc == maxLen || lr == maxLen || lh == maxLen){
res.push_back(-1);
} else {
res.push_back(max(max(lc,lr),lh));
}
}
return res;
}
};
/*******************************************************************************
76. 最小覆盖子串
//leetcode-cn.com/problems/minimum-window-substring/
*******************************************************************************/
class Solution {
public:
string minWindow(string s, string t) {
unordered_map<char, int> need;
unordered_map<char, int> windows;
int len = s.size() + 1;
int start = 0;
//先计算need
for(auto w : t){
++need[w];
}
int left = 0, right = 0, valid = 0; //初始化
while(right < s.size()){
char chr = s[right];
++right;
if(need.count(chr)){
++windows[chr];
if(windows[chr] == need[chr]){
valid++;
}
}
while(valid == need.size()){
if(right - left < len){
start = left;
len = right - left;
}
char chl = s[left];
++left;
if(need.count(chl)){
if(windows[chl] == need[chl]){
--valid;
}
--windows[chl];
}
}
}
return len == s.size()+1 ? "" : s.substr(start, len);
}
};
/*******************************************************************************
438. 找到字符串中所有字母异位词
//leetcode-cn.com/problems/find-all-anagrams-in-a-string/
*******************************************************************************/
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
unordered_map<char, int> window;
unordered_map<char, int> need;
for(auto c : p){
need[c]++;
}
int left = 0, right = 0, valid = 0;
vector<int> res;
while(right < s.size()){
char c = s[right];
right++;
if(need.count(c)){
window[c]++;
if(window[c] == need[c]){
valid++;
}
}
//判断左侧端口是否要收缩
while(right - left >= p.size()){
if(valid == need.size()){
res.push_back(left);
}
char d = s[left];
left++;
if(need.count(d)){
if(window[d] == need[d]){
valid--;
}
window[d]--;
}
}
}
return res;
}
};
/*******************************************************************************
567. 字符串的排列
//leetcode-cn.com/problems/permutation-in-string/
*******************************************************************************/
class Solution {
public:
bool checkInclusion(string s1, string s2) {
unordered_map<char, int> need, window;
for(auto c : s1){
need[c]++;
}
int left = 0, right = 0;
int valid = 0;
while(right < s2.size()){
char c = s2[right];
right++;
if(need.count(c)){
window[c]++;
if(window[c] == need[c]){
valid++;
}
}
while(right - left >= s1.size()){
if(valid == need.size()){
return true;
}
char d = s2[left];
left++;
if(need.count(d)){
if(window[d] == need[d]){
valid--;
}
window[d]--;
}
}
}
return false;
}
};
/*******************************************************************************
3. 无重复字符的最长子串
//leetcode-cn.com/problems/longest-substring-without-repeating-characters/
*******************************************************************************/
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> window;
int left = 0, right = 0;
int res = 0;
while(right < s.size()){
char c = s[right];
right++;
//进行窗口数据更新
window[c]++;
//判断窗口是否要收缩
while(window[c] > 1){
char d = s[left];
left++;
window[d]--;
}
res = max(res, right-left);
}
return res;
}
};
/*******************************************************************************
II. 左旋转字符串
//leetcode-cn.com/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/
*******************************************************************************/
class Solution {
public:
string reverseLeftWords(string s, int n) {
reverse(s.begin(), s.begin()+n);
reverse(s.begin()+n, s.end());
reverse(s.begin(), s.end());
return s;
}
};
/*******************************************************************************
N皇后
//leetcode-cn.com/problems/n-queens/
*******************************************************************************/
class Solution {
public:
vector<vector<string>> res;
vector<vector<string>> solveNQueens(int n) {
vector<string> board(n, string(n, '.'));
backtrack(board, 0);
return res;
}
void backtrack(vector<string>& board, int row){
//触发条件
if(row == board.size()){
res.push_back(board);
return;
}
int n = board[row].size();
for(int col = 0; col < n; col++){
if(!isValid(board ,row, col)){
continue;
}
//做选择
board[row][col] = 'Q';
// 进行下一步策略
backtrack(board, row+1);
//撤回选择
board[row][col] = '.';
}
}
bool isValid(vector<string>& board, int row, int col){
int n = board.size();
//检查列是否有皇后冲突
for(int i = 0; i < n; i++){
if(board[i][col] == 'Q'){
return false;
}
}
//检查右上方是否有皇后互相冲突
for(int i = row-1, j = col + 1; i>=0 && j < n; i--, j++){
if(board[i][j] == 'Q'){
return false;
}
}
//检查左上方是否有皇后互相冲突
for(int i = row-1, j = col - 1; i>=0 && j >= 0; i--, j--){
if(board[i][j] == 'Q'){
return false;
}
}
return true;
}
};
/*******************************************************************************
980. 不同路径 III
//leetcode-cn.com/problems/unique-paths-iii/
*******************************************************************************/
class Solution {
public:
int uniquePathsIII(vector<vector<int>>& grid) {
int startX = 0, startY = 0, stepNum = 1;
//遍历获取起始位置和统计总步数
for(int i = 0; i < grid.size(); i++){
for(int j = 0; j < grid[0].size(); j++){
if(grid[i][j] == 1){
startX = j;
startY = i;
continue;
}
if(grid[i][j] == 0){
stepNum++;
}
}
}
return dfs(startX, startY, stepNum, grid);
}
int dfs(int x, int y, int stepSur, vector<vector<int>>& grid){
if(x < 0 || x >= grid[0].size() || y < 0 || y >= grid.size() || grid[y][x] == -1){
return 0;
}
if (grid[y][x] == 2) return stepSur == 0 ? 1 : 0;
grid[y][x] = -1;
int res = 0;
res += dfs(x-1, y, stepSur -1 ,grid);
res += dfs(x + 1, y, stepSur - 1, grid);
res += dfs(x, y - 1, stepSur - 1, grid);
res += dfs(x, y + 1, stepSur - 1, grid);
grid[y][x] = 0;
return res;
}
};
/*******************************************************************************
833. 字符串中的查找与替换
//leetcode-cn.com/problems/find-and-replace-in-string/
*******************************************************************************/
class Solution {
public:
string findReplaceString(string S, vector<int>& indexes, vector<string>& sources, vector<string>& targets) {
int n = S.size();
vector<string> vec(n, "");
string res = "";
for (int i = 0; i < S.size(); ++i) vec[i] += S[i];
for (int i = 0; i < indexes.size(); ++i) {
int size = sources[i].size();
if (S.substr(indexes[i], size) == sources[i]) {
vec[indexes[i]] = targets[i];
for (int j = indexes[i] + 1; j < indexes[i] + size; ++j)
vec[j] = "";
}
}
for (auto str : vec) {
res += str;
}
return res;
}
};
/*******************************************************************************
84. 柱状图中最大的矩形
//leetcode-cn.com/problems/largest-rectangle-in-histogram/
*******************************************************************************/
class Solution {
public:
int largestRectangleArea(vector<int>& heights)
{
int ans = 0;
vector<int> st;
heights.insert(heights.begin(), 0);
heights.push_back(0);
for (int i = 0; i < heights.size(); i++)
{
while (!st.empty() && heights[st.back()] > heights[i])
{
int cur = st.back();
st.pop_back();
int left = st.back() + 1;
int right = i - 1;
ans = max(ans, (right - left + 1) * heights[cur]);
}
st.push_back(i);
}
return ans;
}
};
class Solution {
public:
int largestRectangleArea(vector<int>& heights){
int res = 0;
stack<int> tack;
heights.insert(heights.begin(), 0);
heights.push_back(0);
for(int i = 0; i < heights.size(); i++){
while(!tack.empty() && heights[tack.top()] > heights[i]){
int cur = tack.top();
tack.pop();
int left = tack.top() + 1;
int right = i - 1;
//heights[cur] 是 离heights[i] 最远的那个且大于heights[i]，right-left 是递增的宽度
res = max(res, (right - left + 1) * heights[cur]);
}
tack.push(i);
}
return res;
}
};
/*******************************************************************************
735. 行星碰撞
//leetcode-cn.com/problems/asteroid-collision/
*******************************************************************************/
class Solution {
public:
vector<int> asteroidCollision(vector<int>& asteroids) {
vector<int> res;
for(auto v : asteroids){
bool flag = true;
while(!res.empty() && v < 0 && res.back() > 0){
int sum = res.back() + v;
if(sum <= 0){
res.pop_back();
}
if(sum >= 0) {
flag = false;
break;
}
}
if(flag){
res.push_back(v);
}
}
return res;
}
};
/*******************************************************************************
2. 两数相加
//leetcode-cn.com/problems/add-two-numbers/
*******************************************************************************/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* head = nullptr;
ListNode* tail = nullptr;
int carry = 0;
if(l1 == nullptr){
return l2;
}
if(l2 == nullptr){
return l1;
}
while(l1 || l2){
int n1 = l1 ? l1->val : 0;
int n2 = l2 ? l2->val : 0;
int sum = n1 + n2 + carry;
if(!head){
head = tail = new ListNode(sum % 10);
} else {
tail->next = new ListNode(sum % 10);
tail = tail->next;
}
carry = sum / 10;
if(l1){
l1 = l1->next;
}
if(l2){
l2 = l2->next;
}
}
if(carry > 0){
tail->next = new ListNode(carry);
}
return head;
}
};
/*******************************************************************************
15. 三数之和---左右指针
//leetcode-cn.com/problems/3sum/
*******************************************************************************/
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(), nums.end());
int target;
for(int i = 0; i < nums.size(); i++){
if(i > 0 && nums[i] == nums[i-1]){
continue;
}
if((target = nums[i]) > 0){
break;
}
int l = i + 1;
int r = nums.size()-1;
while(l < r){
if(nums[l] + target + nums[r] < 0){
++l;
} else if(nums[l] + target + nums[r] > 0){
--r;
} else {
res.push_back({nums[l], target, nums[r]});
++l;
--r;
while(l < r && nums[l] == nums[l-1]){
l++;
}
while(l < r && nums[r] == nums[r+1]){
r--;
}
}
}
}
return res;
}
};
/*******************************************************************************
面试题 08.12. 八皇后---回溯法
//leetcode-cn.com/problems/eight-queens-lcci/
*******************************************************************************/
class Solution1 {
public:
vector<vector<string>> res;
vector<vector<string>> solveNQueens(int n) {
vector<string> board(n, string(n, '.'));
backtrack(board ,0);
return res;
}
void backtrack(vector<string>& board, int row){
if(row == board.size()){
res.push_back(board);
return;
}
int n = board[row].size();
for(int col = 0; col < n; col++){
if(!isValid(board, row, col)){
continue;
}
board[row][col] = 'Q';
backtrack(board, row+1);
board[row][col] = '.';
}
}
bool isValid(vector<string>& board, int row, int col){
int n = board.size();
//检查列是否有冲突
for(int i = 0; i < n; i++){
if(board[i][col] == 'Q'){
return false;
}
}
//检查右上方对角线
for(int i = row-1, j= col+1; i >= 0 && j < n; i--, j++){
if(board[i][j] == 'Q'){
return false;
}
}
//检查左上方对角线
for(int i = row-1, j = col-1; i >= 0 && j >= 0; i--, j--){
if(board[i][j] == 'Q'){
return false;
}
}
return true;
}
};
/*******************************************************************************
980. 不同路径 III---回溯法
//leetcode-cn.com/problems/unique-paths-iii/
*******************************************************************************/
class Solution3{
public:
int uniquePathsIII(vector<vector<int>>& grid){
int res = 0;
int startX = 0, startY = 0;
int step = 0;
for(int i = 0; i < grid.size(); i++){
for(int j = 0; j < grid[0].size(); j++){
if(grid[i][j] == 1){
startX = i;
startY = j;
continue;
}
if(grid[i][j] == 0){
step++;
}
}
}
//step + 1 针对step != 0 时，则直接返回res = 0
trackBack(grid, startX, startY, step+1, res);
return res;
}
void trackBack(vector<vector<int>>& grid, int startX, int startY, int step, int &res){
if(startX < 0 || startX >= grid.size() || startY < 0 || startY >= grid[startX].size() || grid[startX][startY] == -1){
return;
}
if(grid[startX][startY] == 2){
if(step == 0){
res++;
}
return;
}
grid[startX][startY] = -1;
trackBack(grid, startX-1, startY, step-1, res);
trackBack(grid, startX+1, startY, step-1, res);
trackBack(grid, startX, startY-1, step-1, res);
trackBack(grid, startX, startY+1, step-1, res);
grid[startX][startY] = 0;
}
};
