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

2022 年 9 月 23 日
山东
本文字数：1424 字
阅读完需：约 5 分钟

⭐每日算法题解系列文章旨在精选重点与易错的算法题，总结常见的算法思路与可能出现的错误，与笔者另一系列文章有所区别，并不是以知识点的形式提升算法能力，而是以实战习题的形式理解算法，使用算法。
🔥本文已收录于算法刷题系列专栏：每日算法题解欢迎订阅，持续更新。

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;    }};

复制代码

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/b31716ee3be5fa9a0afd89ee2】。未经作者许可，禁止转载。

timerring

关注

还未添加个人签名 2022.07.14 加入

还未添加个人简介

发布

暂无评论

创作场景

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

49.和为 S 的两个数字

数据范围

样例

思路

图解

50.数字排列

数据范围

样例

思路

51.二进制中 1 的个数

数据范围

样例 1

样例 2

思路

timerring

评论