C++ 版本剑指offer

- 日理万妓 2023-10-11 13:02 20阅读 0赞

### 1. 二维数组的查找： ###

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

class Solution {
    public:
        bool Find(int target, vector<vector<int> > array) {
            // 从左下角开始计算
            if (array.empty()) return false;
            int rows = array.size();
            int cols = array[0].size();
            
            int col = 0;
            int row = rows -1;  // 此处记得要减去 1 
            while (col < cols && row >= 0){
                if (array[row][col] == target) return true;
                else if (array[row][col] > target){
                    row --;
                }else{
                    col ++;
                }
    
            }
            return false;
            
        }
    };

### 2.替换空格 ###

从后向前替换，先遍历一遍统计空格的数目，然后扩张字符串使得可以放下替换后的字符，然后从后向前依次复制，非空格字符直接复制，空格字符用题目要求的替换。

class Solution {
    public:
    	void replaceSpace(char *str,int length) {
            if (str == nullptr || length == 0) return ;
            int spaceCount = 0;
            // 计算空格的数量
            for (int i = 0; i< length; i++){
                if (str[i] == ' '){
                    spaceCount += 1;
                }
            }
            if (spaceCount == 0){
                return ;
            }
            int new_length = length + 2 * spaceCount;
            int old_index = length - 1;
            int new_index = new_length -1;
            
            while (new_index > old_index && old_index >= 0){
                if (str[old_index] == ' '){
                    str[new_index--] = '0';
                    str[new_index--] ='2';
                    str[new_index--] ='%';
                    old_index --;
    
                }else{
                    str[new_index--] = str[old_index--]; // 将old 的字符串分配给新的
                }
            }
    
    	}
    };

###  ###

### 4.重建二叉树 ###

/**
     * Definition for binary tree
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
            if (pre.size() == 0 || vin.size() == 0) return NULL;
            vector<int> pre_left, tin_left;
            vector<int> pre_right, tin_right;
            
            // 前序第一个值作为根节点
            TreeNode* root = new TreeNode(pre[0]);
            // 找到第一个根节点，在tin 中的位置
            auto pos = find(vin.begin(), vin.end(), pre[0]);
            int index = pos - vin.begin();
            pre_left = vector<int> (pre.begin()+1, pre.begin() + index +1);
            tin_left = vector<int> (vin.begin(), vin.begin() + index);
            
            pre_right = vector<int> (pre.begin()+index+1, pre.end());
            tin_right = vector<int> (vin.begin() +index+1, vin.end());
            
            root->left = reConstructBinaryTree(pre_left, tin_left);
            root->right = reConstructBinaryTree(pre_right, tin_right);
            return root;
            
            
        }
    };

##  ##

### 树的子结构 ###

/*
    struct TreeNode {
    	int val;
    	struct TreeNode *left;
    	struct TreeNode *right;
    	TreeNode(int x) :
    			val(x), left(NULL), right(NULL) {
    	}
    };*/
    class Solution {
    public:
        bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
        {
            if (pRoot1 == nullptr || pRoot2 == nullptr) return false;
            bool result = false;
            // 如果结点相同，则递归判断左右结点是否相同
            if (pRoot1->val == pRoot2->val){
                result = isSubTree(pRoot1, pRoot2);
            }
            
            // 如果结点不相同，则判断A 树的左子树，右子树
            if (result == false){
                result = HasSubtree(pRoot1->left, pRoot2);
            }
            if (result == false){
                result = HasSubtree(pRoot1->right, pRoot2);
            }
            return result;
    
        }
        
        bool isSubTree(TreeNode* pRoot1, TreeNode* pRoot2){
            if(pRoot2 == nullptr) return true;
            if (pRoot1 == nullptr) return false;
            bool sub1, sub2, sub3;
            sub1 = isSubTree(pRoot1->left, pRoot2->left);
            sub2 = isSubTree(pRoot1->right, pRoot2->right);
            sub3 = (pRoot1->val == pRoot2->val);
            return (sub1 && sub2 && sub3);
        }
    };

### 二叉树的镜像 ###

/*
    struct TreeNode {
    	int val;
    	struct TreeNode *left;
    	struct TreeNode *right;
    	TreeNode(int x) :
    			val(x), left(NULL), right(NULL) {
    	}
    };*/
    class Solution {
    public:
        void Mirror(TreeNode *pRoot) {
            // 先交换左右2个结点，再交换2 个子树
            if (pRoot == nullptr || (pRoot->left == nullptr && pRoot->right == nullptr)){
                return;
            }
            TreeNode* temp = NULL;
            temp = pRoot->left;
            pRoot->left = pRoot->right;
            pRoot->right = temp;
            
            if (pRoot->left != nullptr){
                Mirror(pRoot->left);
            }
            if (pRoot->right != nullptr){
                Mirror(pRoot->right);
            }
            
            
        }
    };

### 包含min函数的栈 ###

#include <vector>
    using namespace std;
    class Solution {
    private:
        vector<int> minstack;
        vector<int> stack;
    public:
        void push(int value) {
            stack.push_back(value);
            if (minstack.size() == 0 || min() > value){
                minstack.push_back(value);
            }else{
                minstack.push_back(min());
            }
        }
        void pop() {
            stack.pop_back();
            minstack.pop_back();
        }
        int top() {
            return stack[stack.size()-1];
        }
        int min() {
            return minstack[minstack.size()-1];
        }
    };

使用栈

class Solution {
    private:
        stack<int> stack1, minstack;
    public:
        void push(int value) {
            if (minstack.empty() || min() > value){
                minstack.push(value);
                stack1.push(value);
            }else{
                minstack.push(min());
                stack1.push(value);
            }
        }
        void pop() {
            stack1.pop();
            minstack.pop();
        }
        int top() {
            return stack1.top();
        }
        int min() {
            return minstack.top();
        }
    };

### 栈的压入弹出序列 ###

class Solution {
    public:
        bool IsPopOrder(vector<int> pushV,vector<int> popV) {
            if (pushV.size() == 0 || popV.size() == 0){
                return false;
            }
            vector<int> stack;
            for (int i =0; i < pushV.size(); i++){
                stack.push_back(pushV[i]);
                while (popV.size() != 0 && stack[stack.size()-1] == popV[0]){
                    stack.pop_back();
                    popV.erase(popV.begin());
                }
            }
            if (stack.size() == 0){
                return true;
            }else{
                return false;
            }
        }
    };

### 从上往下打印二叉树 ###

使用队列

/*
    struct TreeNode {
    	int val;
    	struct TreeNode *left;
    	struct TreeNode *right;
    	TreeNode(int x) :
    			val(x), left(NULL), right(NULL) {
    	}
    };*/
    class Solution {
    public:
        vector<int> PrintFromTopToBottom(TreeNode* root) {
            vector<int> res;
            if (root == nullptr){
                return res;
            }
            queue<TreeNode*> q;
            q.push(root);
            while (!q.empty()){
                res.push_back(q.front()->val);  // 将队列中首个元素放在res中
                if (q.front() -> left != nullptr){
                    q.push(q.front() -> left);
                }
                if (q.front() -> right != nullptr){
                    q.push(q.front() -> right);
                }
                q.pop();  // 将首个元素删除
            }
            return res;
    
        }
    };

### 二叉树的深度 ###

/*
    struct TreeNode {
    	int val;
    	struct TreeNode *left;
    	struct TreeNode *right;
    	TreeNode(int x) :
    			val(x), left(NULL), right(NULL) {
    	}
    };*/
    class Solution {
    public:
        int TreeDepth(TreeNode* pRoot)
        {
            if (pRoot == nullptr) return 0;
            if (pRoot->left == nullptr && pRoot->right == nullptr){
                return 1;
            }
            int len = max(TreeDepth(pRoot->left), TreeDepth(pRoot->right));
            return len +1;
                          
        
        }
    };

### 平衡二叉树 ###

class Solution {
    public:
        bool IsBalanced_Solution(TreeNode* pRoot) {
            if (pRoot == nullptr){
                return true;
            }
            int ld = getDepth(pRoot->left);
            int rd = getDepth(pRoot->right);
            if (abs(ld - rd) > 1){  // 如果左右子树深度大于1，则不是
                return false;
            }
            bool pleft, pright;
            pleft = IsBalanced_Solution(pRoot->left); // 递归判断左右子树
            pright  = IsBalanced_Solution(pRoot->right);
            return (pleft && pright);
    
        }
        
        int getDepth(TreeNode* pRoot){  // 获取树的深度
            if (pRoot == nullptr){
                return 0;
            }
            int leftDepth, rightDepth;
            leftDepth = getDepth(pRoot->left);
            rightDepth = getDepth(pRoot->right);
            return 1 + max(leftDepth, rightDepth);
        }
    };

### 第一次只出现一次的字符 ###

使用map

class Solution {
    public:
        int FirstNotRepeatingChar(string str) {
            map<char, int> mp;
            for (int i = 0;i < str.size(); i++){
                mp[str[i]] ++;
            }
            for (int i = 0; i< str.size(); i++){
                if (mp[str[i]] == 1){
                    return i;
                }
            }
            return -1;
        }
    };

### 数组出现次数超过一半的数字 ###

class Solution {
    public:
        int MoreThanHalfNum_Solution(vector<int> numbers) {
            map<int, int> mp;
            int halfLen = numbers.size() / 2;
            for (int i =0 ; i < numbers.size(); i++){
                mp[numbers[i]] ++;
            }
            for (int i = 0; i< numbers.size(); i++){
                if (mp[numbers[i]] > halfLen){
                    return numbers[i];
                }
            }
            return 0;
        }
    };

### 二叉树的和为某一值的路径 ###

/*
    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> > res;
        vector<int> path;
        void find(TreeNode* root, int sum){  
            if (!root) return;
            path.push_back(root->val);
            if (root->left == nullptr && root->right == nullptr && sum == root->val){
                res.push_back(path);  // 如果左右子树不在，且 最后的sum值就是结点值，则代表找到路径
            }else{
                if (root->left){
                    find(root->left, sum-root->val);
                }
                if (root->right){
                    find(root->right, sum - root->val);
                }
                
            }
            path.pop_back(); // 回溯查找
        }
        vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
            find(root, expectNumber);
            return res;
    
        }
    };

### 二叉树中序的下一个结点（有父节点） ###

1， 如果存在右子树，一直找到左节点； 2.如果不存在，则往上找到父节点

/*
    struct TreeLinkNode {
        int val;
        struct TreeLinkNode *left;
        struct TreeLinkNode *right;
        struct TreeLinkNode *next;
        TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
            
        }
    };
    */
    class Solution {
    public:
        TreeLinkNode* GetNext(TreeLinkNode* pNode)
        {
            // 1， 如果存在右子树，一直找到左节点； 2.如果不存在，则往上找到父节点
            if (pNode->right){
                pNode = pNode->right;
                while (pNode->left){
                    pNode = pNode->left;  // 一直找到左结点
                }
                return pNode;
            }
            while (pNode->next){  // 如果存在父亲节点
                TreeLinkNode* pRoot = pNode->next;
                if (pRoot->left == pNode) return pRoot;
                pNode = pNode->next;
            }
            return NULL;
        }
    };

### 判断是否是对称二叉树 ###

借助辅助函数：判断1.结点值是否相同，2.左子树的右结点 与 右子树左节点是否相同 3. 左子树的左结点 与 右子树右节点是否相同

/*
    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* pRoot)
        {
            if (!pRoot || (!pRoot->left && !pRoot->right)) return true;  // 如果只有0，或1 个结点
            return helper(pRoot->left, pRoot->right);
        
        }
        bool helper(TreeNode* left, TreeNode* right){
            if (!left && !right) return true;
            if (!left || !right) return false;
            bool left_judge = helper(left->left, right->right);
            bool right_judge = helper(left->right, right->left);
            bool isBan = (left->val == right ->val);
            return (left_judge && right_judge && isBan);
        }
    
    };

### 按之字形打印二叉树 ###

/*
    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* pRoot) {
            // 使用队列， 和一个bool类型，是偶数时则翻转
            vector<vector<int>> res;
            if (!pRoot) return res;
            queue<TreeNode*> q;
            bool rev = false;
            q.push(pRoot);
            while (!q.empty()){
                vector<int> vec;
                int size = q.size();
                for (int i =0; i < size; i++){
    
                    TreeNode* node = q.front();
                    q.pop();
                    vec.push_back(node->val);
                    if (node->left) q.push(node->left);
                    if (node->right) q.push(node->right);
                }
                if (rev){
                    std::reverse(vec.begin(), vec.end());
                }
                res.push_back(vec);
                rev = !rev;  // 在 true 和 false 之间转换
            }
            return res;
        }
        
    };

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

使用队列的方法：

/*
    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* pRoot) {
                vector<vector<int> > res;
                if (!pRoot) return res;
                queue<TreeNode*> q;
                q.push(pRoot);
                
                while (!q.empty()){
                    vector<int> vec;
                    int size = q.size();
                    for (int i=0; i< size; i++){
                        TreeNode* node = q.front();
                        q.pop();
                        vec.push_back(node->val);
                        if (node->left) q.push(node->left);
                        if (node->right) q.push(node->right);
                    }
                    res.push_back(vec);
                }
                return res;
                
            
            }
        
    };

### 序列二叉树 ###

### 二叉搜索树的后序遍历顺序 ###

### 二叉树和双向链表 ###

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

通过中序遍历获取结点值

/*
    struct TreeNode {
        int val;
        struct TreeNode *left;
        struct TreeNode *right;
        TreeNode(int x) :
                val(x), left(NULL), right(NULL) {
        }
    };
    */
    class Solution {
    private:
        int count = 0;
    public:
        TreeNode* KthNode(TreeNode* pRoot, int k)
        {
            if (pRoot){
                // 中序遍历结点值， 根 左 右
                TreeNode* ret = KthNode(pRoot->left, k);
                if (ret){
                    return ret;
                }
                if (++count == k) return pRoot;
                ret = KthNode(pRoot->right, k);
                if (ret){
                    return ret;
                }
            }
            return nullptr;
            
        }
    
        
    };