1 321菜鸟起飞

尚未进行身份认证

我要认证

一只小菜鸟

等级
TA的排名 46w+

整数1出现的次数

题目:求出1-13的整数中1出现的次数,并算出100-1300的整数中1出现的次数?为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数(从1 到 n 中1出现的次数)。思路2:分别求固定位出现1 的次数,比如对于数4321,固定十位为1的数字有:10,11,12,13,,,4319,相当于将4321进行分割为a=4321/10=432,b=4321%10=

2020-08-04 22:47:29

数组中出现次数超过一半的数

题目:数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。思路1:利用hash的方法,遍历数组的过程中记录数字出现的次数,如果大于一半,则返回这个数即可,很简单,但是空间复杂度O(n),时间复杂度O(n),空间有点浪费,思路2:既然出现次数超过一半,那么其他数字的次数小于一半,故可遍历的过程中记录锁定数出现的次数,若后一个数与当前数相同,则计数加一

2020-08-04 18:27:20

字符串的排列

题目:输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。思路:利用递归的思想分析可知:设fun(abc)为字符串abc的所有排列情况,则fun(abc)=a fun(bc)+ b fun(ac)+ c fun(ca),可以看作第一个字符依次与后面的字符进行交换位置,然后将第一个字符固定,求后面剩余字符的全排列,交换位置可以使用一个for循环来实现。递推下去可知,fun(bc)

2020-08-04 18:12:48

把数组排成最小的数

题目:输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。思路:可以看出,若要实现组合后的树=数最小,需要事先对给定的数组进行排序,排序算法需要指定比较器,并要转换成stringclass Solution {public: static bool cmp(int a,int b){ string A=""; string B="";

2020-08-03 19:53:27

数字在排序数组中出现的次数

题目:统计一个数字在排序数组中出现的次数。思路:1.暴力法:对数组进行遍历,若找到对应的数字记录位置,因为是排序数字,当继续查找不是目标数字时,记录位置,减去第一个位置,就可以得到该数字出现的次数。2.二分法:运用二分法进行查找,查找数字的上限和下限,找到后相减即可。class Solution {public: int GetNumberOfK(vector<int> data ,int k) { return upper_bound(data.begin()

2020-07-29 11:08:29

和为S的连续正整数序列

题目:小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列?思路:利用滑动窗口技术,计算窗口[lo,hi]内的和,若与目标值相等,则lo++;若比目标值小,则扩大窗口,即hi++;若比目标值大,则缩小窗口,即lo++;因为初始窗口大小为2,并

2020-07-28 16:26:28

动态规划-石子游戏

题目:亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行,每堆都有正整数颗石子 piles[i] 。游戏以谁手中的石子最多来决出胜负。石子的总数是奇数,所以没有平局。亚历克斯和李轮流进行,亚历克斯先开始。 每回合,玩家从行的开始或结束处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止,此时手中石子最多的玩家获胜。假设亚历克斯和李都发挥出最佳水平,当亚历克斯赢得比赛时返回 true ,当李赢得比赛时返回 false 。示例:输入:[5,3,4,5]输出:true解释:亚历克斯先开始,只

2020-07-24 18:27:20

输出字符串中最长连续数字串及个数

题目:输出字符串中最长的数字字符串和它的长度。如果有相同长度的串,则要一块儿输出,但是长度还是一串的长度思路:先输入字符串,再进行遍历,当遇到数字时,开始计数,当遇到字母时,终止计数,看当前数字长度是否大于最大长度,若是,将输出字符串清空,并该段数字用strsub(位置,个数)拷贝到输出字符串,若与最大长度相同,则maxr不变,将该段字符添加到原来输出字符的后面。最后遍历完成后,要看最后计数是不是大于maxr,若最后一个是数字,并没有执行上面的操作。#include<iostream>#i

2020-07-23 14:03:30

字符串指定位置插入

题目:将一个字符中所有出现的数字前后加上符号“*”,其他字符保持不变思路:这里没有选择直接插入,选择使用另一个容器来添加需要的字符。当遇到待插入’'时,就在另一个容器中多添加一个字符“”#include<iostream>#include<vector>#include<string>using namespace std;int main(){ string s; while(cin>>s){ string

2020-07-22 21:38:35

字符统计输出

题目:对字符中的各个英文字符(大小写分开统计),数字,空格进行统计,并按照统计个数由多到少输出,如果统计的个数相同,则按照ASII码由小到大排序输出 。如果有其他字符,则对这些字符不用进行统计。思路:使用hash方法来记录字符出现次数(map),map自动默认按字典排序。使用数组vector<pair<char,int>>来拷贝map中的数据。按照出现次数对数组中元素进行排序,要使用稳定排序stable_sort(),因为拷贝过来的数据是默认字典排序的,相同出现次数不能打乱

2020-07-22 18:07:05

‘&&’运算符短路求值原理

'&&'运算符有一个短路求值原理,比如a&&b,如果出现在条件判断语句中,我们理解的就是a和b都要是true才能完成判断,实际运行过程中,计算机先判断a是否为真,若a为真再判断b是否为真,但若a为假,则后面不会再看b的真假,也就是说如果b为一个表达式,则不会执行这个表达式,这就是短路求值原理,举例如下代码:/*实现求1+2+3+...+n,要求不能使用乘除法,以及for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。*/clas

2020-07-21 09:45:32

查找第一个只出现一次的字符(哈希,队列,find()rfind())

思路:首先看到只出现一次,就想到要用哈希来记录每个字符出现的次数,可以用map或者vector容器等;对于“第一个”这个字眼,首先惯性思维就是使用队列来实现,先进先出,1.如果处理的对象是一个字符串流,则可通过使用队列来保存出现字符的先后顺序,然后依次弹出队列,并查看map中对于应的出现次数,若为1,则即为结果,程序如下:class Solution{public: //Insert one char from stringstream void Insert(char ch)

2020-07-20 17:21:16

不用+-*/实现两个数的相加。

在计算机中,计算都是二进制下的运算,主要设计三种操作符,分别为按位与&,按位或|,按位异或^,两个数相加,若不涉及进位运算,则是两个数进行异或,两个数相加的进位其实是两个数想与&之后的二进制再左移<<一位,然后将这两步所得结果再进行相加,直到进位为0为止。实现如下:class Solution {public: int Add(int num1, int num2) { while(num2!=0){ int res=n

2020-07-20 16:22:30

map容器的查找

map容器中,有两种常用的查找方式,都是寻关键码访问,分别为find(key)和下标[key],其中find函数若没有查找到这个关键码,则返回尾迭代器map.end();若查找到则返回该关键码的迭代器。[]下标是直接按照关键码取查找,类似数组的访问方式,若失败则会创建一个该关键码的节点,并将初始val设置成默认值。...

2020-07-20 15:12:59
勋章 我的勋章
  • 阅读者勋章Lv3
    阅读者勋章Lv3
    授予在CSDN APP累计阅读博文达到30天的你,是你的坚持与努力,使你超越了昨天的自己。
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv3
    勤写标兵Lv3
    授予每个自然周发布7篇到8篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。