Swipe questions and punch in every day on December 24, 2021

Force deduction - one question per day

Sword finger Offer 36 Binary search tree and bidirectional linked list

Enter a binary search tree and convert the binary search tree into a sorted circular two-way linked list. It is required that no new node can be created, and only the node pointer in the tree can be adjusted.

To better understand the problem, take the following binary search tree as an example:

We hope to transform this binary search tree into a two-way circular linked list. Each node in the linked list has a precursor and successor pointer. For a two-way circular linked list, the precursor of the first node is the last node, and the successor of the last node is the first node.

The following figure shows the linked list transformed from the above binary search tree. "head" refers to the node with the smallest element in the linked list.

[external chain picture transfer failed. The source station may have anti-theft chain mechanism. It is recommended to save the picture and upload it directly (img-jtguxnp8-1640356317346)( https://assets.leetcode.com/uploads/2018/10/12/bstdllreturndll.png )]

In particular, we want the conversion to be done in place. After the conversion is completed, the left pointer of the node in the tree needs to point to the precursor and the right pointer of the node in the tree needs to point to the successor. You also need to return the pointer of the first node in the linked list.

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;

    Node() {}

    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
public:
    Node*head,*tail;
    Node* treeToDoublyList(Node* root) {
        if(!root)return head;
        dfs(root);
        head->left=tail;
        tail->right=head;
        return head;
    }
    void dfs(Node*root)
    {
        if(!root)return;
        dfs(root->left);
        if(tail)
            tail->right=root;
        else
             head=root;
        root->left=tail;
        tail=root;
        dfs(root->right);
    }
};

Sword finger Offer 45 Arrange the array into the smallest number

Input a non negative integer array, splice all the numbers in the array into a number, and print the smallest of all the numbers that can be spliced.

Example 1:

input: [10,2]
output: "102"

Here is to sort the array, convert the numbers a and b into strings and splice them. Judge whether the number of a+b is small or the number of b+a is large. Put a smaller combination in front of the array, for example, 10 and 2102 are smaller than 210, so the sorted 10 is placed in front of 2. When the array is sorted, use the string to traverse the elements of the array and splice them.

class Solution {
public:
   static bool cmp(const int& a, const int& b)
    {
        string num1 = to_string(a)+to_string(b), num2 = to_string(b) + to_string(a);
        if (num1 < num2)
            return true;
        else return false;
    }
    string minNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end(), cmp);
        string str;
        for (auto i : nums)
            str += to_string(i);
        return str;
    }
};

Sword finger Offer 61 Shunzi in playing cards

Draw 5 cards randomly from several pairs of playing cards to judge whether it is a surplus, that is, whether the 5 cards are continuous. 2 ~ 10 is the number itself, a is 1, J is 11, Q is 12, K is 13, and DA and Xiao Wang are 0, which can be regarded as any number. A cannot be regarded as 14.

Example 1:

Input: [1,2,3,4,5]
Output: True

Sort the array first, and then traverse the array. Take a variable ans to record the number of 0 and start traversing the array. When 0 is encountered, ans + +. When the current number is the same as the next number and the current number is not 0, It has been explained that the shunzi cannot be formed (how can there be the same number in the shunzi), and false is directly returned; when the current number + 1 is not equal to the next number, subtract num [I-1] - num [i] - 1 from the value of ANS (the empty interpolation between two numbers is replaced by 0, for example, 5 to 8, and two zeros are required in the middle). If the ANS is less than 0 after cutting, it indicates that the shunzi cannot be formed, and false is returned. If false is not returned after traversing the array, true is returned.

class Solution {
public:
    bool isStraight(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int ans=0;
        for(int i=0;i<4;i++)
        {
            if(nums[i]==nums[i+1]&&nums[i]!=0)return false;
            if(nums[i]==0)ans++;
            else if(nums[i]+1!=nums[i+1])
            {
                ans-=nums[i+1]-nums[i]-1;
                if(ans<0)return false;

            }
        }
        return true;
    }
};

   {
            ans-=nums[i+1]-nums[i]-1;
            if(ans<0)return false;

        }
    }
    return true;
}

};