leetcode解题思路分析（九十四）818

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

赛车
你的赛车起始停留在位置 0，速度为 +1，正行驶在一个无限长的数轴上。（车也可以向负数方向行驶。）你的车会根据一系列由 A（加速）和 R（倒车）组成的指令进行自动驾驶。现在给定一个目标位置，请给出能够到达目标位置的最短指令列表的长度。

class Solution {
public:int racecar(int target) {queue<pair<int,int>>que;set<pair<int,int>>vis;que.push({0,1});int cnt=0;while(!que.empty()){for(int sz=que.size();sz>0;sz--){auto[curX,curV]=que.front();que.pop();//cout<<curX<<endl;if(vis.count({curX,curV}))continue;vis.insert({curX,curV});if(abs(curV)>target*2+5)continue;if(curX==target)return cnt;que.push({curX+curV,curV*2});if(curX!=1&&curX!=-1)que.push({curX,curV>0?-1:1});}cnt++;}return -1;}
};

最常见的单词
给定一个段落 (paragraph) 和一个禁用单词列表 (banned)。返回出现次数最多，同时不在禁用列表中的单词。题目保证至少有一个词不在禁用列表中，而且答案唯一。禁用列表中的单词用小写字母表示，不含标点符号。段落中的单词不区分大小写。答案都是小写字母。

用isalpha来判断空格

class Solution {
public:string mostCommonWord(string paragraph, vector<string>& banned) {unordered_set<string> b;for (string bb : banned){b.insert(bb);}string curr;int maxCnt = 0;string res;unordered_map<string, int> str2cnt;for (char c : paragraph){if (isalpha(c)){curr += tolower(c);}else if (curr.size() > 0){// 排序被禁用的单词if (b.find(curr) == b.end()){++str2cnt[curr];if (str2cnt[curr] > maxCnt){maxCnt = str2cnt[curr];res = curr;}}curr = "";}}// 需要考虑最后一个单词if (curr.size() > 0){// 排序被禁用的单词if (b.find(curr) == b.end()){++str2cnt[curr];if (str2cnt[curr] > maxCnt){maxCnt = str2cnt[curr];res = curr;}}curr = "";}return res;}
};

单词的压缩编码
给你一个单词数组 words ，返回成功对 words 进行编码的最小助记字符串 s 的长度。

前缀树+逆序存储即可

class TrieNode{TrieNode* children[26];
public:int count;TrieNode() {for (int i = 0; i < 26; ++i) children[i] = NULL;count = 0;}TrieNode* get(char c) {if (children[c - 'a'] == NULL) {children[c - 'a'] = new TrieNode();count++;}return children[c - 'a'];}
};
class Solution {
public:int minimumLengthEncoding(vector<string>& words) {TrieNode* trie = new TrieNode();unordered_map<TrieNode*, int> nodes;for (int i = 0; i < (int)words.size(); ++i) {string word = words[i];TrieNode* cur = trie;for (int j = word.length() - 1; j >= 0; --j)cur = cur->get(word[j]);nodes[cur] = i;}int ans = 0;for (auto& [node, idx] : nodes) {if (node->count == 0) {ans += words[idx].length() + 1;}}return ans;}
};

字符的最短距离
给你一个字符串 s 和一个字符 c ，且 c 是 s 中出现过的字符。返回一个整数数组 answer ，其中 answer.length == s.length 且 answer[i] 是 s 中从下标 i 到离它最近的字符 c 的距离。

采用返回数组存储索引


class Solution {
public:vector<int> shortestToChar(string s, char c) {int n = s.size();vector<int> res(n, n-1);// 从左往右开始遍历res[0] = s[0] == c ? 0 : res[0];for (int i = 1; i < n; ++i){res[i] = s[i] != c ? res[i-1] + 1 : 0;}// 从右往左开始遍历res[n-1] = s[n-1] == c ? 0 : res[n-1];for (int i = n-2; i >= 0; --i){// 这里需要去res[i] = min(res[i], s[i] != c ? res[i+1] + 1 : 0);}return res;}
};

翻转卡片游戏
在桌子上有 N 张卡片，每张卡片的正面和背面都写着一个正数（正面与背面上的数有可能不一样）。我们可以先翻转任意张卡片，然后选择其中一张卡片。如果选中的那张卡片背面的数字 X 与任意一张卡片的正面的数字都不同，那么这个数字是我们想要的数字。哪个数是这些想要的数字中最小的数（找到这些数中的最小值）呢？如果没有一个数字符合要求的，输出 0。其中, fronts[i] 和 backs[i] 分别代表第 i 张卡片的正面和背面的数字。如果我们通过翻转卡片来交换正面与背面上的数，那么当初在正面的数就变成背面的数，背面的数就变成正面的数

所有正反面相同的都不可以，双面不一致的则统计最小值即可。


class Solution {
public:int flipgame(vector<int>& fronts, vector<int>& backs) {unordered_set<int>cannotNums;for(int i=0;i<fronts.size();i++){if(fronts[i]==backs[i])cannotNums.insert(fronts[i]);}int ans=INT_MAX;for(int i=0;i<fronts.size();i++){if(cannotNums.count(fronts[i])==0){ans=min(ans,fronts[i]);}if(cannotNums.count(backs[i])==0){ans=min(ans,backs[i]);}}return ans==INT_MAX?0:ans;}
};

带因子的二叉树
给出一个含有不重复整数元素的数组 arr ，每个整数 arr[i] 均大于 1。用这些整数来构建二叉树，每个整数可以使用任意次数。其中：每个非叶结点的值应等于它的两个子结点的值的乘积。满足条件的二叉树一共有多少个？答案可能很大，返回对 109 + 7 取余的结果。

定义
d[i]表示对于序号i的组合的数量
初始化
每个数字自己至少是一颗二叉树，所以 d[i]=1
计算
因为叶子必然比树小，所以我们做排序，然后按照每个点从小到大去找左右节点
左右节点用一个数组记录是否存在，便于快速查找
一旦存在左右子树l和r（序号），那么d[i] =d[i]+dp[l]*d[r]


class Solution {
public:int numFactoredBinaryTrees(vector<int>& arr) {int n = arr.size();long d[n];for (int i = 0; i < n; ++i){d[i] = 1;}int base = 1000000007;sort(arr.begin(), arr.end());// 构建数字到序号的映射unordered_map<int, int> num2idx;for (int i = 0; i < n; ++i){num2idx[arr[i]] = i;}for (int i = 1; i < n; ++i){// 找比它更小的数字for (int j = 0; j < i; ++j){if (arr[i] % arr[j] == 0){// 找到另外一个结点if (num2idx.find(arr[i] / arr[j]) != num2idx.end()){d[i] = (d[i] + d[j] * d[num2idx[arr[i] / arr[j]]]) % base;}}}}long res = 0;for (int i = 0; i < n; ++i){res = (res + d[i]) % base;}return res;}
};

山羊拉丁文
给定一个由空格分割单词的句子 S。每个单词只包含大写或小写字母。我们要将句子转换为 “Goat Latin”（一种类似于猪拉丁文 - Pig Latin 的虚构语言）。

遍历做一下即可

class Solution {
public:string toGoatLatin(string s) {string str="";bool tag;char shuzu[]={'a','e','i','o','u','A','E','I','O','U'}; //元音字母放进数组中vector<string> shuzu_str;for(int i=0;i<s.length();i++){if(s[i]!=' '){str+=s[i];}else{shuzu_str.push_back(str);str="";}}shuzu_str.push_back(str);str="";for(int i=0;i<shuzu_str.size();i++){tag=false;for(char x:shuzu){if(shuzu_str[i][0]==x){tag=true;shuzu_str[i]+="ma";break;}}if(!tag){shuzu_str[i]+=shuzu_str[i][0];shuzu_str[i]+="ma";shuzu_str[i]=shuzu_str[i].substr(1,shuzu_str[i].length()-1);}}for(int i=0;i<shuzu_str.size();i++){int j=i+1;while(j--){shuzu_str[i]+="a";}str+=shuzu_str[i];if(i!=shuzu_str.size()-1) str+=" ";}return str;}
};