leetcode解题思路分析（五十五）469 - 475 题

本文主要是介绍leetcode解题思路分析（五十五）469 - 475 题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

470. 用 Rand7() 实现 Rand10()
     已有方法 rand7 可生成 1 到 7 范围内的均匀随机整数，试写一个方法 rand10 生成 1 到 10 范围内的均匀随机整数。

说白了就是进制转换问题。使用两次rand7，可以生成1-49的数字，其中1-40直接拿来表示1-10，多的数字1-9再次rand7，则组成63个数字，再多的3个可以组成21个，接着组成1个，最后回到循环。

// The rand7() API is already defined for you.
// int rand7();
// @return a random integer in the range 1 to 7class Solution {
public:int rand10() {int a, b, idx;while (true) {a = rand7();b = rand7();idx = b + (a - 1) * 7;if (idx <= 40)return 1 + (idx - 1) % 10;a = idx - 40;b = rand7();// get uniform dist from 1 - 63idx = b + (a - 1) * 7;if (idx <= 60)return 1 + (idx - 1) % 10;a = idx - 60;b = rand7();// get uniform dist from 1 - 21idx = b + (a - 1) * 7;if (idx <= 20)return 1 + (idx - 1) % 10;}}
};

472. 连接词
     给定一个不含重复单词的列表，编写一个程序，返回给定单词列表中所有的连接词。

前缀树的使用

class Trie{
private:bool is_string;Trie *next[26];
public:Trie(){is_string=false;memset(next,0,sizeof(next));}void insert(string word){Trie *root=this;for(const auto& w:word){if(root->next[w-'a']==nullptr)root->next[w-'a']=new Trie();root=root->next[w-'a'];}root->is_string=true;}bool search(string word,int index,int count){Trie *root=this;//每次从根节点开始寻找for(int i=index;i<word.size();++i){if(root->next[word[i]-'a']==nullptr)return false;//word的某个字符不在前缀树中root=root->next[word[i]-'a'];if(root->is_string){//到达某个单词尾if(i==word.size()-1)return count>=1;//count的数量至少为2个，若遍历到最后只有一个单词，则count的值还是为0//已前count位的单词作为分解词继续匹配下一个单词,下个单词满足count才能返回ture,否则继续寻找下一个分界单词if(search(word,i+1,count+1))return true;}}return false;}
};
class Solution {
public:vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {Trie *root=new Trie();for(const auto &word:words){root->insert(word);}vector<string> result;for(const auto &word:words){if(root->search(word,0,0))result.push_back(word);}return result;}
};

473. 火茶拼正方形
     输入为小女孩拥有火柴的数目，每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。

先除4，然后数组从大到小排序后查找是否可以找到

class Solution {
public:bool makesquare(vector<int>& nums) {int n = nums.size();if (n < 4) return false;sort(nums.begin(), nums.end(), greater<int>()); //逆排int sum = accumulate(nums.begin(), nums.end(), 0); //累加和if (sum % 4 != 0) return false;  sum /= 4;vector<bool> vis(n, false);  //记录是否被用过for (int i = 0; i < 4; i++)  //四条边都搜索{if (!dfs(nums, vis, 0, sum)) return false;}return true;}bool dfs(vector<int> &nums, vector<bool> &vis, int k, int sum){int n = nums.size();if(sum==0) return true; for(int i=k; i<n; ++i){if(nums[i]<=sum && !vis[i]){vis[i] = true;if(dfs(nums, vis, i+1, sum-nums[i])) return true;  //组合成功就返回，不需要继续搜索。vis[i] = false;  //如果组合失败，需要释放该数}}return false;}};

474. 一和零
     给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
     请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。
     如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

实际上是一个二维背包问题，所以可以用动态规划求解。

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {int S = strs.size();vector<vector<int> > dp(m + 1, vector<int>(n + 1, 0));for (int l = 0; l < S; ++l) {int zero = 0;int one = 0;for (int i = 0; i < strs[l].size(); ++i) {if (strs[l][i] == '0') ++zero;else ++one;}for (int i = m; i >= zero; --i) {for (int j = n; j >= one; --j) {dp[i][j] = max(dp[i][j], 1 + dp[i - zero][j - one]);}}}return dp[m][n];}
};

475. 供暖器
     现在，给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置，请你找出并返回可以覆盖所有房屋的最小加热半径。

本题可采用二分法或者滑动指针求解，前提是要保证升序排列：二分法即对每个房屋找寻左右两侧最合适的取暖器，滑动指针即每次取房屋左边最近的取暖器和右边最近的取暖器，本质是一样的。

//c++
class Solution {
public:int findRadius(vector<int>& houses, vector<int>& heaters) {//找到每个房屋位置所需要的最小半径的最大值int res = 0;int n = heaters.size();sort(heaters.begin(), heaters.end());for (auto house : houses){//二分法找不小于house的第一个值int left = 0, right = n;while (left < right){int mid = left + (right - left)/2;if (house > heaters[mid]) left = mid + 1;else right = mid;}int dist1 = (right == 0) ? INT_MAX : abs(house - heaters[right - 1]);int dist2 = (right == n) ? INT_MAX : abs(house - heaters[right]);res = max(res, min(dist1, dist2));}return res;}
};

//c++
class Solution {
public:
int findRadius(vector<int>& houses, vector<int>& heaters) {sort(houses.begin(), houses.end());sort(heaters.begin(), heaters.end());int ans = 0;int k = 0;for (int i = 0; i < houses.size(); i++) {int radius = INT_MAX;for (int j = k; j < heaters.size(); j++) {k = (houses[i] >= heaters[j]) ? j : k;radius = min(radius, abs(houses[i] - heaters[j]));if (houses[i] < heaters[j]) break;}ans = max(ans, radius);}return ans;
}
};

这篇关于leetcode解题思路分析（五十五）469 - 475 题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---