5 烽火前秦路

尚未进行身份认证

厚积薄发,知识改变命运!

等级
博文 268
排名 1w+

剑指Offer----扩展:空格问题(京东)

问题描述:给定字符串(ASCII码0-255)数组,请在不开辟额外空间的情况下删除开始和结尾处的空格,并将中间的多个连续的空格合并成一个。例如:"iamalittleboy.",变成"iamalittleboy",语言不限,但不要用伪代码作答,函数输入输出请参考如下的函数原型:C++函数原型:voidFormatString(charstr[],i

2016-08-29 16:00:26

剑指Offer----扩展:选择题(京东)

问题描述:设一课完全二叉树共有999个结点,则在该二叉树中的叶节点个数是?分析:在二叉树的第i层上至多有2^(n-1)个结点(n>=1);深度为k的二叉树至多有2^k-1个结点(k>=1).因为2^9-1方法二:其实完全二叉树有这个性质,最后一个节点/2就得到他的父节点了,而此时的父节点必然是最后一个父节点,也就是说他之后的

2016-08-29 12:02:11

剑指Offer----扩展:上台阶(京东)

问题描述:有一楼梯共m级,刚开始时你在第一级,若每次只能跨上一级或者二级,要走上m级,共有多少走法?注:规定从一级到一级有0种走法。给定一个正整数intn,请返回一个数,代表上楼的方式数。保证n小于等于100。为了防止溢出,请返回结果Mod1000000007的值。测试样例:3返回:2分析:这不就是典型的动态规划问题吗,同时也是斐波那契数

2016-08-29 11:20:26

剑指Offer----扩展:小东分苹果(京东)

问题描述:果园里有一堆苹果,一共n头(n大于1小于9)熊来分,第一头为小东,它把苹果均分n份后,多出了一个,它扔掉了这一个,拿走了自己的一份苹果,接着第二头熊重复这一过程,即先均分n份,扔掉一个然后拿走一份,以此类推直到最后一头熊都是这样(最后一头熊扔掉后可以拿走0个,也算是n份均分)。问最初这堆苹果最少有多少个。给定一个整数n,表示熊的个数,返回最初的苹果数。保证有解。

2016-08-29 11:15:03

剑指Offer----扩展:抛小球(京东)

问题描述:小东和三个朋友一起在楼上抛小球,他们站在楼房的不同层,假设小东站的楼层距离地面N米,球从他手里自由落下,每次落地后反跳回上次下落高度的一半,并以此类推知道全部落到地面不跳,求4个小球一共经过了多少米?(数字都为整数)给定四个整数A,B,C,D,请返回所求结果。测试样例:100,90,80,70返回:1020分析:其实这道

2016-08-29 11:08:44

剑指Offer----扩展:年终奖(京东)

问题描述:小东所在公司要发年终奖,而小东恰好获得了最高福利,他要在公司年会上参与一个抽奖游戏,游戏在一个6*6的棋盘上进行,上面放着36个价值不等的礼物,每个小的棋盘上面放置着一个礼物,他需要从左上角开始游戏,每次只能向下或者向右移动一步,到达右下角停止,一路上的格子里的礼物小东都能拿到,请设计一个算法使小东拿到价值最高的礼物。给定一个6*6的矩阵board,其中每个元素为对应

2016-08-29 11:00:58

剑指Offer----扩展:风口的猪-中国牛市(小米)

问题描述:风口之下,猪都能飞。当今中国股市牛市,真可谓“错过等七年”。给你一个回顾历史的机会,已知一支股票连续n天的价格走势,以长度为n的整数数组表示,数组中第i个元素(prices[i])代表该股票第i天的股价。假设你一开始没有股票,但有至多两次买入1股而后卖出1股的机会,并且买入前一定要先保证手上没有股票。若两次交易机会都放弃,收益为0。设计算法,计算你能获得的最大收益。输

2016-08-28 21:51:01

剑指Offer----扩展:二进制(小米)

问题描述:世界上有10种人,一种懂二进制,一种不懂。那么你知道两个int32整数m和n的二进制表达,有多少个位(bit)不同么?输入例子:19992299输出例子:7分析:将两个整数逐位进行比较,累加不同位的个数,直至两个数都为0.源代码:#define_CRT_SECURE_NO_WARNINGS#include#include

2016-08-28 21:48:45

剑指Offer----扩展:构造回文(腾讯)

问题描述:给定一个字符串s,你可以从中删除一些字符,使得剩下的串是一个回文串。如何删除才能使得回文串最长呢?输出需要删除的字符个数。方法一:将输入的字符串翻转,利用动态规划求两个字符串的最大公共子序列!源代码#include#include#include#include//memory函数usingnamespacestd;

2016-08-28 19:32:54

动态规划----最长公共子序列LCS

1、基本概念  一个给定序列的子序列就是该给定序列中去掉零个或者多个元素的序列。形式化来讲就是:给定一个序列X={x1,x2,……,xm},另外一个序列Z={z1、z2、……,zk},如果存在X的一个严格递增小标序列,使得对所有j=1,2,……k,有xij=zj,则Z是X的子序列。例如:Z={B,C,D,B}是X={A,B,C,B,D,A,B}的一个子序列,相应的小标为。从定义可以看出

2016-08-28 18:08:01

剑指Offer----扩展:有趣的数字(腾讯)

问题描述:小Q今天在上厕所时想到了这个问题:有n个数,两两组成二元组,差最小的有多少对呢?差最大呢?输入描述:输入包含多组测试数据。对于每组测试数据:N-本组测试数据有n个数a1,a2...an-需要计算的数据保证:1输出描述:对于每组数据,输出两个数,第一个数表示差最小的对数,第二个数表示差最大的对数。输入例子:64512

2016-08-28 16:25:07

剑指Offer----扩展:字符移位(腾讯)

问题描述:小Q最近遇到了一个难题:把一个字符串的大写字母放到字符串的后面,各个字符的相对位置不变,且不能申请额外的空间。你能帮帮小Q吗?输入描述:输入数据有多组,每组包含一个字符串s,且保证:1输出描述:对于每组数据,出移位输后的字符串。输入例子:AkleBiCeilD输出例子:kleieilABCD方法一:使用STL库中的stable_pa

2016-08-28 13:41:29

剑指Offer----扩展:删除整型数组中所有的重复元素(中兴)

问题描述:删除整型数组中所有的元素!方法一:使用hash_map方法保存非重复的数字:#include#include#includeusingnamespacestd;vectordictinctArray(vector&arr){ hash_mapmmap; sort(arr.begin(),arr.end()); for

2016-08-25 23:41:39

剑指Offer----扩展:交换星号

问题描述:一个字符串只包含*和数字,请把它的*号都放在开头,且数字顺序不能交换!方法一:三次循环数组,第一次将数组中的*号赋给临时数组,第二次将数组中的数字赋给临时数组,第三次将临时数组中的元素赋给原数组!源代码:#include#include#includevoidFunction(char*arr,intlen){ if

2016-08-25 18:20:28

剑指Offer----扩展:删a复制b

问题描述:删除一个字符串中所有的a,并且赋值所有的b,字符串足够大!关键是倒着复制字符串数组!/* 删除一个字符串所有的a,并且复制所有的b。注:数组足够大!*/#include#includevoidFunction(char*str){ if(str==NULL) return; intn=0,numb=0;

2016-08-25 16:57:52

剑指Offer----扩展:0-1交换

问题描述:把一个0-1串(只包含0和1的串)进行排序,你可以交换任意两个位置,使所有的0在前边,所有的1在后边,问最少交换的次数?方法分析:两个指针,分别指向头和尾,当头指向1,尾指向0的时候,进行交换,直至两个指针相遇!#include#include#includeintSwapTime(char*arr,intlength){ if(arr

2016-08-25 16:54:19

动态申请二维数组并释放

1C语言版//申请一个m*n的二维数组,并释放数组#define_CRT_SECURE_NO_WARNINGS#include#includeintmain(){ intm,n; scanf("%d%d",&m,&n); int**arr=NULL; arr=(int**)malloc(m*(sizeof(int*)));//动态申请二维

2016-08-25 11:03:32

动态规划----颜料涂墙问题

问题描述:有一面长度为n(n0代表红色,1代表绿色,2代表蓝色初始值F(1,0)=F(1,1)=F(1,2)=1;状态转移方程:for(n>1)F(n,0)=F(n-1,0)+F(n-1,1)+F(n-1,2)F(n,1)=F(n-1,1)+F(n-1,2)F(n,0)=F(n-1,

2016-08-25 10:42:07

动态规划----硬币问题

问题描述:硬币问题:给你一些面额的硬币,然后给你一个值N,要你求出构成N所需要的最少硬币的数量和方案。分析:这个问题可以尝试用贪心算法去解决,先从面额最大的硬币开始尝试,一直往下找,知道硬币总和为N。但是贪心算法不能保证能够找出解(例如,给,2,3,5,然后N=11)。我们可以换个思路,我们用d(i)表示求总和为i的最少硬币数量(其实就是动态规划中的“状态”),那么怎么从前面的状态(并

2016-08-24 20:12:59

动态规划----Maximun Subarray

问题描述:Findthecontiguoussubarraywithinanarray(containingatleastonenumber)whichhasthelargestsum.Forexample,giventhearray[-2,1,-3,4,-1,2,1,-5,4],thecontiguoussubarray[4,-1,2,

2016-08-24 19:29:14
奖章
  • 专栏达人
    专栏达人
    授予成功创建个人博客专栏的用户。专栏中添加五篇以上博文即可点亮!撰写博客专栏浓缩技术精华,专栏达人就是你!