leetcode_02_part
liduoan.efls Engineer
  2020-05-01 23:57:50 2020-05-01 23:57   2020-05-07 22:24:19    3.8k 字  15 分钟  

前言

难顶，又到五月了。这几天要忙着数学建模。

但是leeetcode还是要接着写呀！

2020.05.01

21. 合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

解析：

这道题是真的简单。初级算法做过类似的题目。

所以我很感谢当初自己坚持做完了初级算法。确实让我见过了大多数的题目。

很明显，两个链表合并。那么我们可以用双指针呀。

直接双指针搞定！核心的代码很简单 ，看下面代码就懂了。

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        //注意到这里我们要判断是否为空
        if(l1==NULL||l2==NULL){
            return l1==NULL?l2:l1;
        }
        //保证头节点，到时候返回头节点
        //利用p节点让后续迭代
        ListNode *head , *p ;
        //获得头节点
        if(l1->val < l2->val){
            head = l1;
            l1 = l1->next;
        }else{
            head = l2;
            l2 = l2->next;
        }
        p = head;
        //直到其中一个为空指针
        while(l1!=NULL && l2!=NULL){
            if(l1->val < l2->val){
                p->next = l1;
                l1 = l1->next;
                p = p->next;
            }
            else{
                p->next = l2;
                l2 = l2->next;
                p = p->next;
            }
        }
        //到时候如果有不是空的就直接处理
        if(l1!=NULL){
            p->next=l1;
        }else{
            p->next=l2;
        }
        return head;
    }
};

2020.05.02

3. 无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:

输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:

输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。

这道题目 也是一道动态规划题目，更加重要的是一道滑动窗口题目。

看到它是子串，不是子序列！！

很有趣的滑动窗口题目！

怎么想呢？——我们需要看到的是子串

那么我们用类似滑动窗口的视角来滑动。这样我们需要有几个步骤

判断字符重复

先移动右边界限，如果出现重复字符 那么再移动左边。

每一次准备移动左边都说明 这次子串结束 计算其长度！

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:
    int lengthOfLongestSubstring(string s) {
        set<char> st;
        //这里我们使用集合来判断是否出现相同字符
        int n = s.size();
        //确定开头为-1  这里是未来后面rk+1 做准备
        //为了 0 < 1  -1 + 1 =0 < 1
        int rk = -1;
        int ans = 0;
        //左边开始增加
        for(int i=0;i<n;i++){
            if(i!=0){
                st.erase(s[i-1]);
            }
            //判断 下一个是不是重复了  存在是1  非 则是0  意思就是为重复 直接脱离循环
            while(rk+1<n&& ! st.count(s[rk+1])){
                st.insert(s[rk+1]);
                rk++;
            }

            ans = max(ans,rk-i+1);
        }
        return ans;
    }
};

2020.05.03

53. 最大子序和

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

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

今天题目，一眼就看的出标准的动态规划

那么动态规划题目一般怎么写呢？【得查查

动态规划类问题常规的解决方法是：

  • 问题拆解，找到问题的定义
  • 状态定义
  • 递归方程求解
  • 实现

我们看这道题目，分析情况，自底向上

。。【我不知道怎么说啊。。。

直接看代码吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if(nums.size()==0)
            return 0;
        vector<int> dp;
        dp.push_back(nums[0]);
        for(int i=1;i<nums.size();i++){
            dp.push_back(max(dp[i-1]+nums[i],nums[i]));
        }
        sort(dp.begin(), dp.end());
        return dp[nums.size()-1];
    }
};

2020.05.05

98. 验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:

输入:
2
/
1 3
输出: true
示例 2:

输入:
5
/
1 4
/
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。

记住二叉搜索树有什么特点

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。【注意没有等于

两种方法：

递归法

思路：

我们要知道 对于一个二叉搜索树，任何一个节点，它的左子树小于其，它的右子树大于其。

也就是说，我们可以这么认为，root节点是左子树的上界，是其右子树的下界。

那么我们只要遍历整颗树，判断他是否满足这个性质就可以了。

理一下递归方程：

这个递归函数的作用： 判断这个值是否目前节点是否在其区间内，是的话返回true

递归出口：如果root为空，返回true

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        //这里需要我们拿取最小最大值，不要用int
        //int的范围会小了一点
        return isBST(root,LLONG_MIN,LLONG_MAX);
    }
    //这里函数  我们也要用long long
    bool isBST(TreeNode* root,long long min,long long max){
        if(root == NULL)//到了根节点
            return true;
        if(root->val<=min || root->val >=max)//这个值不在范围内
            return false;
        return isBST(root->left,min,root->val)&&isBST(root->right,root->val,max);
    }
};

中序遍历

我们知道，对于二叉搜索树，其中序遍历得到的值是递增的

那么，我们只需要获取中序遍历值，然后判断递增不就好了√

那么最笨的方法就是先获取中序遍历数组，再判断是否有序。

但是还有更好的——变遍历边判断！

看代码！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    long long pre = LLONG_MIN;
    bool isValidBST(TreeNode* root) {
        //该递归方程的作用：可以判断本树是否为二叉搜索树
        //如果我是空的 返回真
        if(root == NULL)
            return true;
        //根据中序遍历
        //我们从左子树开始判断是否为二叉搜索树
        if(!isValidBST(root->left))
            return false;
        //左 根 右  现在判断根的情况
        if(root->val  <= pre)
            return false;
        //给pre——前面一个值 进行更新
        pre = root->val;
        //现在是右子树
        return isValidBST(root->right);
    }
};

很难，说实话，我觉得我不够透彻。周末再写一遍这道题目吧

2020.05.06

983. 最低票价

在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。

火车票有三种不同的销售方式：

一张为期一天的通行证售价为 costs[0] 美元；
一张为期七天的通行证售价为 costs[1] 美元；
一张为期三十天的通行证售价为 costs[2] 美元。
通行证允许数天无限制的旅行。 例如，如果我们在第 2 天获得一张为期 7 天的通行证，那么我们可以连着旅行 7 天：第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。

返回你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费。

示例 1：

输入：days = [1,4,6,7,8,20], costs = [2,7,15]
输出：11
解释：
例如，这里有一种购买通行证的方法，可以让你完成你的旅行计划：
在第 1 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 1 天生效。
在第 3 天，你花了 costs[1] = $7 买了一张为期 7 天的通行证，它将在第 3, 4, …, 9 天生效。
在第 20 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 20 天生效。
你总共花了 $11，并完成了你计划的每一天旅行。
示例 2：

输入：days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
输出：17
解释：
例如，这里有一种购买通行证的方法，可以让你完成你的旅行计划：
在第 1 天，你花了 costs[2] = $15 买了一张为期 30 天的通行证，它将在第 1, 2, …, 30 天生效。
在第 31 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 31 天生效。
你总共花了 $17，并完成了你计划的每一天旅行。

提示：

1 <= days.length <= 365
1 <= days[i] <= 365
days 按顺序严格递增
costs.length == 3
1 <= costs[i] <= 1000

这道题目，直接说我不会做，看人家题目解析，看了好久才明白。

但是又不能说很懂。

我们在自己旅行上花的价钱最少，

三种情况

在本日买了一天的票，至此花费的总价格

在七天前买了七天的票，到现在花费的总价钱

在三十天之前买了三十天的票，到现在花费的总价格

然后决定最小值当作我此刻的最好的买票方式

然后代码就出来了

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
30
31
32
33
34
class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        if(days.size()==0 || costs.size() == 0){
            return 0;
        }
        vector<int> dp(days[days.size()-1]+1);
        //给不旅游的时间赋予 0  给旅游的时间赋予max
        for(int i=0;i<days.size();i++){
            dp[days[i]] = INT_MAX;
        }
        //书写dp数组
        for(int i=1;i<dp.size();i++){
            if(dp[i]==0){
                dp[i]=dp[i-1];
                continue;
            }
            /*
            一开始我很疑惑，如果我那天就已经买了七天的票
            那么在我计算dp[i]的时候，又写dp[i-7]+cost[2]不是多买了一次吗
            但是仔细看这个dp方程  在前面的dp数组中，只可能自己买了1天，或者前辈买了7天
            【对于小于7 小于30 的情况另外算
            【小于7 小于 30 的时候，因为最小化的缘故，可以【我也不知道。。
            */
            int n1 = dp[i-1] + costs[0];
            int n2 = i>7?dp[i-7]+costs[1]:costs[1];
            int n3 = i>30?dp[i-30]+costs[2]:costs[2];

            dp[i] = min(min(n1,n2),n3);

        }
        return dp[dp.size()-1];
    }
};

2020.05.07

572. 另一个树的子树

给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。

示例 1:
给定的树 s:

 3
/ \

4 5
/
1 2
给定的树 t：

4
/
1 2
返回 true，因为 t 与 s 的一个子树拥有相同的结构和节点值。

示例 2:
给定的树 s：

 3
/ \

4 5
/
1 2
/
0
给定的树 t：

4
/
1 2
返回 false。

分析：

简单题，但是可以不简单的来写。题解有三种方法

暴力破解 利用前序遍历 利用树哈希

首先暴力破解说说【其他不说了，kmp手写我傻了

我们利用对主树的每一个节点遍历是否和目标树是相同的

【讲真我听起来就觉得它的时间复杂度很高。所以我就直接否定了暴力破解

【结果爆破还真行。。

理一下我们对于爆破的思路

1、遍历主树

2、对每个主树的节点当作数根节点和目标树比较——也就是比较树相等

那么再分别看看这两个步骤

遍历主树——

首先看本节点是否相等 如果相等那么进入树相等判断

之后判断本节点的左节点和右节点

检查树相等——

该节点是否相等

该节点的左节点是否相等

该节点的右节点是否相等

​ 递归出口 都为空返回true

那么代码如下：

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:

    /*
    暴力破解做法：
    循环试探每一个节点作为根节点是否和目标树相同 
    那么我们循环每一个s树的节点试探
    每一个节点都和目标子树进行判断
    两个函数  一个递归本树  一个判断相同
    */
    bool check(TreeNode*s1,TreeNode *t1){
        /**
        如何判断相同呢？
        递归：
            1、本节点是不是相同 
            2、左子树是不是相同
            3、右子树是不是相同
        递归出口： 如果为两节点值为空，贼退出
        */
        //这个是递归出口
        if(s1==nullptr && t1==nullptr)
            return true;
        //如果出现有一个为空 就不可能指向数值
        if(s1==nullptr || t1 == nullptr || (s1->val != t1->val))
            return false;
        return check(s1->right,t1->right) && check(s1->left,t1->left);

    }

    bool dfs(TreeNode* ss,TreeNode* tt){
        //因为我们后面会递归主树的各个节点
        //那么某个节点的左右节点是空节点 就不存在左右节点了
        //所以当进来的ss节点是空节点的时候，直接返回false
        if(ss==nullptr)
            return false;
        return check(ss,tt) || dfs(ss->left,tt) || dfs(ss->right,tt);
    }
    
    bool isSubtree(TreeNode* s, TreeNode* t) {

        return dfs(s,t);
    }
};

一个小tips、如果存在指向左右节点的操作

一定要判断是否本节点为空。如果为空，就不可以进行指向左右节点的操作

这会出现越界的问题。

分析一下时间复杂度：

s树每一个节点都需要访问一次——

树相等操作时，最大的是 t树的每一个节点都访问一次——

那么 时间复杂度大概是O(|s|*|t|)

空间复杂度

递归算法空间复杂度：递归深度n*每次递归所要的辅助空间，如果每次递归所需要的辅助空间为常数，则递归空间复杂度o（n）。

那么 看遍历主树的空间复杂度为 s树的深度

树相同递归中的空间复杂度为t树的深度

两个递归的最大的空间消耗 就是这个程序的空间复杂度 即O(max{ s, t})

  • 本文标题：leetcode_02_part
  • 本文作者：liduoan.efls
  • 创建时间：2020-05-01 23:57:50
  • 本文链接：2020/05/01/Leetcode_每日一题/leetcode-02-part/
  • 版权声明：本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
  1. 1. 前言
    1. 1.1. 2020.05.01
      1. 1.1.1. 21. 合并两个有序链表
    2. 1.2. 2020.05.02
      1. 1.2.1. 3. 无重复字符的最长子串
    3. 1.3. 2020.05.03
      1. 1.3.1. 53. 最大子序和
    4. 1.4. 2020.05.05
      1. 1.4.1. 98. 验证二叉搜索树
      2. 1.4.2. 递归法
      3. 1.4.3. 中序遍历
    5. 1.5. 2020.05.06
      1. 1.5.1. 983. 最低票价
    6. 1.6. 2020.05.07
      1. 1.6.1. 572. 另一个树的子树