[数据结构与算法]LeetCode 热题 HOT 100 第十八天

Leetcode438. 找到字符串中所有字母异位词

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        unordered_map<char, int> cnt;
        for (auto& c : p) cnt[c] ++ ;
        int tot = cnt.size();
        vector<int> res;
        for (int i = 0, j = 0, f = 0; i < s.size(); i ++ ) {
            if (-- cnt[s[i]] == 0) f ++ ;
            if (i - j + 1 > p.size()) {
                if (cnt[s[j]] == 0) f -- ;
                cnt[s[j ++ ]] ++ ;
            }
            if (f == tot) res.push_back(j);
        }
        return res;
    }
};

Leetcode448. 找到所有数组中消失的数字

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        for (auto x : nums) {
            x = abs(x);
            if (nums[x - 1] > 0) nums[x - 1] *= -1;
        }
        vector<int> res;
        for (int i = 0; i < nums.size(); i ++ )
            if (nums[i] > 0)
                res.push_back(i + 1);
        return res;
    }
};

Leetcode461. 汉明距离

class Solution {
public:
    int hammingDistance(int x, int y) {
        int res = 0;
        while (x || y) {
            res += (x & 1) ^ (y & 1);
            x >>= 1, y >>= 1;
        }
        return res;
    }
};

Leetcode494. 目标和

思路一：递归（时间复杂度：指数级别）

$dfs$表示枚举到第$u$个数，且前$u?1$个数和为$cur$的方案数，递归终止条件是$u==nums.size()$

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        return dfs(nums, target, 0, 0);
    }

    int dfs(vector<int>& nums, int target, int u, int cur) {
        if (u == nums.size()) return cur == target;
        int l = dfs(nums, target, u + 1, cur + nums[u]);
        int r = dfs(nums, target, u + 1, cur - nums[u]);
        return l + r;
    }
};

思路二：动态规划

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int n = nums.size(), s = 0;
        for(auto& t : nums) s += t;
        if (target > s || target < -s) return 0;
        vector<vector<int>> f(n + 1, vector<int>(2 * s + 1));
        f[0][s] = 1;
        for (int i = 1; i <= n; i ++ )
            for (int j = -s; j <= s; j ++ ) {
                if (j - nums[i - 1] >= -s) f[i][j + s] += f[i - 1][j - nums[i - 1] + s];
                if (j + nums[i - 1] <= s) f[i][j + s] += f[i -1][j + nums[i - 1] + s];
            } 
        
        return f[n][target + s];
    }
};

Leetcode538. 把二叉搜索树转换为累加树

思路：BST中序遍历有序

先遍历右子树求后缀和，

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int sum = 0;
    TreeNode* convertBST(TreeNode* root) {
        dfs(root);
        return root;
    }

    void dfs(TreeNode* root) {
        if (!root) return ;
        dfs(root->right);
        int x = root->val;
        root->val += sum;
        sum += x;
        dfs(root->left);
    }
};