2022/7/2做题总结

目录

一、141. 环形链表 - 力扣（LeetCode）

题目描述

思路

代码实现

二、103. 二叉树的锯齿形层序遍历 - 力扣（LeetCode）

题目描述

思路：

代码实现

三、33. 搜索旋转排序数组 - 力扣（LeetCode） 

题目描述

思路

代码实现

四、88. 合并两个有序数组 - 力扣（LeetCode） 

题目描述

思路

代码实现

---

一、141. 环形链表 - 力扣（LeetCode）

题目描述

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
 

提示：

链表中节点的数目范围是 [0, 10^4]
-10^5 <= Node.val <= 10^5
pos 为 -1 或者链表中的一个 有效索引 。

思路

快慢指针。前面写过这道题，所以比较快的想到了这个方法。

快指针一直走在慢指针的前面，但是如果链表存在环的话，两个指针最终会相遇，因此判断链表存在环。

代码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head==NULL||head->next==NULL)
        {
            return false;
        }
        ListNode* p;
        ListNode* q;
        p=head;
        q=head;
        while(p!=NULL&&p->next!=NULL)
        {
            p=p->next->next;
            q=q->next;
            if(p==q)
            {
                return true;
            }
        }
        return false;
    }
};

二、103. 二叉树的锯齿形层序遍历 - 力扣（LeetCode）

题目描述

给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]
示例 2：

输入：root = [1]
输出：[[1]]
示例 3：

输入：root = []
输出：[]
 

提示：

树中节点数目在范围 [0, 2000] 内
-100 <= Node.val <= 100

思路：

大致和普通的层序遍历类似。因为要一层一层交替，所以当在层数为奇数的时候（因为我是先遍历右孩子，如果先遍历左孩子也可以，那就是层数为偶数的时候），需要将这一层的遍历结点的顺序逆置。如果层数为偶数时，就正常放入vector数组即可。

代码实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        int x=1;//记录层数
        vector<vector<int>> a;
        queue<TreeNode*> q;
        if(root!=NULL)
        {
            q.push(root);
        }
        while(!q.empty())
        {
            vector<int> b;
            int size=q.size();
            while(size--)
            {
                if(q.front()->right)//先遍历右孩子
                {
                    q.push(q.front()->right);
                }
                if(q.front()->left)//再遍历左孩子
                {
                    q.push(q.front()->left);
                }
                b.push_back(q.front()->val);
                q.pop();
            }
            if(x%2!=0)//当层数（从0开始）是奇数时，对于队列中的结点，先遍历右孩子再遍历左孩子会使它的顺序逆着，所以需要将它逆置。
            {
                vector<int> c;
                for(int i=b.size()-1;i>=0;i--)//逆置
                {
                    c.push_back(b[i]);
                }
                a.push_back(c);
            }
            else
            {
                a.push_back(b);
            }
            x++;//层数加一
        }
        return a;
    }
};

三、33. 搜索旋转排序数组 - 力扣（LeetCode） 

题目描述

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
示例 2：

输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1
示例 3：

输入：nums = [1], target = 0
输出：-1
 

提示：

1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
nums 中的每个值都 独一无二
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-10^4 <= target <= 10^4

思路

这题的难点在于时间复杂度要为O(log n)。直接从前往后遍历数组，肯定超时，所以利用双指针，时间复杂度就可以满足条件了。

代码实现

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int i=0,j=nums.size()-1;
        while(i<=j)
        {
            if(nums[i]==target)
            {
                return i;
            }
            else if(nums[j]==target)
            {
                return j;
            }
            else
            {
                i++;
                j--;
            }
        }
        return -1;
    }
};

四、88. 合并两个有序数组 - 力扣（LeetCode） 

题目描述

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。
示例 3：

输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
 

提示：

nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-10^9 <= nums1[i], nums2[j] <= 10^9

思路

注意，这一题是要将nums2合并到nums1中，不能另外开一个数组。因为nums1后面有空余的空间，所以，从后面往前进行比较，可以不用进行元素的移动，因此时间复杂度也就降低了。起初，用3个指针，分别指向nums1数组的末尾（n+m)，nums1数组的元素的末尾（m)，nums2数组的末尾（n)，依次往前遍历，谁大谁就放入该位置。最后nums1有剩余的话，不用管。如果是nums2有剩余，就得将nums2所有剩余元素放入nums1。

代码实现

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        if(nums1.size()==0)
        {
            for(int i=0;i<nums2.size();i++)
            {
                nums1[i]=nums2[i];
            }
        }
        else
        {
            int i=m,j=n,k=m+n;
            while(i>0&&j>0)
            {
                if(nums1[i-1]>=nums2[j-1])
                {
                    k--;
                    i--;
                    nums1[k]=nums1[i];
                }
                else
                {
                    k--;
                    j--;
                    nums1[k]=nums2[j];
                }
            }
            while(j)
            {
                k--;
                j--;
                nums1[k]=nums2[j];
            }
        }
    }
};