剑指offer08. 二叉树得到下一个节点

这题leetcode上没有找到，不过分析过程是值得学习的。

纯分情况讨论题，要求十分细致完整（其实很难想到qaq 需要画不少图分析）：

1. 一个节点有右子树，它的下一个节点是右子树中的最左节点。
2. 没有右子树：如果该节点为左子节点，那么下一跳就是它的parent，如果是右子节点，要一直向parent查找，直到它成为parent左树的一员

剑指 Offer 11. 旋转数组的最小数字

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

部分有序-> 二分法
num[mid]>num[right] 右半部分有最小值
num[mid]<num[right] （mid在内的左半部分有最小值。。。）
否则–线性查找

注意：一定要跟右边的值作比较。虽然与左边的值作比较能够确定哪个区间有序，但在无法确定最小元素在左还是在右区间。
参考leetcodeK神的分析：

补充思考： 为什么本题二分法不用 nums[m]nums[m] 和 nums[i]nums[i] 作比较？

二分目的是判断 mm 在哪个排序数组中，从而缩小区间。而在 nums[m] > nums[i]nums[m]>nums[i]情况下，无法判断 mm 在哪个排序数组中。本质上是由于 jj 初始值肯定在右排序数组中； ii 初始值无法确定在哪个排序数组中。举例如下：

对于以下两示例，当 i = 0, j = 4, m = 2i=0,j=4,m=2 时，有 nums[m] > nums[i] ，而结果不同。
[1, 2, 3, 4 ,5][1,2,3,4,5] 旋转点 x = 0x=0 ： mm 在右排序数组（此示例只有右排序数组）；
[3, 4, 5, 1 ,2][3,4,5,1,2] 旋转点 x = 3x=3 ： mm 在左排序数组。

所以说最坏情况O（n)，平均情况O（log n)

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 { //直接线性查找即可（或者right--,而不是left++)
                int x = i;
                for(int k = i + 1; k < j; k++) {
                    if(numbers[k] < numbers[x]) x = k;
                }
                return numbers[x];
            }
        }
        return numbers[i];
    }
};

剑指 Offer 12. 矩阵中的路径

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

例如，在下面的 3×4 的矩阵中包含单词 “ABCCED”（单词中的字母已标出）。

class Solution {
public:
    int vis[201][201]={false};
    int dx[4]={1,-1,0,0};
    int dy[4]={0,0,1,-1};
    bool res=false;


    bool exist(vector<vector<char>>& board, string word) {
        int n=board.size(),m=board[0].size();
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(board[i][j]==word[0])
                {
                    dfs(i,j,0,board,word);
                    if(res) return res;

                }

            }
        }

        return false;
    }

    void dfs(int x,int y,int index,vector<vector<char>>& board, string word)
    {
        int n=board.size(),m=board[0].size();
        if(index==word.length()||res)
        {
            res=true;
            return;
        }

        if(x>=0&&x<n&&y>=0&&y<m&&vis[x][y]==false&&board[x][y]==word[index])
        {
            vis[x][y]=true;

            for(int i=0;i<4;i++)
            {
                int tx=x+dx[i];
                int ty=y+dy[i];
                dfs(tx,ty,index+1,board,word);

            }
            vis[x][y]=false;
        }
        else return;



        
    }
};

虽然感觉写的挺好，但是还是只超过5%。
if(index==word.length()||res) 增加条件，要剪枝，否则超时。。。

剑指 Offer 13. 机器人的运动范围

地上有一个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。请问该机器人能够到达多少个格子？

class Solution {
public:
    int dx[2]={0,1};
    int dy[2]={1,0};
    int maxCount=0;
    bool vis[101][101]={false};
    int movingCount(int m, int n, int k) {

        dfs(0,0,m,n,k);
        return maxCount;



    }


    void dfs(int x,int y,int m,int n,int k)
    {
        int numx=getCount(x);
        int numy=getCount(y);
        if(x<0||x>=m||y<0||y>=n||vis[x][y]==true||numx+numy>k) return;
        vis[x][y]=true;
        maxCount++;

            for(int i=0;i<2;i++)
            {
                int tx=x+dx[i];
                int ty=y+dy[i];
                dfs(tx,ty,m,n,k);
            }

    }


    int getCount(int n)
    {   
        int s=0;
        while(n!=0)
        {
            s+=n%10;
            n/=10;
        }
        return s;
    }
};

此题不是寻找一条路径——所以不需要回溯，vis数组记录是否已经计数这个格子