5 freedom098

尚未进行身份认证

暂无相关描述

等级
博文 264
排名 1w+

Longest Valid Parentheses

Givenastringcontainingjustthecharacters‘(’and‘)’,findthelengthofthelongestvalid(well-formed)parenthesessubstring.For“(()”,thelongestvalidparenthesessubstringis“()”,w...

2018-04-09 17:17:45

数字和为sum的方法数

给定一个有n个正整数的数组A和一个整数sum,求选择数组A中部分数字和为sum的方案数。当两种选取方案有一个数字的下标不一样,我们就认为是不同的组成方案。输入描述:输入为两行:第一行为两个正整数n(1≤n≤1000),sum(1≤sum≤1000)第二行为n个正整数Ai,以空格隔开。输出描述:输出所求的方案数...

2018-04-09 11:08:06

数字游戏

小易邀请你玩一个数字游戏,小易给你一系列的整数。你们俩使用这些整数玩游戏。每次小易会任意说一个数字出来,然后你需要从这一系列数字中选取一部分出来让它们的和等于小易所说的数字。例如:如果{2,1,2,7}是你有的一系列数,小易说的数字是11.你可以得到方案2+2+7=11.如果顽皮的小易想坑你,他说的数字是6,那么你没有办法拼凑出和为6现在小易给你n个数,让你找出无法从n个数中选取部...

2018-04-08 09:46:18

跳石板

小易来到了一条石板路前,每块石板上从1挨着编号为:1、2、3…….这条石板路要根据特殊的规则才能前进:对于小易当前所在的编号为K的石板,小易单次只能往前跳K的一个约数(不含1和K)步,即跳到K+X(X为K的一个非1和本身的约数)的位置。小易当前处在编号为N的石板,他想跳到编号恰好为M的石板去,小易想知道最少需要跳跃几次可以到达。例如:N=4,M=24:...

2018-04-04 11:04:38

数列还原

题目描述牛牛的作业薄上有一个长度为n的排列A,这个排列包含了从1到n的n个数,但是因为一些原因,其中有一些位置(不超过10个)看不清了,但是牛牛记得这个数列顺序对的数量是k,顺序对是指满足i<j且A[i]<A[j]的对数,请帮助牛牛计算出,符合这个要求的合法排列的数目。输入描述:每个输入包含一个测试用例。每个测试用例的第一行包含...

2018-04-02 09:50:15

合唱团

有n个学生站成一排,每个学生有一个能力值,牛牛想从这n个学生中按照顺序选取k名学生,要求相邻两个学生的位置编号的差不超过d,使得这k个学生的能力值的乘积最大,你能返回最大的乘积吗?输入描述:每个输入包含1个测试用例。每个测试数据的第一行包含一个整数n(1<=n<=50),表示学生的个数,接下来的一行,包含n个整数,按顺序表示每...

2018-03-31 11:37:36

Find Bottom Left Tree Value

leetcode第513题,给定一个二叉树,找出最后一层最左边的元素。首先,牵扯到二叉树的层结构,第一反应就是广搜。基本思路就是,每次从左到右遍历节点形成一层,到最后的时候如果为空的层,代表循环结束。这里存在一个问题,当遍历到空层的时候,实际我们已经丢失了最后一层的信息,所以这里需要我们提前判断一下是不是到了最后一层。#Definitionforabinarytreen...

2018-03-27 10:32:49

Evaluate Reverse Polish Notation

leetcode第150题,求解逆波兰表达式。这个题套路很清楚,用栈进行模拟就可以了,但是这里面有几个需要注意的地方。因为是要依次把token入栈,所以遍历token数组是大循环的条件。最后结果返回也是在token数组用完之后。除法和减法要注意操作数有先后关系。没有操作符的时候,直接返回最后一个操作数python中的除法有点奇怪,需要做一定的修改classSolution...

2018-03-27 09:19:26

Sum of Two Integers

leetcode第371题,不用加减法实现加法。不用运算符的题目多半就要靠位运算去解决。考虑两个二进制数相加,第一步是用异或,得到相加的原始结果,此时并没有考虑进位。按照二进制加法原则,进位就是两个1碰到一起,所以可以用与运算来模拟,注意这里还需要左移一位,让进位加到后面的一位上才可以。classSolution{public:intgetSum(inta,int...

2018-03-27 08:55:23

move zero

leetcode第283题,把所有的0移动数组后半部,其余元素的相对顺序不改变,要求原地操作。其余元素相对顺序不能变,就意味着双指针法只能一前一后的使用,而不能一头一尾的使用。与数组去重题类似,i为游标指针,start为指向0数组第一个元素的指针,i放过所有为0的元素,遇到不为0的元素时,和start位置的进行交换,交换后start后移继续指向0数组第一个元素,这是与数组去重不同的地方。sta...

2018-03-26 19:59:26

Coin Change

leetcode第332题,硬币找零,使用最少数量的指定硬币凑出目标数。深度搜索,逐个加入硬币,当数额与目标数相等时,记录一下所用的硬币数,找出其中最小的就好了,但是这样做目标数很大的时候就会超时。classSolution(object):defcoinChange(self,coins,amount):""":typecoins:...

2018-03-23 11:25:02

Sort Colors

leetcode第75题,打乱的0,1,2排序可以先用计数排序,由于只有0,1,2这三个数字,因此完全可以先统计各有多少个,然后在数组中重写一遍即可。classSolution:defsortColors(self,nums):""":typenums:List[int]:rtype:voidDonotr...

2018-03-13 09:59:40

Redundant Connection

leetcode684题,一个图是由一棵树多一条边,要求删去那条边,然后形成一棵树。此题可用并查集来做,思路是,遍历所有的边,并用并查集来做归属划分,如果一个边的两个node分属于不同的集合,说明这条边不是多余的,是起到了联通作用的,相反,如果node已经被前面的边连入到一个集合中了,那么说明这条边是多余的了。classSolution:deffindRedundant...

2018-03-13 09:20:50

word search

leetcode第79题,图上的深搜题。第一步,先要写个遍历循环,找到搜索的起点,也就是首字母。第二步,从起点出发开始搜索,搜索时主要要记录已经走过的地方,这里可以使用一个二维的数组单独来记录,或者走过的地方标识为‘#’,搜索后恢复这个位置的字符。注意,每次搜索时,都要比较word和当前路径已经遍历到的字符,这里可以使用增量式的比较方法,每次比较一个字符即可。classSo...

2018-03-09 10:18:37

Odd Even Linked List

leetcode第328题,要求把一个单链表的奇数偶数位置分开,把奇数位置的节点串联起来后放在偶数位置节点的串联之前。一开始的想法是,走两遍循环,一个把奇数位置串起来,另外一个把偶数位置串起来,然后奇数位置后面加挂上偶数串的头部即可。但这样做的问题是,第一遍把奇数位置串起来之后,改变了原始链表,所以后面那个循环就不正确了。正确的做法是,在一个循环里搞定这个事情。首先,拿到奇数头部和偶数头部...

2018-02-28 10:09:36

两个链表的第一个公共结点

输入两个链表,找出它们的第一个公共结点。剑指offer有两种思路,思路一是用栈把节点存起来,然后依次弹出,直到最后一个相同的为止,这种方法比较简单,时间和空间复杂度都是O(m+n)。思路二是先求两个链表的长度,求出长度差,先让长的链表走长度差那几步,这样就可以拉齐两个链表的进度了,这样两个链表一直走下去就会同时会和。ListNode*FindFirstCommonNode(L

2018-01-29 09:31:01

逆序对

在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P简单思路是,挨个遍历数组中的元素,每遍历到一个元素之后和后面的元素再逐一比较,这样的复杂度是O(n^2)。这里时间都花费在了逐一比较上,这样一个个找逆序对显然是比较耗时的。归并排序的思路就是一次性的找出一串来,所以复杂度会低很多,本质就是归并排序的复杂度O(nlog

2018-01-29 09:08:00

字符串反转问题

牛客最近来了一个新员工Fish,每天早晨总是会拿着一本英文杂志,写些句子在本子上。同事Cat对Fish写的内容颇感兴趣,有一天他向Fish借来翻看,但却读不懂它的意思。例如,“student.aamI”。后来才意识到,这家伙原来把句子单词的顺序翻转了,正确的句子应该是“Iamastudent.”。Cat对一一的翻转这些单词顺序可不在行,你能帮助他么?主要思路是,先整个反转字符串数

2018-01-28 19:36:05

和为S的连续正数序列

小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列?GoodLuck!双指针法,一个指向小数,一个指向大数,如果大小数

2018-01-28 10:49:33

数组中只出现一次的数字

一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。思路详见剑指offer,这里值得注意的地方时位运算的操作。如果检查一个int数的第n位是不是1,可以先把这个数右移n位,这样第n位就落到了最右端,这时候与1操作,如果不是1,那么与操作结果就是0.intisBit(intx,intindex){return(x>>ind

2018-01-23 15:42:58
奖章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!