java基礎面試題匯總A篇
文章目錄
- java基礎面試題匯總A篇
- 1.求6&3，-6&-3的值
- 2. 利用&符號能否判斷一個數的奇偶?
- 3.遞回實作字串反轉
- 4.快速排序
- 5.雙指標法
- 6.給定一個包含 n 個整數的陣列 nums，判斷 nums 中是否存在三個元素 a，b，c ，使得 a + b + c = 0 ？
- 7.動態規劃數字塔
- 8.冒泡排序，選擇排序，歸并排序，二分查找
- 9.單鏈表
- 10.單鏈表反轉
- 11.單鏈表實作佇列
- 12.單鏈表實作堆疊
- 13.實作hash表
- 14.實作二叉樹
該系列主要針對校招實習的同學，先寫出基本常見的大廠面試題，后面會持續更新面試的題
1.求6&3，-6&-3的值
決議：
Java使用 補 碼 來 表 示 二 進 制 數 ,在補 碼 表 示 中 ,最高 位 為 符號 位 ,正數 的 符 號 位 為 0,負數 為 1，補 碼 的 規 定 如 下 :
對 正 數 來 說 ,最高位為 0,其余 各 位 代 表 數 值 本 身 (以二 進制 表 示 ),如 +42的補碼 為 00101010，
對 負 數 而 言 ,把該 數 絕 對 值 的 補 碼 按 位 取 反 ,然后 對 整 個數 加 1,即得 該 數的 補 碼 ， 如 -1的補 碼 為11111111111111111111111111111111(00000000000000000000000000000001按 位 取 反 11111111111111111111111111111110+1=11111111111111111111111111111111 )，為何有那么多0、1，java中int是32位的，
按位與（&）
只有兩個運算元對應位同為1時，結果為1，其余全為0. （或者是只要有一個運算元為0，結果就為0）
例如：
6&3=2
6---->110
3---->011
得到結果010=2
-6&-3=-8
-6---->00000000000000000000000000000110取反11111111111111111111111111111001
然后加1 等于11111111111111111111111111111010
-3---->00000000000000000000000000000011取反11111111111111111111111111111100
然后加1 等于11111111111111111111111111111101
兩個結果取& 等于11111111111111111111111111111000
然后-1 等于11111111111111111111111111110111
取反得到00000000000000000000000000001000=8
這是取反的結果原來符號為1，所以是-8
其它：
按位或（|）
只有兩個運算元對應位同為0時，結果為0，其余全為1.（或者是只要有一個運算元為1，結果就為1），
按位非（~）
源運算元為0變為1 源運算元為1變為0
例如：~-5=4
參照前面的補碼取反：
-5---->00101-取反–>11010+1=11011后運行按位~=00100
按位異或的運算規則^
前后兩數不同即為1
左位移（<<）
符號位不變，低位補0，如：2<<2結果為8，
2---->00010
左移兩位01000結果為8
右位移（>>）
低位溢位，符號位不變，并用符號位補溢位的高位，如：-6>>2結果為-2，
-6----->00110取反+1---->11001+1=11010
左移兩位符號位不變得11110然后-1按位取反得到00010 所以是-2
無符號右移（>>>）
低位溢位，高位補0，注意，無符號右移（>>>）中的符號位（最高位）也跟著變，無符號的意思是將符號位當作數字位看待
所以-6>>>2得到的結果是：1073741822
-1>>>1得到Integer.MAX_VALUE
2. 利用&符號能否判斷一個數的奇偶?
可以
n&==1說明n是奇數
因為：偶數的最低位肯定是0，奇數的最低位肯定是1，而1的最低位為1其它為0所以只有當n是奇數時才能得到最低位為1
3.遞回實作字串反轉
public String reverseStr(String str){
if(str.length() <= 1){
return str;
}
return reverseStr(str.substring(1)) + str.charAt(0);
}
4.快速排序
網上有很多說明，我這里就直接給出代碼跟注釋了
/**
* @param numbers:要排序的陣列
* @param begin：排序的起始位置 對應陣列的下標
* @param end：排序的結束位置
*/
private static void fastsort(int[] numbers,int begin,int end) {
int low=begin;
int big=end;
//取第一個數為基準數
int key=numbers[low];
//每次回圈可以確定基準數的位置
while(big>low){
//如果后面的數比基準數大就繼續比較下一位 相等的認為是大
while(big>low&&key<=numbers[big]){
big--;
}
//如果后面的數比基準數小 則進行交換 因為確定基準數的位置就是把比他小的放前面
//比它大的放后面，后面的數比基準數小所以調換到前面來,這個小的數放在基準數原來的位置
if(big>low&&numbers[big]<=key){
int temp = numbers[big];
numbers[big]=key;
numbers[low]=temp;
}
//現在把基準數放在了big的位子，把比基準數小的原來位于big位置的數放在low的位置
//可以確定的是big---end的數都比基準數大，但是無法確定low---big的數比基準數小
//所以需要繼續比較前面
while(big>low&&key>numbers[low]){
low++;
}
//當前面出現比基準數大的數，就交換位置
if(big>low&&numbers[low]>key){
int temp = numbers[low];
numbers[low]=key;
numbers[big]=temp;
}
//因為基準數又放在的low的位置，無法確定low---big中間是否有比基準數小的數所以需要繼續回圈
}
//當回圈結束基準數一定放在的正確的位置：
//比它大的數放在了前面，比他小的數放在了后面
//基準數不用排序了，然后我們只需要繼續對前面跟后面的小陣列再次進行排序，找到所有數的正確位置即可
//當然如果基準數前面就剩一個了就不需要排序了
if(low>begin+1)fastsort(numbers,begin,low-1);
//基準數后面也是一樣的道理
if(big+1<end)fastsort(numbers,big+1,end);
}
5.雙指標法
例如：下面陣列numbers是否存在兩數之和為target的
int []numbers={2,7,11, 15,6,9,8,7,2,11,5,7,4,69,78,61,1,8};
int target=9;
思路：雙指標法，指的是在遍歷物件的程序中，不是普通的使用單個指標進行訪問，而是使用兩個相同方向或者相反方向的指標進行掃描，從而達到相應的目的
先將陣列排好序：
這里使用快速排序：
前面指標為i指向排序好的陣列第一個數的下標
后面指標為j指向排序好的陣列最后一個下標
當numbers[i]+numbers[j]<target時 i++
當numbers[i]+numbers[j]>target時 j–
當i==j時回圈結束
完整代碼：
package cn.cdqf.junge;
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int []numbers={2, 7, 11, 15,6,9,8,7,2,11,5,7,4,69,78,61,1,8};
int target=9;
//快排
fastsort(numbers,0,numbers.length-1);
//列印
Arrays.stream(numbers).forEach(System.out::println);
System.out.println(exits(numbers,target));
}
private static boolean exits(int []numbers,int target){
//先快速排序
fastsort(numbers,0,numbers.length-1);
//一個指標i指向第一位，一個指標j指向最后一位
for(int i=0,j=numbers.length-1;i<j;){
if(numbers[i]+numbers[j]==target){
System.out.println(
"找到第一組滿足條件的數：下標"+i+"值為"+numbers[i]+",下標"+j+"值為"+numbers[j]
+"之和為："+target);
return true;
}
//如果兩數之和大于target則后指標前移，因為只有前移才會使和變小
if(numbers[i]+numbers[j]>target){
j--;
continue;
}
//同上，前指標后移
if(numbers[i]+numbers[j]<target){
i++;
continue;
}
}
return false;
}
/**
* @param numbers:要排序的陣列
* @param begin：排序的起始位置 對應陣列的下標
* @param end：排序的結束位置
*/
private static void fastsort(int[] numbers,int begin,int end) {
int low=begin;
int big=end;
//取第一個數為基準數
int key=numbers[low];
//每次回圈可以確定基準數的位置
while(big>low){
//如果后面的數比基準數大就繼續比較下一位 相等的認為是大
while(big>low&&key<=numbers[big]){
big--;
}
//如果后面的數比基準數小 則進行交換 因為確定基準數的位置就是把比他小的放前面
//比它大的放后面，后面的數比基準數小所以調換到前面來,這個小的數放在基準數原來的位置
if(big>low&&numbers[big]<=key){
int temp = numbers[big];
numbers[big]=key;
numbers[low]=temp;
}
//現在把基準數放在了big的位子，把比基準數小的原來位于big位置的數放在low的位置
//可以確定的是big---end的數都比基準數大，但是無法確定low---big的數比基準數小
//所以需要繼續比較前面
while(big>low&&key>numbers[low]){
low++;
}
//當前面出現比基準數大的數，就交換位置
if(big>low&&numbers[low]>key){
int temp = numbers[low];
numbers[low]=key;
numbers[big]=temp;
}
//因為基準數又放在的low的位置，無法確定low---big中間是否有比基準數小的數所以需要繼續回圈
}
//當回圈結束基準數一定放在的正確的位置：
//比它大的數放在了前面，比他小的數放在了后面
//基準數不用排序了，然后我們只需要繼續對前面跟后面的小陣列再次進行排序，找到所有數的正確位置即可
//當然如果基準數前面就剩一個了就不需要排序了
if(low>begin+1)fastsort(numbers,begin,low-1);
//基準數后面也是一樣的道理
if(big+1<end)fastsort(numbers,big+1,end);
}
}
實戰舉例：在之前有一個優惠券的專案，專案中規定了消費額度的最大優惠額度，每次最多使用2張優惠券，需要在眾多折扣優惠券，現金優惠券中找出最大優惠的兩張優惠券
6.給定一個包含 n 個整數的陣列 nums，判斷 nums 中是否存在三個元素 a，b，c ，使得 a + b + c = 0 ？
這個題可以先計算a+b使用上面雙指標法，在把得到結果+c又是雙指標法，
當然在中途可以利用判斷減少很多不必要的回圈
7.動態規劃數字塔
數字塔是第i行有i個數字組成，從上往下每個數字只能走到他正下方數字或者正右方數字，求數字塔從上到下所有路徑中和最大的路徑，如有下數字塔
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
窮舉演算法:
最簡單演算法，依賴計算機的強大計算能力窮盡每一種可能的情況，窮舉演算法效率不高，但是適合一些沒有明顯規律可循的場合，
貪心演算法:
又稱貪婪演算法(Greedy Algorithm)，是指在對問題求解時，總是做出在當前看來是最好的選擇，也就是說，不從整體最優解出發來考慮，它所做出的僅是在某種意義上的區域最優解，
貪婪演算法是一種分階段的作業，在每一個階段，可以認為所做決定是最好的，而不考慮將來的后果，這種“眼下能夠拿到的就拿”的策略是這類演算法名稱的來源，
貪心演算法沒有固定的演算法框架，演算法設計的關鍵是貪心策略的選擇，必須注意的是，貪心演算法不是對所有問題都能得到整體最優解，選擇的貪心策略必須具備無后效性，即某個狀態以后的程序不會影響以前的狀態，只與當前狀態有關，所以對所采用的貪心策略一定要仔細分析其是否滿足無后效性，
動態規劃
動態規劃實際上是一類題目的總稱，并不是指某個固定的演算法，動態規劃的意義就是通過采用遞推（或者分而治之）的策略，通過解決大問題的子問題從而解決整體的做法，動態規劃的核心思想是巧妙的將問題拆分成多個子問題，通過計算子問題而得到整體問題的解，而子問題又可以拆分成更多的子問題，從而用類似遞推迭代的方法解決要求的問題，
也就是分開計算處理，然后遞推，
比如上題，先看倒數第二行：如果最大值經過倒數第二排的2，那么最后一個一定45中最大值，把這個最大值保存在一個陣列中
最大值經過8那么一定是后面已經求得2或者7求得的最大值，于是有代碼
package cn.cdqf.junge;
public class DTGH {
public static void main(String[] args) {
/**
* 7
* 3 8
* 8 1 0
* 2 7 4 4
* 4 5 2 6 5
*/
int arr[][] = {
{7,0,0,0,0},
{3,8,0,0,0},
{8,1,0,0,0},
{2,7,4,4,0},
{4,5,2,6,5},
};
//創建一個陣列來保存 每個值到最后的最大值
int result[][]=new int[5][5];
//從最后一行開始回圈
for(int i = arr.length-1;i>=0;i--){
//最后一行的最后一個開始回圈，第五行就有5個數字，第一行就一個數字 所以i=行數-1 j<=i
for(int j=0;j<=i;j++){
//當是最后一行得到時候 每個數字的到最后的和就是本身
if(i==arr.length-1){
result[i][j]=arr[i][j];
continue;
}
//result[i][j] 就保存了 第i+1行 第j+1列到后面的最大值
//arr[i][j]就是本身第i+1行 第j+1列的值 比如i為3行 j是0 那么就是第四行第一列的值2
//Math.max(result[i+1][j],result[i+1][j+1])這個是求出 2正下方與2的正前下方得到的結果最大值
//所以行數是i+1 j列跟j+1列比較的最大值
result[i][j]=arr[i][j]+Math.max(result[i+1][j],result[i+1][j+1]);
}
}
//路徑最大值就是第一位
System.out.println(result[0][0]);
//可以列印出每一個數字到最后的最大值
for (int j=0;j< result.length;j++) {
for (int i = 0; i < result[j].length; i++) {
System.out.print(result[j][i]);
System.out.print(" ");
}
System.out.println();
}
}
}
8.冒泡排序，選擇排序，歸并排序，二分查找
略
其中歸并排序：
將待排序元素遞回分成大小大致相同的2個子集合，分別對2個子集合進行排序，最終將排好序的子集合合并成為所要求的排好序的集合，
比如：陣列arr 一個零時陣列temp長度與arr相同
7,4,1,3,6,8,2,5
先分成A組
7,4,1,3
B組
6,8,2,5
再將A組分成
A1：7 4 然后先對A組進行比較排序
A2：1 3 然后對B組進行比較排序
然后組合A1 A2 從最小的下標依次比較排序，合并，放入temp，最后復制到原陣列arr
package cn.cdqf.junge;
import java.util.Arrays;
public class DTGH {
public static void main(String[] args) {
int[] arr = {7,4,1,3,6,8,2,5};
int[] temp = new int[arr.length];
MergeSort(arr,0,arr.length-1,temp);
System.out.println(Arrays.toString(arr));
}
//元素分解
public static void MergeSort(int[] arr,int left,int right,int[] temp){
if (left<right){
//中間索引 第一次就是left=0 right=7
//mid=3
// 只看左邊那么第二次遞回進入該方法 left=0 right=3 mid=1
//再次只看左邊 第三次進入遞回 left=0 right=1 mid=0
//那么第四次進入 左邊就沒有滿足left<right 于是遞回結束
//進入右邊分解 右邊就是left=mid+1=1 right=1也不滿足
//所以回到第三次 直接進行合并方法這個時候 left=0 mid=0 right=1 看下面方法
int mid = (left + right)/2;
//遞回左邊進行分解
MergeSort(arr,left,mid,temp);
//遞回右邊進行分解
MergeSort(arr,mid+1,right,temp);
//到合并
merge(arr,left,mid,right,temp);
}
}
//元素合并
public static void merge(int[] arr,int left,int mid,int right,int[] temp){
//左邊有序序列的初始索引
int i = left;//0
//右邊有序序列的初始索引
int j = mid+1;//1
//指向temp的當前索引
int t = 0;
//先把左右兩邊的有序元素有序的拷貝到temp陣列中
while (i <= mid && j <= right){
//就是比較7,4
if (arr[i] <= arr[j]){
temp[t] = arr[i];
t++;
i++;
}else {
//這個時候temp[0]=4
temp[t] = arr[j];
t++;
j++;
}
}
//把一邊剩余的元素拷貝到temp陣列中
//這個時候i還是0 所以滿足 將7放到temp[1]
while (i <= mid){
temp[t] = arr[i];
t++;
i++;
}
while (j <= right){
temp[t] = arr[j];
t++;
j++;
}
//將temp陣列中元素拷貝到arr陣列中
t = 0;
int templeft = left;
while (templeft <= right){
//所以arr[0]=4 arr[1]=7完成了第一組的比較排序 回到遞回第二次 就是前面兩個陣列
//4,7跟 1,3比較排序
arr[templeft] = temp[t];
templeft++;
t++;
}
}
}
9.單鏈表
鏈表很簡單就是一個一個節點，攜帶資料，并且有個指標指向下一個元素，
所以node類，應該有兩個屬性：
package cn.cdqf.junge;
public class Node<T> {
//攜帶的資料
private T data;
//指向下一個節點的指標 所以屬性還是node型別
private Node next;
public Node(T data, Node next) {
this.data = data;
this.next = next;
}
public Node() {
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
package cn.cdqf.junge;
//單鏈表
public class SingleLinkedList<T> {
Node<T> head;
Node<T> last;
//方便記錄個數
int size;
//增加元素 只需要傳入資料即可
public SingleLinkedList add(T data){
//剛加入的節點 指向的下一個為null
Node<T> node = new Node(data,null);
//現在將剛加入的節點放在鏈表中
//就有兩種情況，1.鏈表存在元素，那么現在加入的放在末尾
//2.鏈表不存在元素，那么就是第一個
//每次都回圈去找第一個不太合適 ，所以可以在前面申明兩個變數
//head用于保存頭元素 last用于保存最后一個元素
if(head==null){//說明當前鏈表中不存在元素，新加進來的元素既是頭也是尾
head = node;
last = node;
}else {//說明鏈表中已經有元素了，只需要把新加進來的放在last的后面就可以了
last.setNext(node);
//然后新加進來的元素又成為了最后一個
last = node;
}
size++;
return this;
}
//遍歷元素
public void show(){
show(head);
}
//方便之后遍歷
public void show(Node node){
Node temp = node;
while(temp!=null){
System.out.println(temp.getData());
temp = temp.getNext();
}
}
public static void main(String[] args) {
SingleLinkedList<String> likedList = new SingleLinkedList<>();
likedList.add("張三").add("李四").add("王五").add("趙六");
likedList.show();
}
}
10.單鏈表反轉
package cn.cdqf.junge;
//單鏈表
public class SingleLinkedList<T> {
Node<T> head;
Node<T> last;
//方便記錄個數
int size;
//增加元素 只需要傳入資料即可
public SingleLinkedList add(T data){
//剛加入的節點 指向的下一個為null
Node<T> node = new Node(data,null);
//現在將剛加入的節點放在鏈表中
//就有兩種情況，1.鏈表存在元素，那么現在加入的放在末尾
//2.鏈表不存在元素，那么就是第一個
//每次都回圈去找第一個不太合適 ，所以可以在前面申明兩個變數
//head用于保存頭元素 last用于保存最后一個元素
if(head==null){//說明當前鏈表中不存在元素，新加進來的元素既是頭也是尾
head = node;
last = node;
}else {//說明鏈表中已經有元素了，只需要把新加進來的放在last的后面就可以了
last.setNext(node);
//然后新加進來的元素又成為了最后一個
last = node;
}
size++;
return this;
}
//遍歷元素
public void show(){
show(head);
}
//方便之后遍歷
public void show(Node node){
Node temp = node;
while(temp!=null){
System.out.println(temp.getData());
temp = temp.getNext();
}
}
public static void main(String[] args) {
SingleLinkedList<String> likedList = new SingleLinkedList<>();
likedList.add("張三").add("李四").add("王五").add("趙六");
likedList.show();
System.out.println("------------反轉-------------------");
likedList.show(reverse(likedList.head));
}
//A-B-C 以B為準 就是先保存C 然后讓B指向A 保存C是因為B指向A后就找不到了
public static Node reverse(Node head){
//找到第二個
Node current = head.getNext();
//第一個原來指向第二個 反轉了后應該指向null
head.setNext(null);
//當第二個不為null
while(true){
//先找到第三個，不然第二個指向第一個后 第三個就丟失了
Node next = current.getNext();
//第二個指向第一個 前面就完成了反轉
current.setNext(head);
//前一個就變成了第二個
head=current;
//在次回圈第三個
current = next;
if(current==null)
return head;
}
}
}
11.單鏈表實作佇列
佇列就是先進先出 FIFO
在剛才的鏈表中添加方法：
public T removeFirst() {
if(size==0)throw new ArrayIndexOutOfBoundsException("沒得元素");
//先取到第一個元素
Node<T> first = head;
T data = first.getData();
//移除了第一個元素 那么第二個就是第一個了
head = head.getNext();
first.setNext(null);
size--;//個數減一
return data;
}
實作佇列：
package cn.cdqf.junge;
public class SingleLinkedListQueue<T> {
private SingleLinkedList<T> singleLinkedList = new SingleLinkedList<>();
//先進
public SingleLinkedListQueue push(T data){
singleLinkedList.add(data);
return this;
}
public T pop(){//先進先出 后進后出 彈出第一個就可以了
return singleLinkedList.removeFirst();
}
//遍歷堆疊
public void show(){
singleLinkedList.show(singleLinkedList.head);
}
public static void main(String[] args) {
SingleLinkedListQueue<String> Queue =new SingleLinkedListQueue();
Queue.push("張三").push("李四").push("王五").push("趙六");
Queue.singleLinkedList.show();
//張三先進 所以彈出張三
System.out.println("彈出一個元素"+Queue.pop());
Queue.show();
}
}
12.單鏈表實作堆疊
堆疊就是先進后出FILO
先在鏈表里面添加方法：
//移除最后一個
public T removeLast() {
if(size==0)throw new ArrayIndexOutOfBoundsException("沒得元素");
T data = last.getData();
last = head;
for(int i = 0;i<size-2;i++){
//回圈找到倒數第二個,因為最后一個已經移除了 倒數第二個就成為了倒數第一個
last = last.getNext();
}
size--;
last.setNext(null);
return data;
}
package cn.cdqf.junge;
public class SingleLinkedListStack<T> {
private SingleLinkedList<T> singleLinkedList = new SingleLinkedList<>();
//先進
public SingleLinkedListStack push(T data){
singleLinkedList.add(data);
return this;
}
//先進后出 后進先出
public T pop(){
return singleLinkedList.removeLast();
}
//遍歷
public void show(){
singleLinkedList.show();
}
public static void main(String[] args) {
SingleLinkedListStack<String> stack = new SingleLinkedListStack();
stack.push("張三").push("李四").push("王五").push("趙六");
System.out.println("彈出后入的元素："+stack.pop());
System.out.println("彈出后入的元素："+stack.pop());
stack.show();
}
}
13.實作hash表
更新中
14.實作二叉樹
更新中
為此專門新建了新群，歡迎加入交流
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/262600.html
標籤：其他
上一篇：Java 開發工程師的核心競爭力