剑指offer题目练习（三）

题目二十一

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

思路：首先就是要了解二叉搜索树的概念，以及后续遍历的概念，找出根节点，确定左右树，递归操作。

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        return BSTree(sequence,0,sequence.size()-1);
    }
    
    bool BSTree(vector<int> sequence,int start,int end){
        if (sequence.empty()||start > end){
            return false;
        }
        int i = start;
        int root = sequence[end];
        for (;i<end;i++){
            if (sequence[i] > root){
                break;
            }
        }
        int j = i+1;
        for (;j<end;j++){
            if (sequence[j] < root){
                return false;
            }
        }
        bool left = true;
        if(i > start){
            return BSTree(sequence,start,i-1);
        }
        bool right = true;
        if(j < end){
            return BSTree(sequence,i+1,end-1);
        }
        
        return left&right;
    }
};

题目二十二

输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

思路：还是递归思想，每遍历到一个节点就将其值加入到一个数组中，并且累加其值，如果这个累加值刚好等于给定的整数，并且这个节点再无子节点，就将这个数组加入到一个全局数组中。

class Solution {
public:
    vector<vector<int> > allPath;
    
    void Find(TreeNode*root,int expectNumber,vector<int>path,int sum){
        path.push_back(root->val);
        sum += root->val;
        if (root->left == nullptr && root->right == nullptr){
            if (sum == expectNumber){
                allPath.push_back(path);
            }
        }
        if (root->left){
            Find(root->left,expectNumber,path,sum);
        }
        if (root->right){
            Find(root->right,expectNumber,path,sum);
        }
    }
    
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        if (root == nullptr){
            return allPath;
        }
        vector<int> path;
        int sum = 0;
        Find(root,expectNumber,path,sum);
        return allPath;
    }
};

题目二十三

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

思路：典型的问题拆分，可以分为三步，复制链表，链接随机指针，拆分链表

class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead)
    {
        if (pHead == nullptr){
            return pHead;
        }
        //首先克隆链表
        cloneNodeList(pHead);
        connectRandom(pHead);
        return reconnectList(pHead);
    }
    
    void cloneNodeList(RandomListNode *pHead){
        RandomListNode *pNode = pHead;
        while (pNode != nullptr){
            //克隆时注意语句顺序，不要让链表断掉
            RandomListNode *cloneNode = new RandomListNode(pNode->label);
            cloneNode->next = pNode->next;
            pNode->next = cloneNode;
            pNode = cloneNode->next;
        }
    }
    
    void connectRandom(RandomListNode *pHead){
        RandomListNode *pNode = pHead;
        while (pNode != nullptr){
            //链接随机指针
            RandomListNode *cloneNode = pNode->next;
            if (pNode->random){
                cloneNode->random = pNode->random->next;
            }
            pNode = cloneNode->next;
        }
    }
    
    RandomListNode *reconnectList(RandomListNode *phead){
        RandomListNode *pNode = phead;
        RandomListNode *resultList = pNode->next;
        while (pNode != nullptr){
            RandomListNode *cloneNode = pNode->next;
            pNode->next = cloneNode->next;
            pNode = pNode->next;
            if (pNode){
                cloneNode->next = pNode->next;
            }
        }
        return resultList;
    }
};

题目二十四

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

思路：二叉搜索树的中序遍历结果其实就是排序的，可以利用这一点，中序遍历二叉树，然后对指针进行操作

class Solution {
public:
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        if (pRootOfTree == nullptr){
            return nullptr;
        }
        TreeNode *pre = nullptr;
        convert2List(pRootOfTree,pre);
        while (pre->left){
            pre = pre->left;
        }
        return pre;
    }
    
    void convert2List(TreeNode *cur,TreeNode *&pre){
        if (cur == nullptr){
            return;
        }else{
            //开始中序遍历
            if (cur->left){
                convert2List(cur->left,pre);
            }
            cur->left = pre;
            if (pre){
                pre->right = cur;
            }
            pre = cur;
            
            if (cur->right){
                convert2List(cur->right,pre);
            }
        }
    }
};

题目二十五

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

思路：我们可以首先让字符串首字母与后面的字符进行交换，比如abc，第一次换完为bac，然后在换成cba，得到三个字符串，在让这三个字符串的第二位与后面交换，比如abc变为acb，bac变成bca。

class Solution {
public:
    vector<string> Permutation(string str) {
        vector<string> res;
        if (str == ""){
            return res;
        }
        helper(str,res,0);
        return res;
    }
    void helper(string str,vector<string> & res,int begin){
        int len = str.size();
        if (begin == len){
            res.push_back(str);
        }
        
        for (int i = begin;i<len;i++){
            if (i != begin && str[i] == str[begin]){
                continue;
            }
            swap(str[i],str[begin]);
            helper(str,res,begin+1);
        }
    }
};

题目二十六

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

思路：如果有符合条件的数字，则它出现的次数比其他所有数字出现的次数和还要多。在遍历数组时保存两个值：一是数组中一个数字，一是次数。遍历下一个数字时，若它与之前保存的数字相同，则次数加1，否则次数减1；若次数为0，则保存下一个数字。

int MoreThanHalfNum_Solution(vector<int> numbers) {
        if (numbers.size() == 0){
            return 0;
        }
        
        //设置一个临时变量
        int temp = numbers[0];
        //次数
        int count = 1;
        
        for (int i = 0;i < numbers.size();i++){
            //如果count变为0，说明遍历到的数字和temp不相同，更换temp
            if (count == 0){
                temp = numbers[i];
            }else if(temp == numbers[i]){
                //相同则count++
                count++;
            }else{
                //否则count--
                count--;
            }
        }
        
        int times = 0;
        for (int i = 0;i < numbers.size();i++){
            if (temp == numbers[i]){
                times++;
            }
        }
        
        if (times > numbers.size()/2){
            return temp;
        }else{
            return 0;
        }
    }

题目二十七

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

思路：快速排序即可

vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> res;
        if (k > input.size()){
            return res;
        }
        sort(input.begin(),input.end());
        for (int i = 0;i < k;i++){
            res.push_back(input[i]);
        }
        return res;
    }

题目二十八

{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和

思路：我们可以一开始就设定两个值cursum和maxsum，让它们都等于6，也就是第一个数字，然后我们开始遍历数组，如果当前的sum小于下一个数，那么直接把cursum记录为下一个数，如果cursum 打击maxsum，则maxsum等于cursum。

int FindGreatestSumOfSubArray(vector<int> array) {
        int cursum = array[0];
        int maxsum = array[0];
        for (int i = 1;i < array.size();i++){
            cursum += array[i];
            if (cursum < array[i]){
                cursum = array[i];
            }
            
            if (cursum > maxsum){
                maxsum = cursum;
            }
        }
        return maxsum;
    }

题目二十九

求出1 ~ 13的整数中1出现的次数,特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次，如何很快的求出任意非负整数区间中1出现的次数(从1 到 n 中1出现的次数）？

思路：可以使用%10运算求出个位是否为1，然后将这个数字除以十再次计算这时的个位数是否为1。

int NumberOf1Between1AndN_Solution(int n)
   {
       int count = 0;
       if (n < 1){
           return count;
       }
       
       for (int i = 1;i <=n;i++){
           int temp = i;
           while(temp){
               if (temp%10==1){
                   count++;
               }
               temp /= 10;
           }
       }
       return count;
   }

题目三十

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

思路：之前做过字符串有多少种排列的题目，这个题目就可以看成可以组成多少种不同的数字，再进行快排即可。

class Solution {
public:
    string PrintMinNumber(vector<int> numbers) {
        int len = numbers.size();
        if (len <= 0){
            return "";
        }
        vector<vector<int> > res;
        helper(numbers,res,0);
        
        int res_len = res.size();
        vector<string> str_arr;
        for (int i = 0;i < res_len;i++){
            vector<int> temp = res[i];
            string temp_str;
            for (int j = 0;j < temp.size();j++){
                temp_str += to_string(temp[j]);
            }
            str_arr.push_back(temp_str);
        }
        
        sort(str_arr.begin(),str_arr.end());
        
        string res_str = str_arr[0];
        
        return res_str;
    }
    
    void helper(vector<int> numbers,vector<vector<int> > & res,int begin){
        int count = numbers.size();
        if (begin == count){
            res.push_back(numbers);
            return;
        }
        
        for (int i = begin;i < count;i++){
            if (i != begin && numbers[i] == numbers[begin]){
                continue;
            }
            
            int temp = numbers[i];
            numbers[i] = numbers[begin];
            numbers[begin] = temp;
            helper(numbers,res,begin+1);
        }
        
    }
};