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虛擬機?？臻g大小的限制。所以最好使用非遞歸實現，效率高。非遞歸算法實現的核心在于，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

總結

以上是生活随笔為你收集整理的滴滴笔试的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。