面试的痛点在于不知道掌握什么--但是目前看来-抓住中小公司的共同点--然后海投

有的会本地IDE-运行-最好提前准备一个Solution的class用于写

快排

public class Solution {
	public static void main(String[] args) {
    int[] arr = new int[] {9,4,6,8,3,10,4,6};
    quickSort(arr,0,arr.length - 1);
    System.out.println(Arrays.toString(arr));
}
  public static void quickSort(int[] arr, int left, int right) {
    if (left < right) {
        int pivot = partition(arr, left, right);
        quickSort(arr, left, pivot - 1);
        quickSort(arr, pivot + 1, right);
    }
}

private static int partition(int[] arr, int left, int right) {
    int pivot = left;
    int index = pivot +1  ;
    for (int i = index; i < right; i++) {
        if (arr[i] < arr[pivot]) {
            int temp = arr[i];
            arr[i] = arr[index];
            arr[index] = temp;
        }
    }
    int temp = arr[pivot];
    arr[pivot] = a[index-1];
    arr[index-1] = temp;
    return index-1;
}
}

还有归并之后写

桶排

值<=t和下标之差<=k

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        int n = nums.length;

        //桶的大小为t+1，允许最大元素和最小元素之差为t
        long w = (long) t + 1;

        //因为一个桶有两个元素就会返回true，因此一个桶只有一个元素，可以用哈希表的一条key-value表示桶
        Map<Long, Long> map = new HashMap<Long, Long>();

        for (int i = 0; i < n; i++) {
            long id = getID(nums[i], w);

            //桶里已有元素x，nums[i]和x同属一个桶，值符合范围
            //只保留下标 i 之前的 k 个元素，因此下标也符合范围
            //桶有两个元素就会返回，因此一个桶只有一个元素
            if (map.containsKey(id)) {
                return true;
            }

            //前一个桶有一个元素，并且值的范围符合要求
            if (map.containsKey(id - 1) && Math.abs(nums[i] - map.get(id - 1)) < w) {
                return true;
            }

            //后一个桶有一个元素，并且值的范围符合要求
            if (map.containsKey(id + 1) && Math.abs(nums[i] - map.get(id + 1)) < w) {
                return true;
            }

            //没有和nums[i]匹配的元素，把nums[i]加入自己的桶里
            map.put(id, (long) nums[i]);

            //下标范围[i-k+1, i]，从nums[i-k]所在桶移除元素
            if (i >= k) {
                map.remove(getID(nums[i - k], w));
            }
        }
        return false;
    }

    public long getID(long x, long w) {
        //非负数区间，如[0, t] 会被归到 id=0
        //其余的区间，如[(n-1)t+1, nt+1]，每t+1个元素会被归到 id = n-1
        if (x >= 0) {
            return x / w;
        }

        //负数区间，如[-t, -1] 会被归到 id=-1
        //其余的区间，如[-(n+1)t-1, -nt-1]，每t+1个元素会被归到 id = -(n+1)
        return (x + 1) / w - 1;
    }
}

1. getId: 0-w-1--->0, -1 to -w -------> -1, 所以才会有（（x+1）/w ） -1
2. 溢出所以使用long
3. 每个桶内部元素只会有一个，因为第一次判断如果已经存在就说明现在有两个元素满足了，就可以直接返回true
4. 然后如果自己的桶不存在，就看相邻的桶的元素是不是小于W的，注意相邻的也只会存在一个，因为两个就会返回true
5. 然后都没有就放进桶，记住还要删除i-k的，因为在下次遍历的时候我们只需要查看前k个元素的即可，所以只需要维护区间K
6. 记住下次遍历是i+1，所以这里删除i-k,这样就是i-k+1 to i - k + k,

前序遍历

//核心
stack.push(root);
while(!stack.isEmpty()){
  TreeNode node = stack.pop();
  list.add(node.val);
  if(node.right!=null){
	stack.push(node.right);
  }
  if(node.left!=null){
	stack.push(node.left);
  }
}
return list.stream().mapToInt(Integer::intValue).toArray();

这个不刷就不好快速写出来，实际上就是先读取根节点，再插入右节点，再插入左节点

出栈-读取-插入右节点-插入左节点-循环

这样子就是先读取根，随后读取左，右节点就一直压着

中序遍历

while（root!=null||!stack.isEmpty()）{
  while(root!=null){
	stack.push(root);
	root = root.left;
 }
  TreeNode node = stack.pop();
  list.add(node.val);
  root = node.right;
}
return list.stream().mapToInt(Integer::intValue).toArray();

我怀疑手撕算法一般真的出前序不出中序，因为中序有点绕；

首先我们需要找到最左边的节点，因此必须一开始就有循环压栈；

那么随后弹出读取-这个相当于根节点了-之后就必须读取右节点；

root等于当前节点右节点-继续迭代

那么如果为空，也没关系，只要栈不为空即可；

所以就是--循环压栈root-最左节点-赋值root最左叶节点右孩子-迭代循环

后序遍历

TreeNode pre = null;
while（root!=null||!stack.isEmpty()）{
  while(root!=null){
	stack.push(root);
	root = root.left;
  }
  TreeNode node = stack.pop();
  if(node.right==null||node.right==pre){
	list.add(node.val);
	pre = node;
  }else{
	stack.push(node);
	root = root.right;
  }
 
}

这个貌似pre就很难理解-中序需要root来帮助遍历；

后续也是遍历到最左-假设此时右边有节点-就会重新把node压入栈中

然后把node.right压入栈中--也就是找到最左节点的右节点进行递归

而终止条件就是右节点为空或者遍历过了。那么假设右节点遍历过了

就应该使用pre指定-节点。

右视图-层序遍历

 que.offer(root);
        TreeNode curr = null;
        while(!que.isEmpty()){
            int size  = que.size();
            for(int i = 0;i<size;i++){
                curr = que.poll();
                if(curr.left!=null) que.offer(curr.left);
                if(curr.right!=null) que.offer(curr.right);
            }
            ans.add(curr.val);
        }
        return ans;

如果不是求每一层的最右边一个，只是遍历的列表，可以不使用size