DFS
什么时候使用 used 数组，什么时候使用 begin 变量
排列问题，讲究顺序（即 [2, 2, 3] 与 [2, 3, 2] 视为不同列表时），需要记录哪些数字已经使用过，此时用 used 数组；
- 排列去除重复:
i>0 && cand[i]==cand[i-1] && !used[i-1]
组合问题，不讲究顺序（即 [2, 2, 3] 与 [2, 3, 2] 视为相同列表时），需要按照某种顺序搜索，此时使用 begin 变量。
- 组合去除重复:
i>begin && cand[i] == cand[i-1]
参考模板：
private void dfs(int[] nums, int n, int index, List<Integer> ans, List<List<Integer>> ret) {if(index == n) {ret.add(new ArrayList<>(ans)); //值传递转拷贝}for(int i=index; i<n; i++) {if(i>index && nums[i]==nums[i-1]) { //去重continue;}ans.add(nums[i]);dfs(nums,n,i+1,ans,ret);ans.remove(ans.size()-1); //回溯}}
HashSet去重
HashSet<List<Integer>> hs = new HashSet<>();dfs() {if(...){hs.add(new ArrayList<>(ans));}}Solution() {List<List<Integer>> ret;for(List<Integer> L : hs) {ret.add(L);}}
int 反转
普通：
public class Solution {public int reverseBits(int n) {int rev = 0;for (int i = 0; i < 32 && n != 0; ++i) {rev |= (n & 1) << (31 - i);n >>>= 1;}return rev;}}
进阶：
n = (n<<16) | (n>>>16);n = ((n&0x00ff00ff)<<8) | ((n&0xff00ff00)>>>8);n = ((n&0x0f0f0f0f)<<4) | ((n&0xf0f0f0f0)>>>4);n = ((n&0x33333333)<<2) | ((n&0xcccccccc)>>>2);n = ((n&0x55555555)<<1) | ((n&0xaaaaaaaa)>>>1);return n;
1的个数
primary:
public int hammingWeight(int n) {int ret = 0;while (n!=0) {if((n&1)==1) ret++;n=n>>>1;}return ret;}
medium:
public int hammingWeight(int n) {int ret = 0;while(n!=0) {ret++;n = n&(n-1); //末位置0}return ret;}
high:
public int hammingWeight(int n) {n = ((n>>>1) & 0x55555555) + (n & 0x55555555);n = ((n>>>2) & 0x33333333) + (n & 0x33333333);n = ((n>>>4) & 0x0f0f0f0f) + (n & 0x0f0f0f0f);n = ((n>>>8) & 0x00ff00ff) + (n & 0x00ff00ff);n = ((n>>>16) & 0x0000ffff) + (n & 0x0000ffff);return n;}
回文类
暴力：
private boolean isPalind(char[] charArray,int left,int right) {while(left < right) {if(charArray[left] != charArray[right]) {return false;}left++;right--;}return true;}
DP：
boolean[][] dp = new boolean[n][n];for(int right=0; right<n; right++) {for(int left=0; left<=right; left++) { //left==right 标记自身//记不住的写法: dp[left][right] = charArray[left]==charArray[right] && (right-left<=2 || dp[left+1][right-1]));//好理解的写法:if(charArray[left] != charArray[right]) {dp[left][right] = false;} else {if(right-left < 3) {dp[left][right] = true;} else {dp[left][right] = dp[left+1][right-1];}}}}
中心扩散：
单调栈
42.接雨水
Deque<Integer> spool = new ArrayDeque<>();for(int i = 0; i < n; i++) {while(!spool.isEmpty() && height[i]>height[spool.peekLast()]) {int cur = spool.pollLast();if(spool.isEmpty()) break;int left = spool.peekLast();int curWidth = i - left - 1;int curHeight = Math.min(height[i],height[left]) - height[cur];ret += curWidth * curHeight;}spool.addLast(i);}
删除有序数组重复元素类
80.删除有序数组的重复项Ⅱ
26，27同理
模板, 最多保留k个重复。
class Solution {public int removeDuplicates(int[] nums) {return process(nums, 2);}int process(int[] nums, int k) {int u = 0;for (int x : nums) {if (u < k || nums[u - k] != x) nums[u++] = x;}return u;}}
最大数
179.最大数
观察知应先比较第一位数，再比较最后一位数，从大到小排，但有点懵怎么排，感觉做起来会比较复杂
看题解，直接暴力拼接字符串比对大小…
学习了一下sort函数怎么用
class Solution {public String largestNumber(int[] nums) {String[] nums2str = new String[nums.length];String ret;for (int i = 0; i < nums.length; i++) {nums2str[i] = Integer.toString(nums[i]); //先全转为String}Arrays.sort(nums2str,(s1,s2)->(s2+s1).compareTo(s1+s2)); //比较s2+s1 < s1+s2if("0".equals(nums2str[0])) {return "0";}return String.join("",nums2str); //依次拼接}}
字典树
208.实现Trie(前缀树)
字典树模板，以下代码的search 和 startsWith其实可以提取一个函数出来。
class Trie {
private Trie[] children;
private boolean isEnd;
/** Initialize your data structure here. */
public Trie() {
children = new Trie[26];
isEnd = false;
}
/** Inserts a word into the trie. */
public void insert(String word) {
Trie node = this;
for(int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
int index = ch - 'a';
if(node.children[index] == null) {
node.children[index] = new Trie();
}
node = node.children[index];
}
node.isEnd = true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
Trie node = this;
for(int i = 0; i <word.length(); i++) {
char ch = word.charAt(i);
int index = ch - 'a';
if(node.children[index] == null) {
return false;
}
node = node.children[index];
}
return node!=null && node.isEnd;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
Trie node = this;
for (int i = 0; i < prefix.length(); i++) {
char ch = prefix.charAt(i);
int index = ch - 'a';
if(node.children[index] == null) {
return false;
}
node = node.children[index];
}
return true;
}
}
打家劫舍-dp
198，213 打家劫舍
很明显的dp题，状态转移方程考虑抢不抢第n间
213因为绕成圈所以不能同时抢第一间和最后一间，应分为两个范围进行计算
198,打家劫舍Ⅰ:
class Solution {
public int rob(int[] nums) {
int n = nums.length;
if(n==0) return 0;
if(n==1) return nums[0];
int pre = 0,cur = 0, tmp;
for (int i = 0; i < n; i++) {
tmp = cur;
cur = Math.max(pre+nums[i], tmp);
pre = tmp;
}
return cur;
}
}
213,打家劫舍Ⅱ
class Solution {
public int rob(int[] nums) {
int n = nums.length;
if(n==0) return 0;
if(n==1) return nums[0];
return Math.max(robRange(Arrays.copyOfRange(nums, 0, nums.length - 1)),
robRange(Arrays.copyOfRange(nums, 1, nums.length)));
}
private int robRange(int[] nums) {
int pre = 0,cur = 0,tmp;
for(int n : nums) {
tmp = cur;
cur = Math.max(pre+n, cur);
pre = tmp;
}
return cur;
}
}
扰乱字符串-dp
87.扰乱字符串
想到了深搜或dp去做，但是一开始拘泥于字符串的形式
看题解恍然只需要划分区间做dp即可。
判断的条件有二： 1. 对应长度必须相等；2. 对应划分字符串中的字母出现频率也是相等的
class Solution {
public boolean isScramble(String s1, String s2) {
if(s1.equals(s2)) return true;
int n = s1.length();
if(n != s2.length()) return false;
char[] c1 = s1.toCharArray();
char[] c2 = s2.toCharArray();
boolean[][][] dp = new boolean[n][n][n+1]; //dp[s1开始位置][s2开始位置][串长度]
//初始化单个字符情况dp[i][j][1]
for(int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dp[i][j][1] = c1[i] == c2[j];
//c1[i] == c2[j] ? dp[i][j][1] = true : dp[i][j][1] = false;
}
}
//len10 i0 k3 -> 0-2 3 3-9 7
//len10 j7 k3 -> 0-6 7 7-9 3
//len7 i4 k4 -> 3-6 4 7-9 3
//len7 j0 k4 -> 0-2 3 3-6 4
for(int len = 2; len <= n; len++) {
for(int i = 0; i <= n-len; i++) {
for(int j = 0; j <= n-len; j++) {
for(int k = 1; k < len; k++) { //k为试探划分位置
boolean stay = dp[i][j][k] && dp[i+k][j+k][len-k]; //两边保持位置不变,比较 ac 与 bd
boolean swap = dp[i][j+len-k][k] && dp[i+k][j][len-k]; //左右交换位置,比较 ad 与 bc
if(swap || stay) {
dp[i][j][len] = true;
break;
}
}
}
}
}
return dp[0][0][n];
}
}
实现strStr()-KMP
28.实现strStr()
talk is cheap , show the code.
class Solution {
public int strStr(String haystack, String needle) {
if(needle.isEmpty()) return 0;
int n = haystack.length() , m = needle.length();
haystack = " " + haystack; //预处理，开头加空格防止j从-1开始处理
needle = " " + needle;
char[] hs = haystack.toCharArray();
char[] nd = needle.toCharArray();
int[] next = new int[m+1]; //开始构造next数组,next数组记录了匹配串中匹配的前缀后缀位置※
for(int i = 2,j=0; i <= m; i++) { //构造从I=2开始
while (j>0 && nd[i]!=nd[j+1]) j = next[j]; //匹配不成功则j跳转到next[j]
if(nd[i] == nd[j+1]) j++; //匹配成功记录j++
next[i] = j;
}
//开始匹配
for(int i=1,j=0; i<=n; i++) {
while(j>0 && hs[i]!=nd[j+1]) j = next[j]; //匹配不成功跳转next[j]
if(hs[i] == nd[j+1]) j++; //匹配成功继续走
if(j==m) return i-m; //匹配完成
}
return -1;
}
}
解码方法-dp
91.解码方法
dp题，当出现子序列选择的时候就可以考虑使用dp解，
这题的状态转移方程还是很明显的。
仅考虑一位时，只需要不为0即可，dp[i] = dp[i-1]
考虑两位时，计数不小于10，不大于26即可。dp[i] = dp[i-2]
一位两位都满足时，dp[i] = dp[i-1] + dp[i-2]
class Solution {
public int numDecodings(String s) {
if(s.charAt(0)=='0') return 0;
int n = s.length();
int[] dp = new int[n+1];
dp[0] = 1;
for (int i = 1; i <= n; i++) {
if(s.charAt(i-1) != '0') {
dp[i] += dp[i-1]; //只检验一位的情况
}
if(i>1 && s.charAt(i-2) != '0' && ((s.charAt(i-2) - '0')*10 + (s.charAt(i-1)-'0')) <= 26) {
dp[i] += dp[i-2]; //检验两位的情况
}
}
return dp[n];
}
}
进阶的，学习一下使用滚动数组来做空间优化。
class Solution {
public int numDecodings(String s) {
if(s.charAt(0)=='0') return 0;
int n = s.length();
//int[] dp = new int[n+1];
int[] dp = new int [3]; //dp[i]只跟dp[i-1]和dp[i-2]相关
dp[0] = 1;
for (int i = 1; i <= n; i++) {
dp[i%3] = 0;
if(s.charAt(i-1) != '0') {
dp[i%3] = dp[(i-1)%3];
}
if(i>1 && s.charAt(i-2) != '0' && ((s.charAt(i-2) - '0')*10 + (s.charAt(i-1)-'0'))<=26) {
dp[i%3] += dp[(i-2)%3];
}
}
return dp[n];
}
}
363.矩形区域不超过K的最大数值和-二维前缀和
矩形区域，数值和，毫无疑问先求个二维前缀和
问题是接下来该怎么查找。
首先肯定是暴力枚举，i,j定位矩形左上角，pq定位右下角
- 时间复杂度：预处理前缀和数组复杂度为 O(m n)O(m∗n)，查找答案的复杂度为 O(m^2 n^2)。整体复杂度为 O(m^2 * n^2)。
- 空间复杂度：O(m * n)O(m∗n)
幸运的是，这题居然暴力能过
class Solution {
public int maxSumSubmatrix(int[][] matrix, int k) {
int m = matrix.length, n = matrix[0].length;
int[][] sum = new int[m+1][n+1];
for(int i = 1; i <= m; i++) {
for(int j = 1; j<=n; j++) { //预处理算二维前缀和
sum[i][j] = matrix[i-1][j-1] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
}
}
int ret = Integer.MIN_VALUE;
for(int i = 1; i <= m; i++) {
for(int j = 1; j <= n; j++) { //(i,j)左上角
for(int p = i; p<=m; p++) {
for(int q=j; q<=n; q++) { //(p,q)右下角
int cur = sum[p][q] - sum[p][j-1] - sum[i-1][q] + sum[i-1][j-1]; //计算所求
if(cur <= k) {
ret = Math.max(ret, cur);
}
}
}
}
}
return ret;
}
}
进阶的..看不太明白..
【宫水三叶】优化枚举的基本思路 & 将二维抽象成一维 & 最大化「二分」效益 & 空间优化
897.递增顺序搜索树
记录一下O(1)空间的Morris中序遍历解法
Morris基本代码：
public void morris(TreeNode root) {
TreeNode cur=root,pre=null;
while(cur!=null){
pre=cur.left;
if(pre!=null){
while(pre.right!=null&&pre.right!=cur){
pre=pre.right;
}
if(pre.right==null){
pre.right=cur;
cur=cur.left;
continue;
}else{
pre.right=null;
}
}
cur=cur.right;
}
}
本题题解：
class Solution {
public TreeNode increasingBST(TreeNode root) {
TreeNode cur=root,pre=null;
TreeNode dummy=new TreeNode(0),tail=dummy;
while(cur!=null){
pre=cur.left;
if(pre!=null){
while(pre.right!=null&&pre.right!=cur){
pre=pre.right;
}
if(pre.right==null){
pre.right=cur;
cur=cur.left;
continue;
}else{
cur.left=null;
}
}
tail.right=cur;
tail=cur;
cur=cur.right;
}
return dummy.right;
}
}
1011.在D天内送达包裹的能力-二分
二分查找，每天的载重肯定在单个最大包裹重量到所有包裹重量和这个区间内，所以要对这个区间进行二分查找。
class Solution {
public int shipWithinDays(int[] weights, int D) {
int left = Arrays.stream(weights).max().getAsInt(); //单个最大包裹
int right = Arrays.stream(weights).sum(); //所有包裹
while (left < right) {
int mid = (left + right) / 2;
int need = 1,cur = 0; //need表示需要的天数，cur表示当前重量
for(int w : weights) {
if(cur + w > mid) {
++need;
cur = 0;
}
cur += w;
}
if(need > D) {
left = mid + 1; //如果当前负重mid无法如期完成，则加大负载
} else {
right = mid; //反之
}
}
return left;
}
}
633.平方数之和-双指针
用最暴力的做法就是两个数依此枚举到sqrt()，那么优化方法就是枚举一个，另一个数用sqrt(c-a*a)判断是否能满足。
class Solution {
public boolean judgeSquareSum(int c) {
for (long a = 0; a * a <= c; a++) { //防止溢出,使用long
double b = Math.sqrt(c - a * a);
if (b == (int) b) {
return true;
}
}
return false;
}
}
另一种思路就是两个数的区间都在0-sqrt(c)，那就用双指针，如果结果比c大了就左移右指针，比 c小就右移左指针。
时间复杂度和上面的枚举一样是O(√c).
class Solution {
public boolean judgeSquareSum(int c) {
int i = 0;
int j = (int)Math.sqrt(c);
while(i<=j) {
int ret = i*i + j*j;
if(ret == c) {
return true;
} else if(ret < c) {
i++;
} else {
j--;
}
}
return false;
}
}
还有一种解法是依据于数学，学习一下就好，下次我还是想不到哈哈。
费马平方和：奇质数能表示为两个平方数之和的充分必要条件是该质数被 4 除余 1 。
即：当且仅当一个自然数的质因数分解中，满足 4k+3 形式的质数次方数均为偶数时，该自然数才能被表示为两个平方数之和。
因此我们对 c 进行质因数分解，再判断满足 4k+3 形式的质因子的次方数是否均为偶数即可。
public class Solution {
public boolean judgeSquareSum(int c) {
for (int i = 2, cnt = 0; i * i <= c; i++, cnt = 0) {
while (c % i == 0 && ++cnt > 0) c /= i;
if (i % 4 == 3 && cnt % 2 != 0) return false;
}
return c % 4 != 3;
}
}
403.青蛙过河-DP || 记忆化搜索
规律如下：
- 能否跳到下个石头上取决于当前所处石头位置和上次跳跃的距离。
- 因此有状态转移方程：
dp[i][k] = dp[j][k-1] || dp[j][k] || dp[j][k+1] - i表示本次跳跃的落点，j是能从哪个石头起跳，
k = stone[i] - stone[j]上次跳跃的距离
- 因此有状态转移方程：
- 那么可以看出，初始条件dp[0][0]为true，青蛙不用跳就已经站在第0个石头上，
k的距离一定不大于stone[i] - stone[i-1]- 预处理：如果有
stone[i] - stone[i-1] > i，青蛙肯定跳不到第i块石头，也肯定到不了终点。 - 因为每次起跳距离至多增加1，石头编号至少增加1，所以有跳跃m次,
.class Solution { public boolean canCross(int[] stones) { int n = stones.length; boolean[][] dp = new boolean[n][n]; dp[0][0] = true; for (int i = 1; i < n; i++) { //预处理 if(stones[i] - stones[i-1] > i) { return false; } } for (int i = 1; i < n; i++) { for(int j = i-1; j >= 0; j--) { //寻找上次能起跳的位置 int k = stones[i] - stones[j]; if( k > j+1 ) { break; } dp[i][k] = dp[j][k-1] || dp[j][k] || dp[j][k+1]; if( i==n-1 && dp[i][k]) { return true; } } } return false; } }
- 预处理：如果有
137.只出现一次的数字-二进制
以前做过的题是其他数字出现两次，那就一遍全部异或就剩下了单次出现的数字，但是这题显然..不会这么简单，在想了半天的异或没想法后，先暴力试了一下，还是过了的
class Solution {
public int singleNumber(int[] nums) {
HashMap<Integer,Integer> map = new HashMap<Integer, Integer>();
for(int num : nums) {
map.put(num,map.getOrDefault(num,0)+1);
}
for(Map.Entry<Integer, Integer> entry : map.entrySet()) {
if(entry.getValue() == 1) {
return entry.getKey();
}
}
return -1;
}
}
然后看看题解学习一下大佬的做法和思路，
第一种方法是依此确定每一个二进制位，非答案的每一个元素都出现3次，那么每个二进制位的和模3即为答案的该位值
答案的第 ii 个二进制位就是数组中所有元素的第 ii 个二进制位之和除以 33 的余数。
不过因为如此来确定每一位的，那就需要保证32都有效，因此需要注意使用的语言对「有符号整数类型」和「无符号整数类型」有没有区分，如果没有区分的语言需要对最高位进行特殊判断。
时间复杂度: 
,其中logC = 32
空间复杂度:
class Solution {
public int singleNumber(int[] nums) {
int ans = 0;
for (int i = 0; i < 32; ++i) {
int total = 0;
for (int num: nums) {
total += ((num >> i) & 1);
}
if (total % 3 != 0) {
ans |= (1 << i);
}
}
return ans;
}
}
第二种方法是数字电路设计..
膜拜大佬orz，这都咋想到的..
时间复杂度：
空间复杂度：
class Solution {
public int singleNumber(int[] nums) {
int a = 0, b = 0;
for (int num : nums) {
int aNext = (~a & b & num) | (a & ~b & ~num), bNext = ~a & (b ^ num);
a = aNext;
b = bNext;
}
return b;
}
}
若有收获，就点个赞吧
0 人点赞
