前言
一年之計在于春 金三銀四已經(jīng)要到來,2019的新的開始渴逻,作為一個開發(fā)人員妙啃,你是否面上了自己理想的公司档泽,薪資達(dá)到心中理想的高度?
如果沒有的話揖赴, 你就需要掌握更加成熟的技術(shù)馆匿,也需要更多的知識儲備,對于我們上班族而言燥滑,工作的好壞就變得格外重要渐北,想要拿高的工資,就好好的做好面試準(zhǔn)備铭拧,
以下是我為大家精心挑選的面試題赃蛛,話不多說,看東西搀菩。
正文
實現(xiàn)階乘
//采用遞歸法
if (number <= 1)
return 1;
else
return number * factorial(number - 1);
}
//采用循環(huán)連乘法
public static int fact(int num){
int temp=1;
int factorial=1;
while(num>=temp){
factorial=factorial*temp;
temp++;
}
return factorial;
}
二分查找
//遞歸法
if (low > high) return -1;
int mid = low + (high - low) / 2;
if (array[mid] > target)
return binarysearch(array, low, mid - 1, target);
if (array[mid] < target)
return binarysearch(array, mid + 1, high, target);
return mid;
}
//循環(huán)法
int low = 0;
int high = a.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (a[mid] > key)
high = mid - 1;
else if (a[mid] < key)
low = mid + 1;
else
return mid;
}
return -1;
}
二分查找中值的計算
- 這是一個經(jīng)典的話題呕臂,如何計算二分查找中的中值?大家一般給出了兩種計算方法:
- 算法一:mid = (low + high) / 2
- 算法二:mid = low + (high – low)/2
- 乍看起來秕磷,算法一簡潔诵闭,算法二提取之后,跟算法一沒有什么區(qū)別澎嚣。但是實際上疏尿,區(qū)別是存在的。算法一的做法易桃,在極端情況下褥琐,(low+high)存在著溢出的風(fēng)險,進而得到錯誤的mid結(jié)果晤郑,導(dǎo)致程序錯誤敌呈。而算法二能夠保證計算出來的mid,一定大于low造寝,小于high磕洪,不存在溢出的問題。
二分查找法的缺陷
- 二分查找法的O(logn)讓它成為十分高效的算法诫龙。不過它的缺陷卻也是那么明顯的析显。就在它的限定之上:必須有序,我們很難保證我們的數(shù)組都是有序的签赃。當(dāng)然可以在構(gòu)建數(shù)組的時候進行排序谷异,可是又落到了第二個瓶頸上:它必須是數(shù)組分尸。
- 數(shù)組讀取效率是O(1),可是它的插入和刪除某個元素的效率卻是O(n)歹嘹。因而導(dǎo)致構(gòu)建有序數(shù)組變成低效的事情箩绍。
解決這些缺陷問題更好的方法應(yīng)該是使用二叉查找樹了,最好自然是自平衡二叉查找樹了尺上,既能高效的(O(n log n))構(gòu)建有序元素集合材蛛,又能如同二分查找法一樣快速(O(log n))的搜尋目標(biāo)數(shù)。
用兩個棧實現(xiàn)隊列
題目描述:
- 用兩個棧來實現(xiàn)一個隊列怎抛,完成隊列的Push和Pop操作仰税。隊列中的元素為int類型。
- 思路:
壓入元素直接壓入stack1 刪除元素先查看stack2是否為空抽诉,非空則彈出;空則將stack1中元素取出吐绵,置于stack2中
代碼:
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node){
stack1.push(node);
}
public int pop(){
if(stack2.empty()){
while(!stack1.empty())
stack2.push(stack1.pop());
}
return stack2.pop();
}
遞歸和迭代的區(qū)別是什么迹淌,各有什么優(yōu)缺點?
程序調(diào)用自身稱為遞歸己单,利用變量的原值推出新值稱為迭代唉窃。
遞歸的優(yōu)點大問題轉(zhuǎn)化為小問題,可以減少代碼量纹笼,同時代碼精簡纹份,可讀性好;缺點就是遞歸調(diào)用浪費了空間廷痘,而且遞歸太深容易造成堆棧的溢出蔓涧。
迭代的好處就是代碼運行效率好,因為時間只因循環(huán)次數(shù)增加而增加笋额,而且沒有額外的空間開銷元暴;缺點就是代碼不如遞歸簡潔
判斷101-200之間有多少個素數(shù),并輸出所有素數(shù)
素數(shù)又稱質(zhì)數(shù)兄猩。所謂素數(shù)是指除了 1 和它本身以外茉盏,不能被任何整數(shù)整除的數(shù),例如17就是素數(shù)枢冤,因為它不能被 2~16 的任一整數(shù)整除鸠姨。思路1):因此判斷一個整數(shù)m是否是素數(shù),只需把 m 被 2 ~ m-1 之間的每一個整數(shù)去除淹真,如果都不能被整除讶迁,那么 m 就是一個素數(shù)。
思路2):另外判斷方法還可以簡化趟咆。m 不必被 2 ~ m-1 之間的每一個整數(shù)去除添瓷,只需被 2 ~ 之間的每一個整數(shù)去除就可以了梅屉。如果 m 不能被 2 ~ 間任一整數(shù)整除,m 必定是素數(shù)鳞贷。例如判別 17 是是否為素數(shù)坯汤,只需使 17 被 2~4 之間的每一個整數(shù)去除,由于都不能整除搀愧,可以判定 17 是素數(shù)惰聂。
原因:因為如果 m 能被 2 ~ m-1 之間任一整數(shù)整除,其二個因子必定有一個小于或等于 咱筛,另一個大于或等于 搓幌。例如 16 能被 2、4迅箩、8 整除溉愁,16=28,2 小于 4饲趋,8 大于 4拐揭,16=44,4=√16奕塑,因此只需判定在 2~4 之間有無因子即可堂污。
public static void main(String args[]){
int i=0;
for(i=101;i<=200;i++)
if(math.isPrime(i)==true)
System.out.println(i);
}
}
class math
{
//方法1
public static boolean isPrime(int x)
{
for (int i=2;i<=x/2;i++)
if (x%2==0)
return false;
return true;
}
//方法2
public static boolean isPrime2(int m)
{
int k=(int)sqrt((double)m);
for (int i=2;i<=k;i++)
if (m%i==0)
return false;
return true;
}
}
字符串小寫字母轉(zhuǎn)換成大寫字母
public String toUpperCase(String str)
{
if (str != null && str.length() > 0) {
for (int i=0; i<str.length(); i++) {
char c = str.charAt(i);
c += 32;
}
}
return str;
}
進制轉(zhuǎn)換:給定一個十進制數(shù) n 和 一個整數(shù) k, 將 十進制數(shù) n 轉(zhuǎn)換成 k進制數(shù)
StringBuffer resultNumber = new StringBuffer();
tenToK(resultNumber, n, k);
System.out.println("n:k:result: " + n +" "+ k + " " + resultNumber.toString());
return resultNumber.toString();
}
private void tenToK(StringBuffer stringBuffer, int n, int k) {
int integral = n/k;
int mode = n % k;
stringBuffer.insert(0, mode);
if (integral >= k) {
tenToK(stringBuffer, integral, k);
} else if (integral > 0) {
stringBuffer.insert(0, integral);
}
}
位運算實現(xiàn)加法
public int aplusb(int a, int b) {
int sum_without_carry, carry;
sum_without_carry = a^b; //沒有進位的和
carry = (a&b)<<1; //進位
if(carry==0) {
return sum_without_carry;
} else {
return aplusb(sum_without_carry, carry);
}
}
二叉樹排序樹
首先定義節(jié)點類
Object obj;
TreeNode parent;
TreeNode lchild;
TreeNode rchild;
public TreeNode(int obj) {
this.obj = obj;
}
}
然后創(chuàng)建一個樹類
public class Tree {
/**
* 先序遍歷二叉樹
* @param root
*/
public void Fprint(TreeNode root){
if(root!=null){
System.out.println(root.obj);
Fprint(root.lchild);
Fprint(root.rchild);
}
}
/**
* 中序遍歷二叉樹
* @param root
*/
public void Mprint(TreeNode root){
if(root!=null){
Mprint(root.lchild);
System.out.println(root.obj);
Mprint(root.rchild);
}
}
/**
* 根據(jù)一個int數(shù)組建立二叉排序樹
* @param a 數(shù)組
* @return
*/
public TreeNode Build(int[] a){
if(a.length==0){
return null;
}
TreeNode root = new TreeNode(a[0]);
for(int i=1;i<a.length;i++){
TreeNode newnode = new TreeNode(a[i]);
sort(root,newnode);
}
return root;
}
/**
* 在二叉排序樹中添加一個節(jié)點
* @param root 二叉樹的根節(jié)點
* @param newnode 新加入的加點
* @return
*/
public void sort(TreeNode root,TreeNode newnode){
TreeNode node = root;
if((Integer)newnode.obj<=(Integer)node.obj){
if(node.lchild==null){
newnode.parent = node;
node.lchild = newnode;
}else{
sort(node.lchild,newnode);
}
}else{
if(node.rchild==null){
newnode.parent = node;
node.rchild = newnode;
}else{
sort(node.rchild,newnode);
}
}
}
}
創(chuàng)建二叉排序樹的時候隨便傳入一個int型數(shù)組a[]
然后通過自頂向下的方式一個一個的將a[0]---a[n]個元素創(chuàng)建的節(jié)點類一個一個的拼接到樹上
此后只需要再創(chuàng)建一個主函數(shù)類來調(diào)用便行了
public static void main(String[] args) {
int a[] = {100,35,3,44,212,453};
Tree t = new Tree();
TreeNode root = t.Build(a);
t.Mprint(root);
}
}
- 這樣便可通過創(chuàng)建二叉排序樹并且中序遍歷該二叉樹的方式,來將一組混亂的數(shù)據(jù)整理成一組從小到大的數(shù)據(jù)了龄砰。
冒泡排序
- 算法描述:對于給定的n個記錄盟猖,從第一個記錄開始依次對相鄰的兩個記錄進行比較,當(dāng)前面的記錄大于后面的記錄時换棚,交換位置式镐,進行一輪比較和交換后,n個記錄中的最大記錄將位于第n位固蚤;然后對前(n-1)個記錄進行第二輪比較碟案;重復(fù)該過程直到進行比較的記錄只剩下一個為止。
/**
* 冒泡排序
* 平均O(n^2),最好O(n),最壞O(n^2);空間復(fù)雜度O(1);穩(wěn)定;簡單
* @author zeng
*
*/
public class BubbleSort {
public static void bubbleSort(int[] a){
int n = a.length;
int temp = 0;
for(int i=0;i<n;i++){
for(int j=0;j<n-i-1;j++){
if(a[j]<a[j+1]){
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
}
public static void main(String[] args){
int[] a ={49,38,65,97,76,13,27,50};
bubbleSort(a);
for(int j:a)
System.out.print(j+" ");
}
}
插入排序
- 算法描述:對于給定的一個數(shù)組颇蜡,初始時假設(shè)第一個記錄自成一個有序序列价说,其余記錄為無序序列。接著從第二個記錄開始风秤,按照記錄的大小依次將當(dāng)前處理的記錄插入到其之前的有序序列中鳖目,直至最后一個記錄插入到有序序列中為止。
/**
* 插入排序
* 平均O(n^2),最好O(n),最壞O(n^2);空間復(fù)雜度O(1);穩(wěn)定;簡單
* @author zeng
*
*/
public class InsertionSort {
public static void insertionSort(int[] a) {
int tmp;
for (int i = 1; i < a.length; i++) {
for (int j = i; j > 0; j--) {
if (a[j] < a[j - 1]) {
tmp = a[j - 1];
a[j - 1] = a[j];
a[j] = tmp;
}
}
}
}
public static void main(String[] args) {
int[] a = { 49, 38, 65, 97, 76, 13, 27, 50 };
insertionSort(a);
for (int i : a)
System.out.print(i + " ");
}
}
選擇排序
- 算法描述:對于給定的一組記錄缤弦,經(jīng)過第一輪比較后得到最小的記錄领迈,然后將該記錄與第一個記錄的位置進行交換;接著對不包括第一個記錄以外的其他記錄進行第二輪比較,得到最小的記錄并與第二個記錄進行位置交換狸捅;重復(fù)該過程衷蜓,直到進行比較的記錄只有一個時為止。
/**
* 選擇排序
* 平均O(n^2),最好O(n^2),最壞O(n^2);空間復(fù)雜度O(1);不穩(wěn)定;簡單
* @author zeng
*
*/
public class SelectionSort {
public static void selectionSort(int[] a) {
int n = a.length;
for (int i = 0; i < n; i++) {
int k = i;
// 找出最小值的小標(biāo)
for (int j = i + 1; j < n; j++) {
if (a[j] < a[k]) {
k = j;
}
}
// 將最小值放到排序序列末尾
if (k > i) {
int tmp = a[i];
a[i] = a[k];
a[k] = tmp;
}
}
}
public static void main(String[] args) {
int[] b = { 49, 38, 65, 97, 76, 13, 27, 50 };
selectionSort(b);
for (int i : b)
System.out.print(i + " ");
}
}
快速排序
- 算法描述:對于一組給定的記錄尘喝,通過一趟排序后磁浇,將原序列分為兩部分,其中前一部分的所有記錄均比后一部分的所有記錄小朽褪,然后再依次對前后兩部分的記錄進行快速排序置吓,遞歸該過程,直到序列中的所有記錄均有序為止缔赠。
/**
* 快速排序
* 平均O(nlogn),最好O(nlogn),最壞O(n^2);空間復(fù)雜度O(nlogn);不穩(wěn)定;較復(fù)雜
* @author zeng
*
*/
public class QuickSort {
public static void sort(int[] a, int low, int high) {
if(low>=high)
return;
int i = low;
int j = high;
int key = a[i];
while (i < j) {
while (i < j && a[j] >= key)
j--;
a[i++] = a[j];
while (i < j && a[i] <= key)
i++;
a[j--] = a[i];
}
a[i] = key;
sort(a,low,i-1);
sort(a,i+1,high);
}
public static void quickSort(int[] a) {
sort(a, 0, a.length-1);
for(int i:a)
System.out.print(i+" ");
}
public static void main(String[] args) {
int[] a = { 49, 38, 65, 97, 76, 13, 27, 50 };
quickSort(a);
}
}
歸并排序
- 算法描述:對于給定的一組記錄衍锚,首先將每兩個相鄰的長度為1的子序列進行歸并,得到 n/2(向上取整)個長度為2或1的有序子序列嗤堰,再將其兩兩歸并戴质,反復(fù)執(zhí)行此過程,直到得到一個有序序列踢匣。
/**
* 歸并排序
* 平均O(nlogn),最好O(nlogn),最壞O(nlogn);空間復(fù)雜度O(n);穩(wěn)定;較復(fù)雜
* @author zeng
*
*/
public class MergeSort {
public static void merge(int[] a, int start, int mid,
int end) {
int[] tmp = new int[a.length];
System.out.println("merge " + start + "~" + end);
int i = start, j = mid + 1, k = start;
while (i != mid + 1 && j != end + 1) {
if (a[i] < a[j])
tmp[k++] = a[i++];
else
tmp[k++] = a[j++];
}
while (i != mid + 1)
tmp[k++] = a[i++];
while (j != end + 1)
tmp[k++] = a[j++];
for (i = start; i <= end; i++)
a[i] = tmp[i];
for (int p : a)
System.out.print(p + " ");
System.out.println();
}
static void mergeSort(int[] a, int start, int end) {
if (start < end) {
int mid = (start + end) / 2;
mergeSort(a, start, mid);// 左邊有序
mergeSort(a, mid + 1, end);// 右邊有序
merge(a, start, mid, end);
}
}
public static void main(String[] args) {
int[] b = { 49, 38, 65, 97, 76, 13, 27, 50 };
mergeSort(b, 0, b.length - 1);
}
}
希爾排序
- 算法描述:先將待排序序列的數(shù)組元素分成多個子序列置森,使得每個子序列的元素個數(shù)相對較少,然后對各個子序列分別進行直接插入排序符糊,待整個待排序序列“基本有序”后,再對所有元素進行一次直接插入排序呛凶。
/**
* 希爾排序
* 平均O(nlogn),最壞O(nlogn);空間復(fù)雜度O(1);不穩(wěn)定;較復(fù)雜
* @author zeng
*
*/
public class ShellSort {
public static void shellSort(int[] a) {
int n = a.length;
int d = n / 2;
while (d > 0) {
for (int i = d; i < n; i++) {
int j = i - d;
while (j >= 0 && a[j] > a[j + d]) {
int tmp = a[j];
a[j] = a[j + d];
a[j + d] = tmp;
j = j - d;
}
}
d = d / 2;
}
}
public static void main(String[] args) {
int[] b = { 49, 38, 65, 97, 76, 13, 27, 50 };
shellSort(b);
for (int i : b)
System.out.print(i + " ");
}
}
基數(shù)排序
- 算法思想:依次按個位男娄、十位...來排序,每一個pos都有分配過程和收集過程漾稀,array[i][0]記錄第i行數(shù)據(jù)的個數(shù)模闲。
/**
* 基數(shù)排序
* 平均O(d(n+r)),最好O(d(n+r)),最壞O(d(n+r));空間復(fù)雜度O(n+r);穩(wěn)定;較復(fù)雜
* d為位數(shù),r為分配后鏈表的個數(shù)
* @author zeng
*
*/
public class RadixSort {
//pos=1表示個位,pos=2表示十位
public static int getNumInPos(int num, int pos) {
int tmp = 1;
for (int i = 0; i < pos - 1; i++) {
tmp *= 10;
}
return (num / tmp) % 10;
}
//求得最大位數(shù)d
public static int getMaxWeishu(int[] a) {
int max = a[0];
for (int i = 0; i < a.length; i++) {
if (a[i] > max)
max = a[i];
}
int tmp = 1, d = 1;
while (true) {
tmp *= 10;
if (max / tmp != 0) {
d++;
} else
break;
}
return d;
}
public static void radixSort(int[] a, int d) {
int[][] array = new int[10][a.length + 1];
for (int i = 0; i < 10; i++) {
array[i][0] = 0;// array[i][0]記錄第i行數(shù)據(jù)的個數(shù)
}
for (int pos = 1; pos <= d; pos++) {
for (int i = 0; i < a.length; i++) {// 分配過程
int row = getNumInPos(a[i], pos);
int col = ++array[row][0];
array[row][col] = a[i];
}
for (int row = 0, i = 0; row < 10; row++) {// 收集過程
for (int col = 1; col <= array[row][0]; col++) {
a[i++] = array[row][col];
}
array[row][0] = 0;// 復(fù)位崭捍,下一個pos時還需使用
}
}
}
public static void main(String[] args) {
int[] a = { 49, 38, 65, 197, 76, 213, 27, 50 };
radixSort(a, getMaxWeishu(a));
for (int i : a)
System.out.print(i + " ");
}
}
堆排序
- 算法描述:對于給定的n個記錄尸折,初始時把這些記錄看作一棵順序存儲的二叉樹,然后將其調(diào)整為一個大頂堆殷蛇,然后將堆的最后一個元素與堆頂元素進行交換后实夹,堆的最后一個元素即為最大記錄;接著將前(n-1)個元素重新調(diào)整為一個大頂堆粒梦,再將堆頂元素與當(dāng)前堆的最后一個元素進行交換后得到次大的記錄亮航,重復(fù)該過程直到調(diào)整的堆中只剩下一個元素時為止。
/**
* 堆排序
* 平均O(nlogn),最好O(nlogn),最壞O(nlogn);空間復(fù)雜度O(1);不穩(wěn)定;較復(fù)雜
* @author zeng
*
*/
public class HeapSort {
public static void heapSort(int[] a) {
int i;
int len = a.length;
// 構(gòu)建堆
for (i = len / 2 - 1; i >= 0; i--)
heapAdjust(a, i, len - 1);
//交換堆頂元素與最后一個元素的位置
for (i = len - 1; i > 0; i--) {
int tmp = a[0];
a[0] = a[i];
a[i] = tmp;
heapAdjust(a, 0, i - 1);
}
}
public static void heapAdjust(int[] a, int pos, int len) {
int child = 2 * pos + 1;
int tmp = a[pos];
while (child <= len) {
if (child < len && a[child] < a[child + 1])
child++;
if (a[child] > tmp) {
a[pos] = a[child];
pos = child;
child = 2 * pos + 1;
} else
break;
}
a[pos] = tmp;
}
public static void main(String[] args) {
int[] a = { 49, 38, 65, 97, 76, 13, 27, 50 };
heapSort(a);
for (int i : a)
System.out.print(i + " ");
}
}
總結(jié)
以上就是這篇文章的內(nèi)容了匀们,喜歡的可以關(guān)注一下哦缴淋,也可以加android學(xué)習(xí)交流群1005956838,謝謝!
最后
希望大家能有一個好心態(tài)重抖,想進什么樣的公司要想清楚露氮,并不一定是大公司,我選的也不是特大廠钟沛。當(dāng)然如果你不知道選或是沒有規(guī)劃畔规,那就選大公司!希望我們能先選好想去的公司再投或內(nèi)推讹剔,而不是有一個公司要我我就去油讯!還有就是不要害怕,也不要有壓力延欠,平常心對待就行陌兑,但準(zhǔn)備要充足。最后希望大家都能拿到一份滿意的 offer 由捎!如果目前有一份工作也請好好珍惜好好努力兔综,找工作其實挺累挺辛苦的。