leetcode解题思路分析（八十五）744 - 750 题

太过爱你忘了你带给我的痛 2022-08-31 11:27 115阅读 0赞

1.  寻找比目标字母大的最小字母  
    给你一个排序后的字符列表 letters ，列表中只包含小写英文字母。另给出一个目标字母 target，请你寻找在这一有序列表里比目标字母大的最小字母。

**直接暴力搜索可以，二分查找亦可以**

class Solution { 
    public:
        char nextGreatestLetter(vector<char>& letters, char target) 
        { 
            int nLeft = 0, nRight = letters.size() - 1;
    
            if (target >= letters[nRight] ||
                target < letters[0]
            )
            { 
                return letters[0];
            }
    
            while (nLeft < nRight)
            { 
                int nMid = nLeft + (nRight - nLeft) / 2;          
                if (letters[nMid] <= target)
                { 
                    nLeft = nMid + 1;
                }
                else
                { 
                    nRight = nMid;
                }
            }
            
            return letters[nRight];
        }
    };

1.  前缀和后缀搜索  
    设计一个包含一些单词的特殊词典，并能够通过前缀和后缀来检索单词。

class Trie
    { 
    public:
        bool isWord;
        int weight;
        unordered_map<char, Trie*> child;
    
        Trie ()
        { 
            this->isWord = false;
            this->weight = -1;
        }
    
        void insert(string word)
        { 
            Trie * rt = this;
            for (char c: word)
            { 
                if (rt->child.count(c) == 0)
                    rt->child[c] = new Trie();
                rt = rt->child[c];
            }
            rt->isWord = true;
        }
    
        bool search(string word)
        { 
            Trie* rt = this;
            for (char c: word)
            { 
                if (rt->child.count(c) == 0)
                    return false;
                rt = rt->child[c];
            }
            return rt->isWord == true;
        }
    
        bool startsWith(string word)
        { 
            Trie* rt = this;
            for (char c: word)
            { 
                if (rt->child.count(c) == 0)
                    return false;
                rt = rt->child[c];
            }
            return true;
        }
    };
    
    
    class WordFilter 
    { 
    public:
        Trie * root;
    
        WordFilter(vector<string>& words) 
        { 
            root = new Trie();
            for (int weight = 0; weight < words.size(); weight ++)
            { 
                string word = words[weight];                //apple
                string tmp = word + '#' + word;             //apple#apple
                for (int i = 0; i < word.size() + 1; i ++)
                { 
                    Trie* cur = root;
                    for (int j = i; j < tmp.size(); j ++)   //如ple#apple
                    { 
                        if (cur->child.count(tmp[j]) == 0)
                            cur->child[tmp[j]] = new Trie();
                        cur = cur->child[tmp[j]];
                        cur->weight = weight;
                    }
                }
            }
        }
        
        int f(string prefix, string suffix) 
        { 
            Trie* rt = root;
            string tmp = suffix + '#' + prefix;
            for (char c: tmp)
            { 
                if (rt->child.count(c) == 0)
                    return -1;
                rt = rt->child[c];
            }
            return rt->weight;
        }
    };

1.  使用最小花费爬楼梯  
    数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost\[i\]（下标从 0 开始）。每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。

**动态规划**

class Solution { 
    public:
        int minCostClimbingStairs(vector<int>& cost) { 
            int n = cost.size();
            int prev = 0, curr = 0;
            for (int i = 2; i <= n; i++) { 
                int next = min(curr + cost[i - 1], prev + cost[i - 2]);
                prev = curr;
                curr = next;
            }
            return curr;
        }
    };

1.  至少是其他数字两倍的最大数  
    给你一个整数数组 nums ，其中总是存在 唯一的 一个最大整数 。请你找出数组中的最大元素并检查它是否 至少是数组中每个其他数字的两倍 。如果是，则返回 最大元素的下标 ，否则返回 -1 。

**遍历即可**

class Solution { 
    public:
        int dominantIndex(vector<int>& nums) 
        { 
            int maxNum = INT_MIN, secondMaxNum = INT_MIN, ret = 0;
            for (int i = 0; i < nums.size(); i++)
            { 
                if (nums[i] > secondMaxNum)
                { 
                    if (nums[i] > maxNum)
                    { 
                        secondMaxNum = maxNum;
                        maxNum = nums[i];
                        ret = i;
                    }
                    else
                    { 
                        secondMaxNum = nums[i];
                    }
                }
            }
    
            if (maxNum / 2 < secondMaxNum)
            { 
                ret = -1;
            }
    
            return ret;
        }
    };

1.  最短补全词  
    给定一个字符串牌照 licensePlate 和一个字符串数组 words ，请你找出并返回 words 中的 最短补全词 。

**直接遍历计数即可**

class Solution { 
    public:
        string shortestCompletingWord(string licensePlate, vector<string>& words) { 
            string licenseChars = "";
            for (const auto& ch : licensePlate) { 
                if (isalpha(ch)) { 
                    licenseChars += tolower(ch);
                }
            }
    
            vector<int> licenceCharFreq(128, 0);
            for (const auto& ch : licenseChars) { 
                licenceCharFreq[ch]++;
            }
    
            int minLen = INT_MAX;
            string res;
            for (const auto& word : words) { 
                vector<int> wordCharFreq(128, 0);
                for (const auto& ch : word) { 
                    wordCharFreq[ch]++;
                }
    
                bool isValidWord = true;
                for (char ch = 'a'; ch <= 'z'; ch++) { 
                    if (licenceCharFreq[ch] > wordCharFreq[ch]) { 
                        isValidWord = false;
                        break;
                    }
                }
    
                if (isValidWord) { 
                    if (word.size() < minLen) { 
                        minLen = word.size();
                        res = word;
                    }
                }
            }
    
            return res;
        }
    };

1.  隔离病毒  
    病毒扩散得很快，现在你的任务是尽可能地通过安装防火墙来隔离病毒。假设世界由二维矩阵组成，0 表示该区域未感染病毒，而 1 表示该区域已感染病毒。可以在任意 2 个四方向相邻单元之间的共享边界上安装一个防火墙（并且只有一个防火墙）。每天晚上，病毒会从被感染区域向相邻未感染区域扩散，除非被防火墙隔离。现由于资源有限，每天你只能安装一系列防火墙来隔离其中一个被病毒感染的区域（一个区域或连续的一片区域），且该感染区域对未感染区域的威胁最大且保证唯一。你需要努力使得最后有部分区域不被病毒感染，如果可以成功，那么返回需要使用的防火墙个数; 如果无法实现，则返回在世界被病毒全部感染时已安装的防火墙个数。

**思路  
每次去遍历病毒区域找到最多会干染病毒去隔离，那么这里需要使用  
1.优先级队列去排序，大顶堆  
2.数据结构Area去保存"“已经被感染” dead（现在是1） 和 ”即将被感染“ toDead（和1紧挨着的0）: 这个用一个数组即可  
3.对于已隔离的area里 dead设置为-1来标记 （更新grid来避免后续处理）  
如何去找每个区域  
深度优先：使用一个visited去避免循环遍历， 遍历有四个方向依次去扩展  
找到当前最多的感染的area  
将隔离的area里所有设置为已经处理-1  
不隔离的区域，则需要把所有toDead都从0设置为1  
循环直到所有区域都处理完毕才结束**

/* */
    
    class Solution { 
    private:
        struct Area
        { 
            unordered_set<int> dead;
            unordered_set<int> toDead;
            // 设置障碍的数量
            int cnt = 0;
        };
    
        // 数组的行数和列数
        int rows;
        int cols;
        bool** visited;
    
        // 遍历四个方向，写到一个数组里了
        int dires[5] = { 0, 1, 0, -1, 0};
    
        // 基于深度优先的找没处理病毒区域（grid[x][y]==1）
        void dfs(const vector<vector<int>>& grid, Area& area, int x, int y)
        { 
            if (grid[x][y] == 0)
            { 
                ++area.cnt;
                area.toDead.insert(x*50+y);
            }
            else
            { 
                // 其实这里只有1的情况，-1已经隔离的病毒在下面会过滤
                area.dead.insert(x*50+y);
                visited[x][y] = true;
                // 四个方向去查找1
                for (int k = 0; k < 4; ++k)
                { 
                    int nx = x + dires[k];
                    int ny = y + dires[k+1];
                    // 有效范围； 没有遍历； 且没被隔离
                    if (nx >= 0 && nx < rows && ny >=0 && ny < cols && !visited[nx][ny] && grid[nx][ny] != -1)
                    { 
                        dfs(grid, area, nx, ny);
                    }
                }
            }
        }
    
    public:
        int containVirus(vector<vector<int>>& grid) { 
            rows = grid.size();
            cols = grid[0].size(); 
            int res = 0;
    
            // visisted来避免循环遍历
            visited = new bool*[rows];
            for (int i = 0; i < rows; ++i)
            { 
                visited[i] = new bool[cols];
                memset(visited[i], 0, sizeof(bool) * cols);
            }
    
            while (true)
            { 
                for (int i = 0; i < rows; ++i)
                { 
                    memset(visited[i], 0, sizeof(bool) * cols);
                }
                // 用一个简单数组记录最大值来模拟优先队列
                vector<Area> q;
                int maxIndex = 0;
    
                // 遍历每个点去dfs找区域
                for (int i = 0; i < rows; ++i)
                { 
                    for (int j = 0; j < cols; ++j)
                    { 
                        // 只有没遍历，而且为没隔离的病毒区域才考虑
                        if (!visited[i][j] && grid[i][j] == 1)
                        { 
                            Area area;
                            dfs(grid, area, i, j);
                            q.emplace_back(area);
                            if (area.toDead.size() > q[maxIndex].toDead.size())
                            { 
                                maxIndex = q.size()-1;
                            }
                        }
                    }
                }
    
                // 所有病毒都处理完
                if (q.empty())
                { 
                    break;
                }
    
                int n = q.size();
                for (int i = 0; i < n; ++i)
                { 
                    auto& a = q[i];
                    if (i != maxIndex)
                    { 
                        for (const int& p : a.toDead)
                        { 
                            grid[p/50][p%50] = 1;
                        }
                    }
                    else
                    { 
                        for (const int& p : a.dead)
                        { 
                            grid[p/50][p%50] = -1;
                        }
                        res += a.cnt;
                    }
                }
            }
    
            return res;
        }
    };

1.  打开转盘锁  
    你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ 。每个拨轮可以自由旋转：例如把 ‘9’ 变为 ‘0’，‘0’ 变为 ‘9’ 。每次旋转都只能旋转一个拨轮的一位数字。锁的初始数字为 ‘0000’ ，一个代表四个拨轮的数字的字符串。列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。

**BFS求解**

class Solution { 
    public:
        int openLock(vector<string>& deadends, string target) { 
            if (target == "0000") { 
                return 0;
            }
    
            unordered_set<string> dead(deadends.begin(), deadends.end());
            if (dead.count("0000")) { 
                return -1;
            }
    
            auto num_prev = [](char x) -> char { 
                return (x == '0' ? '9' : x - 1);
            };
            auto num_succ = [](char x) -> char { 
                return (x == '9' ? '0' : x + 1);
            };
    
            // 枚举 status 通过一次旋转得到的数字
            auto get = [&](string& status) -> vector<string> { 
                vector<string> ret;
                for (int i = 0; i < 4; ++i) { 
                    char num = status[i];
                    status[i] = num_prev(num);
                    ret.push_back(status);
                    status[i] = num_succ(num);
                    ret.push_back(status);
                    status[i] = num;
                }
                return ret;
            };
    
            queue<pair<string, int>> q;
            q.emplace("0000", 0);
            unordered_set<string> seen = { "0000"};
    
            while (!q.empty()) { 
                auto [status, step] = q.front();
                q.pop();
                for (auto&& next_status: get(status)) { 
                    if (!seen.count(next_status) && !dead.count(next_status)) { 
                        if (next_status == target) { 
                            return step + 1;
                        }
                        q.emplace(next_status, step + 1);
                        seen.insert(move(next_status));
                    }
                }
            }
    
            return -1;
        }
    };