云智手撕算法

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 循环，使用了滑动窗口的思想，算法时间复杂度还是 ON 的。

2. 二叉树广度和广度遍历方式

自己定义了一个 TreeNode，构建出来二叉树，然后进行遍历。

深度优先使用递归方式遍历，广度优先使用队列来遍历。

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;
    }
}

深度优先遍历方式:

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

广度优先遍历:

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);
    }
}
}

手写快速排序

先和面试官说快排的思想

采用“分治”的思想，对于一组数据，选择一个基准元素（base），通常选择第一个或最后一个元素，通过第一轮扫描，比base小的元素都在base左边，比base大的元素都在base右边，再有同样的方法递归排序这两部分，直到序列中所有数据均有序为止。

   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);
        }
    }

没写出来，爆战了，很难受。

优化之后的代码:

通过三数字取中减少时间的复杂度。

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

    // 三数取中法选择基准
    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