leetcode解题思路分析(九十四)818 - 824 题

2024-09-05 04:48

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

  1. 赛车
    你的赛车起始停留在位置 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;}
};
  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;}
};
  1. 单词的压缩编码
    给你一个单词数组 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;}
};
  1. 字符的最短距离
    给你一个字符串 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;}
};
  1. 翻转卡片游戏
    在桌子上有 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;}
};
  1. 带因子的二叉树
    给出一个含有不重复整数元素的数组 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;}
};
  1. 山羊拉丁文
    给定一个由空格分割单词的句子 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 题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1137986

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

性能分析之MySQL索引实战案例

文章目录 一、前言二、准备三、MySQL索引优化四、MySQL 索引知识回顾五、总结 一、前言 在上一讲性能工具之 JProfiler 简单登录案例分析实战中已经发现SQL没有建立索引问题,本文将一起从代码层去分析为什么没有建立索引? 开源ERP项目地址:https://gitee.com/jishenghua/JSH_ERP 二、准备 打开IDEA找到登录请求资源路径位置

透彻!驯服大型语言模型(LLMs)的五种方法,及具体方法选择思路

引言 随着时间的发展,大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用,随着人们期望的不断增加,目标也发生了巨大的变化。在短短的几个月的时间里,人们对大模型的认识已经从对其zero-shot能力感到惊讶,转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构(例如Transformer)对海量的、多种多样的数据分布进行建模得到,它包含了大量的先验

SWAP作物生长模型安装教程、数据制备、敏感性分析、气候变化影响、R模型敏感性分析与贝叶斯优化、Fortran源代码分析、气候数据降尺度与变化影响分析

查看原文>>>全流程SWAP农业模型数据制备、敏感性分析及气候变化影响实践技术应用 SWAP模型是由荷兰瓦赫宁根大学开发的先进农作物模型,它综合考虑了土壤-水分-大气以及植被间的相互作用;是一种描述作物生长过程的一种机理性作物生长模型。它不但运用Richard方程,使其能够精确的模拟土壤中水分的运动,而且耦合了WOFOST作物模型使作物的生长描述更为科学。 本文让更多的科研人员和农业工作者

MOLE 2.5 分析分子通道和孔隙

软件介绍 生物大分子通道和孔隙在生物学中发挥着重要作用,例如在分子识别和酶底物特异性方面。 我们介绍了一种名为 MOLE 2.5 的高级软件工具,该工具旨在分析分子通道和孔隙。 与其他可用软件工具的基准测试表明,MOLE 2.5 相比更快、更强大、功能更丰富。作为一项新功能,MOLE 2.5 可以估算已识别通道的物理化学性质。 软件下载 https://pan.quark.cn/s/57

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

衡石分析平台使用手册-单机安装及启动

单机安装及启动​ 本文讲述如何在单机环境下进行 HENGSHI SENSE 安装的操作过程。 在安装前请确认网络环境,如果是隔离环境,无法连接互联网时,请先按照 离线环境安装依赖的指导进行依赖包的安装,然后按照本文的指导继续操作。如果网络环境可以连接互联网,请直接按照本文的指导进行安装。 准备工作​ 请参考安装环境文档准备安装环境。 配置用户与安装目录。 在操作前请检查您是否有 sud

线性因子模型 - 独立分量分析(ICA)篇

序言 线性因子模型是数据分析与机器学习中的一类重要模型,它们通过引入潜变量( latent variables \text{latent variables} latent variables)来更好地表征数据。其中,独立分量分析( ICA \text{ICA} ICA)作为线性因子模型的一种,以其独特的视角和广泛的应用领域而备受关注。 ICA \text{ICA} ICA旨在将观察到的复杂信号

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &