剑指offer刷题（三）（44-66）题

Bertha 。 2021-12-12 14:27 270阅读 0赞

### 44 翻转单词序列 ###

牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？

/*
    首先先把除了空格 每个词都反转
    然后再反转整个句子 就可以了
    注意：要在结尾加个 ' '标志 反转所有时 先去掉
    例：
    student. a am I 
    .tneduts a ma I 
    I am a student.
    */
    class Solution {
    public:
        string ReverseSentence(string str) {
            auto size = str.size();
            if(size == 0) return "";
            int mark=0;
            str += ' ';
            for(int i = 0; i < size+1; ++i){
                if(str[i] == ' '){
                    ReverseWord(str, mark, i-1);
                    mark = i+1;
                }
            }
            str = str.substr(0, size);
            ReverseWord(str, 0, size-1);
            return str;
        }
        void ReverseWord (string &str, int l, int r){
            while(l < r){
                swap(str[l], str[r]);
                ++l;
                --r;
            }
        }
    };

### 45 扑克牌顺子 ###

LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^\_^)...他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子.....LL不高兴了,他想了想,决定大\\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何， 如果牌能组成顺子就输出true，否则就输出false。为了方便起见,你可以认为大小王是0。

/*
    首先 对数组进行排序
    计算0的个数 以及坑的个数
    如果坑的个数 超过0的个数 不符合
    
    例：
    1 3 0 0 5
    sort -> 0 0 1 3 5
    0 1 3 5 count0:1
    1 3 5 count0:2
    3 5 count0:1
    5 count:0
    
    */
    
    
    class Solution {
    public:
        bool IsContinuous( vector<int> ns ) {
            if(!ns.size())return false;
            sort(ns.begin(),ns.end());
            int count0 = 0;
            for(int i = 0; i < 4; i++){
                if(ns[i] == 0) count0++;
                else{
                    // 相邻间隔数大于 1 的个数 （有几个坑）
                    int t = ns[i+1] - ns[i] - 1;
                    if(t > count0) return false;
                    // 有对子且不为0
                    if(ns[i+1] == ns[i]) return false;
                    // 有几个0抵消掉几个坑
                    count0 -= t;
                }
            }
            return true;
        }
    };

### 46 孩子们的游戏(圆圈中最后剩下的数) ###

每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^\_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)

/*
    这题就是小时候上体育课玩的游戏了
    老师报个数m 然后n个学生从第一位开始报数
    报到m的出列 然后从该同学后一个从0开始报
    重复 直到最后一个同学 做20俯卧撑
    
    可以用list模拟
    首先把数组装入list
    然后取一个位置计数器pos 用来每次模拟m
    而对于当前位置的记录 取一个迭代器 开始从第一个同学开始 
    往后如果到最后一个了 就又从原来的开始
    pos--时迭代器++ 直到pos<0 然后从list中删除该迭代器指向的元素
    重复以上 直到list只有一个元素
    
    由于以上方法每个需要查找元素 数据大时 相当耗时 但是很符合正常的思路
    
    当然这题 还有其他更快的解法 就是数学归纳公式
    如果只求最后一个报数胜利者的话，我们可以用数学归纳法解决该问题，为了讨      论方便，先把问题稍微改变一下，并不影响原意：
    问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人 继续从0开始报数。求胜利者的编号。
    我们知道第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新      的约瑟夫环（以编号为k=m%n的人开始）:
            k  k+1  k+2  ... n-2, n-1, 0, 1, 2, ... k-2并且从k开始报0。
    
    现在我们把他们的编号做一下转换：
    
    k     --> 0
    
    k+1   --> 1
    
    k+2   --> 2
    
    ...
    
    
    k-2   --> n-2
    
    k-1   --> n-1
    
    变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解： 例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情 况的解吗？！！变回去的公式很简单，相信大家都可以推出来：x'=(x+k)%n。
    
    令f[i]表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n]。
    
    递推公式
    
    f[1]=0;
    
    f[i]=(f[i-1]+m)%i;  (i>1)
    
    有了这个公式，我们要做的就是从1-n顺序算出f[i]的数值，最后结果是f[n]。 因为实际生活中编号总是从1开始，我们输出f[n]+1。
    
    int LastRemaining_Solution(int n, int m) {
            if(n==0)
                return -1;
            if(n==1)
                return 0;
            else
                return (LastRemaining_Solution(n-1,m)+m)%n;
    }
    */
    class Solution {
    public:
        int LastRemaining_Solution(int n, int m)
        {
            if(n == 0 || m == 0)return -1;
            list<int> ns;
            for(int i =0;i<n;i++)
                ns.push_back(i);
            // 因为从0开始计数 所以要减1
            int pos = m - 1;
            // 迭代器 从第一个数开始
            auto it = ns.begin();
            //直到list只有一个元素
            while(ns.size()>1){
                // 数到第pos个人
                while(pos--){
                    it++;//迭代器每次往前移动一步
                    if(it == ns.end())it = ns.begin();//迭代器后没有数了 又指向第一个元素
                }
                it = ns.erase(it);//从数组中删除迭代器指向位置的元素
                if(it == ns.end())it = ns.begin();// 如果删除的是最后一个数 又指向第一个元素
                pos = m - 1;// pos重新赋值 开始查找一下个元素
            }
            
            return ns.front();
        }
        
    };

### 47 求1+2+3+...+n ###

求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

/*
    不能用乘法
    想了好久 想不出来
    只能参考别人
    用sizeof 计算二维数组的想法
    sizeof是运算符 计算连续数组的长度 
    两个指针分别指向第一个位置 和 最后一个位置
    二维数组的话 相当把所有行加起来
    但我觉得本质上也算乘法了 或者 循环了
    代码 如下
    int Sum_Solution(int n) {
        bool a[n][n+1];//模拟n * n+1
        return sizeof(a)>>1;//a的长度除2
    }
    最好的解法 是参考的
    使用带两个条件的递归
    利用与运算的特性
    当第一个条件不满足
    直接返回
    */
    class Solution {
    public:
        int Sum_Solution(int n) {
            int ans = n;
            // 当递归到n == 0 时 ans = 0 为 false 
            //ans && (ans += Sum_Solution(n - 1)) 直接返回false 结束递归
            ans && (ans += Sum_Solution(n - 1));
            return ans;
        }
    };

### 48 不用加减乘除做加法 ###

写一个函数，求两个整数之和，要求在函数体内不得使用+、-、\*、/四则运算符号。

class Solution {
    public:
        /**
        1.两个数异或：相当于每一位相加，而不考虑进位；
        2.两个数相与，并左移一位：相当于求得进位；
        3.将上述两步的结果相加；
        如 3 + 2
        11 + 10  ^ 01 & 100
        01 + 100 ^ 101 & 0000
        101 + 0000 return 101 = 5
        **/
        int Add(int n1, int n2)
        {
            if(!n2)return n1;
            else return Add(n1^n2,(n1&n2)<<1);
        }
    };

### 49 把字符串转换成整数 ###

将一个字符串转换成一个整数(实现Integer.valueOf(string)的功能，但是string不符合数字要求时返回0)，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0。

class Solution {
    public:
        // 定义int32的最大最小边界
        int maxEdge = INT32_MAX / 10;
        int minEdge = INT32_MIN / 10;
        int maxSV = INT32_MAX % 10;
        int minSV = INT32_MIN % 10;
        
        int StrToInt(string str) {
            int n = str.size();
            if(n <= 0) return 0;
            
            int left = 0;
            bool is_Minus = false;//是不是负数
            int res = 0;
            //去掉开始时的空格
            while(left < n && str[left] == ' ') left ++ ;
            
            //判断有没有负数
            if(str[left] == '+') left ++ ;
            else if(str[left] == '-')
            {
                left ++ ;
                is_Minus = true;// 是负数
            }
            //从下标为left的数开始往后遍历
            int k = left; 
            
            while(k < n)
            {
                if(str[k] >= '0' && str[k] <= '9'){
                    //负数计算
                    if(is_Minus){
                        int t = (- 1) * (str[k] - '0');
                        //超出边界判断
                        if(res < minEdge) return INT32_MIN;
                        if(res == minEdge)
                            if(t < minSV) return INT32_MIN;
                        //结果累加
                        res = res * 10 + t;
                    }
                    else//正数计算相同
                    {
                        int t = str[k] - '0';
                        if(res > maxEdge) return INT32_MAX;
                        if(res == maxSV){
                            if(t >= maxSV) return INT32_MAX;
                        }
                        else res = res * 10 + t;
                    }
                }
                else return 0;//包含其他字母 说明不合法 直接返回0
                //往后遍历
                k++;
            }
            return res;
    
        }
    };

### 50 数组中重复的数字 ###

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组\{2,3,1,0,2,5,3\}，那么对应的输出是第一个重复的数字2。

/*
    取一个map  key 是数组元素 value 是标记重复数字
    如果key包含元素 直接返回
    */
    class Solution {
    public:
        bool duplicate(int numbers[], int length, int* duplication) {
            map<int,bool> m;
            for(int i = 0; i<length;i++){
                if(m.count(numbers[i])){
                    duplication[0] = numbers[i];
                    return true;
                }else
                    m.insert({numbers[i],1});
            }
            return false;
        }
    };

### 51 构建乘积数组 ###

给定一个数组A\[0,1,...,n-1\],请构建一个数组B\[0,1,...,n-1\],其中B中的元素B\[i\]=A\[0\]\*A\[1\]\*...\*A\[i-1\]\*A\[i+1\]\*...\*A\[n-1\]。不能使用除法。

class Solution {
    public:
        /**
        用两个数组left和right，left[i]=A[0]*A[1]*…*A[i-1], 
        left[i]=A[i-1]*left[i-1]; 
        right[i] = A[i+1]*A[i+2]*…*A[n-1]，
        则right[i]=A[i+1]*right[i+1]。
        最后结果B[i]=left[i]*right[i]。
        时间复杂度分析：需要遍历数组，复杂度为O(n)
        **/
        vector<int> multiply(const vector<int>& A) {
            vector<int> left(A.size(), 1);
            vector<int> right(A.size(), 1);
            for(int i = 1; i < A.size(); i++)
                left[i] = A[i - 1] * left[i - 1];
            
            for(int i = A.size()-2; i >= 0; i--)
                right[i] = A[i + 1] * right[i + 1];
            
            vector<int>B(A.size(),0);
            for(int i = 0; i < A.size(); i++)
                B[i] = left[i] * right[i];
            
            return B;
        }
        
    };

### 52 正则表达式匹配 ###

请实现一个函数用来匹配包括'.'和'\*'的正则表达式。模式中的字符'.'表示任意一个字符，而'\*'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab\*ac\*a"匹配，但是与"aa.a"和"ab\*a"均不匹配

/*
    看了很多个题解 觉得下面这个 很好
    (动态规划) O(nm)O(nm)
    状态表示：f[i][j]表示p从j开始到结尾，是否能匹配s从i开始到结尾
    状态转移：
    
    如果p[j+1]不是通配符'*'，则f[i][j]是真，当且仅当s[i]可以和p[j]匹配，且f[i+1][j+1]是真；
    如果p[j+1]是通配符'*'，则下面的情况只要有一种满足，f[i][j]就是真；
    f[i][j+2]是真；
    s[i]可以和p[j]匹配，且f[i+1][j]是真；
    第1种情况下的状态转移很好理解，那第2种情况下的状态转移怎么理解呢？
    
    最直观的转移方式是这样的：枚举通配符'*'可以匹配多少个p[j]，只要有一种情况可以匹配，则f[i][j]就是真；
    这样做的话，我们发现，f[i][j]除了枚举0个p[j]之外，其余的枚举操作都包含在f[i+1][j]中了，所以我们只需判断
    f[i+1][j]是否为真，以及s[i]是否可以和p[j]匹配即可。
    
    时间复杂度分析：nn 表示s的长度，mm 表示p的长度，总共 nmnm 个状态，状态转移复杂度 O(1)O(1)，所以总时间复杂度是 O(nm)O(nm).
    
    参考大神链接：https://www.acwing.com/solution/AcWing/content/736/
    
        例 aaa    ab*ac*a
         res 	[-1,-1,-1,-1,-1,-1,-1]
    			[-1,-1,-1,-1,-1,-1,-1]
    			[-1,-1,-1,-1,-1,-1,-1]
    			[-1,-1,-1,-1,-1,-1,-1]
    	x:0,y:0,first_match:1
    	x:1,y:1,first_match:0
    	x:1,y:3,first_match:1
    	x:2,y:4,first_match:0
    	x:2,y:6,first_match:1
    	x:2,y:6,ans:1,res[2][6]:1
    	x:2,y:4,ans:1,res[2][4]:1
    	x:1,y:3,ans:1,res[1][3]:1
    	x:1,y:1,ans:1,res[1][1]:1
    	x:0,y:0,ans:1,res[0][0]:1
    	return 1
    	
    	例 aaa    a.a
    	 res 	[-1,-1,-1,-1]
    			[-1,-1,-1,-1]
    			[-1,-1,-1,-1]
    			[-1,-1,-1,-1]
    	x:0,y:0,first_match:1
    	x:1,y:1,first_match:1
    	x:2,y:2,first_match:1
    	x:2,y:2,ans:1,res[2][2]:1
    	x:1,y:1,ans:1,res[1][1]:1
    	x:0,y:0,ans:1,res[0][0]:1
    	return 1
    	
    */
    class Solution {
    public:
        vector<vector<int>> res;
        int n, m;
        bool match(char* s, char* p)
        {
            n = strlen(s);
            m = strlen(p);
            
            res = vector<vector<int>>(n + 1, vector<int>(m + 1, -1));
            return dp(0, 0, s, p);
        }
        bool dp(int x, int y, char *s,  char *p)
        {
            if (res[x][y] != -1) return res[x][y];
            if (y == m)
                return res[x][y] = x == n;
            bool first_match = x < n && (s[x] == p[y] || p[y] == '.');
            bool ans;
            if (y + 1 < m && p[y + 1] == '*')
            {
                ans = dp(x, y + 2, s, p) || first_match && dp(x + 1, y, s, p);
            }
            else
                ans = first_match && dp(x + 1, y + 1, s, p);
            return res[x][y] = ans;
        }
    
    };

### 53 表示数值的字符串 ###

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。

class Solution {
    public:
        /*
        先去除行首和行尾空格；
        行首如果有一个正负号，直接忽略；
        如果字符串为空或只有一个'.'，则不是一个合法数；
        循环整个字符串，去掉以下几种情况：
        (1) '.'或'e'多于1个;
        (2) '.'在'e'后面出现；
        (3) 'e'后面或前面为空，或者'e'前面紧跟着'.'；
        (4) 'e'后面紧跟着正负号，但正负号后面为空；
        剩下的情况都合法
        */
        bool isNumeric(char* str)
        {
            int len = strlen(str);
            string s;
            for(int k = 0;k<len;k++)s += str[k];
            
            int i = 0;
            while (i < len && s[i] == ' ') i ++ ;//去掉前面空格
            int j = len - 1;
            while (j >= 0 && s[j] == ' ') j -- ;//去掉后面空格
            if (i > j) return false;
            
            s = s.substr(i, j - i + 1);//处理空格后的字符串
    
            if (s[0] == '-' || s[0] == '+') s = s.substr(1);//去掉正负号
            if (s.empty() || s[0] == '.' && s.size() == 1) return false;//以.开关  不合法
    
            int dot = 0, e = 0;//小数点和指数
            
            for (int i = 0; i < s.size(); i ++ )
            {
                if (s[i] >= '0' && s[i] <= '9');//数字不处理
                else if (s[i] == '.')
                {
                    dot ++ ;
                    if (e || dot > 1) return false;//点只能有一个
                }
                else if (s[i] == 'e' || s[i] == 'E')
                {
                    e ++ ;
                    if (i + 1 == s.size() || !i || e > 1 || i == 1 && s[0] == '.') return false;
                    if (s[i + 1] == '+' || s[i + 1] == '-')//处理e后面的‘+’或者‘-’
                    {
                        if (i + 2 == s.size()) return false;
                        i ++ ;
                    }
                }
                else return false;
            }
            return true;
    
        }
    
    };

### 54 字符流中第一个不重复的字符 ###

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。

/*
    枚举一个256长度的数组 用来存储字符
    以后查找 只需遍历字符串s 找到第一个数组值为1的数
    */
    class Solution
    {
    public:
      //Insert one char from stringstream
        string s;
        char hash[256] = {0};
        void Insert(char ch)
        {
            s += ch;
            hash[ch]++;
        }
      //return the first appearence once char in current stringstream
        char FirstAppearingOnce()
        {
            for(auto x : s)
                if(hash[x] == 1)return x;
            return '#';
        }
    
    };

### 55 链表中环的入口结点 ###

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

/*
    struct ListNode {
        int val;
        struct ListNode *next;
        ListNode(int x) :
            val(x), next(NULL) {
        }
    };
    定义一个快指针和慢指针都指向头结点
    快指针每次走两步 慢指针每次走一步
    当快指针追上慢指针后
    快指针重新指向头结点 此时每次只走一步
    直到两个指针相遇 就是环的入口结点
    
    如： 1 2 3 4 5 6 7 8 环在5入口处
    epoch1: f:1 s:1
    epoch2: f:3 s:2
    epoch3: f:5 s:3
    epoch4: f:7 s:4
    epoch5: f:5 s:5
    epoch6: f:1 s:5
    epoch7: f:2 s:6
    epoch8: f:3 s:7
    epoch9: f:4 s:8
    epoch10: f:5 s:5
    return f -> 5
    
    */
    class Solution {
    public:
        ListNode* EntryNodeOfLoop(ListNode* h)
        {
            if(!h||!h->next)return 0;
            auto fast = h;//快指针
            auto slow = h;
            
            //判断有没有环
            while(slow&&fast){
                slow = slow->next;//慢指针走一步
                
                fast = fast->next;//快指针走两步
                if(fast)fast = fast->next;
                else return 0;
                
                if(slow == fast){
                    fast = h;
                    while(slow!=fast){
                        slow = slow->next;
                        fast = fast->next;
                    }
                    return fast;
                }
                
            }
    
            return 0;
        }
    };

证明：

![webp][]

### 56 删除链表中重复的结点 ###

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

/*
    struct ListNode {
        int val;
        struct ListNode *next;
        ListNode(int x) :
            val(x), next(NULL) {
        }
    };
    
    1->2->3->3->4->4->5
    -1->1
    -1->1->2->4->4->5
    -1->1->2->5
    return 1->2->5
    */
    class Solution {
    public:
        ListNode* deleteDuplication(ListNode* h)
        {
            auto d = new ListNode(-1);
            d->next = h;
            
            auto p = d;
            while(p->next){
                auto q = p->next;
                //如果有相同的，一直往下找，直到找到不相同
                while(q && p->next->val == q->val) q = q->next;
                
                if(p->next && p->next->next == q) p = p->next;
                else p->next = q;
            }
            
            return d->next;
        }
    };

### 57 二叉树的下一个结点 ###

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

/*
    struct TreeLinkNode {
        int val;
        struct TreeLinkNode *left;
        struct TreeLinkNode *right;
        struct TreeLinkNode *next;
        TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
            
        }
    };
    根据二叉树中序遍历，可以知道：
    （1）如果当前节点有右子树，则右子树中最左侧的节点就是当前节点的后继
    （2）如果当前节点没有右儿子，则需要沿着father域一直向上找，找到第一个是其father左儿子的节点，该节点的father就是当前节点的后继。
    */
    class Solution {
    public:
        TreeLinkNode* GetNext(TreeLinkNode* p)
        {
            //如果当前节点有右子树，则右子树中最左侧的节点就是当前节点的后继
            if(p->right){
                p = p->right;
                while(p->left) p = p->left;
                return p;
            }
            //如果当前节点没有右儿子，则需要沿着father域一直向上找，找到第一个是其father左儿子的节点，该节点的father就是当前节点的后继。
            while(p->next && p == p->next->right) p = p->next;
            return p->next;
        }
    };

### 58 对称的二叉树 ###

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

/*
    struct TreeNode {
        int val;
        struct TreeNode *left;
        struct TreeNode *right;
        TreeNode(int x) :
                val(x), left(NULL), right(NULL) {
        }
    };
    二叉树对称 一定是左孩子与右孩子相反
    即左子树的左孩子与右子树的右孩子相等
    左子树的右孩子与右子树的左孩子相等
    空树也对应空树
    */
    class Solution {
    public:
        bool isSymmetrical(TreeNode* r)
        {
            return !r || dfs(r->left,r->right);
        }
        bool dfs(TreeNode* p, TreeNode* q){
            // 如果左右孩子有叶结点，那么两个同时都是叶结点
            if(!p||!q)return !p && !q;
            // 左子树的左孩子与右子树的右孩子相等,左子树的右孩子与右子树的左孩子相等
            return p->val == q->val && dfs(p->left,q->right) && dfs(p->right,q->left);
        }
    };

### 59 按之字形顺序打印二叉树 ###

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

/*
    struct TreeNode {
        int val;
        struct TreeNode *left;
        struct TreeNode *right;
        TreeNode(int x) :
                val(x), left(NULL), right(NULL) {
        }
    };
    */
    class Solution {
    public:
        vector<int> getVal(vector<TreeNode *> levels){
            vector<int> res;
            for( auto &x : levels)
                res.push_back(x->val);
            return res;
        }
        vector<vector<int> > Print(TreeNode* r) {
            vector<vector<int> > res;
            if(!r)return res;
            vector<TreeNode *> levels;
            levels.push_back(r);
            res.push_back(getVal(levels));
            bool zigzag = true;//奇偶层标志，true为偶数层，false为奇数层
            while(true){
                vector<TreeNode *> newLevels;// 存储每层结点
                for(auto &x : levels){//得到当前层的所有结点
                    if(x->left) newLevels.push_back(x->left);
                    if(x->right) newLevels.push_back(x->right);
                }
                if(newLevels.size()){//如果还有下一层
                    vector<int> temp = getVal(newLevels);//得到当前层的所有结点的值
                    if(zigzag)reverse(temp.begin(),temp.end());//如果是偶数层，需要反转，变成从右到左
                    res.push_back(temp);//当前层结果存储
                    levels = newLevels;//更新level为下一层
                }else break;//没有下一层 直接结束循环
                zigzag = !zigzag;//奇偶层变换
            }
            return res;
        }
        
    };

### 60 把二叉树打印成多行 ###

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

/*
    struct TreeNode {
        int val;
        struct TreeNode *left;
        struct TreeNode *right;
        TreeNode(int x) :
                val(x), left(NULL), right(NULL) {
        }
    };
    二叉树的层序遍历 不用说了吧 用队列
    这题的考点是 分层
    可以考虑 每次在输出时 先判断这层有几个结点
    循环把这些结点输出 就可以往下一层
    */
    class Solution {
    public:
            vector<vector<int> > Print(TreeNode* r) {
                vector<vector<int> > res;
                if(!r)return res;
                queue<TreeNode*> q;
                q.push(r);
                while(q.size()){
                    int l = 0, r = q.size();//得到当前层的结点个数
                    vector<int> ress;
                    while(l++ < r){//循环把这些结点输出 就可以往下一层
                        auto x = q.front();
                        q.pop();
                        ress.push_back(x->val);
                        if(x->left)q.push(x->left);
                        if(x->right)q.push(x->right);
                    }
                    res.push_back(ress);
                    
                }
                return res;
            }
        
    };

### 61 序列化二叉树 ###

请实现两个函数，分别用来序列化和反序列化二叉树

/*
    struct TreeNode {
        int val;
        struct TreeNode *left;
        struct TreeNode *right;
        TreeNode(int x) :
                val(x), left(NULL), right(NULL) {
        }
    };
    序列化二叉树:把二叉树用字符来存储
    对二叉树先序遍历，把遍历结果存入缓冲数组，从缓冲数组放入int指针,结果强转int指针为字符指针
    
    反序列化二叉树:把二叉树从存储字符中还原
    按先序遍历构建二叉树，每构建一个结点，指针往后移动一个单位
    */
    class Solution {
    public:
        vector<int> buf;
        void dfs_s(TreeNode *root) {
            if(!root) buf.push_back(0xFFFFFFFF);
            else {
                buf.push_back(root->val);
                dfs_s(root->left);
                dfs_s(root->right);
            }
        }
        TreeNode* dfs_d(int* &p) {
            if(*p==0xFFFFFFFF) {
                p++;
                return NULL;
            }
            TreeNode* res=new TreeNode(*p);
            p++;
            res->left=dfs_d(p);
            res->right=dfs_d(p);
            return res;
        }
        char* Serialize(TreeNode *root) {
            buf.clear();
            dfs_s(root);
            int bufSize=buf.size();
            int *res=new int[bufSize];
            for(int i=0;i<bufSize;i++) res[i]=buf[i];
            return (char*)res;
        }
        TreeNode* Deserialize(char *str) {
            int *p=(int*)str;
            return dfs_d(p);
        }
    
    };

### 62 二叉搜索树的第k个结点 ###

给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8）    中，按结点数值大小顺序第三小结点的值为4。

/*
    struct TreeNode {
        int val;
        struct TreeNode *left;
        struct TreeNode *right;
        TreeNode(int x) :
                val(x), left(NULL), right(NULL) {
        }
    };
    BST的中序遍历 刚好是排序的
    也就是说 把二叉树按中序遍历 遍历到第k次 即为第k小的结点
    如：（5，3，7，2，4，6，8）,BTS是：
            5
        3        7
      2   4    6   8
    
     */
    class Solution {
    public:
        int index = 0;
        TreeNode* KthNode(TreeNode* r, int k)
        {
            if(r){
                auto x = KthNode(r->left,k);//向左子树递归 找到中序遍历第一个结点
                if(x)return x;
                index++;
                if(index == k)return r;//找到了直接返回
                x = KthNode(r->right,k);
                if(x)return x;
            }
            return 0;
        }
    
        
    };

### 63 数据流中的中位数 ###

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

/*
    维护两个优先队列 分别是最大优先队列p（大数在top），最小优先队列q（小数在top）
    约束：
    1、abs(p.size() - q.size())<2:
    （1）if(p.size() == q.size() + 2)q.push(p.top()),p.pop();
    （2）if(p.size() + 1 == q.size())p.push(q.top()),q.pop();
    2p中所有的数要比q的任意数小
    
    如：2 3 5 6 7 9 4 1 0
    epoch1: p:2 q:{}
    epoch2: p:2 q:3
    epoch3: p:2 q:3,5 -> p:2,3 q:5
    epoch4: p:2,3 q:5,6
    epoch5: p:2,3 q:5,6,7 -> p:2,3,5 q:6,7
    epoch6: p:2,3,5 q:6,7,9
    epoch7: p:2,3,4,5 q:6,7,9
    epoch8: p:1,2,3,4,5 q:6,7,9 -> p:1,2,3,4 q:5,6,7,9
    epoch9: p:0,1,2,3,4 q:5,6,7,9
    median: p.top() = 4
    */
    
    class Solution {
    public:
        priority_queue<int> p;//最大优先队列
        priority_queue<int,vector<int>,greater<int>> q;//最小优先队列
        void Insert(int num)
        {
            if(!p.size() || num <= p.top())p.push(num);
            else q.push(num);
            if(p.size() == q.size() + 2)q.push(p.top()),p.pop();
            if(p.size() + 1 == q.size())p.push(q.top()),q.pop();
        }
    
        double GetMedian()
        { 
            return p.size() == q.size()?(p.top() + q.top()) / 2.0 : p.top();
        }
    
    };

### 64 滑动窗口的最大值 ###

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组\{2,3,4,2,6,2,5,1\}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为\{4,4,6,6,6,5\}； 针对数组\{2,3,4,2,6,2,5,1\}的滑动窗口有以下6个： \{\[2,3,4\],2,6,2,5,1\}， \{2,\[3,4,2\],6,2,5,1\}， \{2,3,\[4,2,6\],2,5,1\}， \{2,3,4,\[2,6,2\],5,1\}， \{2,3,4,2,\[6,2,5\],1\}， \{2,3,4,2,6,\[2,5,1\]\}。

class Solution {
    public:
        vector<int> maxInWindows(const vector<int>& num, unsigned int size)
        {
            vector<int> res;
            if(!num.size() || size <= 0 || size > num.size())return res;
            int l = 0, r = size - 1, max;
            
            while(r < num.size()){
                max = INT32_MIN;
                for(int i = l; i <= r; i++)
                    if(max < num[i])max = num[i];
                res.push_back(max);
                l++;
                r++;
            }
            return res;
        }
        
    };

### 65 矩阵中的路径 ###

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。 例如 a b c e s f c s a d e e 这样的3 X 4 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

/*
    dfs
    递归结束标志：
    （1）达到边界条件 或者已经遍历 返回不满足
    （2）能遍历到字符串末尾 说明找了一条路径 返回满足
    
    试探后回溯 一定记得将原来标记走过的点恢复
    */
    class Solution {
    public:
        bool hasPath(char* matrix, int rows, int cols, char* str)
        {
            int strLen = strlen(str);
            if(rows < 0 || cols < 0 || strLen <= 0)return false;
            bool *isVisited = new bool[rows * cols];
            memset(isVisited, 0, rows * cols);
            for(int i = 0; i < rows; i++){
                for(int j = 0; j < cols; j++){
                    if(dfs(matrix, rows, cols, i, j, str, strLen, 0, isVisited))return true;
                }
            }
            delete[] isVisited;
            return false;
        }
    
        bool dfs(char* matrix, int rows, int cols, int row, int col, char* str, int strLen, int strIndex, bool *isVisited){
            //--边界条件 当前走的和原来的字符一一样 或者 已经走过了 就不满足 直接返回
            if(matrix[row * cols + col] != str[strIndex] || isVisited[row * cols + col]) return false;
            //如果走到字符串末尾了 说明找到路线了 满足 返回
            if(strIndex == strLen - 1) return true;
            //当前点匹配  遍历四周的下一个节点,将当前格设为已经遍历
            isVisited[row * cols + col] = true;
            //定义四个方向 左下右上
            int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
            for(int i = 0; i < 4; i++) //遍历周围的节点
            {
                int a = row + dx[i], b = col + dy[i]; 
                if(a >= 0 && a < rows && b >= 0 && b < cols && !isVisited[a * cols + b])
                    if(dfs(matrix, rows, cols, a, b, str, strLen, strIndex + 1, isVisited)) return true;
            }
            isVisited[row * cols + col] = false;//回溯关键  恢复现场  若不满足 将当前结点设置为未遍历回来
            return false;//返回结果，表示找不到
    
        }
    };

### 66 机器人的运动范围 ###

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

class Solution {
    public:
        int movingCount(int threshold, int rows, int cols)
        {
            if(!rows || !cols)return 0;
            // bfs用队列
            queue<pair<int,int>> q;
            // 初始所有坑都没走过
            vector<vector<bool>> st(rows, vector<bool>(cols, false));
            //枚举左下右上四个方向 int x = t.first + dx[i], y = t.second + dy[i];
            int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
            // 结果
            int res = 0;
            //从第一个点开始走
            q.push({0, 0});
            
            while (q.size()) {
                auto t = q.front();
                q.pop();
                // 如果已经走过或者和大于域值 直接算下一个
                if (st[t.first][t.second] || getSum(t) > threshold) continue;
                // 可走 格子加1并标记该坑已经走过
                res ++ ;
                st[t.first][t.second] = true;
                
                //扫描四个方向格子 加入到队列
                for (int i = 0; i < 4; i ++ ) {
                    int x = t.first + dx[i], y = t.second + dy[i];
                    if (x >= 0 && x < rows && y >= 0 && y < cols) q.push({x, y});// 将满足条件的点加入队列
                }
            }
            
            return res;
        }
        // 不能进入行坐标和列坐标的数位之和大于k的格子
        // 判断能不能进入当前点
        int getSum(pair<int,int> p){
            int sum = 0;
            while(p.first){
                sum += p.first % 10;
                p.first /= 10;
            }
            while(p.second){
                sum += p.second % 10;
                p.second /= 10;
            }
            return sum;
        }
    };

[webp]: /images/20211210/5694fa81f144490dbe9b734c5c99275a.png