1. leetcode 3 最長無重復字串

public int lengthOfLongestSubstring(String s) {
       int i=0,j=0;
       Set<Character> set=new HashSet<>();
       int maxLen=0;
       while (j<s.length()){
           char  c=s.charAt(j);
           while (set.contains(c)){
               set.remove(s.charAt(i));
               i++;
           }
           maxLen=Math.max(maxLen,j-i+1);  //更新每次的最大長度
           j++;
           set.add(c);
       }
       return maxLen;
    }

雖然是雙層 while 循環(huán)，使用了滑動窗口的思想，算法時間復雜度還是 ON 的。

2. 二叉樹廣度和廣度遍歷方式

自己定義了一個 TreeNode，構建出來二叉樹，然后進行遍歷。

深度優(yōu)先使用遞歸方式遍歷，廣度優(yōu)先使用隊列來遍歷。

public class TreeNode {

    public Integer value;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(Integer value, TreeNode left, TreeNode right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }

    public TreeNode() {
    }
    public TreeNode(Integer value) {
        this.value=value;
        this.left=null;
        this.right=null;
    }
}

深度優(yōu)先遍歷方式:

    public  static  void  printDFS(TreeNode root){
         if (root==null){
             return;
         }
        //前序遍歷方式
        System.out.println(root.value);
        printDFS(root.left);
        printDFS(root.right);
    }

廣度優(yōu)先遍歷:

public  static  void  printBFS(TreeNode root){
Queue<TreeNode> queue=new ArrayDeque<>();
queue.add(root);
while (!queue.isEmpty()){
    TreeNode node=queue.poll();
    System.out.println(node.value);
    if (node.left!=null){
        queue.add(node.left);
    }
    if (node.right!=null){
        queue.add(node.right);
    }
}
}

手寫快速排序

先和面試官說快排的思想

采用“分治”的思想，對于一組數(shù)據(jù)，選擇一個基準元素（base），通常選擇第一個或最后一個元素，通過第一輪掃描，比base小的元素都在base左邊，比base大的元素都在base右邊，再有同樣的方法遞歸排序這兩部分，直到序列中所有數(shù)據(jù)均有序為止。

   public static void quickSort(int[] arr, int start, int end) {
        //基準值是temp
        if (start < end) {
            int base = arr[start];
            int left = start;
            int right = end;
            while (left < right && arr[right] > base) {
                //后面的小于了temp
                right--;
            }
            arr[left] = arr[right];
            //右邊基準
            while (left < right && arr[left] < base) {
                left++;
            }
            arr[right] = arr[left];
            arr[left] = base;
            quickSort(arr, start, left - 1);
            quickSort(arr, left + 1, end);
        }
    }

沒寫出來，爆戰(zhàn)了，很難受。

優(yōu)化之后的代碼:

通過三數(shù)字取中減少時間的復雜度。

public static void quickSort(int[] arr, int start, int end) {
    if (start >= end) return;

    // 三數(shù)取中法選擇基準
    int mid = start + (end - start) / 2;
    if (arr[start] > arr[end]) swap(arr, start, end);
    if (arr[mid] > arr[end]) swap(arr, mid, end);
    if (arr[start] < arr[mid]) swap(arr, start, mid);

    int base = arr[start];
    int i = start, j = end;
    while (i < j) {
        while (i < j && arr[j] >= base) j--;
        if (i < j) arr[i++] = arr[j];
        while (i < j && arr[i] <= base) i++;
        if (i < j) arr[j--] = arr[i];
    }
    arr[i] = base;
    quickSort(arr, start, i - 1);
    quickSort(arr, i + 1, end);
}

private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

可以參考這個博客

https://blog.csdn.net/qq_39181839/article/details/109478094