每日算法刷题Day16-和为S的两个数字、数字排列、二进制中1的个数

⭐每日算法题解系列文章旨在精选重点与易错的算法题，总结常见的算法思路与可能出现的错误，与笔者另一系列文章有所区别，并不是以知识点的形式提升算法能力，而是以实战习题的形式理解算法，使用算法。

🔥本文已收录于算法刷题系列专栏： 每日算法题解 欢迎订阅，持续更新。

49.和为S的两个数字

输入一个数组和一个数字 s，在数组中查找两个数，使得它们的和正好是 s。

如果有多对数字的和等于 s，输出任意一对即可。

你可以认为每组输入中都至少含有一组满足条件的输出。

数据范围

数组长度 [1,1002]。

样例

输入：[1,2,3,4] , sum=7

输出：[3,4]

思路

此题目可以采用哈希表的方式来实现。

首先遍历数组，判断当前数字之前是否有对应的数字相加得到target

如果没有，则将该数字插入哈希表中，如果有，则返回该数字和其对应的哈希表中的数字。

图解

代码

class Solution {
public:
    vector<int> findNumbersWithSum(vector<int>& nums, int target) {
        unordered_set<int> S;
        for(auto x : nums)
        {
            if(S.count(target - x)) return { x , target - x};
            S.insert(x);
        }
    }
};

50.数字排列

输入一组数字（可能包含重复数字），输出其所有的排列方式。

数据范围

输入数组长度 [0,6]。

样例

输入：[1,2,3]

输出：
      [
        [1,2,3],
        [1,3,2],
        [2,1,3],
        [2,3,1],
        [3,1,2],
        [3,2,1]
      ]

思路

这道题除了暴力搜索，还可以使用STL，采用next_permutation函数。

• STL提供了两个用来计算排列组合关系的算法，分别是next_permutation和prev_permutation。

• next_permutation()会取得[first,last)所标示之序列的下一个排列组合，如果没有下一个排列组合，便返回false;否则返回true。常见的排序范式是字典序或者数字序。

• next_permutation函数demo

#include <algorithm>
bool next_permutation(iterator start,iterator end)

此题可以先sort将数组从小到大排序，然后定义结构vector<vector<int>> res，将结果不断地排下一组和直到返回false为止。

代码

class Solution {
public:
    vector<vector<int>> permutation(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        
        vector<vector<int>> res;
        do res.push_back(nums);
        while(next_permutation(nums.begin(),nums.end()));
        
        return res;
    }
};

51.二进制中1的个数

输入一个 32 位整数，输出该数二进制表示中 1 的个数。

注意：

• 负数在计算机中用其绝对值的补码来表示。

数据范围

−100≤ 输入整数 ≤100

样例1

输入：9
输出：2
解释：9的二进制表示是1001，一共有2个1。

样例2

输入：-2
输出：31
解释：-2在计算机里会被表示成11111111111111111111111111111110，
      一共有31个1。

思路

解法一：可以采用常规方法遍历n中的1（通过移位，& 1 来计数），并且计数。

class Solution {
public:
    int NumberOf1(int n) {
        int res = 0;
        for(int i = 0; i < 32 ;i++)
            if(n >> i & 1) res++;//通过移位，& 1 来计数
        return res;
    }
};

解法二：仿照lowbit的做法

每次求出最后一个1以及后面的0组成的数字，并且减去，不断重复这个过程直到n为0，以此统计1的个数。

class Solution {
public:
    int NumberOf1(int n) {
        int res = 0;
        
        while(n)n -= (n & -n) , res++;
        
        return res;
    }
};