面試遇到的算法題

今天面試遇到了兩道根本算不上算法題的算法題我都沒有寫出來，我特麼都不好意思說出來。

2020-06-15

今天面試遇到了兩道根本算不上算法題的算法題我都沒有寫出來，我特麼都不好意思說出來。這塊的基礎太過於薄弱了。開一篇 blog 記錄一下學習會的算法題，之前學了幾道 LeetCode。當時覺得自己學會了，但是現在也都忘記了。什麼動態規劃之類的。

刪除數組的指定元素#

這我竟然都沒寫出來
{1,2,3,4} 刪除 4

public class DeleArrayValue{
    public static void main(String[] args){
        Integer[] arr = {1,2,3,4};
        arr=deleValue(arr,3);
        System.out.print(arr.toString);
    }
    public static Integer[] deleValue(Integer[] array,Integer value){
        int i=0
        for(; i<array.length;i++){
            if(array[i]==value) break;
        }
        if(i+1<array.length){
            System.arraycopy(array,i+1,array,i,array.length-i-1);
        }
        array[array.length-1]=null;
        return array;
    }
}

反轉鏈表#

1>2>3>4 變為 4>3>2>1

public Node reverse(Node head){
    if(head==null||head.next==null){
        return head;
    }
    Node temp= head.next;//執行到倒數第二個head=3，temp=4
    Node newHead = reversr(head.next); //newHead=4
    temp.next=head;//把當前的3給4的下一個
    head.next=null;//最後一個指向空
    return newHead;
}

頭結點插入法：

public static Node reverseListByIteration(Node head){
    Node temp;
    Node result = new Node(-1);
    while(head!=null){
        temp=head.next;//保存head的下一個用於循環，因為head變化了。
        head.next=result.next;//把result的下一個也就是-1後面的指向的給head的下一個，這樣就把之前放在result後面的放到新的後面。
        result.next=head;//然後把head接到result的後面
        head=temp;//遍歷用。
    }
    return result.next;
}

就地反轉法：

emmmm

中序遍歷#

    public List<Integer> inorderTraversal(TreeNode root) {

        List<Integer> list= new ArrayList<>();//剛測試這個應該放在外面
        if(root.left!=null){
            inorderTraversal(root.left);
        }

        list.add(root.val);
        if(root.right!=null){
           inorderTraversal(root.right);
        }

       return list;
}

前序遍歷#

     public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list= new ArrayList<>();
        list.add(root.val);
        if(root.left!=null)
        inorderTraversal(root.left);
        if(root.right!=null)
        inorderTraversal(root.right);
       return list;
}

後序遍歷#

      public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list= new ArrayList<>();
        if(root.left!=null)
       inorderTraversal(root.left);
       if(root.right!=null)
       inorderTraversal(root.right);
       list.add(root.val);
       return list;
}

刪除單鏈表的倒數第 x 個#

 public static Node deleValue(Node head ,int x){
    Node fast = head;//快指針
    Node slow = head;//慢指針
    for(int j =0;j<x-1;j++){//快指針先走的步數，畫一下圖就是知道是這個x-1.
        fast=fast.next;
    }
    while(fast.next!=null){//當快指針走到頭了，慢指針指向的就是要刪除的
        fast=fast.next;
        slow=slow.next;
    }
    slow.val=slow.next.val;//把慢指針當前指向的下一個值給當前，
    slow.next=slow.next.next;//然後把下一個指向的值給當前
    return head; //返回頭結點
}