收录一些常见的算法题型

常用算法

字符串

1. s.trim():去掉字符串首尾的空格
2. s.split("\\s+"):按照空格对字符串分割

树

前中后序遍历

 /*** 统一一下* @param root* @return*///前序public static List<Integer> preOrder(TreeNode root){List<Integer> list = new ArrayList();Stack<TreeNode> stack = new Stack();TreeNode cur = root;while(cur!=null || !stack.isEmpty()){//一直往左压入栈while(cur!=null){list.add(cur.val);stack.push(cur);cur = cur.left;}cur = stack.pop();cur = cur.right;}return list;}//中序public List<Integer> inorderTraversal(TreeNode root) {if(root == null){return new ArrayList();}List<Integer> list = new ArrayList();Stack<TreeNode> stack = new Stack();TreeNode cur = root;while(cur != null || !stack.isEmpty()){while(cur!=null){stack.push(cur);cur = cur.left;}cur = stack.pop();list.add(cur.val);cur = cur.right;}return list;}//后序遍历，非递归public static List<Integer> postOrder(TreeNode root){Stack<TreeNode> stack = new Stack<>();List<Integer> list = new ArrayList<>();TreeNode cur = root;TreeNode p = null;//用来记录上一节点while(!stack.isEmpty() || cur != null){while(cur != null){stack.push(cur);cur = cur.left;}cur = stack.peek();
//            后序遍历的过程中在遍历完左子树跟右子树cur都会回到根结点。所以当前不管是从左子树还是右子树回到根结点都不应该再操作了，应该退回上层。
//            如果是从右边再返回根结点，应该回到上层。//主要就是判断出来的是不是右子树，是的话就可以把根节点=加入到list了if(cur.right == null || cur.right == p){list.add(cur.val);stack.pop();p = cur;cur = null;}else{cur = cur.right;}}return list;
}

回溯

• 寻找所有的组合，给的candidates中没有重复的元素，candidates中的元素可以重复取

题目链接：https://leetcode.cn/problems/combination-sum/submissions/

class Solution {private List<List<Integer>> ans;// 普通的回溯+关键的去重使用startIndexpublic List<List<Integer>> combinationSum(int[] candidates, int target) {ans = new ArrayList<>();backtracking(0,candidates,target,0,new ArrayList<>());return ans;}public void backtracking(int startIndex,int[] candidates,int target,int sum,List<Integer> path){if(sum==target){ans.add(new ArrayList<>(path));}if(sum>target){return;}for(int i=startIndex;i<candidates.length;i++){path.add(candidates[i]);backtracking(i,candidates,target,sum+candidates[i],path);path.remove(path.size()-1);}}
}

• 组合问题：candidtes无序，candidates中元素有重复的，要求计算组合数，且candidates中同一个数只能取一次

class Solution {private List<List<Integer>> ans;public List<List<Integer>> combinationSum2(int[] candidates, int target) {ans = new ArrayList<>();Arrays.sort(candidates);backtracking(0,candidates,target,0,new ArrayList<>());return ans;}public void backtracking(int startIndex,int[] candidates,int target,int sum,List<Integer> path){if(sum==target){ans.add(new ArrayList<>(path));}if(sum>target){return;}for(int i=startIndex;i<candidates.length;i++){// 这里是i>startIndex表示每次遍历时，如果跟上一次相同就不用再次遍历if(i>startIndex&&candidates[i-1]==candidates[i]){continue;}path.add(candidates[i]);backtracking(i+1,candidates,target,sum+candidates[i],path);path.remove(path.size()-1);}}
}

二分

• 注意要是升序或者降序，时间复杂度：O(log n)
• 正常的二分写法

class Solution {
public:int search(vector<int>& nums, int target) {int left = 0;int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]while (left <= right) { // 当left==right，区间[left, right]依然有效，所以用 <=int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2if (nums[middle] > target) {right = middle - 1; // target 在左区间，所以[left, middle - 1]} else if (nums[middle] < target) {left = middle + 1; // target 在右区间，所以[middle + 1, right]} else { // nums[middle] == targetreturn middle; // 数组中找到目标值，直接返回下标}}// 未找到目标值return -1;}
};

• 变形写法，寻找端点，题目链接：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/

class Solution {public int[] searchRange(int[] nums, int target) {// 因为要取得O(log n)的时间复杂度，因此考虑使用二分法return new int[] {findleft(nums,target),findright(nums,target)};}// 寻找小于等于target的最大的数的下标public int findleft(int[] nums,int target){int l=0,r=nums.length-1;while(l<=r){int mid = (l+r)/2;if(nums[mid]>=target){r = mid-1;}else{l = mid+1;}}if(l>=nums.length||nums[l]!=target){return -1;}return l;}// 寻找大于等于target的最大的数的下标public int findright(int[] nums,int target){int l=0,r=nums.length-1;while(l<=r){int mid = (l+r)/2;if(nums[mid]<=target){l = mid+1;}else{r = mid-1;}}if(r<0||nums[r]!=target){return -1;}return r;}
}

• 变形写法，部分有序：https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/

排序算法

选择排序

思路：每一轮选取未排定的部分中最小的部分交换到未排定部分的最开头，经过若干个步骤，就能排定整个数组。即：先选出最小的，再选出第 2 小的，以此类推。

import java.util.Arrays;public class Solution {// 选择排序：每一轮选择最小元素交换到未排定部分的开头public int[] sortArray(int[] nums) {int len = nums.length;// 循环不变量：[0, i) 有序，且该区间里所有元素就是最终排定的样子for (int i = 0; i < len - 1; i++) {// 选择区间 [i, len - 1] 里最小的元素的索引，交换到下标 iint minIndex = i;for (int j = i + 1; j < len; j++) {if (nums[j] < nums[minIndex]) {minIndex = j;}}swap(nums, i, minIndex);}return nums;}private void swap(int[] nums, int index1, int index2) {int temp = nums[index1];nums[index1] = nums[index2];nums[index2] = temp;}public static void main(String[] args) {int[] nums = {5, 2, 3, 1};Solution solution = new Solution();int[] res = solution.sortArray(nums);System.out.println(Arrays.toString(res));}
}

总结：

• 算法思想 1：贪心算法：每一次决策只看当前，当前最优，则全局最优。注意：这种思想不是任何时候都适用。

• 算法思想 2：减治思想：外层循环每一次都能排定一个元素，问题的规模逐渐减少，直到全部解决，即「大而化小，小而化了」。运用「减治思想」很典型的算法就是大名鼎鼎的「二分查找」。

• 优点：交换次数最少。

• 时间复杂度：O(N^2)，这里 N 是数组的长度；
• 空间复杂度：O(1)，使用到常数个临时变量。

插入排序

思路：每次将一个数字插入一个有序的数组里，成为一个长度更长的有序数组，有限次操作以后，数组整体有序。

public class Solution {// 插入排序：稳定排序，在接近有序的情况下，表现优异public int[] sortArray(int[] nums) {int len = nums.length;// 循环不变量：将 nums[i] 插入到区间 [0, i) 使之成为有序数组for (int i = 1; i < len; i++) {// 先暂存这个元素，然后之前元素逐个后移，留出空位int temp = nums[i];int j = i;// 注意边界 j > 0while (j > 0 && nums[j - 1] > temp) {nums[j] = nums[j - 1];j--;}nums[j] = temp;}return nums;}
}

• 优化：「将一个数字插入一个有序的数组」这一步，可以不使用逐步交换，使用先赋值给「临时变量」，然后「适当的元素」后移，空出一个位置，最后把「临时变量」赋值给这个空位的策略（就是上面那张图的意思）。编码的时候如果不小心，可能会把数组的值修改，建议多调试；

• 特点：「插入排序」可以提前终止内层循环（体现在 nums[j - 1] > temp 不满足时），在数组「几乎有序」的前提下，「插入排序」的时间复杂度可以达到 O(N)O(N)O(N)；

• 由于「插入排序」在「几乎有序」的数组上表现良好，特别地，在「短数组」上的表现也很好。因为「短数组」的特点是：每个元素离它最终排定的位置都不会太远。为此，在小区间内执行排序任务的时候，可以转向使用「插入排序」。

复杂度分析：

• 时间复杂度：O(N^2),这里 N 是数组的长度；
• 空间复杂度：O(1)，使用到常数个临时变量。

归并排序

思路：借助额外空间，合并两个有序数组，得到更长的有序数组。

class Solution {//归并排序public int[] sortArray(int[] nums) {return mergeSort(nums, 0, nums.length-1);  }public int[] mergeSort(int[] nums, int left, int right){//递归退出条件//如果左指针大于右指针，就退出循环//经过左右拆分，数组元素形成单个元素的树if(left >=right){return nums;}//数组中的中位数int mid = (right+left)/2;//数组左拆分mergeSort(nums, left, mid);//数组右拆分mergeSort(nums, mid+1, right);//数组合并，将单个元素进行合并return merge(nums, left, mid, right);}public int[] merge(int[] nums, int left, int mid, int right){//定义一个临时数组，存储排序好的元素int[] temp = new int[right-left+1];//左排序的元素数组的左指针int i = left;//右排序的元素数组的左指针int j = mid+1;//定义一个指向临时数组的左指针int t = 0;//循环判断条件//左数组到mid，右数组到right//左右数组都有元素的时候，进行比较while(i<=mid&&j<=right){//取左右数组中较小的元素，填入临时数组中//并将较小元素所在数组的左指针和临时数组的左指针都一起右移if(nums[i]<=nums[j]){temp[t++] = nums[i++];}else{temp[t++] = nums[j++];}}//当左右数组其中一个数组没有元素的时候//如果左数组中还有剩余元素，就将剩余元素全部加入到临时数组中while(i<=mid){temp[t++]=nums[i++];}//如果有数组中还有元素，就将剩余元素全部加入到临时数组中while(j<=right){temp[t++] = nums[j++];}//将临时数组的元素复制到原数组中去for(int k = 0; k<temp.length;k++){//特别注意这便nums数组起始位置要从 k+left开始 //原因在加右数组的时候，起始位置要加left//这里不理解，直接把它记住。nums[left+k]=temp[k];}//返回原数组return nums;}
}

「归并排序」比「快速排序」好的一点是，它借助了额外空间，可以实现「稳定排序」，Java 里对于「对象数组」的排序任务，就是使用归并排序（的升级版 TimSort，在这里就不多做介绍）。

复杂度分析：

• 时间复杂度：O(Nlog⁡N)，这里 N 是数组的长度；

• 空间复杂度：O(N)，辅助数组与输入数组规模相当。

快速排序

基本思路：快速排序每一次都排定一个元素（这个元素呆在了它最终应该呆的位置），然后递归地去排它左边的部分和右边的部分，依次进行下去，直到数组有序；

import java.util.Random;public class Solution {// 快速排序 1：基本快速排序/*** 列表大小等于或小于该大小，将优先于 quickSort 使用插入排序*/private static final int INSERTION_SORT_THRESHOLD = 7;private static final Random RANDOM = new Random();public int[] sortArray(int[] nums) {int len = nums.length;quickSort(nums, 0, len - 1);return nums;}private void quickSort(int[] nums, int left, int right) {// 小区间使用插入排序if (right - left <= INSERTION_SORT_THRESHOLD) {insertionSort(nums, left, right);return;}int pIndex = partition(nums, left, right);quickSort(nums, left, pIndex - 1);quickSort(nums, pIndex + 1, right);}/*** 对数组 nums 的子区间 [left, right] 使用插入排序** @param nums  给定数组* @param left  左边界，能取到* @param right 右边界，能取到*/private void insertionSort(int[] nums, int left, int right) {for (int i = left + 1; i <= right; i++) {int temp = nums[i];int j = i;while (j > left && nums[j - 1] > temp) {nums[j] = nums[j - 1];j--;}nums[j] = temp;}}// 用来确定pivot的位置private int partition(int[] nums, int left, int right) {int randomIndex = RANDOM.nextInt(right - left + 1) + left;// 交换到最左边swap(nums, left, randomIndex);// 基准值int pivot = nums[left];int lt = left;// 循环不变量：// all in [left + 1, lt] < pivot// all in [lt + 1, i) >= pivotfor (int i = left + 1; i <= right; i++) {if (nums[i] < pivot) {lt++;swap(nums, i, lt);}}swap(nums, left, lt);return lt;}private void swap(int[] nums, int index1, int index2) {int temp = nums[index1];nums[index1] = nums[index2];nums[index2] = temp;}
}

复杂度分析：

• 时间复杂度：O(Nlog⁡N)，这里 N 是数组的长度；
• 空间复杂度：O(log⁡N)，这里占用的空间主要来自递归函数的栈空间。

冒泡排序

基本思想：

1. 从序列的第一个元素开始，对相邻的两个元素进行比较，如果它们的顺序错误就交换它们的位置，即将较大的元素往后移动，直到遍历到序列的最后一个元素。
2. 对剩下的元素重复上述步骤，直到整个序列都已经有序。

public class Solution {public int[] sortArray(int[] nums) {int len = nums.length;for (int i = len - 1; i >= 0; i--) {// 先默认数组是有序的，只要发生一次交换，就必须进行下一轮比较，// 如果在内层循环中，都没有执行一次交换操作，说明此时数组已经是升序数组boolean sorted = true;for (int j = 0; j < i; j++) {if (nums[j] > nums[j + 1]) {swap(nums, j, j + 1);sorted = false;}}if (sorted) {break;}}return nums;}private void swap(int[] nums, int index1, int index2) {int temp = nums[index1];nums[index1] = nums[index2];nums[index2] = temp;}
}

复杂度分析：

• 时间复杂度：O(N^2)，这里 N 是数组的长度；
• 空间复杂度：O(1)，使用到常数个临时变量。

并查集

可以按照多叉树的思想来考虑，我们使用数组的方式来构造一颗两层的多叉树，一般可以套用如下模板：

    public static void init(){for(int i=0;i<father.length;i++){father[i] = i;}}// 连接两条边public static void union(int a,int b){father[find(a)]=find(b);}// 寻找a的根public static int find(int a){return a==father[a]?a:(father[a]=find(father[a]));}

可以参考华为机试题：https://mp.weixin.qq.com/s/BlpsEoitip7ugQYgezCd3g