1.回文链表

题目描述:回文链表:1->2->2->1 true

思路:

  • 首先需要记录中间位置,以便翻转,由此想到快慢指针来进行标记

    1
    2
    3
    4
    5
    6
    7
    8
    9
    while(fast != null && fast.next != null){
    fast = fast.next.next;
    slow = slow.next;
    }
    //遇到的一个小坑!后面解释
    if(fast!=null){
    slow = slow.next;
    }
    当fast指针遍历到末尾时,slow指针遍历到中间
  • 其次是翻转链表,这里定义pre,prepre指针来直接翻转链表,破坏了链表结构,有坑

    1
    2
    3
    4
    5
    6
    7
    8
    ListNode pre=head,prepre=null;
    while(fast != null && fast.next != null){
    pre = slow;
    slow = slow.next;
    fast = fast.next.next;
    pre.next = prepre;
    prepre = pre;
    }
  • 最后,比较pre和slow

    1
    2
    3
    4
    5
    6
    7
    while(pre!=null&&slow!=null){
    if(slow.val!=pre.val){
    return false;
    }
    pre=pre.next;
    slow=slow.next;
    }
  • 完整代码:

    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
    package src.day1;

    /**
    * 回文链表:1->2->2->1 true
    * 通过pre 和 prepre指针来反转链表
    * fast指针走完,slow到一半
    * 只是破坏了链表的结构
    * @author han long yi
    * @create 2021-04-01 20:38
    */
    public class huiwenlianbiao {
    /**
    * 结构体链表
    */
    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 boolean isPalindrome(ListNode head) {
    if(head==null&&head.next==null){
    return true;
    }
    //prepre pre 用来反转链表
    ListNode slow=head,fast=head;
    ListNode pre=head,prepre=null;
    while(fast != null && fast.next != null){
    pre = slow;
    slow = slow.next;
    fast = fast.next.next;
    pre.next = prepre;
    prepre = pre;
    }
    if(fast!=null){
    slow = slow.next;
    }
    while(pre!=null&&slow!=null){
    if(slow.val!=pre.val){
    return false;
    }
    pre=pre.next;
    slow=slow.next;
    }
    return true;
    }
    }

==坑!!!!==

一开始不知道为啥会有 if(fast!=null){slow = slow.next;}这一段代码,因为如果是1->2->3->2->1的回文链表,这样就会让slow只有2->1,除去了3的比较,一开始我一直以为pre和slow是同步的,这样才能翻转比较,但后来仔细看了看代码,pre其实是比slow晚一步的,因为这种pre的方式是破坏了链表结构,链表的前段部分是翻转了的,所以如果pre和slow是同步的话,3其实有两个next,就会出现错误。

所以如果是奇数链表,那么pre和slow都是从3的前一个,后一个元素开始比较,-如果是偶数链表,当然也不会出现这种情况。

2.括号匹配

算是一个比较经典的问题了,首先需要了解几个Java的容器,Map、HashMap、Deque(栈)

题目描述:给定一个只包括'('')''{''}''['']' 的字符串 s ,判断字符串是否有效。

思路:

  • 首先需要思考的是怎么匹配前后括号,因为输入形式是”{[]}”、”()[]{}”这样的,匹配的时候需要,匹配好一对括号就删除,因此想到了栈结构,通过压栈和弹栈来实现

  • 接下来,就考虑如何匹配,想到用HashMap 的k-v键值对来存储括号,因为后括号在前括号之后,所以k存储后括号,v存储前括号,如果遇到前括号,就压栈,如果遇到后括号,看看栈顶和其匹不匹配,匹配就把前括号弹栈。

  • 完整代码:

    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
    package src.day1;

    import java.util.Deque;
    import java.util.HashMap;
    import java.util.LinkedList;
    import java.util.Map;

    /**
    * 括号匹配
    * @author han long yi
    * @create 2021-04-01 20:38
    */
    public class matching {
    public boolean isValid(String s) {
    int n = s.length();
    //如果长度是奇数,一定不匹配
    if (n % 2 == 1) {
    return false;
    }
    Map<Character, Character> pairs = new HashMap<Character,Character>() {{
    put(')', '(');
    put(']', '[');
    put('}', '{');
    }};
    Deque<Character> stack = new LinkedList<>();
    for (int i = 0; i < n; i++) {
    //遍历s
    char ch = s.charAt(i);
    if (pairs.containsKey(ch)) {
    //判断括号是否匹配
    if (stack.isEmpty() || !stack.peek().equals(pairs.get(ch))) {
    return false;
    }
    stack.pop();
    } else {
    stack.push(ch);
    }
    }
    return stack.isEmpty();
    }
    }

3.x的n次幂(递归+快速幂)

题目描述:实现 pow(x, n) ,即计算 x 的 n 次幂函数(即,x^n^)

思路:

  • 首先想到,从左至右xx^2^→x^4^→x^9^→x^19^→x^38^→x^77^,每次都将上次的结果进行平方,但有些步骤需要多*一个x,这就会比较困难,如何判断到底要不要多×一个x
  • 但如果我们从右往左看,分治的思想就十分明显:
    • 当我们要计算 x^n^时,可以先递归的算出y = x^[n/2]^,其中[a]表示对a向下取整
    • 根据递归计算的结果,如果n为偶数,那么x^n^ = y*y,如果n为奇数,那么x^n^ = y * y * x
    • 递归的边界为 n = 0,任意数的 0次方均为 1。
    • 由于每次递归都会使得指数减少一半,因此递归的层数为 O(logn)

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
package src.day1;

/**
* 快速幂+递归实现x的n次幂
* 从右向左分析
* @author han long yi
* @create 2021-04-01 23:41
*/
public class pow{
public double myPow(double x, int n) {
long N = n;
//若n是负数,则1/
return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
}

public double quickMul(double x, long N) {
if (N == 0) {
return 1.0;
}
double y = quickMul(x, N / 2);
return N % 2 == 0 ? y * y : y * y * x;
}
}

复杂度分析

  • 时间复杂度:O(logn),即为递归的层数。
  • 空间复杂度:O(logn),即为递归的层数。这是由于递归的函数调用会使用栈空间。

4.牛顿迭代法实现完全平方数的判断

![G_YXC__JI@5_P_L~22`G5_0.png](https://i.loli.net/2021/04/22/d9fgKHIMhUOjnpZ.png)

由于这种解法太过神仙,就不多解释了,看图就好,这只是一种无限接近的解法,会有误差,但误差在允许的范围之内。

完整代码:

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public boolean isPerfectSquare(int num) {
if (num < 2) return true;

long x = num / 2;
while (x * x > num) {
x = (x + num / x) / 2;
}
return (x * x == num);
}
}

二分法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public boolean isPerfectSquare(int num) {
if (num < 2) {
return true;
}

long left = 2, right = num / 2, x, guessSquared;
while (left <= right) {
x = left + (right - left) / 2;
guessSquared = x * x;
if (guessSquared == num) {
return true;
}
if (guessSquared > num) {
right = x - 1;
} else {
left = x + 1;
}
}
return false;
}
}

5.判断是否是对称二叉树

思路:比较左孩子的与右孩子值是否相等,由此想到递归实现,比较容易理解,就不加赘述了。

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
package src.day2;


/**
* 通过递归实现判断是否是对称二叉树
* 递归终止条件:两个节点都为空;其中一个节点为空;两个节点值不相等
* @author han long yi
* @create 2021-04-02 10:07
*/

public class isSymmetric {
public boolean isSymmetric(TreeNode root) {
if(root==null) {
return true;
}
//调用递归函数,比较左节点,右节点
return dfs(root.left,root.right);
}

boolean dfs(TreeNode left, TreeNode right) {
//递归的终止条件是两个节点都为空
//或者两个节点中有一个为空
//或者两个节点的值不相等
if(left==null && right==null) {
return true;
}
if(left==null || right==null) {
return false;
}
if(left.val!=right.val) {
return false;
}
//再递归的比较 左节点的左孩子 和 右节点的右孩子
//以及比较 左节点的右孩子 和 右节点的左孩子
return dfs(left.left,right.right) && dfs(left.right,right.left);
}
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
}

6. 617 合并二叉树

思路:前序递归遍历二叉树,并将值相加

  • 递归终止条件,两节点有一个或两个节点为null就返回

  • 递归函数内,将两个树的节点相加后,再递归执行两节点的左节点和右节点

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    public TreeNode dfs(TreeNode r1, TreeNode r2) {
    //终止条件
    if (r1 == null || r2 == null) {
    return r1 == null ? r2 : r1;
    }
    //树2合并到树1上
    //前序遍历二叉树
    r1.val += r2.val;
    r1.left = dfs(r1.left, r2.left);
    r1.right = dfs(r1.right, r2.right);
    return r1;
    }

    完整代码:

    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
    package src.day2;

    /**
    * 递归法合并二叉树
    * @author han long yi
    * @create 2021-04-02 15:17
    */
    public class merge {
    public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    }
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
    if (root1 == null || root2 == null) {
    return root1 == null ? root2 : root1;
    }
    return dfs(root1, root2);
    }
    public TreeNode dfs(TreeNode r1, TreeNode r2) {
    //终止条件
    if (r1 == null || r2 == null) {
    return r1 == null ? r2 : r1;
    }
    //树2合并到树1上
    //前序遍历二叉树
    r1.val += r2.val;
    r1.left = dfs(r1.left, r2.left);
    r1.right = dfs(r1.right, r2.right);
    return r1;
    }
    }

7.反转链表

思路:递归遍历到最后一个节点,然后反转

  • 递归终止条件: head == null or head.next == null

  • 递归函数内容:将指针反转,注意节点下一位必须指向null,否则不算成功

  • 时间复杂度:O(n),n为节点个数们,需要遍历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
    package src.day2;

    /**
    * 递归实现反转链表
    * @author han long yi
    * @create 2021-04-02 23:00
    */
    public class reverseList {
    public class ListNode {
    int val;
    ListNode next;
    }
    public ListNode reverseList(ListNode head) {
    //终止条件
    if (head == null || head.next == null){
    return head;
    }
    ListNode newhead = reverseList(head.next);
    //反转指针
    head.next.next = head;
    head.next = null;
    return newhead;
    }
    }

8.移动零 leectcode 283

描述:给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

思路:快排实现移动0,因为除了特殊情况外,快排是所有排序中性能最好的算法。将第一个元素作为基准值,从左至右遍历,如果不为0,则交换,使得所有不为0的元素在数组左侧(数组分治思想

快排:

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
package src.day3;

/**
* 快排实现数组中0都在数组的末尾
* @author han long yi
* @create 2021-04-03 22:48
*/
public class moveZero {
public void moveZeroes(int[] nums) {
if(nums == null){
return ;
}
int j = 0;
for(int i = 0; i < nums.length;i++){
if(nums[i] != 0){
int temp = 0;
temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
j++;
}
}
}
}

9.给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

要点:

  • 连续子数组
  • 最大和

思路:

  • 整数数组有正有负

  • sum 保存动态最大和,又可能出现负数情况

  • 动态规划,ans 保存最后结果

    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
    package src.day4;

    /**
    * 给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
    * @author han long yi
    * @create 2021-04-04 10:43
    */
    public class max {
    public int maxSubArray(int[] nums) {
    int sum = 0;
    // 保存结果
    int ans = nums[0];
    for(int num : nums){
    // 如果sum为负数,直接赋值num
    if(sum <= 0){
    sum = num;
    }else{
    sum += num;
    }
    // 动态规划
    ans = Math.max(sum,ans);
    }
    return ans;
    }
    }

10、二叉树最大深度

思路:简单动态规划实现

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
package src.day4;

/**
* 给定一个二叉树,找出其最大深度。
* @author han long yi
* @create 2021-04-04 21:32
*/
public class maxDepth {
public int maxDepth(TreeNode root) {
if(root == null){
return 0;
}
//递归
int left = maxDepth(root.left);
int right = maxDepth(root.right);
// 动态规划
return Math.max(left,right) + 1;
}

public class TreeNode{
int val;
TreeNode left;
TreeNode right;
}
}

11、给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

思路:

  • 找众数,首先想到用额外的空间map来存放key–遍历的数,value–出现的次数
  • 但空间复杂度比较高,由此想到用一个变量来存放众数出现的次数
  • 若不是candidata 则 -1,若是则 +1
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
package src.day4;

/**
* 题目:给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
* 摩尔投票法:
* 我们遍历数组 nums 中的所有元素,对于每个元素 x,在判断 x 之前,如果 count 的值为 0
* 我们先将 x 的值赋予 candidate,随后我们判断 x:
* 如果 x 与 candidate 相等,那么计数器 count 的值增加 1;
* 如果 x 与 candidate 不等,那么计数器 count 的值减少 1。
* 在遍历完成后,candidate 即为整个数组的众数。
* nums: [7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7]
* candidate: 7 7 7 7 7 7 5 5 5 5 5 5 7 7 7 7
* count: 1 2 1 2 1 0 1 0 1 2 1 0 1 2 3 4
* @author han long yi
* @create 2021-04-04 23:40
*/
public class most {
public int majorityElement(int[] nums) {
int count = 0;
int candidate = 0;

for (int num : nums) {
if (count == 0) {
candidate = num;
}
count += (num == candidate) ? 1 : -1;
}

return candidate;
}
}

12、给定一个链表,判断链表中是否有环。

思路:快慢指针,若链表有环,则快指针一定追上慢指针,且快指针只能比慢指针快偶数倍,如果是奇数倍,若环内元素为偶数,则永远不会相遇(画图可解

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
package src.day5;

/**
* 给定一个链表,判断链表中是否有环。
* 解法:快慢指针,快指针先进入环,如果快指针追上慢指针,证明有环
* @author han long yi
* @create 2021-04-05 14:51
*/
public class cycle {
public boolean hasCycle(ListNode head) {
if(head == null || head.next == null){
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while(slow != fast){
if(fast == null || fast.next == null){
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}
public class ListNode{
int val;
ListNode next;
}
}

13.翻转二叉树

思路:递归实现

  • 递归终止条件:root 为 null,则返回root
  • 递归函数内交换当前节点左右子树,在递归交换子树的左右子树
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
package src.day5;

/**
* 翻转一棵二叉树。
* 递归实现
* @author han long yi
* @create 2021-04-05 17:01
*/
public class invert {
public class TreeNode{
int val;
TreeNode left;
TreeNode right;
}
public TreeNode invertTree(TreeNode root) {
//递归函数的终止条件,节点为空时返回
if(root==null) {
return null;
}
//下面三句是将当前节点的左右子树交换
TreeNode tmp = root.right;
root.right = root.left;
root.left = tmp;
//递归交换当前节点的 左子树
invertTree(root.left);
//递归交换当前节点的 右子树
invertTree(root.right);
//函数返回时就表示当前这个节点,以及它的左右子树
//都已经交换完了
return root;
}
}

14、相交链表

思路:因为两链表相交,所以两链表有一部分重合,一部分不同,若让两指针分别走A+B,B+A的路程,则两指针,一定会在相交的起始节点相遇

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
package src.day5;

/**
* 编写一个程序,找到两个单链表相交的起始节点。
* A+B = B+A 因为相交,所以最后一段相同,所以a,b指针分别走A+B以及B+A,则一定a会=b
* @author han long yi
* @create 2021-04-05 23:15
*/
public class xiangjiao {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null){
return null;
}
ListNode a = headA;
ListNode b = headB;
while(a != b){
a = (a==null) ? headB : a.next;
b = (b==null) ? headA : b.next;
}
return a;
}
public class ListNode{
int val;
ListNode next;
}
}

15、(448)给你一个含 n 个整数的数组 nums ,其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字,并以数组的形式返回结果。

思路:

  • 首先,可以考虑用哈希表记录,但空间复杂度较高
  • 用nums本身来记录,就是每遍历一个 x 就让 nums[x-1] 增加n,这样 x 对应下标的数一定 > n,最后再遍历,,判断小于 n 的数的下标加入数组即可
  • 注意,有可能 num 已经加过 n 了,所以要对 num 取余
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
package src.day6;

import java.util.ArrayList;
import java.util.List;

/**
* 给定一个范围在  1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组,数组中的元素一些出现了两次,另一些只出现一次。
* 找到所有在 [1, n] 范围之间没有出现在数组中的数字。
* 解法:遍历数组,遍历一次x就使nums[x-1] + n,这样如果数组中没有的数字,那么他们-1对应的下标的数应该<=n
* 由此筛选出不是数组中的数字
* @author han long yi
* @create 2021-04-06 15:02
*/
public class findDisappear {
public List<Integer> findDisappearedNumbers(int[] nums) {
int n = nums.length;
for(int num : nums){
//有可能这个x已经加过n了,除于还原原来的数字
int x = (num - 1) % n;
nums[x]+=n;
}
ArrayList<Integer> list = new ArrayList<Integer>();
for(int i = 0;i < n;i++){
if(nums[i] <= n){
list.add(i+1);
}
}
return list;
}
}

16、汉明距离

思路:简单的位运算

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
package src.day6;
/**
* 两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
* 给出两个整数 x 和 y,计算它们之间的汉明距离。
* x y 异或不同位为1,统计异或结果1的数目即为答案
* @author han long yi
* @create 2021-04-06 9:32
*/
public class hamming {
public int hammingDistance(int x, int y) {
//异或。统计xor为1的个数即可
int xor = x ^ y;
int distance = 0;
//右移位统计xor的1
while (xor != 0) {
// 因为若二进制末位为1,则 % 2 一定为1
if (xor % 2 == 1) {
distance += 1;
}
// 右移,判断下一位
xor = xor >> 1;
}
return distance;
}

}

17.最大路径

描述: 给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

思路:动态规划算法

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
package src.day6;

/**
* 给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
* @author han long yi
* @create 2021-04-06 23:40
*/
public class zuidaluj {
int ans;
public int diameterOfBinaryTree(TreeNode root) {
ans = 1;
if(root.left==null && root.right==null){
return 0;
}
depth(root);
return ans;
}
public int depth(TreeNode node) {
if (node == null) {
// 访问到空节点了,返回0
return 0;
}
// 左儿子为根的子树的深度
int L = depth(node.left);
// 右儿子为根的子树的深度
int R = depth(node.right);
// 计算d_node即L+R+1 并更新ans
ans = Math.max(ans, L+R);
// 返回该节点为根的子树的深度
return Math.max(L, R)+1;
}
public class TreeNode{
int val;
TreeNode right;
TreeNode left;
}
}

18.爬楼梯

思路:动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
package src.day7;

/**
* 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
* 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
* 递归实现会超时,why?递归实现时间复杂度为2^n
* @author han long yi
* @create 2021-04-07 10:36
*/
public class climb {
public int climbStairs(int n) {
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 2;
for(int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}

19.(121)股票的最大利润

思路:动态规划,更新最小值,动态规划利润

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
package src.day7;

/**
* 股票问题(动态规划)比较简单
* @author han long yi
* @create 2021-04-07 20:10
*/
public class max {
public int maxProfit(int[] prices) {
int min=prices[0];
int res=0;
for(int i : prices){
if(min>=i){
min = i;
continue;
}
res = Math.max(res,i-min);
}
return res;
}
}

20.(139) 单词拆分

描述:给定一个非空字符串 s 和一个包含非空单词的列表 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

思路:

  • 动态规划,dp[i]表示s前i个字符能否拆分
  • 转移方程:dp[j] = dp[i] && check(s[i+1, j])
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
package src.day8;

import java.util.HashMap;
import java.util.List;

/** 动态规划算法,dp[i]表示s前i个字符能否拆分
* 转移方程:dp[j] = dp[i] && check(s[i+1, j]);
* check(s[i+1, j])就是判断i+1到j这一段字符是否能够拆分
* 其实,调整遍历顺序,这等价于s[i+1, j]是否是wordDict中的元素
* 这个举个例子就很容易理解。
* 假如wordDict=["apple", "pen", "code"],s = "applepencode";
* dp[8] = dp[5] + check("pen")
* 翻译一下:前八位能否拆分取决于前五位能否拆分,加上五到八位是否属于字典
* (注意:i的顺序是从j-1 -> 0哦~,因为substring(x,y)x-->0开始索引 y--->1开始索引)
* @author han long yi
* @create 2021-04-08 20:06
*/
public class chaifen {
public HashMap<String,Boolean> map = new HashMap<>();
//检查s是否属于字典
public boolean check(String s){
return map.getOrDefault(s,false);
}
public boolean wordBreak(String s, List<String> wordDict) {
for(String word : wordDict){
map.put(word,true);
}
boolean[] dp = new boolean[s.length()+1];
for(int j = 1;j < s.length();j++){
for(int i = j-1; i >= 0; i--){
// dp[8] = dp[5] + check("pen")
dp[j] = dp[i] && check(s.substring(i,j));
if(dp[j]){
break;
}
}
}
return dp[s.length()];
}
}

21(79)单词搜索

描述:给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中,返回 true ;否则,返回 false

思路:

  • DFS深度优先搜索
  • 上下左右遍历,并且标记遍历过的值
  • base 条件,是否越界
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
57
58
private static final int[][] DIRECTIONS = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
private int rows;
private int cols;
private int len;
// 标记元素是否被访问过
private boolean[][] visited;
// 单词数组
private char[] charArray;
private char[][] board;

public boolean exist(char[][] board,String word){
rows = board.length;
if(rows == 0){
return false;
}
cols = board[0].length;
visited = new boolean[rows][cols];
this.len = word.length();
this.charArray = word.toCharArray();
this.board = board;
// 通过此循坏来找到正确的初值
for(int i=0;i < rows;i++){
for(int j=0;j < cols;j++){
if(dfs(i,j,0)){
return true;
}
}
}
return false;
}

public boolean dfs(int x, int y, int begin){
if(begin == len - 1){
return board[x][y] == charArray[begin];
}
if(board[x][y]==charArray[begin]){
// 记录是否走过
visited[x][y] = true;
// 左下右上的顺序回溯正确路径
for(int[] direction : DIRECTIONS){
int newX = x + direction[0];
int newY = y + direction[1];
// 新路径未越界,并且没有走过
if(inArea(newX,newY)&&!visited[newX][newY]){
if(dfs(newX,newY,begin+1)){
return true;
}
}
}
// 证明不是正确的初值,清零记录
visited[x][y] = false;
}
return false;
}

private boolean inArea(int x, int y) {
return x >= 0 && x < rows && y >= 0 && y < cols;
}

22.(98)验证二叉搜索树

描述:给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下:

  • 节点的左子树只包含 小于 当前节点的数。
  • 节点的右子树只包含 大于 当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

思路:

  • 中序遍历,对比每一次遍历的值是否 <= pre
  • 用一个 pre 来记录上个遍历的树节点的值
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 TreeNode{
int val;
TreeNode left;
TreeNode right;
}
long pre = Long.MIN_VALUE;
// 中序遍历
public boolean isValidBST(TreeNode root) {
if(root == null){
return true;
}
// 递归遍历左子树
if(!isValidBST(root.left)){
return false;
}
// 访问当前节点:如果当前节点小于等于中序遍历的前一个节点,说明不满足 BST,返回 false;否则继续遍历。
if(root.val <= pre){
return false;
}
pre = root.val;
// 递归遍历右子树
return isValidBST(root.right);
}

23.(62)不同路径

描述:一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。问总共有多少条不同的路径?

思路:

  • 因为机器人只能向下或者向右移动,所以移动到网格的 第一排 以及 第一列 的路径都只有一条
  • 移动到某个位置有多少条路径取决于 它的 上一格 以及 左一格 有多少条路径相加的和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
int i,j;
// 将第一排以及第一列的元素都变成1,因为只有一条路径到达
for(i=0;i<m;i++){
dp[i][0] = 1;
}
for(j=0;j<n;j++){
dp[0][j] = 1;
}
for(i = 1;i < m;i++){
for(j = 1;j < n;j++){
// 左一格 以及 上一格 的和
dp[i][j] = dp[i][j-1] + dp[i-1][j];
}
}
return dp[m-1][n-1];
}

24.(621) 任务调度器

描述: