首先建立对字符串t的哈希映射，这题用到了滑动窗口的思想。假设字串是ABC，如果主串是AAABBC，那么只有到最后一位的时候才能满足。而当满足的时候，我们可以建立一个左指针，他会逐渐右移，直到不满足哈希映射退出。这里注意，不能每次左指针右移都去做substr，会超出内存限制。可以用一个differ来存储不同的数目，把每次check哈希表是否都为0的时间从O(n)降低到O(1),代码如下
class Solution {
public:
string minWindow(string s, string t) {//必须包含t中其中一个字母才能开头
int n=s.size(),m=t.size();
unordered_map<char,int> mp;
int differ=0,r=0,l=0;
int ans=0x3f3f3f3f;
for(int i=0;i<m;i++)
{
if(mp.find(t[i])==mp.end())differ++;
mp[t[i]]++;
}
string s1;
int ansl=-1;
for(r=0;r<n;r++)
{
if(mp.count(s[r])&&--mp[s[r]]==0) differ--;
while(differ==0&&l<=r)
{
if(r-l+1<ans)
{
ans=r-l+1;
ansl=l;
}
if(mp.count(s[l])&&++mp[s[l]]>0)differ++;
l++;
}
}
if(ans==0x3f3f3f3f)return "";
return s.substr(ansl,ans);
}
};做法1：想像一个最大子数组，必然需要加上一个正数。当前位置的最大子数组是什么呢，如果加上当前位置的数字之后，数组更大了，或者说 大于当前这里的数字，那么就选择。其实就是动态规划的思想。这里也不需要开一个数组，可以利用类似滚动数组的思想，只开一个pre就够了
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int pre=0;
int ans=-0x3f3f3f3f;
for(auto &x:nums)
{
pre=max(pre+x,x);
ans=max(ans,pre);
}
return ans;
}
};做法2：线段树解法 虽然因为递归，时间复杂度和空间复杂度都不如做法一优秀，但这个方法可以求解任意区间。感觉自己还是有进步的，之前根本不会线段树，现在都可以很快写出来了
const int N要在类外定义。这里要么在类外定义，要么类内加上static
const int N=1e5+5;
class Solution {
public:
//const int N=1e5+5;
struct tree
{
int l,r;
int lsum,rsum,sum,msum;
}tr[N<<2];
void pushup(int s)
{
int ls=s<<1,rs=s<<1|1;
tr[s].lsum=max(tr[ls].lsum,tr[ls].sum+tr[rs].lsum);
tr[s].rsum=max(tr[rs].rsum,tr[rs].sum+tr[ls].rsum);
tr[s].sum=tr[ls].sum+tr[rs].sum;
tr[s].msum=max(max(tr[ls].msum,tr[rs].msum),tr[ls].rsum+tr[rs].lsum);
}
void build(int l,int r,int id,vector<int>& nums)
{
tr[id].l=l;
tr[id].r=r;
if(l==r)
{
tr[id].sum=tr[id].lsum=tr[id].rsum=tr[id].msum=nums[l];
return;
}
int mid=(l+r)>>1;
build(l,mid,id<<1,nums);
build(mid+1,r,id<<1|1,nums);
pushup(id);
}
int maxSubArray(vector<int>& nums) {
build(0,nums.size()-1,1,nums);
return tr[1].msum;
}
};做法：这题在acwing算法基础课有，所以做起来很快。先给vector排序，按照左端点，空间复杂度O(logn)，时间复杂度O(nlogn)，然后遍历一遍vector即可。最后跳出循环后，不要忘记再push_back一次。
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(),intervals.end());//左端点从小到大排序
int rp=-1;
int lp=-1;
vector<vector<int>> vec;
for(const auto&x:intervals)
{
if(rp==-1&&lp==-1)
{
lp=x[0];
rp=x[1];
continue;
}
if(x[0]<=rp)
{
rp=max(rp,x[1]);//合并
}
else
{
vec.push_back({lp,rp});
lp=x[0],rp=x[1];
}
}
vec.push_back({lp,rp});
return vec;
}
};做法一：开额外的空间，assign一下就好了
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n=nums.size();
vector<int> newarr(n);
for(int i=0;i<n;i++)newarr[(i+k)%n]=nums[i];
nums.assign(newarr.begin(),newarr.end());
}
};做法二：
假设转了a圈回到当前位置，那么a*n就是走过的距离=b（每次遍历的元素）*k也就是步数*步距
每次循环都只需要一个变量prev来交换就可以了。
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n=nums.size();
k%=n;
int count=gcd(k,n);
for(int i=0;i<count;i++)
{
int current=i;
int prev=nums[i];
do
{
int next=(current+k)%n;
swap(nums[next],prev);
current=next;
}while(i!=current)
}
}
};做法三：翻转数组，k%=n,那么后k个元素会被移动到开头，所以只需要整体翻转之后，再翻转头部和尾部就可以啦
class Solution {
public:
void rotate(vector<int>& nums, int k) {
k%=nums.size();
reverse(nums.begin(),nums.end());
reverse(nums.begin(),nums.begin()+k);
reverse(nums.begin()+k,nums.begin()+nums.size());
}
};
做法一，因为题目不让用除法。如果暴力的话复杂度达到O(n^2)，所以不妨采用预处理前缀后缀积的方法。
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n=nums.size();
vector<int> L(n,0),R(n,0);
vector<int> answer(n);
L[0]=1;
for(int i=1;i<n;i++)L[i]=L[i-1]*nums[i-1];
R[n-1]=1;
for(int i=n-2;i>=0;i--)R[i]=R[i+1]*nums[i+1];
for(int i=0;i<n;i++)answer[i]=L[i]*R[i];
return answer;
}
};做法二：其实差不多，只是更节省内存了而已，小优化
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n=nums.size();
vector<int> answer(n);
answer[0]=1;
for(int i=1;i<n;i++)answer[i]=nums[i-1]*answer[i-1];
int R=1;
for(int i=n-1;i>=0;i--)
{
answer[i]=answer[i]*R;
R*=nums[i];
}
return answer;
}
};做法：首先 这个数字一定在[1,n+1]之间，因为如果n数组为[1,n]，那么就为n+1，否则的话就是[1,n]。因为这道题没有办法用哈希表，也不能用双重循环，所以就要利用已有的空间进行类似哈希表的标记。如果我们想让整数1被标记已经出现过了，我们没有办法改变数组值，但是可以加上负号，让nums[0]=-abs(nums[0])即可，后面再进行一次循环，只要读到一个负数，那么这个位置就是答案。
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int n=nums.size();
for(int &num:nums)
{
if(num<=0)num=n+1;
}
for(int i=0;i<n;i++)
{
int num=abs(nums[i]);
if(num<=n)nums[num-1]=-abs(nums[num-1]);
}
for(int i=0;i<n;i++)
{
if(nums[i]>0)return i+1;
}
return n+1;
}
};做法二：还是要利用这个数组，假如存在数字3，那么就和数组nums[3-1]元素交换，直到该位置元素不属于[1,n]，要注意要在相等的时候跳出循环。如果最后某个位置一直没有换。那么说明，这个位置不存在对应元素
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int n=nums.size();
for(int i=0;i<n;i++)
{
while(nums[i]>0&&nums[i]<=n&&nums[nums[i]-1]!=nums[i])
{
swap(nums[nums[i]-1],nums[i]);
}
}
for(int i=0;i<n;i++)
if(nums[i]!=i+1)return i+1;
return n+1;
}
};做法一：直接暴力
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m=matrix.size();
int n=matrix[0].size();
vector<int> row(m),col(n);
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(!matrix[i][j])row[i]=col[j]=true;
}
}
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(row[i]||col[j])matrix[i][j]=0;
}
}
}
};做法二：之前的做法需要O(m+n)的空间，但其实可以缩减到常量级空间，所以，我们必须要利用已经存在的空间。先开两个常量，用来判断第一行和第一列需不需要全部置0，然后用第一行第一列来判断。如果某一位置的元素为0，那么第一行第一列对应元素置0，如果本来就为0，那也是一样的。
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
bool flag_row=false,flag_col=false;
int n=matrix.size();//行
int m=matrix[0].size();//列;
for(int i=0;i<m;i++)
{
if(matrix[0][i]==0)
{
flag_row=true;
break;
}
}
for(int i=0;i<n;i++)
{
if(matrix[i][0]==0)
{
flag_col=true;
break;
}
}
for(int i=1;i<n;i++)
for(int j=1;j<m;j++)
if(matrix[i][j]==0)
matrix[i][0]=matrix[0][j]=0;
for(int i=1;i<n;i++)
for(int j=1;j<m;j++)
if(matrix[i][0]==0||matrix[0][j]==0)
{
matrix[i][j]=0;
}
if(flag_row)
for(int i=0;i<m;i++)matrix[0][i]=0;
if(flag_col)
for(int i=0;i<n;i++)matrix[i][0]=0;
}
};做法一：设计一个标记数组即可，因为每次转向方向固定，所以可以用一个数组来存储要转向的方向，变动方向的时候只需要加一即可
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
if(matrix.size()==0||matrix[0].size()==0)return {};
int rows=matrix.size(),cols=matrix[0].size();
vector<vector<bool>> visited(rows,vector<bool>(cols,false));
int count=rows*cols;
vector<int> ans(count);
int row=0,col=0;
int index=0;
for(int i=0;i<count;i++)
{
ans[i]=matrix[row][col];
visited[row][col]=true;
int nerow=row+dir[index][0],necol=col+dir[index][1];
if(nerow<0||nerow>=rows||necol<0||necol>=cols||visited[nerow][necol])
index=(index+1)%4;
row+=dir[index][0];
col+=dir[index][1];
}
return ans;
}
};做法二：不开标记数组，直接设置四个指针，然后遍历。要注意的是，需要考虑一种情况，[[2],[3]]，也就是一列下来有两行，如果不特判一下，下面会多存
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
if(matrix.size()==0||matrix[0].size()==0)return {};
int rows=matrix.size(),columns=matrix[0].size();
vector<int> ans;
int left=0,right=columns-1,top=0,bottom=rows-1;
while(left<=right&&top<=bottom)
{
for(int column=left;column<=right;column++)
{
ans.push_back(matrix[top][column]);
//cout<<1;
}
for(int row=top+1;row<=bottom;row++)
{
ans.push_back(matrix[row][right]);
//cout<<2;
}
if(right>left&&bottom>top)
{
for(int column=right-1;column>left;column--)
{
ans.push_back(matrix[bottom][column]);
//cout<<3;
}
for(int row=bottom;row>top;row--)
{
ans.push_back(matrix[row][left]);
//cout<<4;
}
}
left++;
right--;
top++;
bottom--;
}
return ans;
}
};做法一：需要额外空间的做法。观察可得式子。每一行九十度旋转后，都对应旋转后的一列。满足matrix[row][col]->matrix_new[col][n-row-1]
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n=matrix.size();
auto m1=matrix;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
m1[j][n-i-1]=matrix[i][j];
}
matrix=m1;
}
};做法二：不需要额外矩阵空间.但需要注意 当为奇数的时候 (n^2-1)/4=(n+1)/2*(n-1)/2。
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n=matrix.size();
for(int i=0;i<n/2;i++)
for(int j=0;j<(n+1)/2;j++)
{
int temp=matrix[i][j];
matrix[i][j]=matrix[n-j-1][i];
matrix[n-j-1][i]=matrix[n-i-1][n-j-1];
matrix[n-i-1][n-j-1]=matrix[j][n-i-1];
matrix[j][n-i-1]=temp;
}
}
};做法三：进行翻转.我们画一个简单图就能发现，先进行水平轴翻转再进行主对角线（左上到右下）翻转就能得到相应翻转矩阵。推导如下
水平轴翻转：matrix[row][col]->matrix[n-row-1][col]
主对角线翻转：matrix[n-row-1][col]->matrix[col][n-row-1]。这其实就和那个式子一样了
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n=matrix.size();
for(int i=0;i<n/2;i++)
{
for(int j=0;j<n;j++)
{
swap(matrix[i][j],matrix[n-i-1][j]);
}
}
for(int i=0;i<n;i++)
for(int j=0;j<i;j++)
swap(matrix[i][j],matrix[j][i]);
}
};解法一：对每一行二分，时间复杂度O(mlogn)，空间复杂度O(1)，用lower_bound，其本质就是二分。代码如下
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
for(const auto &row:matrix)
{
auto it=lower_bound(row.begin(),row.end(),target);
if(it!=row.end()&&*it==target)return true;
}
return false;
}
};解法二： 从矩阵右上角开始判断，这个真的有点难想
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m=matrix.size(),n=matrix[0].size();
int x=0,y=n-1;
while(x<m&&y>=0)
{
if(matrix[x][y]==target)return true;
if(matrix[x][y]>target)y--;
else x++;
}
return false;
}
};做法一：曾经不知道什么时候做过，哎，大一的时候为啥不好好努力呢。用一个set来存储，一个先遍历，然后每个都存入，另外一个逐渐遍历即可
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
unordered_set<ListNode*>visited;
ListNode *temp=headA;
while(temp!=nullptr)
{
visited.insert(temp);
temp=temp->next;
}
temp=headB;
while(temp!=nullptr)
{
if(visited.count(temp))return temp;
temp=temp->next;
}
return nullptr;
}
};做法二：双指针，分别遍历两条链表，这个真的太妙了。力扣官方的题解解释的很清楚
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if(headA==NULL||headB==NULL)return NULL;
ListNode *pa=headA,*pb=headB;
while(pa!=pb)
{
pa=pa==NULL?headB:pa->next;
pb=pb==nullptr?headA:pb->next;
}
return pb;
}
};4.1 22：02结束今日学习，还是得提高效率，加油，争取能在这周清明假期结束之前结束一百题