剑指offer 面试57题
2024-09-14 14:50:58
面试57题:
题目:和为s的数字
题目描述
输入一个递增排序的数组和一个数字S,在数组中查找两个数,是的他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。
输出描述:
对应每个测试案例,输出两个数,小的先输出。
解题思路:使用while循环从两端向中间扫描数组,时间复杂度为O(n)
解题代码:
# -*- coding:utf-8 -*-
class Solution:
def FindNumbersWithSum(self, array, tsum):
# write code here
if len(array)<2:
return []
found=False
fst,lst=0,len(array)-1
while fst<lst:
sum_total=array[fst]+array[lst]
if sum_total==tsum:
found=True
return [array[fst],array[lst]]
elif sum_total<tsum:
fst +=1
else:
lst -=1
return []
拓展题目:
题:输出所有和为S的连续正数序列。序列内按照从小至大的顺序,序列间按照开始数字从小到大的顺序
解题思路同上。
代码如下:
# -*- coding:utf-8 -*-
class Solution:
def FindContinuousSequence(self, tsum):
# write code
if tsum<3:
return []
small,big=1,2
middle=(tsum+1)//2
curSum=small+big
res=[] while (small<middle):
if curSum==tsum:
res.append(list(range(small,big+1)))
while(curSum>tsum and small<middle):
curSum -= small
small +=1
if curSum==tsum:
res.append(list(range(small,big+1)))
big+=1
curSum +=big
return res
最新文章
- C语言 插入排序 算法导论chapter2
- bzoj 2287: 【POJ Challenge】消失之物
- Windows phone应用开发[18]-下拉刷新
- node06-path
- Qt Sqlite qwt 发布过程中碰到的问题runtime error
- [转]Python 中的 lambda,filter,map,reduce,apply
- 实现QQ在线咨询(需先添加好友)
- Testng使用方法示例
- Great StackOverflow questions
- Java中获取路径的各种方法
- DLL函数中内存分配及释放的问题
- Ubuntu配置java环境变量
- iOS 三种录制视频方式
- cf #214div2
- gem5 设定checkpiont以及从checkpoint开始运行
- jaxb和dozer简介
- Zookeeper的安装和配置
- 【Splay】例题
- 史上最全CentOS安装教程,图文结合
- MemCache详细解读(转)
热门文章
- Atitit.论垃圾文件的识别与清理&#160;文档类型垃圾文件&#160;与api概要设计pa6.doc
- [ci]安装配置jenkins及其插件
- 怎样正确写网站title、keywords、description比较标准。
- linux下调试使用的 一些shell命令
- WebLogic配置自己定义密钥库和SSL的操作手冊
- hdu 4786 Fibonacci Tree(最小生成树)
- Java并发编程(九)安全发布
- stm32开发板无法正常写入的问题或者写入后无法正常运行的问题
- 小米Note全网通支持7模19频:先发标准版
- Ubuntu17.10 Install Docker-ce