LeetCode 热题 HOT 100 第四天

• LeetCode 热题 HOT 100
• 前言
• 九十二、目标和
• 九十一、汉明距离
• 九十、找到所有数组中消失的数字
• 八十九、找到字符串中所有字母异位词
• 八十八、路径总和 III
• 总结

备战秋招，每天坚持，注意这不是题解，有的题我觉得简单的都没有注释，这相当于自己记录，督促自己的一个渠道。
题目顺序：前后交替

回顾：每一天回顾前一天没刷出来的题目，依次累加进行

提示：以下是本篇文章正文内容，下面案例可供参考

494. 目标和

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 ‘+’ 或 ‘-’ ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-’ ，然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

  一道01背包的转换问题，主要在于如何转换成01背包

class Solution {
public:
    int findTargetSumWays(vector& nums, int target) {
        int sum = 0;
        for (auto &a : nums) {
            sum += a;   
        }

        if ((target + sum) % 2 == 1) return 0;//注意
        if (abs(target) > sum) return 0;

        int bagSize = (target + sum) / 2;
        vector dp(bagSize + 1, 0);
        dp[0] = 1;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = bagSize; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[bagSize];

    }
};

461. 汉明距离

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。

给你两个整数 x 和 y，计算并返回它们之间的汉明距离。

位运算经典题目

思路：两个数在某一位的二进制数不同，表示两数异或的结果在这一位为1

class Solution {
public:
    int hammingDistance(int x, int y) {
        //先取得有多少位不同，异或
        int z = x ^ y;
        int cnt = 0;
        while (z) {
            cnt += z & 1;//与，都是1就为1
            z >>= 1;//右移
        }
        return cnt;
    }
};

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

给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

class Solution {
public:
    vector findDisappearedNumbers(vector& nums) {
        for (int i = 0; i < nums.size(); i++) {
            while (true) {
                int pos = nums[i] - 1;
                if (nums[i] == nums[pos]) break;
                swap(nums[i], nums[pos]);
            }
        }

        vector res;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != i + 1) {
                res.push_back(i + 1);
            }
        }
        return res;
    }
};

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

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

class Solution {
public:
    vector findAnagrams(string s, string p) {
        vector res;
        int m = s.size();
        int n = p.size();

        vector windows(26, 0);
        vector st(26, 0);
        for (int i = 0; i < n; i++) {
            st[p[i] - 'a']++;
        }

        int slow = 0;
        for (int fast = 0; fast < m; fast++) {
            windows[s[fast] - 'a']++;

            if (fast >= n) {
                windows[s[slow] - 'a']--;
                slow++;
            }
            if (windows == st) {
                res.push_back(slow);
            }
        }
        return res;
    }
};

路径总和 III

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

class Solution {
public:
    int pathSum(TreeNode* root, int targetSum) {
        int res = 0;
        mp[0] = 1;
        traversal(root, targetSum, 0, res);
        return res;
    }
    void traversal(TreeNode* root, int targetSum, long long curSum, int& res) {
        if (root == nullptr) return ;
        curSum += root -> val;
        if (mp.find(curSum - targetSum) != mp.end()) {
            res += mp[curSum - targetSum];
        }
        mp[curSum]++;
        traversal(root -> left, targetSum, curSum, res);
        traversal(root -> right, targetSum, curSum, res);
        mp[curSum]--;
    }
private:
    unordered_map mp;
};

总之，加油