算法算法突破计划
FANSEA算法突破计划
动态规划
递归 + 记忆化 => 减少计算 核心问题：动态转移方程！
动态规划由大问题拆成子问题，子问题推出大问题（这个就涉及到动态转移方程），这个步骤利用到了原先计算的结果，减少了计算量。
而在这个子问题推出大问题的步骤中其实计算的dp矩阵的结果不一定是期望的值，也可能是这个步骤中间不断刷新的变量，所以千万不要在想动态转移方程的的时候陷入“我一定要以题目的结果作为dp的最终值”的问题中！
动态规划（基础版） - 学习计划 - 力扣（LeetCode）全球极客挚爱的技术成长平台
菜鸟
斐波那契数列
斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
1
2
| F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
|
给定 n ，请计算 F(n) 。
1
2
3
4
5
6
7
8
9
10
11
12
| public int fibPlus(int n) {
int[] fib = new int[n+1];
fib[0] = 0;
if(n>0){
fib[1] = 1;
}
for (int i = 2; i <= n; i++) {
fib[i] = fib[i-1] + fib[i-2];
}
return fib[n];
}
|
走方格
在for循环中不断执行动态转移函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| public class FindWay {
static int[][] arr = new int [30][30];
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
if (i == 1 && j == 1){
arr[i][j] = 1;
continue;
}
if ((i&2)==0 && (j&2)==0){
continue;
}
arr[i][j] = arr[i-1][j] + arr[i][j-1];
}
}
System.out.println(arr[n][m]);
return;
}
}
public class FindWay {
static int[][] arr = new int [30][30];
static int n;
static int m;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
m = scanner.nextInt();
System.out.println(dg(1, 1));
}
private static int dg(int i,int j) {
if (i < 0 || i > n || j < 0 || j > m) {
return 0;
}
if (i % 2 == 0 && j % 2 == 0) {
return 0;
}
if (i == n && j == m) {
return 1;
}
return dg(i,j+1) + dg(i+1,j);
}
}
|
01背包问题❤
背包问题主要是指一个给定容量的背包若干，具有一定价值和空间的物品,如何选择物品放入背包使物品的价值最大。其中又分01背包（01背包：每个物品只有一件可用）和完全背包(完全背包指的是:每种物品都有无限件可用)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| public class Knapsack {
public static void main(String[] args) {
int[] weight = {1, 3, 4};
int[] value = {15, 20, 30};
int capacity = 4;
int res = knapsack(weight, value, capacity);
System.out.println(res);
}
private static int knapsack(int[] weight, int[] value, int capacity) {
int[][] dp =new int[weight.length+1][capacity+1];
for (int i = 1; i <= weight.length; i++) {
for (int j = 1; j <= capacity; j++)
if (j < weight[i-1]){
dp[i][j] = dp[i-1][j];
}else {
dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-weight[i-1]]+value[i-1]);
}
}
return dp[weight.length][capacity];
}
}
|
零钱兑换
LCR 103. 零钱兑换 - 力扣（LeetCode）
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
你可以认为每种硬币的数量是无限的。
示例 1：
1
2
3
| 输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
|
dp[i]代表凑成i数值的最小数量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public int coinChange(int[] coins, int amount) {
int max = amount + 1;
int[] dp = new int[amount + 1];
Arrays.fill(dp, max);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.length; j++) {
if (coins[j] <= i) {
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
|
中等
打劫家舍
198. 打家劫舍 - 力扣（LeetCode）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public int rob(int[] nums) {
if (nums.length == 1) {
return nums[0];
}
if(nums.length == 2) {
return Math.max(nums[0], nums[1]);
}
int[] dp = new int[nums.length];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < nums.length; i++) {
dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]);
}
return dp[nums.length-1];
}
|
最长回文字符串
5. 最长回文子串 - 力扣（LeetCode）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| public String longestPalindrome(String s) {
int len = s.length();
if (len < 2) {
return s;
}
int maxLen = 1;
int begin = 0;
boolean[][] dp = new boolean[len][len];
for (int i = 0; i < len; i++) {
dp[i][i] = true;
}
char[] charArray = s.toCharArray();
for (int L = 2; L <= len; L++) {
for (int i = 0; i < len; i++) {
int j = L + i - 1;
if (j >= len) {
break;
}
if(charArray[i] != charArray[j]){
dp[i][j] = false;
} else{
if(L <= 3){
dp[i][j] = true;
}
else{
dp[i][j] = dp[i+1][j-1];
}
}
if (dp[i][j] && L > maxLen) {
maxLen = L;
begin = i;
}
}
}
return s.substring(begin, begin + maxLen);
}
|
单词拆分☆
139. 单词拆分 - 力扣（LeetCode）
1
2
3
4
5
6
7
8
9
10
11
12
13
| public boolean wordBreak(String s, List<String> wordDict) {
boolean[] dp = new boolean[s.length()+1];
dp[0] = true;
for(int i = 1; i <= s.length(); i++) {
for(int j=0;j<i;j++) {
if(dp[j] && wordDict.contains(s.substring(j,i)))
dp[i] = true;
}
}
return dp[s.length()];
}
|
最长递增子列☆
最长递增子序列
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列
示例 1：
1
2
3
| 输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4
|
动态转移方程：
dp[i]代表以i为结尾的最大递增子序列的长度
$$
dp[i] = Max(dp[j]+1,dp[i])
$$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public int lengthOfLIS(int[] nums) {
int l = nums.length;
int[] dp = new int[l];
Arrays.fill(dp,1);
for(int i=1;i<l;i++){
for(int j=0;j<i;j++){
if(nums[j]<nums[i]){
dp[i] = Math.max(dp[j]+1,dp[i]);
}
}
}
return Arrays.stream(dp).max().getAsInt();
}
}
|
真题
京东笔试，难度中等（0831秋招笔试真题解析） (qq.com)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[][] a = new int[2][n];
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < n; ++j) {
a[i][j] = scanner.nextInt();
}
}
int[][] r = new int[2][n];
int[][] dp = new int[2][n];
dp[1][n - 1] = a[1][n - 1];
dp[0][n - 1] = a[0][n - 1] + dp[1][n - 1];
for (int j = n - 2; j >= 0; --j) {
for (int i = 0; i < 2; ++i) {
r[i][j] = dp[i][j + 1] + a[i][j];
}
for (int i = 0; i < 2; ++i) {
if ((i + j) % 2 != 0) {
dp[i][j] = Math.max(dp[i][j + 1], r[i ^ 1][j]) + a[i][j];
} else {
dp[i][j] = Math.min(dp[i][j + 1], r[i ^ 1][j]) + a[i][j];
}
}
}
System.out.println(dp[0][0]);
}
|
DFS/BFS
剪枝+优化
推荐阅读：
菜鸟
二叉树最大深度
104. 二叉树的最大深度 - 力扣（LeetCode）
1
2
3
4
5
6
7
|
public int treeDepth(TreeNode root) {
if (root == null) {
return 0;
}
return Math.max(treeDepth(root.left), treeDepth(root.right)) + 1;
}
|
路径总和
112. 路径总和 - 力扣（LeetCode）
图中是否有环（DFS）
DFS
拓扑图
递归
菜鸟
反转链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| public class ReverseLinkedList {
public static void main(String[] args) {
ListNode head = ListNodeUtil.LIST_NODE_Lang;
ListNodeUtil.printListNode(head);
ListNode listNode = reverseList(head,null);
ListNodeUtil.printListNode(listNode);
}
private static ListNode reverseList(ListNode head,ListNode pre) {
if (head == null ) {
return pre;
}
if (head.next == null) {
head.next = pre;
return head;
}
ListNode next = head.next;
ListNode temp = head.next.next;
next.next = head;
head.next = pre;
return reverseList(temp,next);
}
|
链表
菜鸟
删除节点
https://leetcode.cn/leetbook/read/illustration-of-algorithm/7fmls1/
本题注意点：
- 通过中间变量保存前后节点信息
- 注意后节点可能为空（由于跨度比较大）=>
while 条件选择 cur.next !=null
- 单独讨论删除节点为头结点/尾节点的情况
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public ListNode deleteNode(ListNode head, int val) {
ListNode pre = null;
ListNode next = head.next;
ListNode cur = head;
while(cur.next!=null){
if(cur.val == val){
if(cur==head){
head.next = null;
return next;
}
pre.next = next;
break;
}
pre = cur;
next = next.next;
cur = cur.next;
}
if(cur.next==null&&cur.val==val){
pre.next = null;
}
return head;
}
|
模拟
哈希
- 加快查询：查询时间复杂度为
O(n)
- 哈希码区分数据
最长连续子序列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| class Solution {
public int longestConsecutive(int[] nums) {
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
if(nums.length == 0){
return 0;
}
if(nums.length == 1){
return 1;
}
for(int i=0;i<nums.length;i++){
map.put(nums[i],0);
}
int max = 1;
for(int i=0;i<nums.length;i++){
int count = 1;
int x = nums[i];
if(map.containsKey(x-1)&&map.get(x-1)!=0){
continue;
}
while(true){
x +=1;
if(map.containsKey(x)){
count++;
map.put(x,1);
}else{
max = Math.max(count,max);
break;
}
}
}
return max;
}
}
|
字符串
KMP算法❤
匹配度算法
Levenshtein Distance 算法
上面的值加 1 ，得到 1+1=2 ，
左面的值加 1 ，得到 1+1=2 ，
左上角的值根据字符是否相同，相同加 0 ，不同加 1 。A 处由于是两个 a 相同，左上角的值加 0 ，得到 0+0=0 。
然后从我们上面计算出来的 2，2，0 三个值中选取最小值，所以 A 处的值为 0 。
I 处: 表示 abc 和 abe 有1个需要编辑的操作（ c 替换成 e ）。这个是需要计算出来的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| public double minDistance(String word1, String word2) {
int len1 = word1.length();
int len2 = word2.length();
int[][] dp = new int[len1+1][len2+2];
for (int i = 0; i <= len1; i++) {
dp[i][0] = i;
}
for (int j = 0; j <= len2; j++) {
dp[0][j] = j;
}
char[] arr1 = word1.toCharArray();
char[] arr2 = word2.toCharArray();
for(int i=1;i<len1+1;i++){
for (int j=1;j<len2+1;j++){
int leftUp = dp[i-1][j-1];
if (arr1[i-1] != arr2[j-1]){
leftUp++;
}
dp[i][j] = Math.min(Math.min(dp[i][j-1]+1,dp[i-1][j]+1),leftUp);
}
}
return 1 - (double) dp[len1][len2] /Math.max(len1,len2);
}
|
分治
汉罗塔❤
LeetCode百题斩
2279. 装满石头的背包的最大数量 - 力扣（LeetCode）
最长回文字符串
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| class Solution {
public String longestPalindrome(String s) {
if (s.length() == 1) {
return s;
}
char[] arr = s.toCharArray();
int maxIndex = 0, maxLen = 0;
for (int i = 0; i <s.length(); i++) {
int count = 1;
int left = i, right = i;
while (left >= 0 && right < s.length() && arr[left] == arr[right]) {
if (left == right){
left--;right++;
continue;
}
count+=2;
if (count > maxLen){
maxLen = count;
maxIndex = i;
}
left--;right++;
}
}
for (int i = 0; i <s.length()-1; i++) {
int count = 2;
int left = i, right = i+1;
while (left >=0 && right < s.length() && arr[left] == arr[right]) {
if (left+1 == right){
left--;right++;
if (maxLen<count){
maxLen = count;
maxIndex = i;
}
continue;
}
count+=2;
if (count > maxLen){
maxLen = count;
maxIndex = i;
}
left--;right++;
}
}
if (maxLen==0&&maxIndex==0){
return String.valueOf(arr[0]);
}
return maxLen%2==1?s.substring(maxIndex-maxLen/2,maxIndex+maxLen/2+1):s.substring(maxIndex-(maxLen-2)/2,maxIndex+(maxLen-2)/2+2);
}
}
|
路径总和
1
2
3
4
5
6
7
8
9
| public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) {
return false;
}
if (root.left == null && root.right == null) {
return sum == root.val;
}
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}
|
合并区间
合并区间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
public int[][] merge(int[][] intervals) {
if (intervals.length == 0) {
return new int[0][2];
}
int l = intervals.length;
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
List<int[]> list = new ArrayList<>();
int start = intervals[0][0];
int end = intervals[0][1];
for (int i = 1; i < l; i++) {
if (end >= intervals[i][0]) {
end = Math.max(end,intervals[i][1]);
}
else if(end < intervals[i][0]){
list.add(new int[]{start,end});
start = intervals[i][0];
end = intervals[i][1];
}
if (i==l-1){
list.add(new int[]{start,end});
}
}
int[][] res = new int[list.size()][2];
for (int[] ints : list){
res[list.indexOf(ints)] = ints;
}
return res;
}
|
小技巧
String类
char数组转化字符串
1
| String s = new String(new char[]{'a', 'b', 'c'});
|
字符串除去空格
1
| String s = new String(new char[]{'a', 'b', 'c',' '}).trim();
|
排序技巧
- 对于
int[]
降序
1
| Arrays.sort(capacities);
|
升序
比较器的使用要求数组元素必须是对象
1
2
3
4
5
|
Integer[] integerArray = Arrays.stream(intArray)
.boxed()
.toArray(Integer[]::new);
Arrays.sort(integerArray,(a,b)-> b-a);
|
- 对于
int[][]
1
2
3
4
5
6
7
8
9
10
11
12
|
int[][] batches;
Arrays.sort(batches, (a, b) -> a[0] - b[0]);
List<int[]> batches = new ArrayList<>();
for (int i = 0; i < numBatches; i++) {
int customers = scanner.nextInt();
int revenue = scanner.nextInt();
batches.add(new int[]{customers, revenue});
}
batches.sort((a, b) -> Integer.compare(b[1], a[1]));
|
真题
四道编程题：（2小时）
1.单词规律——力扣290
2.下一个更大元素——力扣556
3.找两个和为目标值且不重叠的子数组——力扣1477
循环右移二叉树
