Q1-合并k个排序列表⚠️⚠️⚠️
暴力解法：直接把所有的列表全部合并，然后用sort(),其时间复杂度是$O(n\log n)$
Q2-反转链表
link
话说我写这个题的时候，非常靠直觉？一开始写的是return curr;然后报错，然后就先改成了prev，提交通过。然后通过了之后开始想，为什么return prev是对的：应该是走到最后的时候curr=nullptr了，反倒是prev才存的是最后一个节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* prev=head;
ListNode* curr=head;
while(curr!=nullptr){
ListNode* tmp=nullptr;
if(curr->next!=nullptr)tmp=curr->next;
if(prev==curr)curr->next=nullptr;
else curr->next=prev;
prev=curr;
curr=tmp;
}
return prev;
}
};
|
Q3-使数组和能被p整除
link
思路：我得到前缀和数组 s，遍历 curr，找一个最靠近 curr 的 prev，使得 (s[curr] - s[prev]) % p == x， 也就是 s[prev] % p == (s[curr] - x + p) % p，用 curr - prev 更新最小长度。
TLE版本：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
复杂度分析
class Solution {
public:
int minSubarray(vector<int>& nums, int p) {
bool flag=false;
int min_cnt=nums.size();
int x=0;
for(int i=0;i<nums.size();i++){
x=(x+nums[i]%p)%p;
}
if(x==0)return 0;
for(int i=0;i<nums.size();i++){
int y=0;
int cnt=0;
for(int j=i;j<nums.size();j++){
y+=nums[j];cnt++;
cout<<"y: "<<y<<" p:"<<p<<" x:"<<x<<" cnt:"<<cnt<<" min cnt:"<<min_cnt<<endl;
if(y%p==x&&cnt!=nums.size()){
flag=true;
if(cnt<min_cnt)min_cnt=cnt;
}
}
}
if(!flag)return -1;
else return min_cnt;
}
};
|
AC版本：卡在了为什么要加hash表last很长时间，最后大概理解了随循环的话，每一步添加或者是修改了对应的前缀和的值，使得得到的是prev_sum[prev],然后现在遍历prev_sum[curr]是否存在。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
int minSubarray(vector<int>& nums, int p) {
vector<int> prev_sum(nums.size()+1);
prev_sum[0]=0;
int x=0;
for(int i=0;i<nums.size();i++){
x=(x+nums[i]%p)%p;
prev_sum[i+1]=x;
}
if(x==0)return 0;
int ans=nums.size();
unordered_map<int,int> last;
for(int i=0;i<nums.size()+1;i++){
auto it=last.find((prev_sum[i]-x+p)%p);
if(it!=last.end()){
ans=min(ans,i-it->second);
}
last[prev_sum[i]]=i;
}
return ans<nums.size()?ans:-1;
}
};
|
33.搜索旋转排序数组
link
思路：重点在于mid的一侧一定是有序的。而且有nums[l]>num[r]必然成立。需要注意的是在有序的判定后，target可能等于nums[r]/nums[l],千万不要遗漏这种情况。这个题还是我上次面试做的。。上次就没搞清楚边界条件。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
int search(vector<int>& nums, int target) {
int l=0;
int r=nums.size()-1;
while(l<=r){
int m=(l+r)/2;
if(target==nums[m])return m;
if(nums[m]>=nums[l]){
//mid左边有序
if(target>=nums[l]&&target<nums[m])r=m-1;
else l=m+1;
}
else {
//mid右边有序
if(target>nums[m]&&target<=nums[r])l=m+1;
else r=m-1;
}
}
return -1;
}
};
|
