LeetCode2022年每日一题4月打卡汇总
点击题目即可跳转至LeetCode题目
4.1：二倍数对数组
给定一个长度为偶数的整数数组 arr，只有对 arr 进行重组后可以满足 “对于每个 0 <= i < len(arr) / 2，都有 arr[2 i + 1] = 2 arr[2 * i]” 时，返回 true；否则，返回 false。
示例1：
输入：arr = [3,1,3,6]
输出：false示例2：
输入：arr = [2,1,2,6]
输出：false示例3：
输入：arr = [4,-2,2,-4]
输出：true
解释：可以用 [-2,-4] 和 [2,4] 这两组组成 [-2,-4,2,4] 或是 [2,4,-2,-4]提示：
- $0 <= arr.length <= 3 * 10^4$
arr.length是偶数- $-10^5 <= arr[i] <= 10^5$
题解：哈希+排序
首先将数组中所有元素出现的次数存入哈希表中，通过题意我们不难发现，只需要判断下标为奇数（下标从0开始）的数是前面数字的两倍即可。
于是自定义排序：按照绝对值的大小从大到小排序
遍历排好序的数组，只需判断当前数字是否还存在（可能是前面数字的两倍）以及它乘以两倍的数字是否存在即可。
如果存在n/2对数对，则返回true，否则返回false。
注意：需要特判下0
C++代码：
class Solution {
public:
static bool cmp(int x,int y){
return abs(x)<abs(y);
}
bool canReorderDoubled(vector<int>& arr) {
int n=arr.size();
map<int,int> mp;
for(int i=0;i<n;i++) mp[arr[i]]++;
sort(arr.begin(),arr.end(),cmp);
int cnt=0;
for(int i=0;i<n;i++){
if(mp[arr[i]]==0||mp[2*arr[i]]==0) continue;
if(arr[i]==0&&mp[arr[i]]<2) continue;
cnt++;
--mp[arr[i]];--mp[2*arr[i]];
}
if(cnt<n/2) return false;
return true;
}
};4.3：寻找比目标字母大的最小字母
给你一个排序后的字符列表 letters ，列表中只包含小写英文字母。另给出一个目标字母 target，请你寻找在这一有序列表里比目标字母大的最小字母。
在比较时，字母是依序循环出现的。举个例子：
如果目标字母 target = ‘z’ 并且字符列表为 letters = [‘a’, ‘b’]，则答案返回 ‘a’
示例1：
输入: letters = ["c", "f", "j"]，target = "a"
输出: "c"示例2：
输入: letters = ["c","f","j"], target = "c"
输出: "f"示例3：
输入: letters = ["c","f","j"], target = "d"
输出: "f"提示：
- $2 <= letters.length <= 10^4$
- letters[i] 是一个小写字母
- letters 按非递减顺序排序
- letters 最少包含两个不同的字母
- target 是一个小写字母
题解：模拟
直接遍历列表，判断是否存在大于target的字母，若不存在则输出列表中第一个字符即可。
class Solution {
public:
char nextGreatestLetter(vector<char>& letters, char target) {
int n=letters.size();
for(int i=0;i<n;i++){
if(letters[i]>target) return letters[i];
}
return letters[0];
}
};4.11：统计各位数字都不同的数字个数
题解一：暴力DFS
n最大为8，比较容易想到的思路便是直接通过dfs遍历每一位数字，如果各位数字都不同则记录数+1，最终统计满足条件的个数即可。
注意：前导0的情况需要特判下。
缺点：费时
C++代码：
class Solution {
public:
map<int,int> mp;
int ans;
int check(){
for(int i=1;i<10;i++) if(mp[i]) return 0;
return 1;
}
void dfs(int cnt,int n){
if(cnt>n){
++ans;return ;
}
for(int i=0;i<10;i++){
if(mp[i]) continue;
if(check()&&i==0){ //前面全是前导0
dfs(cnt+1,n);
}else{
mp[i]++;
dfs(cnt+1,n);
mp[i]--;
}
}
}
int countNumbersWithUniqueDigits(int n) {
mp.clear();
if(n==1) return 10;
ans=0;
dfs(1,n);
return ans;
}
};题解二：排列组合
官方提供的思路。
- n=0时：$0<=x<1$，满足条件个数为：1个
- n=1时：$0<=x<10$，满足条件个数为：0~9，10个
n=2时：$0<=x<100$，可以由两部分构成：只有一位数的情况和两位数的情况。其中
- 只有一位数的情况由上述可得x有10种；
- 有两位数的情况：第一位可以取1~9（9种）， 第二位可以取0~9除了和第一位不同的数字（9种），于是就有：9*9=81种。
n=3时，可以分为三部分：一位数、两位数、三位数
- 一位数：10种（0~9）
- 两位数：9*9=81种
- 三位数：9*9*8
- 扩展至n>=2：含有n位数字的情况，可以表示为：9*$A_{9}^{n-1}$
于是代码如下：
C++代码：
class Solution {
public:
int countNumbersWithUniqueDigits(int n) {
if(n==0) return 1;
else if(n==1) return 10;
int ans=10,num=9;
for(int i=1;i<=n-1;i++){
num*=(9-i+1); //9*9*8*....
ans+=num;
}
return ans;
}
};当然，还有其他的解法，比如：n最大为8，可以直接打表（存储n为0~8的结果）；还可以用dp等等，此处并不一一列举。
4.12：写字符串需要的行数
题解：模拟
直接根据题意模拟即可，如果当前行已有的宽度+当前遍历字符的宽度>100，则直接换行即可。
C++代码：
class Solution {
public:
vector<int> numberOfLines(vector<int>& widths, string s) {
int n=s.length(),num=0,cnt=1;
for(int i=0;i<n;i++){
if(num+widths[s[i]-'a']>100){
++cnt;num=widths[s[i]-'a'];
}else{
num+=widths[s[i]-'a'];
}
}
vector<int> ans(2);ans[0]=cnt;ans[1]=num;
return ans;
}
};4.13：O(1) 时间插入、删除和获取随机元素
题解：哈希表
对于获取随机元素，数组可以在O(1)时间做到，但是对于插入和删除操作，数组却无能为力。
对于插入和删除操作，哈希表可以在O(1)时间做到，但是对于获取随机元素操作，哈希表却又不可奈何。
于是思考：能否将两者结合，实现O(1)时间：插入、删除和获取随机元素。
- 用一可变数组num：存储集合中的元素
- 哈希表中：key存储num中的元素，value存储对应的索引
当执行插入操作（插入元素在集合中未出现）时：
- num数组直接在末尾添加
- 哈希表则把插入的元素和对应的末尾下标存入其中
当执行删除操作（待删除元素在集合中）时：
- 将num数组中末尾元素移动至当前需要删除元素的索引处
- 在哈希表中更新num数组中末尾对应的value值（即索引）
- num数组删除最后一个元素，哈希表删除待删除的元素
借此巩固下Java集合类的使用，于是提供C++和Java代码：
C++代码：
class RandomizedSet {
public:
unordered_map<int,int> mp; //key->num,value->index
vector<int> num;
RandomizedSet() {
mp.clear();num.clear();
srand(time(0)); //随机数种子
}
bool insert(int val) {
if(mp.count(val)) return false;
num.push_back(val);
mp[val]=num.size()-1;
return true;
}
bool remove(int val) {
if(!mp.count(val)) return false;
//将num数组中最后一个元素填入到此位置
int index=mp[val];
int x=num.back();
mp[x]=index;
num[index]=x;
//在num数组中删除最后一个元素，同时mp中也删除需要删除的元素
num.pop_back();mp.erase(val);
return true;
}
int getRandom() {
int pos=rand()%num.size();
return num[pos];
}
};
/**
* Your RandomizedSet object will be instantiated and called as such:
* RandomizedSet* obj = new RandomizedSet();
* bool param_1 = obj->insert(val);
* bool param_2 = obj->remove(val);
* int param_3 = obj->getRandom();
*/Java代码：
class RandomizedSet {
Map<Integer,Integer> map;
List<Integer> num;
public RandomizedSet() {
map=new HashMap<Integer,Integer>();
num=new ArrayList<>();
}
public boolean insert(int val) {
if(map.containsKey(val)) return false;
num.add(val);
map.put(val,num.size()-1);
return true;
}
public boolean remove(int val) {
if(!map.containsKey(val)) return false;
//将num最后一个元素移动至当前位置
int index=map.get(val);
int last=num.get(num.size()-1);
num.set(index,last);
map.put(last,index);
//删除num最后一个元素，删除map中需要删除的元素
num.remove(num.size()-1);
map.remove(val);
return true;
}
public int getRandom() {
Random rand=new Random();
int index=rand.nextInt(num.size());
return num.get(index);
}
}4.14：最富有客户的资产总量
题解：模拟
直接按照题意，计算每位客户的资产总量，在选出最大的资产总量即可。
C++代码：
class Solution {
public:
int maximumWealth(vector<vector<int>>& accounts) {
int ans=0,num=0;
for(int i=0;i<accounts.size();i++){
num=0;
for(int j=0;j<accounts[i].size();j++){
num+=accounts[i][j];
}
ans=max(ans,num);
}
return ans;
}
};4.15：迷你语法分析器
题解：dfs或栈
今天题目可能有点小复杂，但难度不大，可以理解为模拟。
可以使用dfs和栈来实现，dfs思路比较简单，但是相比于栈比较复杂，于是在此用栈来模拟实现。
栈中元素保存的是NestedInteger对象。
每一个NestedInteger对象存在两个元素：整数 或 列表
- 当出现 $[$ 字符时，则表示创建新的NestedInteger对象
- 当出现 $,$ 或 $]$ 字符时，表示要创建新的元素或对象
- 如果是 $,$ 则表示此时是一个列表，把上一个整数添加至栈顶元素的列表中
- 如果是 $]$ ，则此时NestedInteger对象已经结束，添加至栈顶
最后只需要返回栈顶元素即可。具体见代码。
注意：如果只有一个整数表示的情况，如示例1，则需要特判下。
C++代码
/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* class NestedInteger {
* public:
* // Constructor initializes an empty nested list.
* NestedInteger();
*
* // Constructor initializes a single integer.
* NestedInteger(int value);
*
* // Return true if this NestedInteger holds a single integer, rather than a nested list.
* bool isInteger() const;
*
* // Return the single integer that this NestedInteger holds, if it holds a single integer
* // The result is undefined if this NestedInteger holds a nested list
* int getInteger() const;
*
* // Set this NestedInteger to hold a single integer.
* void setInteger(int value);
*
* // Set this NestedInteger to hold a nested list and adds a nested integer to it.
* void add(const NestedInteger &ni);
*
* // Return the nested list that this NestedInteger holds, if it holds a nested list
* // The result is undefined if this NestedInteger holds a single integer
* const vector<NestedInteger> &getList() const;
* };
*/
class Solution {
public:
NestedInteger deserialize(string s) {
if(s[0]!='['){ //只有一个数字的情况，如示例1
return NestedInteger(stoi(s)); //stoi()：c++内置string to int函数
}
stack<NestedInteger> sta;
int n=s.length();
bool flag=0; //记录正负
int num=0;
for(int i=0;i<n;i++){
if(s[i]=='-') flag=1;
else if(isdigit(s[i])){ // c++内置判断是否为数字函数
num=num*10+(s[i]-'0');
}else if(s[i]=='['){ //创建一个新的对象
sta.push(NestedInteger());
}else if(s[i]==','||s[i]==']'){ //新的元素或对象
if(isdigit(s[i-1])){
if(flag) num=-num;
sta.top().add(NestedInteger(num));
}
num=0;flag=0;
if(s[i]==']'&&sta.size()>1){
NestedInteger ni=sta.top();
sta.pop();
sta.top().add(ni);
}
}
}
return sta.top();
}
};4.16：最大回文数乘积
题解：数学+枚举
由于需要计算两位n位整数乘积的最大回文整数。于是可以直接枚举所有的回文数（由于是求最大值，所有从大到小枚举）
两位n位整数最多也只能产生$10^{2n}$位的数字。又由于是回文数，我们可以只枚举一半，于是可以从$10^n-1$开始枚举回文数的一半。
然后再遍历它的因子，如果两个因子都是n位整数，则找到答案，即可结束循环。
C++代码：
class Solution {
public:
int largestPalindrome(int n) {
if(n==1) return 9;
int ans=0;
//枚举回文数左边
for(int i=pow(10,n)-1;i>pow(10,n-1);i--){
int num=i;long long p=i; //p表示回文数
while(num){
p=p*10+num%10;num/=10;
}
//遍历它的因子
for(long long j=pow(10,n)-1;j*j>=p;j--){
if(p%j==0&&(j>pow(10,n-1))){
ans=p%1337;break;
}
}
if(ans!=0) break;
}
return ans;
}
};4.17：最常见的单词
题解：模拟
- 首先将所有字母转化为小写字母
- 截取段落中所有的单词存储到一个哈希表中，key存储单词，value存储单词出现的次数
- 在哈希表中找出出现次数最多，且不在禁用列表中的单词
注意：截取段落中的所有单词可能会存在一些小细节，需要留意下（例如最后一个单词末尾可能是字母或者是其他字符等）
C++代码：
class Solution {
public:
char s[7]={' ','!','?','\'',',',';','.'};
int get_minpos(string paragraph,int pos){
int n=paragraph.size();
int res=n-1;
for(int i=pos;i<n;i++){
for(int j=0;j<7;j++){
if(paragraph[i]==s[j]){
res=i;break;
}
}
if(res!=n-1) break;
}
return res;
}
string mostCommonWord(string paragraph, vector<string>& banned) {
int n=paragraph.size();
//先将字符串中所有字母转化为小写
for(int i=0;i<n;i++){
if(paragraph[i]>='A'&¶graph[i]<='Z') paragraph[i]+=32;
}
// cout<<paragraph<<endl;
map<string,int> mp;
int pos=0;
while(pos<n-1){
int p=get_minpos(paragraph,pos);
string str;
if(paragraph[p]>='a'&¶graph[p]<='z') str=paragraph.substr(pos,p-pos+1);
else str=paragraph.substr(pos,p-pos);
// cout<<pos<<"--"<<p<<"---"<<str<<endl;
if(str!="") mp[str]++;
pos=p+1;
}
int maxnum=0;string ans;
for(auto it:mp){
if(count(banned.begin(),banned.end(),it.first)) continue;
if(it.second>maxnum){
maxnum=it.second;ans=it.first;
}
}
return ans;
}
};4.18：字典序排数
题解：DFS
题目要求按照字典序返回[1,n]中的所有数字。时间复杂度要求为$O(n)$，空间复杂度要求为：$O(1)$
例如：n=13时，输出为：[1,10,11,12,13,2,3,4,5,6,7,8,9]。
思考能否直接从1开始遍历出第一位数字为1且小于等于n的所有数字；然后再遍历2,3,…9。这样便可在$O(n)$时间复杂度条件下实现题目要求。
显然dfs可以实现上述思路：
- 最高位从1到9
- 次高为从1到9
- ….
期间如果遍历的数字超过了n则直接结果此轮的dfs。
代码如下：
C++代码：
class Solution {
public:
int cnt,num;
vector<int> ans;
void dfs(int now,int n){
if(now>n||cnt>n) return ;
++cnt;ans.push_back(now);
for(int i=0;i<=9;i++){
dfs(now*10+i,n);
}
}
vector<int> lexicalOrder(int n) {
cnt=1,num=1;
for(int i=1;i<=9;i++){
dfs(i,n);
}
return ans;
}
};4.19：字符的最短距离
题解一：暴力
首先将字符串s中所有字符c的位置存入数组中，然后遍历字符串s，假设当前遍历位置为i，再二重循环遍历所有字符c的位置，找出两个下标之间的最小距离。
时间复杂度：$O(n^2)$
C++代码：
class Solution {
public:
vector<int> shortestToChar(string s, char c) {
vector<int> pos_arr;
int n=s.length();
for(int i=0;i<n;i++){
if(s[i]==c) pos_arr.push_back(i);
}
vector<int> ans(n,0x3f3f3f3f);
for(int i=0;i<n;i++){
for(auto j:pos_arr){
ans[i]=min(ans[i],abs(i-j));
}
}
return ans;
}
};题解二：两次遍历
- 第一次遍历，从左到右遍历，找出s[i]到左侧最近的字符c的距离
- 第二次遍历，从右到左遍历，找出s[i]到右侧最近的字符c的距离
然后选择其中的最小值即可。
注意：可能存在此时并没出现过字符c的情况（例如：从左到右遍历时，左侧并没有字符c，从右到左遍历同理）所以需要初始化一个最大值，为方便处理：
- 从左开始遍历时，我们可以初始字符c的位置为：$pos=-n$，如果未出现则取：i-pos>=n，显然可行
- 从右开始遍历时，我们可以初始字符c的位置为：$pos=2n$，如果未出现则取：pos-i>n，显然可行
当然也可以直接初始化非常大的值。
C++代码：
class Solution {
public:
vector<int> shortestToChar(string s, char c) {
int n=s.length();
vector<int> ans(n);
int pos=-n;
for(int i=0;i<n;i++){
if(s[i]==c) pos=i;
ans[i]=i-pos;
}
pos=2*n;
for(int i=n-1;i>=0;i--){
if(s[i]==c) pos=i;
ans[i]=min(ans[i],pos-i);
}
return ans;
}
};4.20：文件的最长绝对路径
题解：模拟
注意：题目给出的换行符$\n$和制表符$\t$，都只是字符，而不是由两个字符组成。
上述理解后，这题就不难了，对于每一个文件file：
- 要么是由上一层的文件夹所得到，此时路径长度为：文件名长度+上一层路径长度+1（表示/）
- 要么直接为根目录下的文件，此时路径长度直接为：文件名长度
判断当前遍历的为文件还是文件夹 ，于是只需要判断是否存在字符 $.$ 即可。
又由于只需要计算文件的最长绝对路径，于是我们只需要存储每一层的绝对路径的长度，然后按照上述规则不断更新结结果即可。
具体见代码注释。
C++代码：
class Solution {
public:
int lengthLongestPath(string input) {
int n=input.length();
int ans=0;
int pos=0; //遍历字符串
int dep; //遍历文件的层数
vector<int> f(n+1); //记录每一层的路径长度
while(pos<n){
//当前层数
dep=1;
while(pos<n&&input[pos]=='\t'){
pos++;dep++;
}
//记录当前文件/文件夹的长度
int len=0;
bool flag=false; //判断是否为文件
while(pos<n&&input[pos]!='\n'){
if(input[pos]=='.') flag=true;
pos++;len++;
}
// 不是根目录
if(dep>1) len+=f[dep-1]+1;
if(flag){ //is file
ans=max(ans,len);
}else{ //is folder
f[dep]=len;
}
//跳过换行符
pos++;
}
return ans;
}
};4.21：山羊拉丁文
题解：模拟
直接按照题意模拟即可。通过一次遍历便可按照题意输出想要的结果
- 元音字母包含大小写10个
- 如果此时遍历的是单词的第一个字母，且为辅音字母，则直接跳过（因为该字母需要加入到单词末尾）
- 如果此时遍历的空格，则表示此时已经遍历了一个单词，按照题目要求进行相应的操作（如果单词第一个字母为辅音字母则加入到末尾；然后加入对应数量的字母a）
可以发现，这样处理对于最后一个单词不是很友好，因为末尾没有空格，为了方便处理，可以在末尾加入一个空格，直接一步到位。
官方题解时间复杂度为$O(n^2)$，此思路时间复杂度为$O(n)$
C++代码：
class Solution {
public:
string str="aeiouAEIOU";
bool check(char c){
for(int i=0;i<10;i++) if(c==str[i]) return true;
return false;
}
string toGoatLatin(string s) {
//为了方便处理最后一个单词，所以在字符串末尾添加' '
s+=' ';
int n=s.length();
string ans="";
int cnt=0; //记录单词在句子中的索引
int pos=0; //记录当前遍历的单词第一个字母位置
for(int i=0;i<n;i++){
if(i==pos && !check(s[i])){//单词以辅音字母开头
continue;
}
if(s[i]==' '){
++cnt;
if(!check(s[pos])) ans+=s[pos]; //如果第一个字母是辅音字母则加入到末尾
ans+="ma";
for(int j=0;j<cnt;j++) ans+='a';
pos=i+1; //更新pos
}
if(i!=n-1) ans+=s[i];
}
return ans;
}
};4.22：旋转函数
题解：迭代+思维
通过具体示例进行讲解：例如nums = [4, 3, 2, 6]
F[0] = (0*4) + (1*3) + (2*2) + (3*6)
F[1] = (1*4) + (2*3) + (3*2) + (0*6) = F[0] + sum - n*nums[n-1]（其中sum表示数组nums所有元素总和）
F[2] = (2*4) + (3*3) + (0*2) + (1*6) = F[1] + sum - n*nums[n-2]进而推广至$k(1<k<n)$：$F[k]=f[k-1]+sum-n*nums[n-k]$
从F[]数组中选择最大值即为答案。
C++代码
class Solution {
public:
int maxRotateFunction(vector<int>& nums) {
int n=nums.size();
//数组元素的和
int sum=0;
for(int i=0;i<n;i++) sum+=nums[i];
vector<int> f(n);
for(int i=1;i<n;i++) f[0]+=i*nums[i];
int ans=f[0];
for(int k=1;k<n;k++){
f[k]=f[k-1]+sum-n*nums[n-k];
ans=max(ans,f[k]);
}
return ans;
}
};当然可以通过变量存储每一次旋转函数的值，从而降低空间复杂度。
4.25：随机数索引
题解：哈希表
题目给定数组长度最大为$2*10^4$，同时最多调用pick函数$10^4$次，于是可以直接通过哈希表存储数组中的元素对应的下标，即：
- key为数组元素
- value为数组元素对应下标的列表
对于随机数，直接使用C++ rand()函数即可。
C++代码：
class Solution {
public:
map<int,vector<int> > mp;
Solution(vector<int>& nums) {
srand(time(0));
int n=nums.size();
for(int i=0;i<n;i++){
mp[nums[i]].push_back(i);
}
}
int pick(int target) {
int n=mp[target].size();
return mp[target][rand()%n];
}
};
/**
* Your Solution object will be instantiated and called as such:
* Solution* obj = new Solution(nums);
* int param_1 = obj->pick(target);
*/