2021.1.28 算法练习

LeetCode

724. 寻找数组的中心索引

使用前缀和数组，假设前缀和数组为sum

对于nums[i]而言，左侧元素的相加等于sum[i - 1]，右侧元素的相加等于sum[n - 1] - sum [i] （n为数组长度）

同时需要对i == 0 和 i == n - 1的位置进行特殊处理

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int n = nums.size() ;
        if (n == 0) {
            return -1 ;
        }
        // 前缀和数组
        vector<int> sum(n, 0) ;
        int t = 0 ;
        for (int i = 0;i < n;i++) {
            t += nums[i] ;
            sum[i] = t ;
        }

        for (int i = 0;i < n;i++) {
            if (i == 0) {
                if (sum[n - 1] - nums[0] == 0) return i ;
                else continue ; 
            }
            if (i == n - 1) {
                if (sum[n - 2] == 0) return i ;
                else continue ;
            }
            if (sum[i - 1] == sum[n - 1] - sum[i]) {
                return i ;
            }
        }
        return -1 ;
    }
};

剑指 Offer 34. 二叉树中和为某一值的路径

使用回溯法，递归遍历二叉树的每一个路径，当遍历到叶子节点时，计算当前路径节点的和，如果等于目标值，就把该路径添加到结果数组中，并结束递归

class Solution {
public:
    vector<vector<int>> ans ;
    void dfs(TreeNode* root, int sum, vector<int>& num) {
        if (root->left == NULL && root->right == NULL) {
            num.push_back(root->val) ;
            if (accumulate(num.begin(),num.end(), 0) == sum) {
                ans.push_back(num) ;
            }
            num.pop_back() ;
            return ;
        }
        num.push_back(root->val) ;
        if (root->left != NULL) dfs(root->left, sum, num) ;
        if (root->right != NULL) dfs(root->right, sum, num) ;
        num.pop_back() ;
    }
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        if (root == NULL) {
            return ans ;
        }
        vector<int> num ;
        dfs(root, sum, num) ;
        return ans ;
    }
};

剑指 Offer 68 - II. 二叉树的最近公共祖先

首先遍历整个二叉树，使用一个map存放每个节点的父节点，这里取名为record

然后根据之前存放父节点的record，将第一个节点往上遍历，第一个节点的各个祖先都存放到另一个map里，这里取名为first_node

接下来只要将第二个节点往上遍历，每遍历一个节点，检查该节点是否是first_node里的键

class Solution {
public:
    TreeNode* node ;
    // record用于记录每一个节点的父节点
    unordered_map<TreeNode*, TreeNode*> record ;
    // first_node 用于记录第一个结点往上追溯的父节点（包括他自己）
    // 判断时只需要判断当前是否存在这个键
    unordered_map<TreeNode*, bool> first_node ;
    // 递归找寻每一个节点的父节点
    void find_parent(TreeNode* node) {
        if (node->left != NULL) {
            record[node->left] = node ;
            find_parent(node->left) ;
        }
        if (node->right != NULL) {
            record[node->right] = node ;
            find_parent(node->right) ;
        }
    }
    // 递归寻找第一个节点的父节点（包括他自己）
    void find_first_node_parent(TreeNode* p) {
        if (p == NULL) {
            return  ;
        }
        first_node[p] = true ;
        find_first_node_parent(record[p]) ;
    }
    void solve(TreeNode* q) {
        if (q == NULL) {
            record ;
        }
        if (first_node.find(q) != first_node.end()) {
            node = q ;
            return ;
        }
        solve(record[q]) ;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        node == NULL ;
        // 根节点没有父节点，存放为NULL
        record[root] = NULL ;
        find_parent(root) ;
        find_first_node_parent(p) ;
        solve(q) ;
        return node ;

    }
};

剑指 Offer 66. 构建乘积数组

本题需要维护两个数组

数组一保存每个节点左侧元素的乘积

数组二保存每个节点右侧元素的乘积

class Solution {
public:
    vector<int> constructArr(vector<int>& a) {
        int n = a.size() ;
        vector<int> ans ;
        if (n == 0) {
            return ans ;
        }
        vector<int> dp_left(n, 1) ;
        vector<int> dp_right(n, 1) ;
        for (int i = 1;i < n;i++) {
            dp_left[i] = dp_left[i - 1] * a[i - 1] ;
        }
        for (int i = n - 2;i >= 0;i--) {
            dp_right[i] = dp_right[i + 1] * a[i + 1] ; 
        }
        for (int i = 0;i < n;i++) {
            ans.push_back(dp_right[i] * dp_left[i]) ;
        }
        return ans ;
    }
};

1736. 替换隐藏数字得到的最晚时间

这题是对字符串的简单处理

分钟部分：如果遇到“?”部分，要么是 5 ，要么是 9

小时部分：如果遇到“?”部分，需要另外一位的情况，对于十位来说，如果个位小于等于3，十位只能是1，如果个位大于3，十位只能是2，如果个位是"?"，那么十位只能是2，此时个位必定为3；对于个位来说，如果十位是"?"，那么个位一定是3，十位必定为2，如果十位是1，个位必须为9，如果个位是2，十位必须是3。

class Solution {
public:
    string maximumTime(string time) {
        if (time[0] == ‘?‘) {
            if (time[1] >= ‘4‘ && time[1] != ‘?‘) {
                time[0] = ‘1‘ ;
            } else {
                time[0] = ‘2‘ ;
            }
        }
        if (time[1] == ‘?‘) {
            if (time[0] >= ‘2‘) {
                time[1] = ‘3‘ ;
            } else {
                time[1] = ‘9‘ ;
            }
        }
        if (time[3] == ‘?‘) time[3] = ‘5‘ ;
        if (time[4] == ‘?‘) time[4] = ‘9‘ ;
        return time ;

    }

};

2021.1.28 算法练习

原文：https://www.cnblogs.com/Suans/p/14344248.html