catalogue

Title: Sword finger offer03: repeated numbers in the array

Title: Sword finger offer04: search in two-dimensional array

Title: Sword finger offer05: replace spaces

Title: Sword finger offer06: print linked list node information from end to end

Title: Sword finger offer07: reconstruction of binary tree (pre order + middle order)

Title: Sword finger offer09: queue with two stacks

Title: Sword finger offer10-1: Fibonacci sequence 10-2: frog jumping steps

Title: Sword finger offer03: repeated numbers in the array

Title Link:

https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/

Title Description:

All numbers in an array num of length n are in the range of 0 ~ n-1. Some numbers in the array are repeated, but I don't know how many numbers are repeated, or how many times each number is repeated. Please find any duplicate number in the array.

Example 1:

Input:
[2, 3, 1, 0, 2, 5, 3]
Output: 2 or 3 

Specific code implementation:

Method 1:

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        unordered_set<int> st;
        for(auto i : nums){
            if(st.find(i) != st.end())
                return i;
            else
                st.insert(i);
        }
        return -1;
    }
};

Method 2:

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        unordered_map<int,int> mp;
        for(int i = 0;i < nums.size();i++){
            if(mp.find(nums[i]) != mp.end()){
                return nums[i];
            }else{
                mp[nums[i]]++;
            }
        }
        return -1;
    }
};

Method 3:

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        for(int i = 0;i < nums.size();i++){
            while(nums[i] != i){ //When the current number is not equal to the number with the current number as the subscript
                if(nums[i] == nums[nums[i]])
                    return nums[i];
                else{
                    int tmp = nums[nums[i]];
                    nums[nums[i]] = nums[i];
                    nums[i] = tmp;
                }
            }
        }
        return -1;
    }
};

Title: Sword finger offer04: search in two-dimensional array

Title Link:

https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/

Title Description:

In an n * m two-dimensional array, each row is sorted in ascending order from left to right, and each column is sorted in ascending order from top to bottom. Please complete an efficient function, input such a two-dimensional array and an integer, and judge whether the array contains the integer.

Example:

The existing matrix is as follows:

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

Specific implementation:

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        if(matrix.size() == 0)
            return false;
        int row = matrix.size();
        int i = 0;
        int j= matrix[0].size()-1;
        while(i < row && j >=0){
            if(matrix[i][j] < target){
                i++;
            }else if(matrix[i][j] > target){
                j--;
            }else
                return true;
        }
        return false;
    }
};

Time complexity: O(m+n)

Space complexity: O(1)

Title: office05

Title Link:

https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/

Title Description:

Please implement a function to replace each space in the string "{s}" with "% 20".

Example 1:

Input: s = "We are happy."
Output:"We%20are%20happy."

Specific implementation:

class Solution {
public:
    string replaceSpace(string s) {
        if(s.empty())
            return s;
        int count = 0;
        for(int i = 0;i < s.length();i++){
            if(s[i] == ' ')
                count++;
        }
        int sz = s.size(); //Save the length of s before resize (the length of s after resize changes)
        int length = sz+2*count;
        s.resize(length);
        int end1 = sz-1;
        int end2 = length-1;
        while(end1 >=0 && end1<end2){
            if(s[end1] == ' '){
                s[end2--] = '0';
                s[end2--] = '2';
                s[end2--] = '%';
            }else{
                s[end2--] = s[end1];
            }
            end1--;
        }
        return s;
    }
};

Title: Sword finger offer06: print linked list node information from end to end

Title Link:

https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/

Title Description:

Enter the head node of a linked list, and return the value of each node from tail to head (returned by array).

Example 1:

Input: head = [1,3,2]
Output:[2,3,1]

Specific implementation method:

class Solution {
public:
    //Recursive implementation
    void reversePrintR(ListNode* head,vector<int>& result){
        if(head == nullptr)
            return;
        if(head->next)
            reversePrintR(head->next,result);
        result.push_back(head->val);
    }
    vector<int> reversePrint(ListNode* head) {
        vector<int> result;
        if(head == nullptr)
            return result;
        reversePrintR(head,result);
        return result;
    }
};

Title: Sword finger offer07: reconstruction of binary tree (pre order + middle order)

Title Link:

https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/

Title Description:

Enter the results of preorder traversal and inorder traversal of a binary tree, please rebuild the binary tree. It is assumed that the input pre order traversal and middle order traversal results do not contain duplicate numbers.

Give, for example

preorder = [3,9,20,15,7]
Middle order traversal inorder = [9,3,15,20,7]
Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

Specific implementation method:

class Solution {
public:
    int prev_indx;
    unordered_map<int,int> mp;

    TreeNode* helper(vector<int>& preorder,vector<int>& inorder,int left,int right){
        if(left > right)
            return nullptr;
        int root_val = preorder[prev_indx];
        TreeNode* root = new TreeNode(root_val);
        int idex = mp[root_val];
        prev_indx++;
        //First build the left subtree
        root->left = helper(preorder,inorder,left,idex-1);
        //Then construct the right subtree
        root->right = helper(preorder,inorder,idex+1,right);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        prev_indx = 0;
        int idex = 0;
        for(auto i : inorder){
            mp[i] = idex++;  //Middle order element = corresponding subscript
        }
        return helper(preorder,inorder,0,preorder.size()-1);
    }
};

Title: Sword finger offer09: queue with two stacks

Title Link:

https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/

Title Description:

Implement a queue with two stacks. The declaration of the queue is as follows. Please implement its two functions appendTail and deleteHead to insert integers at the end of the queue and delete integers at the head of the queue respectively. (if there is no element in the queue, the deleteHead} operation returns - 1)

Specific implementation:

class CQueue {
public:
    CQueue() { //initialization
        while(!s1.empty()){
            s1.pop();
        }
        while(!s2.empty()){
            s2.pop();
        }
    }
    
    void appendTail(int value) { //Tail insertion
        s1.push(value);
    }
    
    int deleteHead() { //Header deletion
        if(s2.empty()){
            while(!s1.empty()){
                int top = s1.top();
                s1.pop();
                s2.push(top);
            }
        }
        if(s2.empty()){
            return -1;
        }else{
            int val = s2.top();
            s2.pop();
            return val;
        }
    }
private:
    stack<int> s1; //Line up
    stack<int> s2; //Out of queue stack
};

Title: Sword finger offer10-1: Fibonacci sequence 10-2: frog jumping steps

Title: 10-1 Fibonacci sequence

Title Link:

https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/

Title Description:

Write a function, enter n, and find the nth term of Fibonacci sequence (i.e. F(N)). Fibonacci sequence is defined as follows:

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), where n > 1
The Fibonacci sequence starts with 0 and 1, and the subsequent Fibonacci numbers are obtained by adding the previous two numbers.

The answer needs to take the module 1e9+7 (1000000007). If the initial result is 1000000008, please return 1.

Title Link:

class Solution {
public:
    int fib(int n) {
        if(n < 2)
            return n;
        int first = 0;
        int second = 1;
        int third;
        for(int i = 2;i <= n;i++){
            third = (first+second)%(1000000007);
            first = second;
            second = third;
        }
        return second;
    }
};

Title: 10-2 frog jumping steps

Title Link:

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

Title Description:

A frog can jump up one step or two steps at a time. Find out the total number of jumping methods for the frog to jump up an n# step.

The answer needs to take the module 1e9+7 (1000000007). If the initial result is 1000000008, please return 1.

Specific implementation:

class Solution {
public:
    int numWays(int n) {
        int first = 1;
        int second = 1;
        int third;
        for(int i = 2;i <= n;i++){
            third = (first+second)%(1000000007);
            first = second;
            second = third;
        }
        return second;
    }
};