【大厂高频算法题】阿里后端春招

【大厂高频算法题】阿里后端春招

大部分居然都是简单题，有点不敢置信。。。

1、反转链表（剑指offer 24）

分析：
整个链表翻转有两种方法——头插法 和 指针反转
两者都要注意一个置空的操作，避免出现环

**头插法图解：
**

//头插法
class Solution {public ListNode reverseList(ListNode head) {if(head == null ||  == null){return head;}ListNode pre = new ListNode(0); = head;ListNode cur = ;//下边这句非常重要，使用头插法，最后一个节点一定要指向null，不然就会有环。 = null;while(cur!=null){ListNode tmp = ; =  = ; = cur;cur = tmp;};}
}

反转指针图解

//翻转指针
class Solution {public ListNode reverseList(ListNode head) {if(head == null ||  == null){return head;}ListNode cur = ; = null;while(cur!=null){ListNode tmp = ; = head;head = cur;cur = tmp;}    return head;}
}

2、链表内指定区间翻转

3、数组中的第K个最大元素

分析：
1、排序（快排）：随机快排（任意指定pivot）/首元素作为pivot
随机快排效率会高很多，但是要是记不住随机，就写首元素作为pivot的快排吧
2、优先队列——堆

//首元素作为pivot
class Solution {public int findKthLargest(int[] nums, int k) {quickSort(nums,k,0,nums.length-1);return nums[k-1];}private void quickSort(int[] nums,int k,int left,int right){if(left >= right){return;}int pivot = left;int end = right;while(left < right){    while(left < right && nums[right] <= nums[pivot]){right--;}while(left < right && nums[left] >= nums[pivot]){left++;}//到达需要交换位置的地方swap(nums,left,right);}//一次划分完毕swap(nums,pivot,left);//一定要注意！！！这里是k-1啊！！！！！if(left < k-1){quickSort(nums,k,left+1,end);}else if(left > k-1){quickSort(nums,k,pivot,left-1);}else{return;}}private void swap(int[] nums,int left,int right){if(left == right){return;}int tmp = nums[left];nums[left] = nums[right];nums[right] = tmp;}
}

//随机快排
class Solution {private static Random random = new Random(System.currentTimeMillis());public int findKthLargest(int[] nums, int k) {int len = nums.length;int target = len-k;int left = 0;int right = len-1;while(true){int index = quickSort(nums,left,right);if(index < target){left = index+1;}else if(index > target){right = index-1;}else{return nums[index];}}}private int quickSort(int[] nums,int left,int right){//在区间随机选择一个元素作为pivotif(left < right){int randomIndex = left+Int(right - left);swap(nums,left,randomIndex);}int pivot = nums[left];int j = left;//将下标存储for(int i = left+1;i <= right;i++){if(nums[i] < pivot){j++;swap(nums,j,i);}}swap(nums,left,j);return j;}private void swap(int[] nums, int index1, int index2) {int temp = nums[index1];nums[index1] = nums[index2];nums[index2] = temp;}
}

//优先级队列
class Solution {public int findKthLargest(int[] nums, int k) {PriorityQueue<Integer> heap = new PriorityQueue<>((o1,o2)->(o1-o2));int i = 0;for(i = 0;i < nums.length;i++){heap.add(nums[i]);if(heap.size() > k){heap.poll();}}return heap.poll();}   
}

4、二叉树的后序遍历

分析：
1、递归；
2、非递归

//递归
class Solution{List<Integer> res = new ArrayList<>();public List<Integer> postorderTraversal(TreeNode root) {if(root == null){return res;}postTraverse(root);return res;}private void postTraverse(TreeNode root){if(root == null){return;}postTraverse(root.left);postTraverse(root.right);res.add(root.val);}
}

//非递归:verse(根右左);
class Solution{List<Integer> res = new ArrayList<>();public List<Integer> postorderTraversal(TreeNode root) {Stack<TreeNode> s = new Stack<>();if(root == null){return res;}while(root!=null || !s.isEmpty()){while(root!=null){s.push(root);res.add(root.val);root = root.right;}TreeNode node = s.pop();root = node.left;}verse(res);return res;}
}

5、两数之和

class Solution {public int[] twoSum(int[] nums, int target) {int[] res = new int[2];//map里放数组元素为了达到target需要的数字Map<Integer,Integer> map = new HashMap<>();for(