Brush the title "sword finger offer" day01

Title source ： Power button 《 The finger of the sword Offer》 The second edition
Completion time ：2022/07/21

03. Repeated numbers in an array

My explanation

class Solution {
    
public:
    int findRepeatNumber(vector<int>& nums) {
    
        sort(nums.begin(),nums.end());
        vector<int> check(nums.size());
        for (int i = 0;i < nums.size(); i++){
    
            if(check[nums[i]] == 1){
    
                return nums[i];
            }
            check[nums[i]] = 1;
        }
        return -1;
    }
};

04. Search in a two-dimensional array

My explanation

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

05. Replace blank space

My explanation

class Solution {
    
public:
    string replaceSpace(string s) {
    
        string r = "";
        for(int i = 0;i < s.size();i++) {
    
            if(s[i] == ' '){
    
                r += "%20";
            }else {
    
                r += s[i];
            }
        }
        return r;
    }
};

06. Print linked list from end to end

My explanation

Conventional methods

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
class Solution {
    
public:
    vector<int> reversePrint(ListNode* head) {
    
        vector<int> result;

        while(head != nullptr) {
    
            result.push_back(head->val);
            head = head->next;
        }
        reverse(result.begin(),result.end());
        return result;
    }
};

Recursive implementation

    /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
class Solution {
    
public:
    // Recursive implementation 

    void check(vector<int>& result,ListNode* node) {
    
        if(node->next != nullptr){
    
            check(result,node->next);
        }
        result.push_back(node->val);
    }

    vector<int> reversePrint(ListNode* head) {
    
        vector<int> result;
        if(head != nullptr)
            check(result,head);
        return result;
    }

};