Brush the title "sword finger offer" day04

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

11. Minimum number of rotation array

My explanation

There are a lot of holes in this problem , Because there will be several special situations , I had no idea at first , The code on the book is typed , It's not simple enough .

class Solution {
    
public:
    int minArray(vector<int>& numbers) {
    
        int right = numbers.size() - 1,left = 0,mid = left;
        while(numbers[left] >= numbers[right]) {
    
            if(right - left == 1){
    
                mid = right;
                break;
            }
            mid = left + (right - left) / 2;
            // If the three are the same , Then you can only search by order 
            if(numbers[mid] == numbers[right] && numbers[mid] == numbers[left]){
    
                return minInOrder(left,right,numbers);
            }
            if(numbers[mid] >= numbers[right]) {
    
                left = mid;
            }else if(numbers[mid] <= numbers[right]){
    
                right = mid;
            }
        }
        return numbers[mid];
    }

    // In order to find 
    int minInOrder(int left,int right,vector<int>& numbers) {
    
        int min = numbers[left];
        for(int i = 0;i < right;i++) {
    
            if(numbers[i] < min){
    
                min = numbers[i];
            }
        }
        return min;
    }
};

13. The range of motion of the robot

My explanation

This problem can be solved by deep search

class Solution {
    
public:
// Check whether the grid can enter 
    bool check(int x,int y,int k,int m,int n,vector<vector<int>>& myMap) {
    
        if(x > m-1 || y > n-1 || x < 0 || y < 0 || myMap[x][y] == 1){
    
            return false;
        }
        int result = 0;
        while(x > 0) {
    
            result += x % 10;
            x /= 10;
        }
        while(y > 0) {
    
            result += y % 10;
            y /= 10;
        }
        return result <= k;
    }

    int dfs(int m,int n,int x,int y,int k,vector<vector<int>>& myMap) {
    
        int count = 0;
        if(check(x,y,k,m,n,myMap)){
    
            myMap[x][y] = 1;
            count = 1;
            count += dfs(m,n,x+1,y,k,myMap);
            count += dfs(m,n,x-1,y,k,myMap);
            count += dfs(m,n,x,y+1,k,myMap);
            count += dfs(m,n,x,y-1,k,myMap);
        }
        return count;
    }

    int movingCount(int m, int n, int k) {
    
        vector<vector<int>> myMap(m);
        for(int i= 0;i < m;i++){
    
            myMap[i].resize(n);
        }        
        return dfs(m,n,0,0,k,myMap);
    }

};