文档章节

剑指Offer(Java版):和为s的两个数字VS和为s的连续正数序列

一贱书生
 一贱书生
发布于 2016/08/03 15:55
字数 1190
阅读 43
收藏 0

题目一:输入一个递增排序的数组和一个数字s,在数组中查找两个数,使得它们的和正好是s。如果有多个数字的和等于s,输出任意一对即可。

例如输入数组{1,2,4,7,11,15}和数字15.由于4+11=15,因此输出4和11.

在面试的时候,很重要的一点是应聘者要表现出很快的反应能力。只要想 到一个办法,应聘者就可以立马告诉面试官,即使这个办法不一定是最好的。比如这个问题,很多人会立即能想到O(n2)的方法,也就是先在数组中固定一个数 字,再依次判断数组中其余n-1个数字与它的和是不是等于s。面试官会告诉我们这不是最好的方法。不过这没有关系,至少面试官会知道我们的思维还是比较敏 捷的。

接着我们寻找更好的算法。我们先在数组中选择两个数字,如果他们的和 等于输入的s,我们就找到了要找的两个数字。如果小于s呢?我们希望两个数字的和再大一点。由于数组已经排好序了,我们可以考虑选择较小的数字后面的数 字。因为排在后面的数字要大一点,那么这两个数字的和也要大一点,就有可能等于输入的数字s了。同样,当两个数字的和大于输入的数字的时候,我们就可以选 择较大的数字前面的数字了,因为排在前面的数字要小一些。

基于上面的思路,我们实现代码如下:

 

package cglib;

public class jiekou {
    public static void main(String[] args) {
        jiekou p=new jiekou();
        int[] data={1,2,4,7,11,15};
        int sum=15;
        System.out.println(p.findNumberWithSum(data, sum));
        }
    public boolean findNumberWithSum(int[] data,int sum){
        boolean found=false;
        if(data==null)
            return found;
        
        int num1=0;
        int num2=0;
        int start=0;
        int end=data.length-1;
        while(start<end){
        int curSum=data[start]+data[end];
        if(curSum==sum){
        num1=data[start];
        num2=data[end];
        found=true;
        break;
        }
        else if(curSum>sum)
        end--;//当两个数字的和大于输入的数字的时候,我们就可以选择较大的数字前面的数字了,因为排在前面的数字要小一些。
        else
        start++;
        }
        System.out.println(num1);
        System.out.println(num2);
        return found;
        }
        }

 

输出:
4
11
true

这种算法的时间复杂度为O(n)

 

 

题目二:输入一个正数s,打印出所有的和为s的连续正数序列(至少含有两个数字)。例如输入15,由于1+2+3+4+5=4+5+6=7+8=15,所以结果打印出3个连续的序列1——5,4——6,7——8.

有了前面的经验,我们也考虑用两个树small和big分别表示序列 的最小值和最大值。首先把small初始化为1,big初始化为2.如果从small到big的序列的和大于s,我们可以从序列中去掉较小的值,也就是增 大small的值。如果从small到big的序列的和小于s,我们可以增大big,让这个序列包含更多的数字。因为这个序列至少要有两个数字,我们一直 增加small 到(1+s)/2为止。

Java代码实现上面的思路:

package cglib;

public class jiekou {
    public static void main(String[] args) {
        jiekou p=new jiekou();
        int sum=15;
        p.findContinuesSequence(sum);
        }
    public void findContinuesSequence(int s){
        if(s<3)
        return;
        int small=1;
        int big=2;
        while(small <(s+1)/2){  
            int curSum = 0;  
            for(int i = small ;i<=big;i++)  
            {
                System.out.println("i="+i);
                curSum +=i;
                System.out.println("curSum="+curSum);
                
            }
            
            System.out.println("此时curSum="+curSum);
            if(curSum == s){  
                System.out.println("find one");  
                printContineNum(small, big);  
                small++;  
            }  
            else{  
                if(curSum > s)  
                    small++;  
                else  
                    big++;  
            }  
        }  
        
    }
    private void printContineNum(int small, int big) {
    for(int i=small;i<=big;i++){
    System.out.print(i+" ");
    }
    System.out.println();
    }
        
        }
   

输出:

i=1
curSum=1
i=2
curSum=3
此时curSum=3
i=1
curSum=1
i=2
curSum=3
i=3
curSum=6
此时curSum=6
i=1
curSum=1
i=2
curSum=3
i=3
curSum=6
i=4
curSum=10
此时curSum=10
i=1
curSum=1
i=2
curSum=3
i=3
curSum=6
i=4
curSum=10
i=5
curSum=15
此时curSum=15
find one
1 2 3 4 5
i=2
curSum=2
i=3
curSum=5
i=4
curSum=9
i=5
curSum=14
此时curSum=14
i=2
curSum=2
i=3
curSum=5
i=4
curSum=9
i=5
curSum=14
i=6
curSum=20
此时curSum=20
i=3
curSum=3
i=4
curSum=7
i=5
curSum=12
i=6
curSum=18
此时curSum=18
i=4
curSum=4
i=5
curSum=9
i=6
curSum=15
此时curSum=15
find one
4 5 6
i=5
curSum=5
i=6
curSum=11
此时curSum=11
i=5
curSum=5
i=6
curSum=11
i=7
curSum=18
此时curSum=18
i=6
curSum=6
i=7
curSum=13
此时curSum=13
i=6
curSum=6
i=7
curSum=13
i=8
curSum=21
此时curSum=21
i=7
curSum=7
i=8
curSum=15
此时curSum=15
find one
7 8

 

© 著作权归作者所有

一贱书生
粉丝 19
博文 724
码字总数 600123
作品 0
私信 提问
【剑指offer纪念版】-- 面试题目录

2.实现Singleton模式 3.二维数组中的查找 4.替换空格 5.从尾到头打印链表 6.重建二叉树 7.用两个栈实现队列 8.旋转数组的最小数字 9.斐波那契数列 【剑指offer纪念版】--9 斐波那契数列 10.二...

细节探索者
01/19
0
0
[算法总结] 3 道题搞定 BAT 面试——堆栈和队列

本文首发于我的个人博客:尾尾部落 0. 基础概念 栈:后进先出(LIFO) 队列:先进先出(FIFO) 1. 栈的 java 实现 2. 队列的 java 实现 3. 用两个栈实现队列 剑指offer:用两个栈实现队列 Le...

繁著
2018/09/04
0
0
剑指offer 41. 和为S的连续正数序列

原题 小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,...

dby_freedom
2018/11/20
0
0
[剑指offer] 和为S的连续正数序列

本文首发于我的个人博客:尾尾部落 题目描述 小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序...

繁著
2018/08/07
0
0
给广大码农分享福利:一个业界良心的github仓库,中文计算机资料

我今天查资料时无意发现的,https://github.com/CyC2018/CS-Notes 这个仓库包含了下列几个维度的计算机学习资料: 深受国内程序员喜爱,已经有超过3万多star了。 1. 算法 (1) 剑指 Offer 题解...

JerryWangSAP
2018/10/12
0
0

没有更多内容

加载失败,请刷新页面

加载更多

研究下这代码,用到了guava和线程池

import com.google.common.util.concurrent.FutureCallback;import com.google.common.util.concurrent.Futures;import com.google.common.util.concurrent.ListenableFuture;import c......

暗中观察
20分钟前
2
0
《css 揭秘》 之垂直居中的实现

最近看了 Lea Verou 的 《css揭秘》一书,让我对自己的 css学习产生了深深的怀疑。这本书真是太棒了,里面涉及到很多优雅又有趣的效果实现,真的是非常棒。如果你有时间,十分建议你去看看。...

IrisHuang
25分钟前
1
0
java 抽象类(2)

/*需求: 描述一个图形、圆形、 矩形三个类。不管哪种图形都会具备计算面积与周长的行为,但是每种图形计算的方式不一致而已。常量的命名规范:全部字母大写,单词与单词 之间 使用下...

hellation_
28分钟前
2
0
总结:堆和栈

堆 堆比较好理解,即存放对象的地方。这里的对象由GC管理 1、类变量(static修饰的变量):在程序加载时系统就为它在堆中开辟了内存,堆中的内存地址存放于栈以便于高速访问。静态变量的生命...

浮躁的码农
34分钟前
1
0
JavaScript 新语法详解:Class 的私有属性与私有方法

译者按: 为什么偏要用**#**符号? 原文:JavaScript's new #private class fields 译者:Fundebug 本文采用意译,版权归原作者所有 proposal-class-fields与proposal-private-methods定义了 ...

Fundebug
36分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部