349. 两个数组的交集
- 首先记录下nums1中出现过的数字，如果nums2中也出现就将其加入到集合中。
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int,int> map;
unordered_set<int> set;
for(auto var :nums1)
{
map[var] = 1;
}
for(auto var :nums2)
{
if(map.find(var)!=map.end())
{
set.insert(var);
}
}
return vector<int>(set.begin(),set.end());
}
};
941. 有效的山脉数组
845-数组中的最长山脉的简化版本
{% note warning simple %}
for循环内部如果没有语句，要注意后面要加上;
{% endnote %}
class Solution {
public:
bool validMountainArray(vector<int>& A) {
if(A.size()<3)
return false;
int i,j;
for(i=1;i<A.size()&&A[i]>A[i-1];i++);
for(j=i;j<A.size()&&A[j]<A[j-1];j++);
if(i!=1 && j !=i && j==A.size())
return true;
return false;
}
};
57. 插入区间
- 虽然标记是hard，感觉还是挺简单的，只是条件处理稍稍多了一点
- 判断要插入的区间的左右端点，在原先的区间列表中的位置，在分各种情况讨论，选择插入区间或者合并区间插入。
class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
vector<vector<int>> rets;
int i=0;
while(i<intervals.size()&&intervals[i][1]<newInterval[0])
{
rets.push_back(intervals[i]);
i++;
}
int j= i;
while(j<intervals.size()&&intervals[j][1]<newInterval[1]) j++;
if(i==intervals.size())
{
rets.push_back(newInterval);
return rets;
}
if(j==intervals.size())
{
if(intervals[i][0]>newInterval[0])
rets.push_back(newInterval);
else
rets.push_back(vector<int>({intervals[i][0],newInterval[1]}));
return rets;
}
if(intervals[i][0]>newInterval[0]&&intervals[j][0]>newInterval[1])
rets.push_back(newInterval);
else if(intervals[i][0]>newInterval[0])
{
rets.push_back(vector<int>({newInterval[0],intervals[j][1]}));
j++;
}
else if(intervals[j][0]>newInterval[1])
{
rets.push_back(vector<int>({intervals[i][0],newInterval[1]}));
}
else
{
rets.push_back(vector<int>({intervals[i][0],intervals[j][1]}));
j++;
}
while(j<intervals.size())
{
rets.push_back(intervals[j]);
j++;
}
return rets;
}
};
127. 单词接龙
补上昨天的
- 采用图的广度优先遍历算法，但是一直是最后一个用例超时
- 采用双端广度优先算法。
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
int len = wordList.size();
int str_len = beginWord.size();
vector<int> visit(len);
vector<int> visit1(len);
int layer = 0;
queue<string> q,q1;
q.push(beginWord);
for(int i=0;i<wordList.size();i++)
{
if(wordList[i]==endWord)
{
q1.push(endWord);
visit1[i] = 1;
}
}
if(q1.empty())
return 0;
while((!q.empty())&&(!q1.empty()))
{
layer++;
for(int sz = q.size();sz>0;sz--)
{
string j = q.front();
q.pop();
for(int k=0;k<len;k++)
{
if(visit[k] ==0 && Judge(j,wordList[k],str_len))
{
visit[k] = 1;
q.push(wordList[k]);
if(visit1[k]==1)
return layer*2 ;
}
}
}
for(int sz = q1.size();sz>0;sz--)
{
string j = q1.front();
q1.pop();
for(int k=0;k<len;k++)
{
if(visit1[k] ==0 && Judge(j,wordList[k],str_len))
{
visit1[k] = 1;
q1.push(wordList[k]);
if(visit[k]==1)
return layer*2 + 1;
}
}
}
}
return 0;
}
int Judge(string key,string end,int len)
{
int sum = 0;
for(int i=0;i<len;i++)
{
if(key[i]!=end[i])
sum++;
}
return sum==1;
}
};
1356. 根据数字二进制下 1 的数目排序
- 先统计每个数字的二进制下1的数目，计数可以参考338. 比特位计数,或者直接位运算
- 对每个数字根据1的数目进行排序，可以选用计数排序。
class Solution {
public:
vector<int> sortByBits(vector<int>& arr) {
vector<int> res(arr.size());
vector<int> cnt(arr.size());
int dt[34]={0};
sort(arr.begin(),arr.end());
for(int i=0;i<arr.size();i++)
{
cnt[i] = GetBits(arr[i]);
dt[cnt[i]+1]++;
}
for(int i=1;i<34;i++)
{
dt[i] += dt[i-1];
}
for(int i=0;i<arr.size();i++)
{
res[dt[cnt[i]]++] = arr[i];
}
return res;
}
int GetBits(int i)
{
int sum = 0;
while(i)
{
sum += i&1;
i=i>>1;
}
return sum;
}
};
327. 区间和的个数
- 暴力法，超时
- 还有一种方法是求前缀和
class Solution {
public:
int countRangeSum(vector<int>& nums, int lower, int upper) {
int res = 0;
int len = nums.size();
for(int i=0;i<len;i++)
{
long sum = 0;
for(int j=i;j<len;j++)
{
sum+=nums[j];
res += sum>=lower&&sum<=upper;
}
}
return res;
}
};
- 利用了归并排序的思想
class Solution {
public:
int Merge(vector<long> &sum,int lower,int upper,int left,int right)
{
if(left==right)
return 0;
int mid = (left+right)/2;
int res=Merge(sum,lower,upper,left,mid)+Merge(sum,lower,upper,mid+1,right);
int i=left;
int l = mid+1;
int r = mid+1;;
while(i<=mid)
{
while(l<=right&&sum[l]-sum[i]<lower) l++;
while(r<=right&&sum[r]-sum[i]<=upper) r++;
res+=r-l;
i++;
}
vector<long> sort(right-left+1);
int p=0,p1 = left,p2 = mid+1;
while(p1<=mid||p2<=right)
{
if(p1>mid)
sort[p++] = sum[p2++];
else if(p2>right)
sort[p++]= sum[p1++];
else
{
if(sum[p1]>sum[p2])
sort[p++] = sum[p2++];
else
sort[p++]= sum[p1++];
}
}
for(int i=left;i<=right;i++)
{
sum[i] = sort[i-left];
}
return res;
}
int countRangeSum(vector<int>& nums, int lower, int upper) {
vector<long> sum(nums.size()+1);
long s = 0;
sum[0]=0;
for(int i=0;i<nums.size();i++)
{
s+=nums[i];
sum[i+1] = s;
}
return Merge(sum,lower,upper,0,sum.size()-1);
}
};
122. 买卖股票的最佳时机 II
- 如果今天比昨天售价低，就假设今天买入，然后找到与今天连续的价格最高的点，然后卖出加到盈利里面，然后再假设在最高点后一天再买入，如果没有连续的比今天价格高的点，就假设明天买入。
- 另一种的是简化，只要今天比昨天大，就卖出。
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size()<2)
return 0;
int buy= prices[0];
int profit = 0;
for(int i=1;i<prices.size();i++)
{
if(prices[i]<prices[i-1])
{
profit += prices[i-1]-buy>0? prices[i-1]-buy:0;
buy = prices[i];
}
}
profit += prices[prices.size()-1]-buy>0? prices[prices.size()-1]-buy:0;
return profit;
}
};
973. 最接近原点的 K 个点
- 先计算出所有的欧几里德距离
- 然后将他们的索引进行排序，前K个就是题目所求
class Solution {
public:
vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
vector<double> keys(points.size());
vector<int> indexes(points.size());
for(int i=0;i<keys.size();i++)
{
keys[i] = sqrt(points[i][0]*points[i][0] +points[i][1]*points[i][1] );
indexes[i] = i;
}
sort(indexes.begin(),indexes.end(),[&](int x,int y){return keys[x]<keys[y];});
vector<vector<int>> res(K);
for(int i=0;i<K;i++)
{
res[i] = points[indexes[i]];
}
return res;
}
};
- 第二部排序中可以借鉴使用快速排序，边排序边排除不符合要求的。期望的时间复杂度O(n)
31. 下一个排列
- 题目的意思是，对于一个排列组成的数，找到一个只比这个数大的
- 从后往前找，找到第一个$nums[i]>nums[i-1]$，如果没有，显然这个数就是最大的。
- 然后从i开始往后找，找一个最小的，但是比$nums[i-1]$大的数，然后这个数和$nums[i-1]$交换
- 对于i以及之后的数，必然是一个降序的序列，进行反转后就得到这个数了。
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int len = nums.size();
int i;
for(i=len-1;i>0;i--)
{
if(nums[i]>nums[i-1])
{
int j=i;
for(;j<len&&nums[j]>nums[i-1];j++);
swap(nums[j-1],nums[i-1]);
reverse(nums.begin()+i,nums.end());
break;
}
}
if(i==0)
sort(nums.begin(),nums.end());
}
};
514. 自由之路
- 深度搜索，超时
class Solution {
public:
int findRotateSteps(string ring, string key) {
return key.size() + min(Deep(ring,key,0,0,0),Deep(ring,key,0,0,1));
}
int Deep(string ring, string key,int ri,int ki,int direct)
{
if(ki==key.size())
return 0;
int i=0,k;
if(direct==0)
{
while(i<ring.size()&&ring[(ri+i)%ring.size()]!=key[ki]) i++;
k = (ri+i)%ring.size();
}
else
{
while(i<ring.size()&&ring[(ri+ring.size()-i)%ring.size()]!=key[ki]) i++;
k = (ri+ring.size()-i)%ring.size();
}
return i + min(Deep(ring,key,k,ki+1,0),Deep(ring,key,k,ki+1,1));
}
};
-动态规划，见题解
class Solution {
public:
int findRotateSteps(string ring, string key) {
vector<vector<int>> dp(key.size(),vector<int>(ring.size(),0x3f3f3f3f)) ;
vector<int> pos[26];
int m = key.size();
int n = ring.size();
for(int i=0;i<ring.size();i++)
{
pos[ring[i]-'a'].push_back(i);
}
for(auto & var :pos[key[0]-'a'])
{
dp[0][var] = min(var, n - var) + 1;
}
for(int i=1;i<key.size();i++)
{
for(auto & j : pos[key[i]-'a'])
{
for(auto &k :pos[key[i-1]-'a'])
dp[i][j] = min(dp[i][j],dp[i-1][k]+min(abs(j-k),(n-abs(j-k)))+1);
}
}
return *min_element(dp[dp.size() - 1].begin(), dp[dp.size() - 1].end());
}
};
922. 按奇偶排序数组 II
{% note warning simple %}
==的优先级要高于&，再用这两个符号求一个数的奇偶性的时候，&运算符两侧操作数外要加()
{% endnote %}
- 从开始遍历，找到奇数偶数两种分别不符合条件的数，进行交换。
class Solution {
public:
vector<int> sortArrayByParityII(vector<int>& A) {
int i=0,j=1;
while(i<A.size()&&j<A.size())
{
while(i<A.size()&&(A[i]&1)==0) i+=2;
while(j<A.size()&&(A[j]&1)==1) j+=2;
if((i<A.size()&&j<A.size()))
swap(A[i],A[j]);
i+=2;
j+=2;
}
return A;
}
};
328. 奇偶链表
- 有一点点像昨天的题目，一次遍历分别奇偶节点串起来，最后两个链表连接
class Solution {
public:
ListNode* oddEvenList(ListNode* head) {
if(!head)
return head;
ListNode *tail = head,*cur = head->next,*head2 = head->next;
while(cur&&cur->next)
{
tail->next = cur->next;
tail = tail->next;
cur->next = tail->next;
cur = cur->next;
}
tail->next = head2;
return head;
}
};
1122. 数组的相对排序
- 计数排序减少时间
class Solution {
public:
vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
unordered_map<int,int> map;
for(auto var:arr1)
{
auto it = map.find(var);
if(it==map.end())
map[var]=1;
else
map[var]++;
}
vector<int> res;
for(auto var:arr2)
{
res.insert(res.end(),map[var],var);
map.erase(var);
}
int x = res.size();
for(auto var:map)
res.insert(res.end(),var.second,var.first);
sort(res.begin()+x,res.end());
return res;
}
};
402. 移掉K位数字
- 从前向后遍历，如果前面一个数比后面大就将前面的这个数删掉。
- 前面一位变化的即使是 1 也比后面的变化为 9 的数变化大。
- 然后剩下的就是一些边界条件问题了。
class Solution {
public:
string removeKdigits(string num, int k) {
if(num.size()==k)
return "0";
int i;
for(i=0;i<num.size()-1; i++)
{
if(num[i]>num[i+1] && k>0)
{
num.erase(num.begin()+i);
k--;
if(i>0)
i--;
i--;
}
}
while(k-->0) num.erase(num.end()-1);
i=0;
while(i<num.size()-1&&num[i]=='0') i++;
num.erase(num.begin(),num.begin()+i);
return num;
}
};
406. 根据身高重建队列
- 以身高为第一关键字，个数为第二关键字排序，
- 插入结果vector中，从最矮的人开始，对于一个人(h,k)，此时前面还未插入的/vector为空的人的身高一定高于h，没经过一个空时，k-1，直到k==0的这个空位就是这个人(h,k)所应该在的位置。
1030. 距离顺序排列矩阵单元格
- 从目标所给点的曼哈顿距离为0开始，直到最大，每次将所有曼哈顿距离为此值的一圈矩阵值加到向量中。
class Solution {
public:
vector<vector<int>> allCellsDistOrder(int R, int C, int r0, int c0) {
vector<vector<int>>res;
res.push_back(vector<int>({r0,c0}));
for(int i=1;i<=R+C;i++)
{
for(int x=0;x<=i;x++)
{
int y = i-x;
int x1=r0+x,y1=c0+y;
int x2=r0+x,y2=c0-y;
int x3=r0-x,y3=c0+y;
int x4=r0-x,y4=c0-y;
if(x!=0&&y!=0)
{
if(x1>=0&&x1<R&&y1>=0&&y1<C)
res.push_back(vector<int>({x1,y1}));
if(x2>=0&&x2<R&&y2>=0&&y2<C)
res.push_back(vector<int>({x2,y2}));
if(x3>=0&&x3<R&&y3>=0&&y3<C)
res.push_back(vector<int>({x3,y3}));
if(x4>=0&&x4<R&&y4>=0&&y4<C)
res.push_back(vector<int>({x4,y4}));
}
else if(x==0)
{
if(x1>=0&&x1<R&&y1>=0&&y1<C)
res.push_back(vector<int>({x1,y1}));
if(x2>=0&&x2<R&&y2>=0&&y2<C)
res.push_back(vector<int>({x2,y2}));
}
else
{
if(x2>=0&&x2<R&&y2>=0&&y2<C)
res.push_back(vector<int>({x2,y2}));
if(x3>=0&&x3<R&&y3>=0&&y3<C)
res.push_back(vector<int>({x3,y3}));
}
}
}
return res;
}
};
134. 加油站
- 如果汽车从某个点开始，他必须能到达所有加油站，先假设汽车从某个加油站开始，如果能到达下一个加油站就继续走，如果不能就再假设从下一个加油站开始走
- 汽车总耗油量必须小于等于加油站能加的汽油和
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int run=0,all=0,begin=0;
for(int i=0;i<gas.size();i++)
{
run+=gas[i]-cost[i];
all+=gas[i]-cost[i];
if(run<0)
{
run=0;
begin=i+1;
}
}
if(all<0)
return -1;
return begin;
}
};
283. 移动零
- 双指针移动
- 对0进行计数，然后把数字发放到该放的位置
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int begin=0;
for(int i=0;i<nums.size();i++)
{
if(nums[i])
nums[begin++] = nums[i];
}
for(;begin<nums.size();begin++)
nums[begin]=0;
}
};
147. 对链表进行插入排序
- 插入排序转化成链表的形式，维护一个有序列表，每次选择未排序部分的一个值插入到有序列表中对应的位置。
class Solution {
public:
ListNode* insertionSortList(ListNode* head) {
if(!head) return head;
ListNode *cur = head->next,*pos = head;
pos->next=NULL;
while(cur!=NULL)
{
while(pos->next&&pos->next->val<cur->val) pos=pos->next;
if(pos->val>cur->val)
{
head=cur;
cur=cur->next;
head->next=pos;
pos=head;
}
else
{
ListNode *temp = cur;
cur=cur->next;
temp->next=pos->next;
pos->next=temp;
pos=head;
}
}
return head;
}
};
242. 有效的字母异位词
- 哈希表记录，然后判断两个是否相等
class Solution {
public:
bool isAnagram(string s, string t) {
vector<int> sc(26),tc(26);
for(auto c :s)
sc[c-'a']++;
for(auto c :t)
tc[c-'a']++;
for(int i=0;i<26;i++)
{
if(sc[i]!=tc[i])
return false;
}
return true;
}
};
452. 用最少数量的箭引爆气球
- 首先对气球数组进行排序，排序的第一个key是气球开始坐标，第二个key是气球结束坐标。
- 贪心，首先，尽量往气球的结束位置射，对于两个有重叠部分的气球，前面的结束位置一定是大于后面的开始位置的，对于这种有重叠部分的气球，射箭的位置取这两个气球中结束位置较小的结束位置。否则只能射一支新箭。
- 解析中直接对气球结束坐标排序的思路更简便一些。
class Solution {
public:
int findMinArrowShots(vector<vector<int>>& points) {
if(points.size()==0) return 0;
if(points.size()==1) return 1;
sort(points.begin(),points.end(),[&](vector<int> &x,vector<int> &y)
{
if(x[0]==y[0]) return x[1]<y[1];
return x[0]<y[0];
});
int arrs=1;
int end = points[0][1];
for(int i=1;i<points.size();i++)
{
if(points[i][0]>end)
{
arrs++;
end = points[i][1];
}
else
end = min(end,points[i][1]);
}
return arrs;
}
};
222. 完全二叉树的节点个数
- 暴力直接求解
- 利用完全二叉树的性质和位运算，首先找到二叉树的层数，根据完全二叉树的性质通过二分法找到树最底层的最后一个节点
class Solution {
public:
int countNodes(TreeNode* root) {
if(!root) return 0;
int n=0;
TreeNode* cur=root;
while(cur) {n++;cur=cur->left;}
int low = 1<<(n-1),high=(1<<n)-1,mid;
while(low<high)
{
mid = (high + low + 1) / 2 ;
if(Exist(root,n-1,mid))
low = mid;
else
high = mid-1;
}
return low ;
}
bool Exist(TreeNode *root,int lev,int pos)
{
int bit = 1<<(lev-1);
while(root&&bit)
{
if(bit&pos)
root = root->right;
else
root = root->left;
bit=bit>>1;
}
return root!=NULL;
}
};
1370. 上升下降字符串
- 先记录下字符的数量，然后来回放置。
class Solution {
public:
string sortString(string s) {
vector<int> cnt(26);
for(auto c:s)
cnt[c-'a']++;
int last = s.size();
string res = "";
while(res.size()<s.size())
{
for(int i=0;i<26;i++)
{
if(cnt[i]>0)
{
res+='a'+i;
cnt[i]--;
}
}
for(int i=25;i>=0;i--)
{
if(cnt[i]>0)
{
res+='a'+i;
cnt[i]--;
}
}
}
return res;
}
};
164. 最大间距
- 暴力法，map排序找最大间隔
class Solution {
public:
int maximumGap(vector<int>& nums) {
if(nums.size()<2) return 0;
map<int,bool> cnt;
for(auto num:nums)
{
cnt[num]=true;
}
int res=0,count=0;
auto begin = cnt.begin();
for(auto it=++cnt.begin();it!=cnt.end();it++)
{
res=max(res,(it->first)-(begin->first));
begin=it;
}
return res;
}
};
- 使用桶排序完成数组在时间复杂度n内的排序，然后找到结果
454. 四数相加 II
- 先计算前两个组中的数相加，存到哈希表中，在计算后两个组中的数相加时，在哈希表中查看是否有四组之和为0的
class Solution {
public:
int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
int res=0;
unordered_map<int,unsigned short int> CD;
for(int i=0;i<C.size();i++)
{
for(int j=0;j<D.size();j++)
{
CD[C[i]+D[j]]++;
}
}
for(int i=0;i<A.size();i++)
{
for(int j=0;j<B.size();j++)
{
if(CD.find(-A[i]-B[j])!=CD.end())
res+=CD[-A[i]-B[j]];
}
}
return res;
}
};
976. 三角形的最大周长
- 先排序，然后从长的边开始，找符合三角形的三条边
class Solution {
public:
int largestPerimeter(vector<int>& A) {
sort(A.begin(),A.end());
for(int i=A.size()-1;i>1;i--)
if(A[i-1]+A[i-2]>A[i])
return A[i]+A[i-1]+A[i-2];
return 0;
}
};
767. 重构字符串
- 先判断字符串能否重构，出现次数最多的不能超过总数的一半(上取整)
- 然后以出现次数最多的字符构成字符串，其他的字符往这个字符串插入
class Solution {
public:
string reorganizeString(string S) {
vector<int> cnt(26);
string res;
int max_num=0;
for(auto c :S)
{
cnt[c-'a']++;
max_num = max(max_num,cnt[c-'a']);
}
if(2*max_num>S.size() + 1)
return "";
for(int i=0;i<cnt.size(); i++)
if(max_num==cnt[i])
{
res = string(max_num,i+'a');
cnt[i]=0;
break;
}
int pos=1;
for(int i=0;i<cnt.size(); i++)
{
while(cnt[i]--)
{
res.insert(pos,1,'a'+i);
pos+=2;
if(pos>res.size())
pos=1;
}
}
return res;
}
};