正文

leetcode刷题笔记-数据结构-day5(代码片段)

ΘLLΘ  ΘLLΘ  2022-12-19  482

关键词：

文章目录

LeetCode刷题笔记-数据结构-day5

LeetCode刷题笔记-数据结构-day5

334.递增的三元子序列

1.题目描述

原题链接：334. 递增的三元子序列

2.解题思路

题目要求：你能实现时间复杂度为 O(n) ，空间复杂度为 O(1) 的解决方案吗？

算法：贪心

这里我们使用贪心，用两个数a和b表示遍历中最小的两个数，我们只需要在找出比b大的的第三个数就行。

具体操作（当前遍历的数为x）：

如果x<=a。则将最小值a修改为x
如果上面的不满足，但是x<=b则将第二小的值修改为x
如果上面两个都不满足，说明此时的数已经大于前面两个，条件构成，返回true

需要注意的是，可以会有 4(a)、6(b)、3(x)这种情况，也就是说如果x比a还小，那就把a的值设为x，然后继续遍历找最终的答案（这样的话a会跑到b的后边，但是不要紧，因为在b的前边，老a还是满足的），我们最终的第三个数只需要大于b即可！

3.代码

class Solution 
public:
    bool increasingTriplet(vector<int>& nums) 
        int a=INT_MAX,b=INT_MAX;
        for(auto x:nums)
            if(x<=a) a=x;
            else if(x<=b) b=x;
            else return true;
        
        return false;
    
;

238.除自身以外数组的乘积

1.题目描述

原题链接：238. 除自身以外数组的乘积

2.解题思路

题目要求：不要使用除法，且在 O(n) 时间复杂度内完成此题。尽量在常数空间复杂度内完成

我们可以两次遍历数组：

第一次从左边遍历，用一个数t记录前缀乘积
第二次从右边遍历，t重新置为1，记录后缀乘积
每个位置的结果只需要乘上遍历到该的位置的t即可
最终时间复杂度O(n),空间复杂度O(1)。

3.代码

class Solution 
public:
    vector<int> productExceptSelf(vector<int>& nums) 
        int n=nums.size();
        vector<int> res(n,1);
        int t=1;
        for(int i=0;i<n;i++)
            res[i]*=t;
            t*=nums[i];
        
        t=1;
        for(int i=n-1;i>=0;i--)
            res[i]*=t;
            t*=nums[i];
        
        return res;
    
;

560.和为 K 的子数组

1.题目描述

原题链接：560. 和为 K 的子数组

2.解题思路

算法：前缀和+哈希表

我们可以用哈希表hash记录前缀和sum出现的次数。每次只需要hash[sum]++即可，hash[0]=1需要特别处理。

当我们遍历到某个位置的时候，hash[sum-k]的值就是前面出现的和为 k 的连续子数组的个数。

3.代码

class Solution 
public:
    int subarraySum(vector<int>& nums, int k) 
        map<int,int> hash;
        int sum=0;
        int res=0;
        hash[0]=1;
        for(auto x:nums)
            sum+=x;
            res+=hash[sum-k];
            hash[sum]++;
        
        return res;
    
;

leetcode刷题笔记-动态规划-day5(代码片段)

文章目录LeetCode刷题笔记-动态规划-day553.最大子数组和1.题目2.解题思路3.代码918.环形子数组的最大和1.题目2.解题思路3.代码LeetCode刷题笔记-动态规划-day553.最大子数组和1.题目原题链接：53.最大子数组和2.解题思路算法：... 查看详情

leetcode刷题笔记-数据结构-day19(代码片段)

文章目录LeetCode刷题笔记-数据结构-day19997.找到小镇的法官1.题目描述2.解题思路3.代码1557.可以到达所有点的最少点数目1.题目描述2.解题思路3.代码841.钥匙和房间1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day19997.找到小... 查看详情

leetcode刷题笔记-数据结构-day19(代码片段)

leetcode刷题笔记-数据结构-day14(代码片段)

文章目录LeetCode刷题笔记-数据结构-day14155.最小栈1.题目描述2.解题思路3.代码1249.移除无效的括号1.题目描述2.解题思路3.代码1823.找出游戏的获胜者1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day14155.最小栈1.题目描述原题... 查看详情

leetcode刷题笔记-数据结构-day12(代码片段)

文章目录LeetCode刷题笔记-数据结构-day1224.两两交换链表中的节点1.题目描述2.解题思路3.代码707.设计链表1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day1224.两两交换链表中的节点1.题目描述原题链接：24.两两交换链表... 查看详情

leetcode刷题笔记-数据结构-day21(代码片段)

文章目录LeetCode刷题笔记-数据结构-day21451.根据字符出现频率排序1.题目2.解题思路3.代码973.最接近原点的K个点1.题目2.解题思路3.代码LeetCode刷题笔记-数据结构-day21451.根据字符出现频率排序1.题目原题链接：451.根据字符出现频... 查看详情

leetcode刷题笔记-数据结构-day21(代码片段)

leetcode刷题笔记-数据结构-day16(代码片段)

文章目录LeetCode刷题笔记-数据结构-day16199.二叉树的右视图1.题目描述2.解题思路3.代码113.路径总和II1.题目描述2.解题思路3.代码450.删除二叉搜索树中的节点1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day16199.二叉树的右视... 查看详情

leetcode刷题笔记-数据结构-day15(代码片段)

文章目录LeetCode刷题笔记-数据结构-day15108.将有序数组转换为二叉搜索树1.题目描述2.解题思路3.代码105.从前序与中序遍历序列构造二叉树1.题目描述2.解题思路3.代码103.二叉树的锯齿形层序遍历1.题目描述2.解题思路3.代码LeetCode刷... 查看详情

leetcode刷题笔记-数据结构-day20(代码片段)

文章目录LeetCode刷题笔记-数据结构-day20215.数组中的第K个最大元素1.题目2.解题思路3.代码347.前K个高频元素1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day20215.数组中的第K个最大元素1.题目原题链接：215.数组中的第K个... 查看详情

leetcode刷题笔记-数据结构-day20(代码片段)

leetcode刷题笔记-数据结构-day6(代码片段)

文章目录LeetCode刷题笔记-数据结构-day6415.字符串相加1.题目描述2.解题思路3.代码409.最长回文串1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day6415.字符串相加1.题目描述原题链接：415.字符串相加2.解题思路直接套用大... 查看详情

leetcode刷题笔记-数据结构-day11(代码片段)

文章目录LeetCode刷题笔记-数据结构-day11160.相交链表1.题目描述2.解题思路3.代码82.删除排序链表中的重复元素II1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day11160.相交链表1.题目描述原题链接：160.相交链表2.解题思路... 查看详情

leetcode刷题笔记-数据结构-day18(代码片段)

文章目录LeetCode刷题笔记-数据结构-day18236.二叉树的最近公共祖先1.题目描述2.解题思路3.代码297.二叉树的序列化与反序列化1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day18236.二叉树的最近公共祖先1.题目描述原题链接... 查看详情

leetcode刷题笔记-数据结构-day18(代码片段)

leetcode刷题笔记-数据结构-day3(代码片段)

文章目录LeetCode刷题笔记-数据结构-day3119.杨辉三角II1.题目描述2.解题思路3.代码48.旋转图像1.题目描述2.解题思路3.代码59.螺旋矩阵II1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day3119.杨辉三角II1.题目描述原题链接：11... 查看详情

leetcode刷题笔记-数据结构-day7(代码片段)

文章目录LeetCode刷题笔记-数据结构-day790.单词规律1.题目描述2.解题思路3.代码763.划分字母区间1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day790.单词规律1.题目描述原题链接：90.单词规律2.解题思路算法：哈希表... 查看详情