leetcode解题思路分析（十四）92 - 98题

亦凉 2023-07-10 08:19 3阅读 0赞

1.  反转链表 II  
    反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。  
    说明:1 ≤ m ≤ n ≤ 链表长度。

**找到第m个开始计算，逐个反转即可**

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
    class Solution { 
    public:
        ListNode* reverseBetween(ListNode* head, int m, int n) {   
            ListNode *dummy = new ListNode(-1);
            dummy->next = head;
    
            // 第m-1个节点
            ListNode *pre=dummy;
            for(int i=1; i<m; i++){ 
                pre = pre->next;
            }
    
            // 第m个节点
            ListNode *t, *cur=pre->next, *mNode=pre->next;
            // 头插法
            for(int i=m; i<=n; i++){ 
                t = cur->next;
                cur->next = pre->next;
                pre->next = cur;
                cur = t;
            }
            // 第m个节点指向第n+1个节点
            mNode->next = cur;
            
            return dummy->next;
        }
    };

1.  复原IP地址  
    给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

**本题采用回溯剪纸进行，IP地址的特点在于用点分十进制表示，其中四个数字均在0-255之间，所以可以不断地加上点，如果最后大于255则回溯上一步继续尝试**

class Solution { 
        vector<string> res;
    public:
    	vector<string> restoreIpAddresses(string s) { 
    		string ip;
    		helper(s, 0, ip);
    		return res;
    	}
    	void helper(string s, int n, string ip) { 
    		if (n == 4) 
            { 
    			if (s.empty()) res.push_back(ip); 
    		}
    		else 
            { 
    			for (int k = 1; k < 4; ++k) 
                { 
    				if (s.size() < k) break;
    				int val = stoi(s.substr(0, k));
    				if (val > 255 || k != std::to_string(val).size()) continue; //剪枝
    				helper(s.substr(k), n + 1, ip + s.substr(0, k) + (n == 3 ? "" : "."));
    			}
    		}
    		return;
    	}
    };

1.  二叉树中序遍历

**中序遍历即左-根-右的顺序，递归很容易，非递归的话先把根存栈内，搜索左边然后再出栈，再搜索右边即可**

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
    class Solution { 
        vector<int> ret;
    public:
        vector<int> inorderTraversal(TreeNode* root) { 
            if(root) { 
                inorderTraversal(root->left);
                ret.push_back(root->val);
                inorderTraversal(root->right);
            }
            return ret;
        }
    };

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
    class Solution { 
    public:
        vector<int> inorderTraversal(TreeNode* root) { 
            stack<TreeNode*> S;
            vector<int> v;
            TreeNode* rt = root;
            while(rt || S.size()){ 
                while(rt){ 
                    S.push(rt);
                    rt=rt->left;
                }
                rt=S.top();S.pop();
                v.push_back(rt->val);
                rt=rt->right;
            }
            return v;        
        }
    };

1.  不同的二叉搜索树  
    给定一个整数 n，生成所有由 1 … n 为节点所组成的二叉搜索树。

**对于求全解，回溯法显然可解，由于此问题具有最优子结构，也可以用动态规划求解：依次求解从1到n的结果  
设当前在求解k的结果，则可以设根值r为1到k分别的情况，左子树的所有可能情况在dp\[r - 1\]中，右子树的所有可能情况在dp\[k - r\]中。备注: 右子树最终拷贝的时候启示值需要从r + 1开始**

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
    class Solution { 
    public:
    /* 递归版本的拷贝树实现 TreeNode *copyTree(TreeNode *root, int delta = 0) { auto nroot = new TreeNode(root->val + delta); if (root->left) nroot->left = copyTree(root->left, delta); if (root->right) nroot->right = copyTree(root->right, delta); return nroot; } */
        // 非递归版本的拷贝树实现
        TreeNode *copyTree(TreeNode *root, int delta = 0) { 
            auto nroot = new TreeNode(root->val + delta);
            queue<TreeNode*> qt;
            queue<TreeNode*> qo;
            qo.push(root);
            qt.push(nroot);
            while (!qt.empty()) { 
                auto o_root = qo.front();
                qo.pop();
                auto t_root = qt.front();
                qt.pop();
                if (o_root->left) { 
                    t_root->left = new TreeNode(o_root->left->val + delta);
                    qo.push(o_root->left);
                    qt.push(t_root->left);
                }
                if (o_root->right) { 
                    t_root->right = new TreeNode(o_root->right->val + delta);
                    qo.push(o_root->right);
                    qt.push(t_root->right);
                }
            }
            return nroot;
        }
    
        vector<TreeNode*> generateTrees(int n) { 
            // 使用static变量，节省用例不同用例执行时的重复求解开销
            static vector<vector<TreeNode*>> dp(1, vector<TreeNode*>(1, NULL));
            int c_size = n + 1; 
            int o_size = dp.size();
            if (c_size > dp.size())
                dp.resize(c_size);
    
            for (int i = o_size; i <= n; i++) {  // 升序求解
                for (int j = 1; j <= i; j++) {  // 遍历以不同的数的为根
                    const auto &left = dp[j - 1];
                    const auto &right = dp[i - j];
                    auto &cc = dp[i];
                    for (const auto left_ptr : left) // 遍历所有可能的左子树
                        for (const auto right_ptr : right) {  // 遍历所有可能的右子树
                            auto root = new TreeNode(j);
                            if (j > 1)
                                root->left = copyTree(left_ptr); // 拷贝左子树
                            if (i > j)
                                root->right = copyTree(right_ptr, j); // 拷贝右子树，并加上偏移值
                            cc.push_back(root);
                        }
                }
            }
            if (n == 0)
                return { };
            return dp[n];
        }
    };

1.  不同的二叉搜索树  
    给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？

**本题和上题类似，但是只需要给出二叉树的数目，根据卡特兰数的定义可以直接求解**

class Solution 
    { 
    public:
        int numTrees(int n) 
        { 
    
            int dp[n + 1] = { 0};
    
            dp[0] = 1;
            dp[1] = 1;
            
            for(int i = 2; i < n + 1; i++)
            { 
                for(int j = 1; j < i + 1; j++) 
                { 
                    dp[i] += dp[j-1] * dp[i-j];
                }
            }
            
            return dp[n];
        }
    };

1.  交错字符串  
    给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。

**比较容易理解的方式是采取二维数组做动态规划：dp\[i\]\[j\]表示s1的子串i和s2的子串j是否可以组成s3的子串。但是这种存储方式会比较浪费。更好的方式是采取一维数组dp\[i\]表示s1的子串和s2的子串在长度为i的情况下是否可以组成s3的子串。但是需要考虑较多情况，比如一个字符串已经结束了等**

class Solution { 
    public:
        bool isInterleave(string s1, string s2, string s3) { 
            const int len1=s1.size();
            const int len2=s2.size();
            const int len3=s3.size();
            if(len1 == 0) return s2 == s3;
            if(len2 == 0) return s1 == s3;
            if(len1 + len2 != len3) return false;
            vector<int> d(len1+1,0);
            for(int j=0;j<=len2;++j){ 
                for(int k=0;k<=len1;++k){ 
                    const int i = j + k;
                    if(j == 0 && k == 0){ 
                        d[k] = 1;
                    }else if(j == 0 && k > 0){ 
                        d[k] = d[k - 1] && (s3[i - 1] == s1[k - 1]);
                    }else if(k == 0 && j > 0){ 
                        d[k] = d[k] && s3[i - 1] == s2[j - 1];
                    }else{ 
                        d[k] = d[k - 1] && (s3[i - 1] == s1[k - 1]) || 
                               d[k] && (s3[i - 1] == s2[j - 1]);
                    }
                }
            }
            return d[len1];
        }
    };

1.  验证二叉搜索树  
    给定一个二叉树，判断其是否是一个有效的二叉搜索树。  
    假设一个二叉搜索树具有如下特征：  
    节点的左子树只包含小于当前节点的数。  
    节点的右子树只包含大于当前节点的数。  
    所有左子树和右子树自身必须也是二叉搜索树。

**作为树的遍历，可以采取前序、中序、后序，可以用递归也可以用堆栈，其实都差不多。引入上下边界  
对于树的每个节点 val ，设其上下边界 low , high。(用 long 防止 INT\_MAX 溢出 )  
判断根结点时，须满足 low < val < high ，否则返回 false  
判断左节点时，仅 上界 变化 ( 新上界为 high 与 val 较小值。又因 val 必小于 high，故新上界为 val )  
判断右节点时，仅 下界 变化 ( 同理，新下界为 val )**

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
    class Solution { 
    public:
        bool fun(struct TreeNode* root, long low, long high) { 
            if (root == NULL) return true;
            long num = root->val;
            if (num <= low || num >= high) return false;
            return fun(root->left, low, num) && fun(root->right, num, high);
        }
        bool isValidBST(struct TreeNode* root){ 
            return fun(root, LONG_MIN, LONG_MAX);
        }
    
    };