滴滴笔试

1.把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

思路1：最简单的思路，从1到大数，每个数都检测一遍是否是丑数。一个数一个数的判断，如果能被2整除，就一直除以2，如果能被3整除，就一直除以3，如果能被5整除，就一直除以5。如果最后的商为1，则说明为丑数。

static boolean isUgly(long m){while(m%2==0){m/=2;}while(m%3==0){m/=3;}while(m%5==0){m/=5;}return m==1?true:false;}

思路2：思路1的时间复杂度很高，因为每一个数都要判断（不是丑数的也要进行运算）。现在考虑以空间换时间，注意到：一个丑数的2、3、5倍也一定是丑数，而1是丑数，所以可以根据1来推出所有的丑数。

先用1乘以2、3、5，所得的数中的最小值作为第二个丑数，再用1、2分别乘以2、3、5，所得的数中的最小值作为第三个丑数。以此内推。package com.bili.hello;import java.util.*;

public class Main{public static void main(String[] args){System.out.println(GetUglyNumber(14));}public static int GetUglyNumber(int index){ //边界判断if (index <= 0){return 0;}//定义一个数组用于存放丑数int[] uglyNumbers = new int[index];uglyNumbers[0] = 1;int nextUglyIndex = 1;int multiply2 = 0;int multiply3 = 0;int multiply5 = 0;int min = 0;while (nextUglyIndex < index){min = Min(uglyNumbers[multiply2] * 2, uglyNumbers[multiply3] * 3, uglyNumbers[multiply5] * 5);uglyNumbers[nextUglyIndex] = min;while (uglyNumbers[multiply2] * 2 <= uglyNumbers[nextUglyIndex]){multiply2++;}while (uglyNumbers[multiply3] * 3 <= uglyNumbers[nextUglyIndex]){multiply3++;}while (uglyNumbers[multiply5] * 5 <= uglyNumbers[nextUglyIndex]){multiply5++;}nextUglyIndex++;}int result = uglyNumbers[index - 1];uglyNumbers = null;return result;}private static int Min(int num1, int num2, int num3){ //比较三个数中的最小数int min = num1 < num2 ? num1 : num2;min = min < num3 ? min : num3;return min;} }

 

 

2.手写二分查找算法

思路：有递归和非递归两种实现，但是用递归实现的话，函数调用会有一定的开销，也受到java虚拟机栈空间大小的限制。所以最好使用非递归实现，效率高。非递归算法实现的核心在于，while循环。

public class Main{public static void main(String[] args){int[] a={3,6,7,12,16,24,32,35,46,92,93,104,146,324};System.out.println(binarySearch(a,6));}private static int binarySearch(int[] arr,int target) {int left=0,right=arr.length-1;while(left<=right){int middle=(left+right)/2;if(arr[middle]>target){right=middle-1;}else if(arr[middle]<target){left=middle+1;}else{
　　　　　　　　　 //如果找到了，就返回target的位置return middle;}}
//否则返回-1.return -1;} }

 

转载于:https://www.cnblogs.com/james111/p/7508943.html

总结

以上是生活随笔为你收集整理的滴滴笔试的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。