1、旋转数组中的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。

示例 1：

输入：[3,4,5,1,2]
输出：1

示例 2：

输入：[2,2,2,0,1]
输出：0

方法一：利用旋转数组的特性进行遍历

class Solution {
public:
    int minArray(vector<int>& numbers) {
        int res=numbers[0];
        int n=numbers.size();
        for(int i=1;i<n;i++){
            if(numbers[i]<numbers[i-1]){
                res=numbers[i];
                break;
            }
        }
        return res;
    }
};

方法二：二分

class Solution {
public:
    int minArray(vector<int>& numbers) {
        int i = 0, j = numbers.size() - 1;
        while (i < j) {
            int m = (i + j) / 2;
            if (numbers[m] > numbers[j]) i = m + 1;
            else if (numbers[m] < numbers[j]) j = m;
            else j--;
        }
        return numbers[i];
    }
};

2、机器人的运动范围

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

示例 1：

输入：m = 2, n = 3, k = 1
输出：3

示例 2：

输入：m = 3, n = 1, k = 0
输出：1

方法一：DFS

class Solution {
public:
    int m,n,k;
    int cnt=1;
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};
    bool visited[105][105];
    int movingCount(int m, int n, int k) {
        this->m=m;
        this->n=n;
        this->k=k;
        dfs(0,0);
        return cnt;
    }
    void dfs(int x,int y){
        visited[x][y]=true;
        int xx,yy;
        for(int i=0;i<4;i++){
            xx=x+dx[i];
            yy=y+dy[i];
            if(xx>=0&&yy>=0&&xx<m&&yy<n){
                if(res(xx,yy)&&(!visited[xx][yy])){
                    cnt++;
                    dfs(xx,yy);
                }
            }
        }
    }
    bool res(int x,int y){
        int sum=0;
        while(x){
            sum+=x%10;
            x=x/10;
        }
        while(y){
            sum+=y%10;
            y=y/10;
        }
        if(sum<=k)
            return true;
        else
            return false;
    }
};

方法二：BFS

class Solution {
public:
    int m,n,k,x,y,xx,yy;
    pair<int,int> temp;
    int cnt=1;
    queue<pair<int,int>> q;
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};
    bool visited[105][105];
    int movingCount(int m, int n, int k) {
        this->m=m;
        this->n=n;
        this->k=k;
        q.push(make_pair(0,0));
        visited[0][0]=true;
        while(!q.empty()){
            temp=q.front();
            q.pop();
            x=temp.first;
            y=temp.second;
            for(int i=0;i<4;i++){
                xx=x+dx[i];
                yy=y+dy[i];
                if(xx>=0&&yy>=0&&xx<m&&yy<n){
                    if(res(xx,yy)&&(!visited[xx][yy])){
                        visited[xx][yy]=true;
                        cnt++;
                        q.push(make_pair(xx,yy));
                    }
                }
            }
        }
        return cnt;
    }
    bool res(int x,int y){
        int sum=0;
        while(x){
            sum+=x%10;
            x=x/10;
        }
        while(y){
            sum+=y%10;
            y=y/10;
        }
        if(sum<=k)
            return true;
        else
            return false;
    }
};

力扣剑指Offer（三）

原文：https://www.cnblogs.com/oucmly/p/14754972.html