dfs dfs的注意点： 回复现场，也就是进入递归之前和退出递归的时候，状态是一样的 有明确的结束的标记，也就是不能产生死循环  import java.util.*; public class Solution { public ArrayList<ArrayList<Integer>> pathSum (TreeNode root, int sum) { ArrayList<ArrayList<Integer>> ret = new ArrayList<>(); if(root != null) dfs(root,sum,ret,...

动态规划 区间dp 设f[i][j]为[i,j]能够形成回文串，如果s[i] == s[j] && (i + 1 > j - 1 || f[i + 1][j - 1])，那么即为回文串 i + 1 > j - 1：形如aa这样的形式 f[i + 1][j - 1]：更一般的形式 abba  import java.util.*; /* 区间dp */ public class Solution { public int getLongestPalindrome(String A, int n) { boolean f[][] = new boolean[n + 10...

遍历 倒序遍历，从后往前遍历即可 import java.util.*; public class Solution { /** * 反转字符串 * @param str string字符串 * @return string字符串 */ public String solve (String str) { int n = str.length(); char strs[] = new char[n]; for(int i = n - 1;i >= 0;i--){ strs[i] = str.charAt(n - 1 - i); } return new String(strs); } }

dfs遍历 前序遍历：输出当前节点 递归处理左子节点 递归处理右子节点 中序遍历：递归处理左子节点 输出当前节点 递归处理右子节点 后序遍历：递归处理左子节点 递归处理右子节点 输出当前节点  import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */ public class Solution { int idx = 0; public int[][] threeOrders (TreeNode root) { i...

快速排序 快速排序在笔试中应该是比较常见的了 下面附上了快排比较简单的实现代码，也可以用 Arrays.sort(a); 调用 注意：在递归处理左右两边时候，注意选取的分割点，搞不好会死循环的。 import java.util.*; public class Solution { public int findKth(int[] a, int n, int k) { //Arrays.sort(a); quick_sort(a,0,n - 1); return a[n - k]; } public void quick_sort(int arr[],int l,int r){ if(l &g...

前缀和 考虑一般情况： 设前缀和数组为：s 以下分析过程下标均为1 ~ n，但是代码中是0 ~ n-1，前缀和一般来说以1 ~ n 进行分析比较简单。 取1~i的连续子数组的最大和res：那么res = s[i] - s[j] 或者 res = s[i] j的取值范围为[1,i - 1]; 所以我们维护一个变量记录最小值即可。  public class Solution { public int FindGreatestSumOfSubArray(int[] arr) { int n = arr.length; int mi = 100000000; int res = -100000000...

从前往后进行遍历 需要开辟空间 import java.util.*; public class Solution { public void merge(int A[], int m, int B[], int n) { int tmp[] = new int[n + m]; int i = 0,j = 0; int idx = 0; while(i < m && j < n){ if(A[i] <= B[j]){ tmp[idx++] = A[i++]; }else { tmp[idx++] = B[j++]; } } while(i < m){tm...

排序，输出k个数即可 import java.util.*; public class Solution { public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) { Arrays.sort(input); ArrayList<Integer> ret = new ArrayList<>(); int cnt = 0; int idx = 0; while(cnt < k){ ret.add(input[idx++]); cnt++; } return ret; ...

双指针+模拟 思路：开一个数组，记录每个值出现的次数，然后进行双指针，当下标i++的时候，只有st[arr[i]]的个数会发生改变，所以用另一个下标j进行去除即可。  import java.util.*; public class Solution { int st[] = new int[100010]; public int maxLength (int[] arr) { int res = 0; int n = arr.length; for(int i = 0,j = 0;i < n;i++){ st[arr[i]]++; while(j <= i && ...

动态规划 这一个基本的动态规划的题，我们需要对问题进行拆分 假设我们处于x层，在合法的情况下，我们考虑，那些可能是结果集。 可以发现，答案是类似：  aaaaa...aaaax 路径 bbbbb...aaaax  似乎很不好考虑（最后都是在x层），我们不妨考虑最后一步，也就是如何到x的，在合法的情况下，到x的途径有两种，即x-1而来，x-2而来，于是可以得出：f[n] = f[n - 1] + f[n - 2]; 于是得出了出版的答案：可以ac public class Solution { int f[] = new int[41]; public int jumpFloor(int tar...

队列  import java.util.*; public class Solution { //数组模拟队列 TreeNode q[] = new TreeNode[1510]; public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) { int hh = 0,tt = 0; q[0] = root; ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>(); A...

二分  import java.util.*; public class Solution { public int search (int[] nums, int target) { int n = nums.length; int l = 0,r = n - 1; while(l < r){ int mid = l + r >> 1; if(nums[mid] >= target)r = mid; else l = mid + 1; } if(n == 0 || nums[l] != target)l = -1; return l; } }