2021.1.26 算法练习

1128. 等价多米诺骨牌对的数量

算法思路:

这题是要求出给出的一堆数对中,统计有多少对数对符合要求

形式上,dominoes[i] = [a, b] 和 dominoes[j] = [c, d] 等价的前提是 a == c 且 b == d ,或是 a == d 且 b == c。

因此 [1, 2]和[2, 1]可以认为是等价的的,判断两者相同可以通过较小的数*10 + 较大的数的值来进行比较,由于题目规定数值是一位数,所以这样相加不会出现重合。

class Solution {
public:
    int numEquivDominoPairs(vector<vector<int>>& dominoes) {
        // table用于保存,【较小的数*10 + 较大的数】有多少个,由于数值规定为一位数,所以不会超过100
        vector<int> table(100) ;
        int ans = 0 ;
        for (int i = 0;i < dominoes.size();i++) {
            if (dominoes[i][0] > dominoes[i][1]) {
                // 当该表达式第一次出现时,table中对应数值为0, ans = 0,此时凑不成一对
                // 第二次出现时,table中对应数值为1,ans = 0 + 1,此时可以凑成一对
                // 第三次出现时,table中对应数值为2,ans = 0 + 1 + 2,此时可以凑成三对
                // 第四次书显示,table中对应数值为3,ans = 0 + 1 + 2 + 3 = 6,此时可以凑成六对
                // 以此类推
                // 这是组合数C(n,2) 在 n 个元素中选2个,公式为0 + 1 + 2 + …… + n - 1 = n(n - 1) / 2
                ans += table[dominoes[i][1] * 10 + dominoes[i][0]] ;
                table[dominoes[i][1] * 10 + dominoes[i][0]] ++ ;
            } else {
                ans += table[dominoes[i][0] * 10 + dominoes[i][1]] ;
                table[dominoes[i][0] * 10 + dominoes[i][1]] ++ ;
            }
        }
        return ans ;
    }
};

394. 字符串解码

算法思路:

首先使用栈得到每个'['字符对应的']'的位置,用unordered_map进行存储

然后使用深度优先搜索对每个方括号内的内容进行递归,并根据给的数字返回字符串。

class Solution {
public:
    string ans ;
    // 无序map,用于存储每个[对应的]的位置
    unordered_map<int, int> find_right ;
    // dfs
    // l r 分别对应[ 和 ]
    // count 表示方括号的内容要重复多少遍
    string dfs(int count, int l, int r, string& s) {
        // 创建返回的字符串,为空
        string temp = "" ;
        // 从l + 1 至 r - 1,这是方括号内的内容,进行遍历
        for (int i = l + 1;i < r;i++) {
            // 如果当前字符不是[],且不为数字字符,则为普通字符,直接添加到字符串后面即可
            if (s[i] != '[' && s[i] != ']' && (s[i] < '0' || s[i] > '9')) {
                temp.append(1, s[i]) ;
            } else if (s[i] >= '0' && s[i] <= '9') {
                // 说明当前字符时数字,数字不知一位,所以往后继续找同为数字的一位
                int k = i + 1 ;
                for (;k < s.size();k++) {
                    if (s[k] < '0' || s[k] > '9') {
                        // 当前寻找到的非数字字符,往前退一位
                        k -- ;
                        break ;
                    }
                }
                // 使用substr函数将字符串中找到的数字截取,并使用atoi将该字符串转换成整数
                int count_next = atoi(s.substr(i, k - i + 1).c_str()) ;
                // dfs往下搜索
                temp.append(dfs(count_next, k + 1, find_right[k + 1], s)) ;
                // 搜索完毕,i跳跃到]字符的后一位
                i = find_right[k + 1] ;
            }
        }
        string tt = temp ;
        for (int i = 0;i < count - 1;i++) {
            temp.append(tt) ;
        }
        return temp ;
    }
    string decodeString(string s) {
        ans = "" ;
        stack<int> st ;
        // 根据栈获得每个[对应的]
        for (int i = 0;i < s.size();i++) {
            if (s[i] == '[') {
                st.push(i) ;
            }
            if (s[i] == ']') {
                find_right[st.top()] = i ;
                st.pop() ;
            }
        }
        // 以下和dfs函数中的遍历一样
        for (int i = 0;i < s.size();i++) {
            if (s[i] != '[' && s[i] != ']' && (s[i] < '0' || s[i] > '9')) {
                ans.append(1, s[i]) ;
            } else if (s[i] >= '0' && s[i] <= '9') {
                int k = i + 1 ;
                for (;k < s.size();k++) {
                    if (s[k] < '0' || s[k] > '9') {
                        k -- ;
                        break ;
                    }
                }
                int count_next = atoi(s.substr(i, k - i + 1).c_str()) ;
                ans.append(dfs(count_next, k + 1, find_right[k +c++ 1], s)) ;
                i = find_right[k + 1] ;
            }
        }
        return ans ;
    }
};

106. 从中序与后序遍历序列构造二叉树

算法思路:

后序遍历的顺序是:左节点 -> 右节点 -> 根节点 因此后序遍历的最后一个元素一定是当前二叉树的根节点,然后根据根节点找到该元素在中序遍历中的位置,中序遍历的顺序是:左节点 -> 根节点 -> 右节点 所以在根节点左边的一定是左子树的节点,右边的一定是右子树的节点,明确了左右子树元素的个数后,进行递归调用就可以构造二叉树了。

class Solution {
public:
    unordered_map<int, int> hashtable ;
    TreeNode* helper(vector<int>& inorder, vector<int>& postorder, int postorder_left, int postorder_right, int inorder_left, int inorder_right) {
        if (postorder_left > postorder_right) return nullptr ;
        // 后序遍历的最后一个元素一定是根节点
        int tree_root = postorder[postorder_right] ;

        int inorder_tree_root = hashtable[tree_root] ;

        TreeNode* root = new TreeNode(tree_root) ;

        // 计算右子树的节点数
        int right_num = inorder_right - inorder_tree_root ;
	
        root->left = helper(inorder, postorder, postorder_left , postorder_right - right_num - 1, inorder_left, inorder_tree_root - 1) ;
        root->right = helper(inorder, postorder, postorder_right - right_num, postorder_right - 1, inorder_tree_root + 1, inorder_right) ;

        return root ;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int n = inorder.size() ;
        for (int i = 0;i < n;i++) {
            hashtable[inorder[i]] = i ;
        }
        return helper(inorder, postorder, 0, n-1, 0, n-1) ;
    }
};

207. 课程表

算法思路

这是拓扑排序问题,就是判断这个图是不是有向无环图,求出这个图的一个拓扑排序后,判断拓扑排序的数目是否和节点数相等,若不相等说明图中有环

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {

        // 预处理获得每个节点的入度
        // [0, 1] 就是 1 -> 0
        vector<int> indegree(numCourses, 0) ;
        for (int i = 0;i < prerequisites.size();i++) {
            indegree[prerequisites[i][0]] ++ ;
        }

        queue<int> q ;
		// 将入度为0的节点添加到队列中
        for (int i = 0;i < indegree.size();i++) {
            if (indegree[i] == 0) {
                q.push(i) ;
            }
        
        // BFS
        vector<int> res ;
        while (! q.empty()) {
            int node = q.front() ;
            q.pop() ;
            res.push_back(node) ;
            for (int i = 0;i < prerequisites.size();i++) {
                if (prerequisites[i][1] == node) {
                    indegree[prerequisites[i][0]] -- ;
                    if (indegree[prerequisites[i][0]] == 0) {
                        q.push(prerequisites[i][0]) ;
                    }
                }
            }
        }
        return res.size() == numCourses ;

    }
};

129. 求根到叶子节点数字之和

算法思路

使用回溯法,每次遍历到一个节点,判断是否是叶子节点,如果是叶子节点,将该节点值添加到数组中,然后计算数组组合起来的数字,并将数字加到总和中,然后回溯,将该节点抛弃,并return。如果不是叶子节点,先将该节点值添加到数组中,判断是否有左右子树,有的话继续递归。左右子树递归求解完后,将该节点值从数组抛弃。

class Solution {
public:
    int ans ;
    void helper(vector<int>& sum, TreeNode* node) {
        if (node->left == nullptr && node->right == nullptr) {
            sum.push_back(node->val) ;
            int sum_t = 0;
            for (int i = 0;i < sum.size();i++) {
                sum_t = sum_t * 10 + sum[i] ;
            }
            ans += sum_t;
            sum.pop_back() ;
            return ;
        }
        sum.push_back(node->val) ;
        if (node->left != nullptr) helper(sum, node->left) ;
        if (node->right != nullptr) helper(sum, node->right) ;
        sum.pop_back() ;
    }
    int sumNumbers(TreeNode* root) {
        ans = 0 ;
        if (root == nullptr) {
            return ans ;
        }
        vector<int> sum ;
        helper(sum, root) ;
        return ans ;
    }
};
上一篇:一到九乘法口诀VB源码


下一篇:力扣LeetCode #105 从前序和中序遍历序列构造二叉树(BuildTree)