5分钟手写快排归并广度-二叉树栈前序中序后序
面试的痛点在于不知道掌握什么--但是目前看来-抓住中小公司的共同点--然后海投
有的会本地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;
}
}
- getId: 0-w-1--->0, -1 to -w -------> -1, 所以才会有（（x+1）/w ） -1
- 溢出所以使用long
- 每个桶内部元素只会有一个，因为第一次判断如果已经存在就说明现在有两个元素满足了，就可以直接返回true
- 然后如果自己的桶不存在，就看相邻的桶的元素是不是小于W的，注意相邻的也只会存在一个，因为两个就会返回true
- 然后都没有就放进桶，记住还要删除i-k的，因为在下次遍历的时候我们只需要查看前k个元素的即可，所以只需要维护区间K
- 记住下次遍历是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
