- 博客(14)
- 收藏
- 关注
RSS订阅原创 整数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
115
原创 数组中出现次数超过一半的数
题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为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
124
原创 字符串的排列
题目：输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串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
109
原创 把数组排成最小的数
题目：输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。思路：可以看出，若要实现组合后的树=数最小，需要事先对给定的数组进行排序，排序算法需要指定比较器，并要转换成stringclass Solution {public: static bool cmp(int a,int b){ string A=""; string B="";
2020-08-03 19:53:27
86
原创 数字在排序数组中出现的次数
题目：统计一个数字在排序数组中出现的次数。思路：1.暴力法：对数组进行遍历，若找到对应的数字记录位置，因为是排序数字，当继续查找不是目标数字时，记录位置，减去第一个位置，就可以得到该数字出现的次数。2.二分法：运用二分法进行查找，查找数字的上限和下限，找到后相减即可。class Solution {public: int GetNumberOfK(vector<int> data ,int k) { return upper_bound(data.begin()
2020-07-29 11:08:29
92
原创 和为S的连续正整数序列
题目：小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列?思路：利用滑动窗口技术，计算窗口[lo,hi]内的和，若与目标值相等，则lo++；若比目标值小，则扩大窗口，即hi++；若比目标值大，则缩小窗口，即lo++；因为初始窗口大小为2，并
2020-07-28 16:26:28
163
原创 动态规划-石子游戏
题目：亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行，每堆都有正整数颗石子 piles[i] 。游戏以谁手中的石子最多来决出胜负。石子的总数是奇数，所以没有平局。亚历克斯和李轮流进行，亚历克斯先开始。 每回合，玩家从行的开始或结束处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止，此时手中石子最多的玩家获胜。假设亚历克斯和李都发挥出最佳水平，当亚历克斯赢得比赛时返回 true ，当李赢得比赛时返回 false 。示例：输入：[5,3,4,5]输出：true解释：亚历克斯先开始，只
2020-07-24 18:27:20
236
原创 输出字符串中最长连续数字串及个数
题目：输出字符串中最长的数字字符串和它的长度。如果有相同长度的串，则要一块儿输出，但是长度还是一串的长度思路：先输入字符串，再进行遍历，当遇到数字时，开始计数，当遇到字母时，终止计数，看当前数字长度是否大于最大长度，若是，将输出字符串清空，并该段数字用strsub(位置，个数)拷贝到输出字符串，若与最大长度相同，则maxr不变，将该段字符添加到原来输出字符的后面。最后遍历完成后，要看最后计数是不是大于maxr，若最后一个是数字，并没有执行上面的操作。#include<iostream>#i
2020-07-23 14:03:30
1424
原创 字符串指定位置插入
题目：将一个字符中所有出现的数字前后加上符号“*”，其他字符保持不变思路：这里没有选择直接插入，选择使用另一个容器来添加需要的字符。当遇到待插入’'时，就在另一个容器中多添加一个字符“”#include<iostream>#include<vector>#include<string>using namespace std;int main(){ string s; while(cin>>s){ string
2020-07-22 21:38:35
201
1
原创 字符统计输出
题目：对字符中的各个英文字符（大小写分开统计），数字，空格进行统计，并按照统计个数由多到少输出,如果统计的个数相同，则按照ASII码由小到大排序输出 。如果有其他字符，则对这些字符不用进行统计。思路：使用hash方法来记录字符出现次数（map），map自动默认按字典排序。使用数组vector<pair<char,int>>来拷贝map中的数据。按照出现次数对数组中元素进行排序，要使用稳定排序stable_sort()，因为拷贝过来的数据是默认字典排序的，相同出现次数不能打乱
2020-07-22 18:07:05
148
原创 ‘&&’运算符短路求值原理
'&&'运算符有一个短路求值原理，比如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
800
原创 查找第一个只出现一次的字符(哈希，队列，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
513
原创 不用+-*/实现两个数的相加。
在计算机中，计算都是二进制下的运算，主要设计三种操作符，分别为按位与&，按位或|，按位异或^，两个数相加，若不涉及进位运算，则是两个数进行异或，两个数相加的进位其实是两个数想与&之后的二进制再左移<<一位,然后将这两步所得结果再进行相加，直到进位为0为止。实现如下：class Solution {public: int Add(int num1, int num2) { while(num2!=0){ int res=n
2020-07-20 16:22:30
161
原创 map容器的查找
map容器中，有两种常用的查找方式，都是寻关键码访问，分别为find(key)和下标[key]，其中find函数若没有查找到这个关键码，则返回尾迭代器map.end();若查找到则返回该关键码的迭代器。[]下标是直接按照关键码取查找，类似数组的访问方式，若失败则会创建一个该关键码的节点，并将初始val设置成默认值。...
2020-07-20 15:12:59
1110
1
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人