算法题（三）

本文最后更新于：2021年4月13日下午

概览：LeetCode刷题。

<details>
    <summary>折叠/查看代码</summary>
    
</details>

9 回文数【逻辑】

2021/04/08

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。

示例 1：

输入：x = 121
输出：true
示例 2：

输入：x = -121
输出：false
解释：从左向右读, 为 -121 。从右向左读, 为 121- 。因此它不是一个回文数。
示例 3：

输入：x = 10
输出：false
解释：从右向左读, 为 01 。因此它不是一个回文数。
示例 4：

输入：x = -101
输出：false

提示：

-231 <= x <= 231 - 1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

优化：如果当前数字最后一位为0，且其不等于0，则就可以直接排除！！

思路1：转字符串

使用c++的streamstring这个对象保存数据，然后调用.str()转为字符串，再判断即可。

头文件：#include <sstream>

折叠/查看代码

class Solution {
public:
    bool isPalindrome(int x) {
        //如果是负数 不是回文数
        if(x < 0) return false;
        //如果是0或者正数
        if(x >= 0 && x <= 9) return true;

        stringstream s;
        s<<x;
        string s1 = s.str();
        int i = 0;
        int j = s1.size()-1;
        while(i<j){
            if(s1[i] == s1[j]){
                i++;
                j--;
            }else{
                return false;
            }
        }
        return true;
    }
};

思路2：提取后一半数字进行对比

将整个数字转换的话，数字很可能会溢出，那么尝试只转换一半的数字。

处理：

如果是回文数字，那么循环处理，x不断除以10删减最低位置，临时数字则不断拿取x的最低位构造自己。这个循环的条件就是x > 临时数字。
- 特殊情况，奇数个位数时，循环处理的结果就是，临时数字比x多了最中间的一位，那么判断的时候除去那一位就好了。
如果不是回文数字，则上述循环执行结束会，对比不成立就会返回false。

折叠/查看代码

class Solution1 {
public:
    bool isPalindrome(int x) {
        //如果是负数 不是回文数
        if (x < 0) return false;
        if (x % 10 == 0 && x != 0) return false;//末尾为0的情况不再考虑

        int nums = 0;
        while (x > nums) {
            nums = nums * 10 + x % 10;
            x = x / 10;
        }
        /* 如果是奇数位，nums/10可略去中间那位*/
        return x == nums || x == nums / 10;
    }
};

55 跳跃游戏【偶数科技面试】|【贪心】

2021/04/08

给定一个非负整数数组 nums ，你最初位于数组的第一个下标。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2：

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ，所以永远不可能到达最后一个下标。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/jump-game
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

贪心算法，要转变思路，是否能达到下标位置？

如果每次按照最大的步数往下走，则这一步能走到的范围内，无论如何都能到达！

所以把走几步的问题，转变为范围扩展的问题，只要范围扩展到了边界，就说明可以达到。

折叠/查看代码

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int len = nums.size();
        if (len <= 1) return true;//长度为1肯定直接达到

        int cur = nums[0];//表示最远能够到达的范围
        for (int i = 1; i < len; i++) {
            if (cur >= len - 1) {//到达边界
                return true;
            }

            //只有这个范围可达，才能进入
            if(cur >= i){
                cur = max(cur, nums[i] + i);
            }else{
                return false;//若当前的点都到不了，那么之后肯定都到不了
            }
        }
        return false;
    }
};

45 跳跃游戏2 【贪心】

2021/04/08

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
说明:

假设你总是可以到达数组的最后一个位置。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/jump-game-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

300 最长递增子序列【动规】|【跟谁学笔试题】

2021/04/09

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4
示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

提示：

1 <= nums.length <= 2500
-104 <= nums[i] <= 104

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-increasing-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

使用动态规划思想，使用一个一维数组dp，dp[i]表示从0到当前索引，递增子序列的最大长度。

状态转移方程：当nums[i] > nums[j]的时候，dp[i] = max(dp[i],dp[j]+1)。

即：索引为i的数字如果大于了索引为j的数字，那么最大递增子序列就等于0到索引j的子序列的最大递增子序列长度再加1.

折叠/查看代码

class Solution {
public:

    //使用动态规划思想：选出最长的递增子序列
    //dp[i] 表示从0到当前索引i中，其中最长的递增子序列的长度

    int lengthOfLIS(vector<int>& nums) {
        int len = nums.size();
        int maxlen = 1;//长度最短为1
        vector<int> dp(len,1);//全部初始化为1

        for(int i = 1;i<len;i++){//当前元素
            for(int j=0;j<i;j++){//前面元素
                if(nums[i] > nums[j]){
                    dp[i] = max(dp[i],dp[j]+1);
                }
            }
            maxlen = max(maxlen,dp[i]);
        }

        return maxlen;
    }
};

70 爬楼梯【斐波那契】

2021/04/10

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2
解释：有两种方法可以爬到楼顶。

1 阶 + 1 阶

2 阶
示例 2：

输入： 3
输出： 3
解释：有三种方法可以爬到楼顶。

1 阶 + 1 阶 + 1 阶

1 阶 + 2 阶

2 阶 + 1 阶

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/climbing-stairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

仔细分析题目，倒推一步，可以发现，第n节台阶的上法，可以是到达n-1节台阶与到达n-2节台阶之和。

即f(n) = f(n-1) + f(n-2)。这就像是斐波那契数列或者动态规划方程。

斐波那契数列解法

折叠/查看代码

class Solution {
public:

    int climbStairs(int n) {
        if(n == 0 || n==1)
            return 1;
        else return climbStairs(n-1) + climbStairs(n-2);
    }
};

显然时间超限，甚至还会溢出！

记忆化斐波那契-1

采用数组的形式记忆

剑指青蛙跳台阶

https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/submissions/

折叠/查看代码

class Solution {
public:
    //有多少种方法的题目。多少带一点递推性质
    //f(n) = f(n-1) + f(n-2)
    //就像是斐波那契数列，f(0) = 1 f(1) = 1 f(2) = 2
    //直接递归会超出时间限制
    //采用记忆化递归，将结果保存到数组中
    int numWays(int n) {
        vector<int> nums(101,-1);
        nums[0] = 1;
        nums[1] = 1;
        nums[2] = 2;

        for(int i = 3;i<=n;i++){
            nums[i] = (nums[i-1]+nums[i-2])% 1000000007;
        }
        return nums[n] ;
    }
};

记忆化斐波那契-2

将上述代码简化，我们只需要简单的记录前1个和前2个的数值就行了，然后顺序向后延展，就能够得到最终结果。

折叠/查看代码

class Solution {
public:
    int climbStairs(int n) {

        if(n == 1 || n==2) return n;

        int a1 = 1;
        int a2 = 2;
        int sum = 0;

        for(int i = 3;i<=n;i++){
            sum = a1 + a2;
            a1 = a2;
            a2 = sum;
        }
        return sum;
    }
};

待续

98 验证二叉搜索树【二叉树】

2021/04/10

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

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

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/validate-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路1：递归

二叉搜索树特性：左子树只包含比根节点小的节点，右子树只包含比根节点大的节点。然后左右子树都又满足这个特性。

给定一个函数，要包含判断节点的最小和最大的范围，超出这个范围就不是二叉搜索树。

然后问题就是处理如何传递对应的范围：

对于左子树，其最大值一定小于根节点，func(root->left,min = ,max = root->val).
- 最小值继承其父节点的范围
对于右子树，其最小值一定大于根节点，func(root->right,min = root->val,max = )
- 最大值继承其父节点的范围

然后函数入口(root,min = long_min,max = long_max)即可

折叠/查看代码

class Solution {
public:

    //节点，范围，
    bool func(TreeNode * root,long minval,long maxval){
        if(root == nullptr) return true;

        if(root->val >= maxval || root->val <= minval){
            return false;
        }

        //对左右两个子节点判断
        return func(root->left,minval,root->val) && func(root->right,root->val,maxval);

    }

    bool isValidBST(TreeNode* root) {
       return func(root,LONG_MIN,LONG_MAX);
    }
};

思路2：中序遍历-递归

二叉搜索树的特点，中序遍历是一个完全递增序列。

如果遍历过程中发现不是递增。直接返回false。

折叠/查看代码

class Solution {
public:
    long pre = LONG_MIN;
    bool result = true;//类似全局变量，来记录

    void func(TreeNode* root){
        if(result && root != nullptr){
            func(root->left);
            if(root->val <= pre){
                result = false;
            }
            pre = root->val;//记录前一个值
            func(root->right);
        }
    }

    bool isValidBST(TreeNode* root) {
       func(root);
       return result;
    }
};

思路3：中序遍历-非递归

折叠/查看代码

class Solution {
public:

    bool isValidBST(TreeNode* root) {
       stack<TreeNode* > st;
        TreeNode * tmp;
        TreeNode * t= root;
        long pre = LONG_MIN;

       while(t != nullptr || !st.empty()){

           if(t!=nullptr){
               st.push(t);
               t = t->left;
           }else{
               //当左子树为空的时候，
                tmp = st.top();
                st.pop();

                if(tmp->val  <= pre)
                    return false;

                pre = tmp->val;

                t = tmp->right;//然后看其节点的右子树，右子树就是尽力向左访问
           }
       }
       return true;
    }
};

19 删除链表的倒数第N个结点【链表】

2021/04/11

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

进阶：你能尝试使用一趟扫描实现吗？

实例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：
输入：head = [1], n = 1
输出：[]

示例 3：
输入：head = [1,2], n = 1
输出：[1]

提示：

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：前后指针法，先使得i与j之间相差n个节点，然后j向后遍历找到链表尾部，同时i也跟着向后移动。这样当j到达链表尾部的时候，i就指向了被删除的节点，然后再使用pre指针记录i的前一个节点。

折叠/查看代码

class Solution {
public:

    //返回链表的头节点。仅扫描一次
    //双指针法
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode * temp = head;
        ListNode * i = head;
        ListNode * j = i;

        for (int k = 0; k < n; k++) {
            j = j->next;
        }

        ListNode * pre = i;
        while (j != nullptr) {
            pre = i;
            i = i->next;
            j = j->next;
        }

        //这时i指向了对应的元素
        //pre指向了前一个要删除的元素

        if (pre == i) {//pre == i 即头节点，若前一个要删除的元素 就是头节点
            return pre->next;
        }
        else {
            pre->next = pre->next->next;
        }
        return temp;
    }
};

15 三数之和要求不重复

2021/04/11

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
示例 2：

输入：nums = []
输出：[]
示例 3：

输入：nums = [0]
输出：[]

提示：

0 <= nums.length <= 3000
-105 <= nums[i] <= 105

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

折叠/查看代码

class Solution {
public:

    vector<vector<int>> threeSum(vector<int>& nums) {
        int len = nums.size();
        if(len < 3)
            return {};
        //先对数据进行排序
        sort(nums.begin(), nums.end());
        vector<vector<int>> result;
        for (int first = 0; first < len; first++) {
            if (first > 0 && nums[first] == nums[first - 1])//重复的不再使用
                continue;
            int target = -nums[first];//第二、三个数加起来等于它即可
            int third = len - 1;
            for (int second = first + 1; second < len; second++) {
                if (second > first + 1 && nums[second] == nums[second - 1])//重复的不再使用
                    continue;
                //third = len - 1;//没有比要，而且对于[0,0,0,0]这种数组会出错
                while (second < third &&  nums[second] + nums[third] > target)//当前数组是递增排列，和比目标值大，就直接舍去 
                    third--;
                if(second == third)
                    break;
                if (nums[second] + nums[third] == target) {
                    result.push_back({nums[first],nums[second],nums[third]});
                }
            }
        }
        return result;
    }
};

25 K个一组翻转链表

2021/04/12

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

进阶：

你可以设计一个只使用常数额外空间的算法来解决此问题吗？
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]
示例 2：

输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]
示例 3：

输入：head = [1,2,3,4,5], k = 1
输出：[1,2,3,4,5]
示例 4：

输入：head = [1], k = 1
输出：[1]
提示：

列表中节点的数量在范围 sz 内
1 <= sz <= 5000
0 <= Node.val <= 1000
1 <= k <= sz

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路1：单纯改变节点内的值，每k个一组保存到栈中，然后逐个出栈重新赋值。

思路：数组暂存

思路2：找一个前置节点pre，然后每次都是下一组需要翻转节点的前一个节点，找到需要翻转的末尾，这中间要用数组把节点的地址都记录下来，然后数组反向遍历，逐个串接到pre节点。、

对于返回结果，需要提前保存一下链表开头，然后最后返回！

折叠/查看代码

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if (k == 1) return head;

        //否则先处理头节点
        ListNode * tmp = head;
        ListNode *pre = new ListNode(0,head);
        ListNode * ppre = pre;

        vector<ListNode*> kvec(k, nullptr);

        int index = 0;

        while (tmp != nullptr) {

            for (index = 0; index < k; ++index) {
                if (tmp == nullptr) {
                    //到达末尾，结束了
                    return ppre->next;
                }
                kvec[index] = tmp;
                tmp = tmp->next;
            }

            //进行翻转
            int i;
            for (i = k - 1; i >= 0; --i) {
                pre->next = kvec[i];
                pre = pre->next;//更新前置指针
            }
            pre->next = tmp;//要更改指向！！！否则会在原来的指向上造成混乱

        }
        return ppre->next;

    }
};

思路：直接翻转再连接

记得处理两个节点

翻转前的链表头，翻转后变成链表尾，可以更新Pre
翻转前的链表尾，翻转后变成链表头，可以用来连接链表！

折叠/查看代码

class Solution1 {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if (k == 1) return head;

        //否则先处理头节点
        ListNode * tmp = head;
        ListNode *pre = new ListNode(0, head);
        ListNode * ppre = pre;

        int index = 0;

        while (tmp != nullptr) {

            //头节点前一个 pre
            //尾节点后一个 tmp

            ListNode * prelast = nullptr;//记录被翻转的最后一个节点，翻转后就会变成首节点，用于连接链表

            //每次记录头尾节点
            for (index = 0; index < k; index++) {
                if (tmp == nullptr) {
                    return ppre->next;
                }
                prelast = tmp;
                tmp = tmp->next;
            }

            //置换
            //通过pre -- tmp的前一个访问到那个链表
            //链表原地翻转
            ListNode * head = pre->next;
            ListNode *tail = tmp;
            ListNode * tmppre = pre->next;//记录翻转前的第一个节点，翻转后会变成最后一个节点，来更新pre。

            while (head != tmp) {
                ListNode * nex = head->next;

                head->next = tail;
                tail = head;
                head = nex;
            }

            //翻转完成之后，更新pre，连接链表
            pre->next = prelast;//将链表与反转后的连接起来
            pre = tmppre;//更新pre的位置，要保证指向下一组的前一个

        }
        return ppre->next;

    }
};

21 合并两个有序链表

2021/04/12

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

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：

输入：l1 = [], l2 = []
输出：[]
示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按非递减顺序排列

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-two-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：就是比较大小然后串接起来，但是串接节点时出现了问题！

方式1：在堆上开辟节点，然后串接。需要额外的空间！

折叠/查看代码

//双指针向后移动
while(l1 != nullptr && l2 != nullptr){
    if(l1->val < l2->val){
        ListNode* tmp = new ListNode(l1->val);
        newlist->next = tmp;
        l1 = l1->next;
        newlist = newlist->next;

    }else{
        ListNode* tmp = new ListNode(l2->val);
        newlist->next = tmp;
        newlist = newlist->next;
        l2 = l2->next;
    }
}

while(l1 != nullptr){
    ListNode* tmp = new ListNode(l1->val);
    newlist->next = tmp;
    l1 = l1->next;
    newlist = newlist->next;
}

if(l2 != nullptr){
    ListNode* tmp = new ListNode(l2->val);
    newlist->next = tmp;
    newlist = newlist->next;
    l2 = l2->next;
}

方法二：串接原来的节点，但是要注意串接时各个变量的放置顺序！

折叠/查看代码

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == nullptr)
            return l2;
        if (l2 == nullptr)
            return l1;

        ListNode * newlist = new ListNode(0);
        ListNode * pre = newlist;

        //双指针向后移动
        while (l1 != nullptr && l2 != nullptr) {
            if (l1->val < l2->val) {
                newlist->next = l1;				
                newlist = newlist->next;
                l1 = l1->next;
            }
            else {
                newlist->next = l2;
                newlist = newlist->next;
                l2 = l2->next;
            }
        }
        if (l1 != nullptr) {
            newlist->next = l1;
        }
        if (l2 != nullptr) {
            newlist->next = l2;
        }
        return pre->next;
    }
};

算法

LeetCode

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

Linux线程同步上一篇

Linux线程下一篇

算法题（三）

9 回文数【逻辑】

思路1：转字符串

思路2：提取后一半数字进行对比

55 跳跃游戏 【偶数科技面试】|【贪心】

45 跳跃游戏2 【贪心】

300 最长递增子序列【动规】|【跟谁学笔试题】

70 爬楼梯【斐波那契】

斐波那契数列解法

记忆化斐波那契-1

记忆化斐波那契-2

98 验证二叉搜索树【二叉树】

思路1：递归

思路2：中序遍历-递归

思路3：中序遍历-非递归

19 删除链表的倒数第N个结点【链表】

15 三数之和 要求不重复

题解

25 K个一组翻转链表

思路： 数组暂存

思路：直接翻转再连接

21 合并两个有序链表

55 跳跃游戏【偶数科技面试】|【贪心】

15 三数之和要求不重复

思路：数组暂存