Skip to main content

moregeek program

每日算法刷题day16-和为s的两个数字、数字排列、二进制中1的个数_wx62e40d60030b6的博客-多极客编程

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

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

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

49.和为S的两个数字

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

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

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

数据范围

数组长度 [1,1002]。

样例

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

输出:[3,4]
思路

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

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

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

图解

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

代码

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

qfiledialog文件对话框_五个板栗的博客-多极客编程

QFileDialog能遍历整个文件系统来选择一个或者多个文件或者目录函数原型(F1或者Fn+F1查看帮助文档,有更详细的解释)QString QFileDialog::getOpenFileName(QWidget *parent = nullptr, const QString &caption = QString()

有序查找及顺序查找_wx619474981d7fe的博客-多极客编程

1 有序查找 查找就是根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素。 查找表按照操作方式分成两大种: 静态查找表(Static Search Table):只作查找操作的查找表 查询某个“特定的”数据元素是否在查找表中。 检索某个“特定的”数据元素和各种属性。 动态查找(Dynamic Search Table):在查找过程中同时插入查找表中不存在的数据元素,或者从查找

[ 数据结构进阶 - c++ ] 二叉搜索树 bstree_小白又菜的博客-多极客编程

 到如今,C++的基本语法已经了解过了。在之前,​​数据结构初阶​​​是使用C语言实现的,我们进入进阶数据结构之后,将使用C++语言来实现。本篇文章我们将学习了解二叉搜索树-​​二叉树​​的进阶。1.二叉搜索树1.1二叉搜索树的概念二叉搜索数又称二叉排序树(BST,Binary Search Tree),它或者是一颗空树,或者是有以下性质的二叉树:若它的左子树不为空,则左子树上的所有节点的值都小于

双向带头循环链表的(增删查改)的实现_萌新的日常的博客-多极客编程

(文章目录) 一、双向带头循环链表 构成 二、双向带头循环链表的实现 1.函数的定义和结构体的创建——list.h #include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int datatype; struct listNode { datatype val; struct l

单链表的(增删查改)的实现_萌新的日常的博客-多极客编程

(文章目录) 一、链表 1.链表的概念 一种物理存储结构上非连续,非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针连接次序实现的。 2.链表优点 1.空间上按需所给空间 2.在头部和中间插入时,不需要挪动数据 二、单链表的实现 1.函数的定义和结构体的创建——list.h #include<stdio.h> #include<stdlib.h> #includ

二叉排序树_wx619474981d7fe的博客-多极客编程

1 二叉排序树的定义果查找的数据集是有序线性表,并且是顺序存储的,查找可以用折半查找算法来实现,因为有序,在插入和删除操作上,就需要耗费大量的时间。假设现在我们的数据只有一个数{62,88,58,47,35,73,51,99,37,93}做查找,建立好的二叉排序树如图所示,62、88、58创建好后,下一个数47因比58小,是它的左子树,35是47的左子树,73比62大,但比88小,是88的左子树,

用了那么久的vue,你了解vue的报错机制吗?_wx6237f50e82bc0的博客-多极客编程

Vue的5种处理Vue异常的方法相信大家对Vue的不陌生。在使用Vue的时候也会遇到报错,也会使用浏览器的F12 来查看报错信息。但是你知道Vue是如何进行异常抛出的吗?vue 是如何处理异常的呢?接下来和大家介绍介绍,Vue是如何处理者几种常见的报错的。先很大家说说常见的报错,再和大家介绍如何处理 Vue 中异常处理包含以下几个方面的技巧:errorHandlerwarnHandlerrende

腾讯云告警回调参数region与使用api相关region参数映射_oaixnah_的博客-多极客编程

注:不排除之后腾讯云后端同学将缩写修改为全称的可能alarm_region = { 'gz': 'ap-guangzhou', 'gzopen': 'ap-guangzhou-open', 'szjr': 'ap-shenzhen-fsi', 'sh': 'ap-shanghai', 'shjr': 'ap-shanghai-fsi', 'bj': 'ap-be

java基于hadoop及微服务架构的前后端分离购物系统(源码)_wx6237f50e82bc0的博客-多极客编程

一、项目介绍基于Hadoop及微服务架构的前后端分离购物系统。前台购物页面 使用 Vue + ElementUi , 后台管理页面使用 html 和 Ajax。后端使用 Spring Boot + Spring Cloud+Nacos+OpenFeign+Spring Cloud GateWay+MyBatis进行开发,使用 Shiro 做登录验证和权限校验,使用支付宝的沙箱环境进行支付,使用 E

判断两个cidr是否有ip冲突_5201314的博客-多极客编程

1.校验网段是否合法1.1函数import ( "fmt" "net")func IsNetWorkOk(network string ) bool{ _, _, err := net.ParseCIDR(network) if err != nil { return false } return true}1.2分析第一步就是先split变成ip

#yyds干货盘点# leetcode 热题 hot 100:合并k个升序链表_灰太狼_cxh的博客-多极客编程

题目:给你一个链表数组,每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中,返回合并后的链表。 示例 1:输入:lists = [[1,4,5],[1,3,4],[2,6]]输出:[1,1,2,3,4,4,5,6]解释:链表数组如下:[  1->4->5,  1->3->4,  2->6]将它们合并到一个有序链表中得到。1->1->2->3

#yyds干货盘点# 面试必刷top101:岛屿数量_风的博客-多极客编程

1.简述:描述给一个01矩阵,1代表是陆地,0代表海洋, 如果两个1相邻,那么这两个1属于同一个岛。我们只考虑上下左右为相邻。岛屿: 相邻陆地可以组成一个岛屿(相邻:上下左右) 判断岛屿个数。例如:输入[[1,1,0,0,0],[0,1,0,1,1],[0,0,0,1,1],[0,0,0,0,0],[0,0,1,1,1]]对应的输出为3(注:存储的01数据其实是字符'0','1')示例1输入:[[