当前位置：网站首页>2022/7/2 question summary

Give you a list of the head node head , Judge whether there are links in the list .
If there is a node in the linked list , It can be done by continuously tracking next The pointer reaches again , Then there is a ring in the linked list . To represent a ring in a given list , The evaluation system uses an integer pos To indicate where the end of the list is connected to the list （ Index from 0 Start ）. Be careful ：pos Not passed as an argument . Just to identify the actual situation of the linked list .
If there are rings in the list , Then return to true . otherwise , return false .
Example 1：
Input ：head = [3,2,0,-4], pos = 1
Output ：true
explain ： There is a link in the list , Its tail is connected to the second node .
Example 2：
Input ：head = [1,2], pos = 0
Output ：true
explain ： There is a link in the list , Its tail is connected to the first node .
Example 3：
Input ：head = [1], pos = -1
Output ：false
explain ： There are no links in the list .

Tips ：
The number range of nodes in the linked list is [0, 10^4]
-10^5 <= Node.val <= 10^5
pos by -1 Or one of the lists Valid index .

Ideas

Speed pointer . I wrote this question before , So I quickly thought of this method .

The fast pointer keeps ahead of the slow pointer , But if there are links in the linked list , The two pointers will eventually meet , Therefore, it is judged that there are links in the linked list .

Code implementation

/**
 * 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;
    }
};

Two 、103. Zigzag sequence traversal of binary tree - Power button （LeetCode）

Title Description

Give you the root node of the binary tree root , Returns the Zigzag sequence traversal .（ First from left to right , And then from the right to the left for the next level of traversal , And so on , Alternate between layers ）.
Example 1：

Input ：root = [3,9,20,null,null,15,7]
Output ：[[3],[20,9],[15,7]]
Example 2：
Input ：root = [1]
Output ：[[1]]
Example 3：
Input ：root = []
Output ：[]

Tips ：
The number of nodes in the tree is in the range [0, 2000] Inside
-100 <= Node.val <= 100

Ideas ：

It is roughly similar to ordinary sequence traversal . Because it needs to alternate layer by layer , So when the number of layers is odd （ Because I traverse the right child first , If you traverse the left child first , That is when the number of layers is even ）, You need to reverse the order of traversing nodes in this layer . If the number of layers is even , Put it normally vector The array can be .

Code implementation

/**
 * 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;// Record the number of layers 
        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)// First traverse the right child 
                {
                    q.push(q.front()->right);
                }
                if(q.front()->left)// Then traverse the left child 
                {
                    q.push(q.front()->left);
                }
                b.push_back(q.front()->val);
                q.pop();
            }
            if(x%2!=0)// When the number of layers （ from 0 Start ） It's an odd number , For nodes in the queue , Traversing the right child first and then the left child will make its order reverse , So we need to reverse it .
            {
                vector<int> c;
                for(int i=b.size()-1;i>=0;i--)// Inversion 
                {
                    c.push_back(b[i]);
                }
                a.push_back(c);
            }
            else
            {
                a.push_back(b);
            }
            x++;// Number of layers plus one 
        }
        return a;
    }
};

3、 ... and 、33. Search rotation sort array - Power button （LeetCode）

Title Description

An array of integers nums In ascending order , The values in the array Different from each other .
Before passing it to a function ,nums In some unknown subscript k（0 <= k < nums.length） On the rotate , Make array [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（ Subscript from 0 Start Count ）. for example , [0,1,2,4,5,6,7] In subscript 3 It may turn into [4,5,6,7,0,1,2] .
Here you are. After rotation Array of nums And an integer target , If nums There is a target value in target , Returns its subscript , Otherwise return to -1 .
You have to design a time complexity of O(log n) The algorithm to solve this problem .
Example 1：
Input ：nums = [4,5,6,7,0,1,2], target = 0
Output ：4
Example 2：
Input ：nums = [4,5,6,7,0,1,2], target = 3
Output ：-1
Example 3：
Input ：nums = [1], target = 0
Output ：-1

Tips ：
1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
nums Each value in the unique
Topic data assurance nums Rotated on a previously unknown subscript
-10^4 <= target <= 10^4

Ideas

The difficulty of this problem is that the time complexity should be O(log n). Traverse the array directly from front to back , It must be over time , So use double pointers , The time complexity can meet the conditions .

Code implementation

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;
    }
};

Four 、88. Merge two ordered arrays - Power button （LeetCode）

Title Description

Here are two buttons Non decreasing order Array of arranged integers nums1 and nums2, There are two other integers m and n , respectively nums1 and nums2 The number of elements in .
Would you please Merge nums2 To nums1 in , Make the merged array press Non decreasing order array .
Be careful ： Final , The merged array should not be returned by the function , It's stored in an array nums1 in . In response to this situation ,nums1 The initial length of is m + n, The top m Elements represent the elements that should be merged , after n Elements are 0 , It should be ignored .nums2 The length of is n .
Example 1：
Input ：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output ：[1,2,2,3,5,6]
explain ： Need merger [1,2,3] and [2,5,6] .
The combined result is [1,2,2,3,5,6] , In which, bold italics indicates nums1 The elements in .
Example 2：
Input ：nums1 = [1], m = 1, nums2 = [], n = 0
Output ：[1]
explain ： Need merger [1] and [] .
The combined result is [1] .
Example 3：
Input ：nums1 = [0], m = 0, nums2 = [1], n = 1
Output ：[1]
explain ： The array to be merged is [] and [1] .
The combined result is [1] .
Be careful , because m = 0 , therefore nums1 No elements in .nums1 The only remaining 0 Just to ensure that the merged results can be successfully stored in nums1 in .

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

Ideas

Be careful , This question is to nums2 Merge into nums1 in , You cannot open another array . because nums1 There is free space in the back , therefore , Compare from the back to the front , There is no need to move elements , Therefore, the time complexity is reduced . At first , use 3 A pointer to the , Point to respectively nums1 The end of the array （n+m),nums1 The end of the element of the array （m),nums2 The end of the array （n), Go forward in turn , Whoever is older will be put in this position . Last nums1 If there is anything left , Never mind . If it is nums2 There is a surplus , You have to nums2 All remaining elements are put into nums1.

Code implementation

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];
            }
        }
    }
};

原网站

版权声明
本文为[Ls really can't]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/186/202207050455325285.html