每日算法刷题Day16-和为S的两个数字、数字排列、二进制中1的个数
每日算法刷题Day16-和为S的两个数字、数字排列、二进制中1的个数
timerring
发布于 2022-11-02 17:15:26
发布于 2022-11-02 17:15:26
文章目录
49.和为S的两个数字
输入一个数组和一个数字 s，在数组中查找两个数，使得它们的和正好是 s。
如果有多对数字的和等于 s，输出任意一对即可。
你可以认为每组输入中都至少含有一组满足条件的输出。
数据范围
数组长度 [1,1002]。
样例
输入：[1,2,3,4] , sum=7
输出：[3,4]思路
此题目可以采用哈希表的方式来实现。
首先遍历数组，判断当前数字之前是否有对应的数字相加得到target
如果没有，则将该数字插入哈希表中，如果有，则返回该数字和其对应的哈希表中的数字。
图解
image-20220828011826708
代码
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;
}
};本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2022-10-23，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录