【转】http://zhedahht.blog.163.com/blog/static/25411174200732711051101/
题目:输入一个正数n,输出所有和为n连续正数序列。
例如输入15,由于1+2+3+4+5=4+5+6=7+8=15,所以输出3个连续序列1-5、4-6和7-8。
分析:这是网易的一道面试题。
这道题和本面试题系列的第10题有些类似。我们用两个数small和big分别表示序列的最小值和最大值。首先把small初始化为1,big初始化为2。如果从small到big的序列的和大于n的话,我们向右移动small,相当于从序列中去掉较小的数字。如果从small到big的序列的和小于n的话,我们向右移动big,相当于向序列中添加big的下一个数字。一直到small等于(1+n)/2,因为序列至少要有两个数字。
基于这个思路,我们可以写出如下代码:
void PrintContinuousSequence(int small, int big);
/////////////////////////////////////////////////////////////////////////
// Find continuous sequence, whose sum is n
/////////////////////////////////////////////////////////////////////////
void FindContinuousSequence(int n)
{
if(n < 3)
return;
int small = 1;
int big = 2;
int middle = (1 + n) / 2;
int sum = small + big;
while(small < middle)
{
// we are lucky and find the sequence
if(sum == n)
PrintContinuousSequence(small, big);
// if the current sum is greater than n,
// move small forward
while(sum > n)
{
sum -= small;
small ++;
// we are lucky and find the sequence
if(sum == n)
PrintContinuousSequence(small, big);
}
// move big forward
big ++;
sum += big;
}
}
/////////////////////////////////////////////////////////////////////////
// Print continuous sequence between small and big
/////////////////////////////////////////////////////////////////////////
void PrintContinuousSequence(int small, int big)
{
for(int i = small; i <= big; ++ i)
printf("%d ", i);
printf("\n");
}
分享到:
相关推荐
1.5.10. 输入一个正数 n,输出所有和为 n 连续正数序列 ................................125 1.6. 面试题集合(五) .......................................................................................126...
使用list,最简短的代码,输入一个正数n,输出所有和为n的连续正数序列,结果添加到list中
57.和为S的连续正数序列 Array 关注 58.翻转单词序列 String 58.左旋转字符串 String 59.滑动窗口的最大值 Queue 常考 60.n个骰子的点数 61.扑克牌顺子 62.孩子们的游戏 Math 63.股票的最大利润 Math 64.求1...
如果是小学教师并为数学教学做准备,他们应该对自然数系统N的性质有扎实的知识,并了解其位置作为构建所有其他数字系统的基础。 在某种程度上,这些老师还应该熟悉在学校中沿线进行的数字系统的进一步扩展:自然数...
和为S的连续正数序列 so.42.和为S的两个数字 so.50.数组中重复的数字 so.51.构建乘积数组 so.64.滑动窗口的最大值 lc.15.三数之和 lc.41.缺失的第一个正数 lc.54.螺旋矩阵 lc.88.合并两个有序数组 1.2 链表 题目 ...
数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。 求所有子数组的和的最大值。要求时间复杂度为O(n)。 例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2, ...
学校 1.中位数 ...让我们以通过粘贴连续的正数形成的无限数字序列为例:S = 123456789101112131415 ...确定给定序列A在无限序列S中的首次出现(编号从1开始)。 输入示例:6789 111 样本输出:6 12
8、 已知A[n]为正数数组,试写出实现下列运算的递归算法; a. 求数组A中的最大整数; b. 求n个数的平均值; c. 求n个整数的平均值; 9、 已知f为单链表的表头指针,链表中存储的都是整型数据,试写...
和为s的连续正数序列 10、 58-I. 翻转单词顺序 11、58-II. 左旋转字符串 12、66. 构建乘积数组 二、栈和队列 1、06. 从尾到头打印链表 2、09.用两个栈实现队列 3、30.包含min函数的栈 4、59-I. 滑动窗口 5、59-II. ...
1.4 最长连续序列 1.5 累加和 1.6 移除数组中指定值 1.7 下一个排列 1.8 第n个全排列 1.9 验证数独的正确性 1.10 容纳雨水的量 1.11 旋转图像 1.12 数字加1 1.13 爬楼梯 1.14 格雷码 1.15 设置矩阵的行列为0 1.16 ...
16.设m.n均为自然数,m可表示为一些不超过n的自然数之和,f(m,n)为这种表示方式的数目。例f(5,3)=5, 有 5种表示方式:3+2,3+1+1,2+2+1,2+1+1+1,1+1+1+1+1。 ①以下是该函数的程序段,请将未完成的部分填入,...
设a和n都已定义为整型变量。 5 第4章 最简单的C程序设计——顺序程序设计 6 4.4 若a=3,b=4,c=5,x=1.2,y=2.4,z=-3.6,u=51247,n=128765,c1=’a’,c2=’b’,想得到以下的输出格式和结果,请写出程序(包括...
一个典 型的操作集包括与内部数据类型相关的基本算术指令(即实数和整数加法、减法、乘法和 除法等)、测试数据项性质(如是否为零,是正数或负数等)的指令 、对数据项的某一部 分进行存取和修改 (如在一个字中存取一...
为此,LINGO为用户提供了两个可选部分:输入集成员和数据的数据部分(Data Section)和为决策变量设置初始值的初始部分(Init Section)。 3.1 模型的数据部分 3.1.1 数据部分入门 数据部分提供了模型相对静止部分...
要求时间复杂度为O(n)。 3.最长回文 4.顺序统计量 5.Strassen矩阵乘法 dynamic:动态规划 1.最长公共序列 2.最长公共子串 3.矩阵链乘法 4.最优二叉查找树 greedy:贪心算法 leetcode: LeetCode上的题目 ...
(2) 序列“001”的输入如果直接输入“001”,系统会自动判断001为数据1,解决办法是:首先输入“'”(西文单引号),然后输入“001”。(3) 日期的输入如果要输入“4月5日”,直接输入“4/5”,再敲回车就行了。...
当按二、八、十六进制输出时,是按其补码形式输出,最高位是符号位(正数为0、负数为1)。 所以此法可得到一个负数的补码表示。 (1)按二进制输出 %b或%B %b等价与%B。 %b 12 = 0b1100 %b 0xffffffff = 0b1111 ...