原创Posted 2023-08-07Updated 2024-10-08数据结构33 minutes read (About 4959 words)0 visits

leetcode100题_2

版权申明：本文为原创文章，转载请注明原文出处

原文链接：http://example.com/post/266d9ac.html

leetcode100题_2

leetcode必做100题第二部分

多数元素（简单）

题目描述

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

知识点

找到哈希的最大键值及索引

//定义比较的函数
bool cmp_value(const pair<int, int> left,const pair<int,int> right){
	return left.second < right.second;
}
 
int main(){
	map<int, int> test;
	//初始化
	test.emplace(10, 5);
	test.emplace(3, 17);
	test.emplace(19, 20);
	test.emplace(20, 15);
	//输出按序排列的key值
	for (auto it : test)
		cout << it.first << " ";
	cout << endl;
	//i是迭代器  返回值为19-20
	auto i= max_element(test.begin(),test.end(),cmp_value);
	cout << i->first << i->second << endl;
}

思路（两个思路）

思路一

用哈希，键是元素，值是元素在数组中的次数，也就是遍历一次数组，时间空间复杂度均为n

代码一

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int,int>hash;
        for(int i:nums){
            hash[i]++;
        }
        auto i = max_element(hash.begin(), hash.end(), [](const auto& p1, const auto& p2){
       return p1.second < p2.second;
   });
        return i->first;
    }
};

思路二：Boyer-Moore 投票算法

我在这里对这个算法有一个另外的解释，比如在一个数组中，7是这个数组中的众数，现在我们随机删除两个不同的数，最后留下来的肯定就都是众数，考虑两种极端情况，只删除不是众数的值，很显然符合，如果都删除是众数的值，但是众数的值已经超过了一半，而且我们考虑的是删除两个不同的值，所以就算其他值删完了，众数还存在

代码删除值的方式为记录一个值出现的次数，遇到相同的次数加一，遇到不同的减一，最后变为0就相当于删除了和它同等数量的不同的值，再进行新一轮，记录新的值出现的次数，最后剩下的肯定是众数

代码二

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate=nums[0];
        int count=0;
        for(int number:nums){
            if(candidate==number){
                count++;
            }else{
                if(count>0){
                    count--;
                }else{
                    candidate=number;
                    count=1;
                }
            }
        }
        return candidate;
    }
};

轮转数组（中等）

题目描述

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

思路

思路一

最简单的思路，将数组复制，再移动

时间复杂度为O(n)，空间复杂度为O(n)

代码一

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        vector<int> numcopy(nums.begin(),nums.end());
        int length=nums.size();
        for(int i=0;i<length;i++){
            nums[(i+k)%length]=numcopy[i];
        }
    }
};

思路二

绞尽脑汁想出来的哈哈哈

大概思路是选一个点进行移动，移动到最后肯定会返回值到最初的那个点，然后记录下移动过的数离自己最近的点，下次移动就移动这一个区间就可以了，移动的思路就是tempo2记录i位置的值，tempo1记录i+k位置的值，i+k换成tempo2，tempo2更新为tempo1，直到最后要更新的位置是起始点

时间复杂度为O(n)，空间复杂度为O(1)

代码二

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int length=nums.size();
        if(k==0||length==1){
            return;
        }
        int tempo1;
        int tempo2;
        int add=k;
        int start;
        for(int i=0;i<add;i++){
            start=i;
            tempo2=nums[i];
            while((start+k)%length!=i){
                add=min(add,(start+k)%length);
                tempo1=nums[(start+k)%length];
                nums[(start+k)%length]=tempo2;
                tempo2=tempo1;
                start+=k;
            }
            nums[i]=tempo2;
        }
    }
};

除自身以外数组的乘积（中等）

题目描述

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请不要使用除法，且在 O(*n*) 时间复杂度内完成此题。

思路

由于规定了时间复杂度，所以我们得知只能遍历能计算数量次数的数组

先说说lz最开始的思路：用两个数组，用遍历一次分别存储前i位和后i位的乘积，再遍历到最后算某个数的时候，就用前后相乘就可以了，总共两次遍历，大概如下方代码所示：

1	ans.push_back(begin[i-1]*end[length-2-i]);

但是这样时间和内存只打败了不到百分之十的人，于是lz再次思考，两次循环肯定不能省，因为对于某一个元素的前面的乘积和后面的乘积没办法一次算完，应该从内存上下手，可以看到我定义了三个数组，结果ans数组可以不管，begin和end应该是可以省掉的，在计算begin的时候，我是通过从前往后遍历数组，然后算前面的累计乘积，这个顺序和最后算ans的顺序是一样的，所以可以把begin的计算过程放在后面，也就是遍历得到ans的时候，顺便算begin，代码如下：

1 2	begin=nums[i-1];//begin累计乘 ans.push_back(beginend[length-2-i]);

这样的时间复杂度确实下降了，但是不够理想，再次思考能不能把end去了，既然begin可以用累计的方式计算，不用存每一次计算的结果，计算之后就直接用，那end应该也可以！我们知道end是从后往前遍历的，那就让我们的ans再从后往前遍历，乘上end，让end每次都有用，代码如下：

1 2	end=nums[i+1]; ans[i]=end;

最后的时间和空间效果都比较理想

代码

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int begin=1;
        int end=1;
        int length=nums.size();
        vector<int>ans(length,1);
        for(int i=0;i<length;i++){
            if(i==0){
                ans[i]=1;
            }else{
                begin*=nums[i-1];
                ans[i]=begin;
            }
        }
        for(int i=length-2;i>=0;i--){
            end*=nums[i+1];
            ans[i]*=end;
        }
        return ans;
    }
};

缺失的第一个正数（困难）

题目描述

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

思路（两种思路）

思路一

by myself

排序
去重
找缺失值

这种方法时间复杂度不合要求

代码一

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int first=0;
        sort(nums.begin(),nums.end());
        nums.erase(unique(nums.begin(),nums.end()),nums.end());
        int length=nums.size();
        for(int i=0;i<length;i++){
            if(nums[i]>0){
                if(first==0){
                    if(nums[i]!=1){
                        return 1;
                    }
                    first=1;
                }
                if(nums[i]!=1&&nums[i]!=nums[i-1]+1){
                    return nums[i-1]+1;
                }
            }
        }
        if(nums[length-1]+1<=0){
            return 1;
        }
        return nums[length-1]+1;
    }
};

思路二

将原数组进行排序，我们可以根据题目得到，最后要得到的那个数前面的数一定都是排序好了的，所以，可以在原数组上进行排序，但是为了不缺失数据，排序的方式是：将下标作为排序的排名，当然肯定会有些值无法找到对应地点，这种值也不用管，我们只能确认我们要求的那个值前面的值一定都是排序好了的，找到第一个不能正确排序的位置就行了，大概步骤如下：

遍历数组，将数组中的值和应该存放的地方进行交换，比如0存的是3，2存的是4，3存的是1（我们是为了找到正数，所以排序就让0存1，1存2）
首先0存的值不是1，把3和下标为3-1=2的位置的值进行交换，0存的就变成4，也不规范，就和4-1=3的下标的值进行交换，最后0存的就变成1了，以此类推

代码二

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int length=nums.size();
        for(int i=0;i<length;i++){
                while(nums[i]>0&&nums[i]!=i+1&&nums[i]<length&&nums[i]!=nums[nums[i]-1]){
                    swap(nums[i],nums[nums[i]-1]);
                }
            
        }
        for(int i=0;i<length;i++){
            if(nums[i]!=i+1){
                return i+1;
            }
        }
        return nums[length-1]+1;
    }
};

二叉树展开为链表(中等)

题目描述

给你二叉树的根结点 root ，请你将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。

思路（两种思路）

思路一

规规矩矩前序遍历，由于要求在原链表上本地操作，前序遍历是先遍历左边，再遍历右边，所以我先把存的值放在左边，最后再统一移到右边

代码一

class Solution {
public:
    TreeNode* ans = new TreeNode(); // 使用括号调用构造函数
    void pre(TreeNode* root){
        if(root==NULL){
            return;
        }
        ans->left=root;
        ans=ans->left;
        pre(root->left);
        pre(root->right);
    }
    void flatten(TreeNode* root) {
        if(root==NULL){
            return;
        }
        pre(root);
        ans=root;
        while(ans){
            ans->right=ans->left;
            ans->left=NULL;
            ans=ans->right;
        }
    }
};

思路二

反前序遍历，和前面前序遍历相反，先遍历右边，再遍历左边，记录上次遍历的节点

代码二

class Solution {
public:
    TreeNode* preNode;
    void flatten(TreeNode* root) {
        if (root == NULL) return;
        flatten(root->right);
        flatten(root->left);
        root->left = NULL;
        root->right = preNode;
        preNode = root;
    }
};

最小覆盖字串（困难）

题目描述

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

思路

定义收缩指针i，扩张指针j
首先j往后扩，直到i和j之内的字符串包含了t中所有字符
i往后缩，获得最小的符合标准的字符串
记录长度
i再往后缩一格，重复步骤一，将得到的长度和前面得到的长度进行对比，取最小值

重点在于如何判断i和j之内的字符串包含了t中所有字符：我采取的是设置一个哈希表，键是字符，值是字符在t中出现的次数，也就是需要的次数，同时设置needcnt表示还需要几个字符，j每往后移一格，哈希表对应字符就减1，如果增加的字符刚好的需要的字符，needcnt就减一，直到needcnt等于0即代表该段字符串包含所有需要字符，i每往后移一格，哈希表对应字符就加一，同时保证所以字符都不需要，就是都小于0，不等于0是因为保证出现一次，但是尽量不重复

代码

class Solution {
public:
    string minWindow(string s, string t) {
        vector<int>ans(2,0);
        ans[1]=INT_MAX;
        unordered_map<char,int>hashmap;
        for(char ch:t){
            hashmap[ch]++;
        }
        int needcnt=t.size();
        for(int i=0,j=0;i<s.size() && j<s.size();)
        {
            while(j<s.size()&&needcnt>0){
                if(hashmap[s[j]]>0){
                    needcnt--;
                }
                hashmap[s[j]]--;
                j++;
            }
            while(i<s.size()&&hashmap[s[i]]<0){
                hashmap[s[i]]++;
                i++;
            }
            if(needcnt==0&&j-i<ans[1]-ans[0]){
                ans[1]=j;
                ans[0]=i;
            }
            hashmap[s[i]]++;
            needcnt++;
            i++;
        }
        return ans[1]-ans[0]==INT_MAX?"":s.substr(ans[0],ans[1]-ans[0]);
    }
};

滑动窗口最大值（困难）

题目描述

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

知识点

优先队列：
- 升序队列，小根堆：priority_queue <int,vector<int>,greater<int> > p;
- 降序队列，大根堆：priority_queue <int,vector<int>,less<int> >q;
- 对于基础数据类型，默认是大顶堆：priority_queue<int> r; //等同于 priority_queue<int, vector<int>, less<int> > r;
pair：
- pair将两个数据（经常为不同数据类型）组合成一组数据。
- pair的实现是一个结构体，主要的两个成员变量是first、second。
优先队列+pair：
- priority_queue<pair<int, int> > a;：
- pair的比较规则：先比较第一个元素，第一个相等比较第二个。 6 1 1 5 1 2
vector访问最后一个元素：
1
vec.back();

思路（三种思路）

思路一：暴力求解

——会超时

每一轮就更新一次最大值下标的位置
在新加入的元素比原最大值下标大的情况直接将最大值下标设为新加入元素位置

代码一

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int length=nums.size();
        if(length<=k){
            return {*max_element(nums.begin(),nums.end())};
        }
        int maxindex;
        vector<int> ans(length-k+1);
        for(int i=0;i+k-1<length;i++){
            if(i==0||(nums[i+k-1]<nums[maxindex]&&maxindex<i)){
                maxindex=i+distance(nums.begin()+i,max_element(nums.begin()+i,nums.begin()+i+k));
            }else{
                if(nums[i+k-1]>=nums[maxindex]){
                    maxindex=i+k-1;
                }
            }
            ans[i]=nums[maxindex];
        }
        return ans;
    }
};

思路二：优先队列+pair

队列里存数据对，正如前面所言，会根据pair的第一个元素排列，接着是第二个，再每次进入新元素的时候，先将新元素插入，然后取队列的最大值，但是这里要先比较队列的最大值的索引是否已经小于了滑动窗口的最小索引，小于了就去除顶元素，用while

代码二

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int length=nums.size();
        vector<int> ans(length-k+1);
        priority_queue<pair<int,int>>maxindex;
        for(int i=0;i<k;i++){
            maxindex.emplace(nums[i],i);
        }
        ans[0]=maxindex.top().first;
        for(int i=k;i<length;i++){
            maxindex.emplace(nums[i],i);
            while(!maxindex.empty()&&maxindex.top().second<=i-k){
                maxindex.pop();
            }
            ans[i-k+1]=maxindex.top().first;
        }
        return ans;
    }
};

思路三：思路二的进阶

在插入元素的时候比较一下，如果插入的元素比原队列的某些元素大，原队列的某些元素可以永久剔除掉，那些元素没被删时，插入的元素肯定也没被删，但是如果取最大的元素也不可能是那些比插入元素小的数，这里如果只比较对头则效果不好，因为如果都比队头大了那肯定就是最大的了，队列都可以删了，这种情况很少见，所以要比较队尾，这里就要用双端队列，这里只存下标

这种情况下相当于插在队尾，将队尾比自己小的都删了，这样也相当于手工进行排列，(感觉也可以用vector：经实验不行，vector相当于动态数组，不能很好的删除第一个元素，浪费时间和空间)

代码三

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int length=nums.size();
        deque<int> maxindex;
        vector<int>ans(length-k+1);
        maxindex.push_back(0);
        for(int i=1;i<k;i++){
            while(!maxindex.empty()&&nums[i]>=nums[maxindex.back()]){
                maxindex.pop_back();
            }
            maxindex.push_back(i);
        }
        ans[0]=nums[maxindex.front()];
        for(int i=k;i<length;i++){
            while(!maxindex.empty()&&nums[i]>=nums[maxindex.back()]){
                maxindex.pop_back();
            }
            maxindex.push_back(i);
            while(maxindex.front()<=i-k){
                maxindex.pop_front();
            }
            ans[i-k+1]=nums[maxindex.front()];
        }
        return ans;
    }
};

最小栈（中等）

题目描述

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

知识点

栈的定义及基本使用：

stack<int> stk;
s.empty()               如果栈为空返回true，否则返回false
s.size()                返回栈中元素的个数
s.pop()                 删除栈顶元素但不返回其值
s.top()                 返回栈顶的元素，但不删除该元素
s.push()                在栈顶压入新元素

思路(两种思路)

思路一：栈+队列

用队列来存储当前的最小值，大概思路如下：先加入第一个元素，接着对每个加进来的元素进行判断，如果加进来的元素比队列第一个元素大，那么最小值就不可能返回这个值，就不将其加在队列中，如果比第一个元素小就加在队列中，这样队列的第一个元素一定是最小值，接着如果要对栈顶部元素进行删除，如果栈顶部元素为队列第一个元素，则队列也删除第一个元素就行了，返回最小值永远是队列的第一个元素

代码一

class MinStack {
public:
    stack<int> num;
    deque<int> minnum;
    MinStack() {
    }
    void push(int val) {
        num.push(val);
        if(minnum.empty()||val<=minnum.front())minnum.push_front(val);
    }
    void pop() {
        int topnum=num.top();
        num.pop();
        if(topnum==minnum.front())minnum.pop_front();
        
    }
    int top() {
        return num.top();
    }
    int getMin() {
        return minnum.front();
    }
};

思路二：栈

栈里面既存元素又存加入该元素后的最小值，只需要在加入元素的时候比较一下，如果加入的元素比上一个元素最小值小就更新

代码二

class MinStack {
public:
    stack<pair<int, int>> st;
    MinStack() {
    }
    
    void push(int x) {
        if (st.size() == 0) {
            st.push({x, x});
        } else {
            st.push({x, min(x, st.top().second)});
        }
    }
    void pop() {
        st.pop();
    }
    int top() {
        return st.top().first;
    }
    int getMin() {
        return st.top().second;
    }
};

最大子数组和（中等）

题目描述

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

思路

动态规划：遍历数组，记录到该值时右侧的最大连续数和，就是到前一个数最大连续数和加上该值，如果比该值更大，就记录该和是到该值的最大连续数和，用一个值存所有连续数和的最大值

代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxbypreindex=nums[0];
        int maxnum=maxbypreindex;
        int length=nums.size();
        for(int i=1;i<length;i++){
            maxbypreindex=max(maxbypreindex+nums[i],nums[i]);
            maxnum=max(maxbypreindex,maxnum);
        }
        return maxnum;
    }
};

下一个排列（中等）

题目描述

整数数组的一个排列就是将其所有成员以序列或线性顺序排列。

例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。

整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。

给你一个整数数组 nums ，找出 nums 的下一个排列。

必须原地修改，只允许使用额外常数空间。

知识点

反转数组

vector<int> reverseArray(vector<int> a)
{
    reverse(a.begin(),a.end());
    return a;
}

思路

用两个下标i,j，i从length-1开始往前，j从i前一个开始往前
记录nums[i]>nums[j]最大的j和i
交换两者数字，对后面数字进行排列，即得到结果
由于i就是从最大到最小不用管，找最大的j即可

代码

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        vector<int>ans(2,-1);
        int length=nums.size();
        for(int i=length-1;i>=1;i--){
            for(int j=i-1;j>=0;j--){
                if(j<ans[0]||nums[j]<nums[i]){
                    if(j>ans[0]){
                        ans[0]=j;
                        ans[1]=i;
                    }
                    break;
                }              
            }
        }
        if(ans[0]==-1){
            reverse(nums.begin(),nums.end());
        }else{
            swap(nums[ans[0]],nums[ans[1]]);
            sort(nums.begin()+ans[0]+1,nums.end());
        }
        return;
    }
};

字符串解码(中等)

题目描述

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

知识点

字符串拼接

1
2
3

string s1 = "alan";
string s2 = "xiho";
string s3 = s1 + s2;

字符串复制: 假设str1和str2是两个字符串对象，len是子字符串的长度。我们要将字符串str1复制到字符串对象str2中，则语法应类似于:
1
2
str1.copy(str2,len);
str1.copy(str2,len,pos);
str2: str2是保留复制的字符串的目标字符串对象。 len: 定义子字符串的长度。 pos: 确定要包含的第一个字符的位置。

思路

整体还是比较简单，不知道为什么第一次没做出来哈哈哈，过了几天反而又做出来了~

用递归的思路，可以发现对字符串解码过程其实就是一个不断重复地过程，因为对一个字符串解码和对其子字符串解码的步骤都是一样的，用递归就很好的避免了重复步骤

代码

class Solution {
public:
    string decodeString(string s) {
        string ans;
        int length=s.size();
        int n;
        string tempans;
        int judge=0;
        string numStr;
        for(int i=0;i<length;i++){
            while(i<length&&((int(s[i])-48>9)||(int(s[i])-48<0)))ans.push_back(s[i++]);
            if((int(s[i])-48<=9)&&(int(s[i])-48>=0)){
                numStr.clear();
                numStr.push_back(s[i]);
                while((int(s[i+1])-48<=9)&&(int(s[i+1])-48>=0))numStr.push_back(s[++i]);
                n=stoi(numStr);
                judge=1;
                i+=2;
                tempans.clear();
                while(i<length&&judge!=0){
                    if(s[i]=='[')judge++;
                    if(s[i]==']')judge--;
                    if(judge!=0){
                        tempans.push_back(s[i]);
                        i++;
                    }
                }
                tempans=decodeString(tempans);
                while(n--)ans+=tempans;
            }
        }
        return ans;
    }
};

最长公共子序列（中等）

题目描述

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

知识点

二维vector初始化空间(r行c列)

1	vector<vector<int> > newOne(r, vector<int>(c, 0));

思路

二位动态规划，dp[i][j]代表text1前i个和text2前j个的最长公共子序列，首先确认前0个和另一个字符串最长公共子序列都是零，状态转换：

if text1[i]==text2[j]:
	dp[i+1][j+1]=dp[i][j]+1
else:
	dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);

代码

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int length1=text1.size();
        int length2=text2.size();
        int maxAns=0;
        vector<vector<int>>dp(length1+1,vector<int>(length2+1,0));
        for(int i=0;i<length1;i++){
            for(int j=0;j<length2;j++){
                if(text1[i]==text2[j]){
                    dp[i+1][j+1]=dp[i][j]+1;
                }else{
                    dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);
                }
                maxAns=max(dp[i+1][j+1],maxAns);
            }
        }
        return maxAns;
    }
};

盛最多水的容器(中等)

题目描述

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

思路

不知道大家对有一道leetcode题还有没有印象，也是盛水，不过是算所有缝隙的水，感觉有异曲同工之妙

思路很简单，就是双指针，如果left指向的高度小于right，left就往这边移，这才可能会遇到会有最大面积的容器，因为事实上我们将left往右移，只是遗弃了原left和原left+1这一块的体积，但是本来left指向的高度就小于right，left和left+1组成块的面积肯定小于或者等于left和right

代码

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left=0;
        int right=height.size()-1;
        int maxArea=0;
        while(left!=right){
            maxArea=max(maxArea,(right-left)*min(height[right],height[left]));
            if(height[left]>height[right]){
                right--;
            }else{
                left++;
            }
        }
        return maxArea;
    }
};

实现Trie（前缀树）（中等）

题目描述

Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

请你实现 Trie 类：

Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

思路

使用链表+哈希，因为哈希查找元素的复杂度为1，以单词前缀作为哈希索引,ifis代表该节点是否真实有值

代码

class Trie {
public:
    struct ListNode{
        char val;
        int ifIS;
        unordered_map<char,struct ListNode*>next;
    };
    ListNode*head=new ListNode();
    Trie() {
    }
    
    void insert(string word) {
        ListNode*copy=head;
        for(char ww:word){
            if(copy->next.find(ww)!=copy->next.end()){
                copy=copy->next[ww];
            }else{
                ListNode*newnode=new ListNode();
                newnode->val=ww;
                newnode->ifIS=0;
                copy->next[ww]=newnode;
                copy=newnode;
            }
        }
        copy->ifIS=1;
    }
    
    bool search(string word) {
        ListNode*copy=head;
        for(char ww:word){
            if(copy->next.find(ww)!=copy->next.end()){
                copy=copy->next[ww];
            }else{
                return false;
            }
        }
        if(copy->ifIS==1){
            return true;
        }else{
            return false;
        }
        // return true;
    }
    
    bool startsWith(string prefix) {
        ListNode*copy=head;
        for(char ww:prefix){
            if(copy->next.find(ww)!=copy->next.end()){
                copy=copy->next[ww];
            }else{
                return false;
            }
        }
        return true;
    }
};

杨辉三角（简单）

题目描述

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

思路

用ans1算下一行

代码

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>>ans;
        vector<int>ans1;
        ans.push_back({1});
        for(int i=1;i<numRows;i++){
            ans1.push_back(1);
            for(int j=0;j<ans.back().size()-1;j++){
                ans1.push_back(ans.back()[j]+ans.back()[j+1]);
            }
            ans1.push_back(1);
            ans.push_back(ans1);
            ans1.clear();
        }
        return ans;
    }
};

打家劫舍（中等）

题目描述

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

思路

很简单的动态规划，dp[i]=dp[i]+max[dp[i-2],dp[i-3]……]

代码

class Solution {
public:
    int rob(vector<int>& nums) {
        int maxmoney=0;
        for(int i=0;i<nums.size();i++){
            if(i>=2){
                nums[i]+=*max_element(nums.begin(),nums.begin()+i-1);
            }
            maxmoney=max(nums[i],maxmoney);
        }
        return maxmoney;
    }
};

旋转图像(中等)

题目描述

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

思路

找到旋转的规律，其实坐标总体变化是固定的

代码

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int length=matrix.size();
        int temp1;
        for(int i=0;i<length/2;i++){
            for(int j=i;j<length-i-1;j++){
                temp1=matrix[i][j];
                matrix[i][j]=matrix[length-1-j][i];
                matrix[length-1-j][i]=matrix[length-1-i][length-1-j];
                matrix[length-1-i][length-1-j]=matrix[j][length-1-i];
                matrix[j][length-1-i]=temp1;
            }
        }
    }
};

和为k的子数组（中等）

题目描述

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。

思路

暴力解法会超时，只介绍前缀加哈希

首先考虑用一个二维数组保存前i+1个数的和，比如sum[1]表示下标0和下标1的和，sum[100]表示下标0-100的和，接下来遍历数组，比如我们要找下标结尾为j的连续子数组和为k，我们知道sum[j]是多少，只需要找到一个i使得sum[j]-sum[i]为k即可，即sum[i]=sum[j]-k。

优化：哈希找key的复杂度为1，所以考虑用哈希，哈希的键是前缀和，也就是sum，值是前缀和出现的次数，也就是可能前i个数和前j个数的和都是一样的值，这种算连续数组的时候也要算两次，所以需要记录。我们遍历数组的时候是以遍历的下标作为结尾，只考虑该坐标和该坐标前的sum，那么就暂时不需要考虑后面的sum，所以sum的计算和遍历可以同时进行

代码

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int,int>preSumMap;
        preSumMap[0]=1;
        int count=0;
        int pre=0;
        for(int number:nums){
            pre+=number;
            auto it=preSumMap.find(pre-k);
            if(it!=preSumMap.end()){
                count+=it->second;
            }
            preSumMap[pre]++;
        }
        return count;
    }
};

二叉搜索树中第K小的元素(中等)

题目描述

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

思路

思路一：优先队列暴力求解

用dfs遍历二叉树，存在优先队列中，再取第k个最小的数

代码一

class Solution {
public:
    priority_queue <int,vector<int>,greater<int> > p;
    void dfs(TreeNode* root){
        if(root==NULL){
            return;
        }else{
            p.emplace(root->val);
            dfs(root->left);
            dfs(root->right);
        }
    }
    int kthSmallest(TreeNode* root, int k) {
        dfs(root);
        while(--k){
            p.pop();
        }
        return p.top();
    }
};

思路二：利用二叉搜索树的性质

二叉搜索树中序遍历即升序排列，利用该性质可方便求解

代码二：

class Solution {
public:
    int km;
    int ans;
    void dfs(TreeNode* root){
        if(root==NULL||km==0){
            return;
        }
        dfs(root->left);
        if(--km==0){
            ans=root->val;
            return;
        }
        dfs(root->right);
    }
    int kthSmallest(TreeNode* root, int k) {
        km=k;
        dfs(root);
        return ans;
    }
};

搜索插入位置（简单）

题目描述

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

思路

很明显使用二分查找

代码

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int mid=0;
        int right=nums.size()-1;
        int left=0;
        while(left<right){
            mid=(right+left)/2;
            if(nums[mid]>=target){
                right=mid;
            }else{
                left=mid+1;
            }
        }
        if(nums[left]<target){
            return left+1;
        }
        return left;
    }
};

划分字母区间（中等）(待做)

题目描述

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

示例 1：

输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。