常考算法题
...大约 4 分钟算法
1、二叉树的遍历
https://blog.csdn.net/m0_47114547/article/details/130680358
- 前序遍历(Preorder Traversal)
public void preorderTraversal(TreeNode root) {
if(root == null) return;
System.out.print(root.val + " ");
preorderTraversal(root.left);
preorderTraversal(root.right);
}
- 中序遍历(Inorder Traversal)
public void inorderTraversal(TreeNode root) {
if(root == null) return;
inorderTraversal(root.left);
System.out.print(root.val + " ");
inorderTraversal(root.right);
}
- 后序遍历(Postorder Traversal)
public void postorderTraversal(TreeNode root) {
if(root == null) return;
postorderTraversal(root.left);
postorderTraversal(root.right);
System.out.print(root.val + " ");
}
- 层序遍历(Level Order Traversal)
public void levelOrder(TreeNode root) {
if(root == null) return;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()) {
TreeNode node = queue.poll();
System.out.print(node.val + " ");
if(node.left != null) queue.add(node.left);
if(node.right != null) queue.add(node.right);
}
}
或者
public class Test{
public ArrayList<Integer> levelOrder(TreeNode root){
ArrayList<Integer> res = new ArrayList<>();
if(root==null) return res;
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
while(!q.isEmpty()){
TreeNode node = q.poll();
res.add(node.val);
if(node.left!=null){
q.add(node.left);
}
if(node.right!=null){
q.add(node.right);
}
}
return res;
}
}
2、反转链表
public class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
public ListNode reverseList(ListNode head) {
// prev指针初始为null,用于保存翻转后的头节点
ListNode prev = null;
// curr指针初始为头节点head
ListNode curr = head;
// 循环遍历链表
while(curr != null) {
// 保存curr的下一个节点到临时变量
ListNode nextTemp = curr.next;
// 修改curr的next域为prev
curr.next = prev;
// 将prev和curr同步前移一位
prev = curr;
// curr则移动到下一个节点
curr = nextTemp;
}
// 返回反转后的头结点
return prev;
}
算法步骤:
- 初始化prev为null,curr为头结点head
- 在循环中,先存Curr的下一个节点到临时变量nextTemp
- 然后修改Curr的next指针指向prev
- 再将prev和curr平移一个位置
- 最后curr更新为下一个节点nextTemp
- 循环结束后prev就指向了反转后的头结点
- 返回prev就是反转链表的结果
时间复杂度O(n),只遍历一次链表。空间复杂度O(1),只使用了一个prev指针作为辅助空间。
3、快速排序
public class QuickSort {
public void sort(int[] arr, int left, int right) {
if(left < right) {
int pivotIndex = partition(arr, left, right);
sort(arr, left, pivotIndex-1);
sort(arr, pivotIndex+1, right);
}
}
private int partition(int[] arr, int left, int right) {
int pivot = arr[left];
int i = left, j = right;
while(i < j) {
while(i < j && arr[j] >= pivot) j--;
if(i < j) arr[i++] = arr[j];
while(i < j && arr[i] < pivot) i++;
if(i < j) arr[j--] = arr[i];
}
arr[i] = pivot;
return i;
}
}
4、冒泡排序
public class BubbleSort {
public void sort(int[] arr) {
for(int i=0; i<arr.length; i++) {
for(int j=0; j<arr.length-i-1; j++) {
if(arr[j] > arr[j+1]) {
swap(arr, j, j+1);
}
}
}
}
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
5、两数之和
public class TwoSum {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for(int i=0; i<nums.length; i++) {
int complement = target - nums[i];
if(map.containsKey(complement)) {
return new int[] {map.get(complement), i};
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}
}
6、三数之和
https://leetcode.cn/problems/3sum/description/?envType=study-plan-v2&envId=top-100-liked
给你一个整数数组
nums
,判断是否存在三元组[nums[i], nums[j], nums[k]]
满足i != j
、i != k
且j != k
,同时还满足nums[i] + nums[j] + nums[k] == 0
。请你返回所有和为
0
且不重复的三元组。**注意:**答案中不可以包含重复的三元组。
示例 1:
输入:nums = [-1,0,1,2,-1,-4] 输出:[[-1,-1,2],[-1,0,1]] 解释: nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意,输出的顺序和三元组的顺序并不重要。
示例 2:
输入:nums = [0,1,1] 输出:[] 解释:唯一可能的三元组和不为 0 。
示例 3:
输入:nums = [0,0,0] 输出:[[0,0,0]] 解释:唯一可能的三元组和为 0 。
提示:
3 <= nums.length <= 3000
-105 <= nums[i] <= 105
public class ThreeSum {
// threeSum方法返回所有三元组列表
public List<List<Integer>> threeSum(int[] nums) {
// 排序数组
Arrays.sort(nums);
// 结果列表
List<List<Integer>> res = new ArrayList<>();
// 外层循环一个数i
for (int i = 0; i < nums.length - 2; i++) {
// 去重
if (i == 0 || (i > 0 && nums[i] != nums[i-1])) {
// 初始化另外两个数的索引和目标值
int lo = i+1, hi = nums.length-1, sum = 0 - nums[i];
// 双指针查找
while (lo < hi) {
// 匹配就添加结果
if (nums[lo] + nums[hi] == sum) {
res.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
// 去重
while (lo < hi && nums[lo] == nums[lo+1]) lo++;
while (lo < hi && nums[hi] == nums[hi-1]) hi--;
// 更新指针
lo++;
hi--;
} else if (nums[lo] + nums[hi] < sum) {
// 两数和小了,右指针左移
lo++;
} else {
// 两数和大了,左指针右移
hi--;
}
}
}
}
return res;
}
}
Powered by Waline v3.2.0