Leetcode刷题笔记--Hot91--100

1--汉明距离（461）

主要思路：

      按位异或，统计1的个数；  

#include <iostream>
#include <vector>class Solution {
public:int hammingDistance(int x, int y) {int z = x ^ y; // 按位异或int res = 0;while(z){if((z % 2) == 1) res++;z = z >> 1; // 右移}return res;}
};int main(int argc, char* argv[]){// x = 1, y = 4int x = 1, y = 4;Solution S1;int res = S1.hammingDistance(x, y);std::cout << res << std::endl;return 0;
}

2--目标和

主要思路：

        

主要思路：
        转化为 0-1 背包问题，一部分数值连同 target 转化为背包容量，剩余一部分数值转化为物品，求解恰好装满背包容量的方法数；

        dp[j] 表示背包容量为 j 时，装满背包的方法数；

        状态转移方程：dp[j] += dp[j - nums[i]]，其实质是：当背包已经装了nums[i]时，剩余容量为 j - nums[i]，此时装满剩余容量的方法数为 dp[j - nums[i]]，遍历不同的 nums[i] 将方法数相加即可；

        是有点难理解。。。

#include <iostream>
#include <vector>class Solution {
public:int findTargetSumWays(std::vector<int>& nums, int target) {int sum = 0;for(int num : nums) sum += num;if(sum < std::abs(target)) return 0; // 数组全部元素相加相减都不能构成targetif((sum + target) % 2 == 1) return 0; // 不能二等分int bagsize = (sum + target) / 2;std::vector<int> 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];}
};int main(int argc, char *argv[]) {// nums = [1, 1, 1, 1, 1], target = 3std::vector<int> test = {1, 1, 1, 1, 1};int target = 3;Solution S1;int res = S1.findTargetSumWays(test, target);std::cout << res << std::endl;return 0;
}