• 等级
  • 61656 访问
  • 197 原创
  • 21 转发
  • 23423 排名
  • 12 评论
  • 95 获赞

有效的完全平方数

publicbooleanisPerfectSquare(intnum){inti=1,j=num;while(i<=j){intmid=(i+j)/2;if(mid==(num*1.0/mid))//防止乘法溢出...

2019-03-08 11:39:20

寻找比目标字母大的最小字母

publiccharnextGreatestLetter(char[]letters,chartarget) { //先判断最后一个字母是否比目标字母大 if(letters[letters.length-1]<=target) returnletters[0]; intlow=0,high=letters.length-1...

2019-03-08 11:29:45

区间列表的交集

解题思路:先要考虑两个集合存在交集的情况。通过分析,可以知道当a.s>=b.s时,交集为[a.s,min(a.e,b.e)],同理当b.s>=a.s时,交集为[b.s,min(a.e,b.e)]。 publicInterval[]intervalIntersection(Interval[]A,Interval[]B) { Arra...

2019-03-07 12:15:09

两数之和II

publicint[]twoSum(int[]numbers,inttarget) { inti=0,j=numbers.length-1; int[]ret=newint[2]; while(i<j) { while(target>0&&numbers[j]>target) ...

2019-03-06 12:09:07

删除排序数组中的重复项

publicintremoveDuplicates(int[]nums) { intj=1;//慢指针 for(inti=1;i<nums.length;i++) { if(nums[i]!=nums[i-1]) { nums[j++]=nums[i]; } } returnj; }...

2019-03-06 11:38:18

有序数组的平方

publicint[]sortedSquares(int[]A) { inti=0,j=A.length-1; intk=A.length-1; int[]tmp=newint[A.length]; while(i<=j) { if(A[i]*A[i]<=A[j]*A[j]) { ...

2019-03-06 11:12:03

移除元素

双指针:两个指针分别指向首尾,遍历头指针,遇到等于val时,遍历尾指针,找到不等于val的值,进行交换,两指针相撞时,结束。 publicintremoveElement(int[]nums,intval) { inti=0,j=nums.length-1; //将等于val的数移动到数组右边 while(i<=j) { ...

2019-03-05 13:14:16

寻找重复数

解题思路:二分法。在区间[1,n]中搜索,首先求出中点mid,然后遍历整个数组,统计所有小于等于mid的数的个数,如果个数小于等于mid,则说明重复值在[mid+1,n]之间,反之,重复值应在[1,mid-1]之间,然后依次类推,直到搜索完成,此时的right就是我们要求的重复值。publicintfindDuplicate(int[]nums)...

2019-03-04 21:05:20

两个数组的交集

二分法:先排序,对两个数组做归并运算,使用set来去重。 publicint[]intersection(int[]nums1,int[]nums2) { inti=0,j=0,k=0; //排序 Arrays.sort(nums1); Arrays.sort(nums2); HashSet<Integer>...

2019-03-04 20:41:38

反转字符串中的元音字母

publicStringreverseVowels(Strings) { inti=0; intj=s.length()-1; charc; char[]ss=s.toCharArray(); while(i<j) { while(i<j&&containsVowels(ss[i])...

2019-03-04 20:16:52

盛最多水的容器

解题思路:两个指针,一前一后,分别指向第一个元素和最后一个元素,计算此时容纳水的容量,根据两边的高度调整移动方向,指针向高的那边移动(贪心性质)两个指针相撞时就结束。 publicintmaxArea(int[]height) { inti=0; intj=height.length-1; intmaxWater=0; whil...

2019-03-04 16:38:40

最低票价

int[][]memo=null;//备忘录 intr(intidx,int[]days,int[]costs,intdeadLine) { inta,b,c,min; if(idx==days.length) return0; //有效期超过最后一天 if(deadLine>=days[days...

2019-03-01 18:48:53

完全平方数

解题思路:该题目与CoinChange很相似,先找出到n为止的所有的完全平方数,然后暴力法进行搜索。当然,可以继续优化为动态规划。 int[][]memo=null;//备忘录 publicintsovle(intn,int[]squares,intidx) { if(n==0)//找到一种组合 return0; ...

2019-03-01 15:28:37

翻转矩阵后的得分

解题思路:先判断每一行的第一个元素,是否是0,如果是,就翻转该行;判断第2列到最后一列中,每列0的个数是否大于1的个数,如果是,就翻转该列;之后按照二进制数的解释进行计算。 publicintmatrixScore(int[][]A) { if(A==null||A.length==0) return0; introws=A....

2019-03-01 14:53:39

加油站

解题思路:先计算从每一个站点的油量与前往下一个站点的油量之间的差,判断是否可以从改点通往其他站点。再对每一个有可能的站点,计算环路的耗油量,如果跑完全程耗油量不小于0,则能行驶一周。 publicintcanCompleteCircuit(int[]gas,int[]cost) { int[]costGas=newint[gas.length]; ...

2019-02-28 15:16:31

小Q的歌单

  解题思路:分别考虑使用全使用A,全使用B,以及A,B混合使用的情况。 staticlong[][]memo=null;//备忘录 publicstaticvoidmain(String[]args) { intk,a,x,b,y; Scannerscan=newScanner(System.in); while(scan.h...

2019-02-27 16:29:39

编辑距离

int[][]memo=null;//备忘录 intsolve(Stringword1,Stringword2,intc1,intc2) { inta,b,c; intn1=word1.length(); intn2=word2.length(); if(c1==n1&&c2==n2...

2019-02-26 17:37:56

租用游艇问题

   长江俱乐部在长江设置了n个游艇出租站1,2,…n,游客可在这些游艇出租站租用游艇,并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i,j),设计一个算法,计算出从出租站1到出租站n所需要的最少租金。解题思路:f(i,n)=min(f(i,j)+f(j,k)+..+f(k,n))。publicclassRentYa...

2019-02-26 15:43:03

无重叠区间

解题思路:该题目类似于活动安排问题,先按照结束时间的长短进行排序,结束时间短的排在前面,在根据后一个活动的开始时间要比前一个活动的结束时间要晚的原则,从前向后筛选即可。  publicinteraseOverlapIntervals(Interval[]intervals) { intn=intervals.length; intncount=0; ...

2019-02-25 16:54:41

判断子序列

双指针法 publicbooleanisSubsequence(Strings,Stringt) { //s为空串 if(s.isEmpty()) returntrue; inti=0,j=0; while(i<s.length()&&j<t.length()) {...

2019-02-25 15:34:12

-Billy

关注
  • 中国