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);
*/