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

本文主要是介绍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;
    }
};

这篇关于leetcode解题思路分析（九十四）818 - 824 题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

C/C++教程

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

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯