正则表达式匹配

剑指 Offer 19. 正则表达式匹配

难度困难185收藏分享切换为英文接收动态反馈

请实现一个函数用来匹配包含'. '和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。

示例 1:

1
2
3
4
5
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:

1
2
3
4
5
输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

示例 3:

1
2
3
4
5
输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

示例 4:

1
2
3
4
5
输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

示例 5:

1
2
3
4
输入:
s = "mississippi"
p = "mis*is*p*."
输出: false
  • s 可能为空，且只包含从 a-z 的小写字母。
  • p 可能为空，且只包含从 a-z 的小写字母以及字符 . 和 *，无连续的 '*'。

注意：本题与主站 10 题相同：https://leetcode-cn.com/problems/regular-expression-matching/

动态规划

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
以一个例子详解动态规划转移方程：
S = abbbbc
P = ab*d*c
1. 当 i, j 指向的字符均为字母（或 '.' 可以看成一个特殊的字母）时，
   只需判断对应位置的字符即可，
   若相等，只需判断 i,j 之前的字符串是否匹配即可，转化为子问题 f[i-1][j-1].
   若不等，则当前的 i,j 肯定不能匹配，为 false.
   
       f[i-1][j-1]   i
            |        |
   S [a  b  b  b  b][c] 
   
   P [a  b  *  d  *][c]
                     |
                     j
   

2. 如果当前 j 指向的字符为 '*'，则不妨把类似 'a*', 'b*' 等的当成整体看待。
   看下面的例子

            i
            |
   S  a  b [b] b  b  c  
   
   P  a [b  *] d  *  c
            |
            j
   
   注意到当 'b*' 匹配完 'b' 之后，它仍然可以继续发挥作用。
   因此可以只把 i 前移一位，而不丢弃 'b*', 转化为子问题 f[i-1][j]:
   
         i
         | <--
   S  a [b] b  b  b  c  
   
   P  a [b  *] d  *  c
            |
            j
   
   另外，也可以选择让 'b*' 不再进行匹配，把 'b*' 丢弃。
   转化为子问题 f[i][j-2]:

            i
            |
   S  a  b [b] b  b  c  
    
   P [a] b  *  d  *  c
      |
      j <--

3. 冗余的状态转移不会影响答案，
   因为当 j 指向 'b*' 中的 'b' 时, 这个状态对于答案是没有用的,
   原因参见评论区 稳中求胜 的解释, 当 j 指向 '*' 时,
   dp[i][j]只与dp[i][j-2]有关, 跳过了 dp[i][j-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
class Solution {
    public boolean isMatch(String s, String p) {
        int m=s.length();
        int n=p.length();

        boolean [][]dp=new boolean[m+1][n+1];
        dp[0][0]=true;

        for(int i=0;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(p.charAt(j-1)=='*'){
                    dp[i][j]=dp[i][j-2];
                    if(matches(s,p,i,j-1)){
                        dp[i][j] = dp[i][j]||dp[i-1][j];
                    }
                }else if(matches(s,p,i,j)){
                    dp[i][j]=dp[i-1][j-1];
                }
            }
        }
        return dp[m][n];
    }

    public boolean matches(String s,String p,int i,int j){
        if(i==0)return false;
        if(p.charAt(j-1)=='.')return true;
        return s.charAt(i-1)==p.charAt(j-1);
    }
}

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool isMatch(string s, string p) {
        return match(s, p, 0, 0);
    }
private:
    bool match(string &s, string &p, int i, int j)
    {
        if(i == s.size() && j == p.size())
            return true;
        if(j + 1 < p.size() && p[j + 1] == '*')
            return match(s, p, i, j + 2) || (i != s.size() && (s[i] == p[j] || p[j] == '.') && match(s, p, i + 1, j));
        else
            return i != s.size() && j != p.size() && (s[i] == p[j] || p[j] == '.') && match(s, p, i + 1, j + 1);
    }
};

参考引用内容
https://leetcode-cn.com/problems/regular-expression-matching/solution/zheng-ze-biao-da-shi-pi-pei-by-leetcode-solution/

https://leetcode-cn.com/problems/regular-expression-matching/solution/zheng-ze-biao-da-shi-pi-pei-by-leetcode-solution/452279

展开全文 >>

主持人调度

题目描述

有n个活动即将举办，每个活动都有活动的开始时间与活动的结束时间，第i个活动的开始时间是$start_i$,第i个活动的结束时间是end_i,举办某个活动就需要为该活动准备一个活动主持人。一位活动主持人在同一时间只能参与一个活动。并且活动主持人需要全程参与活动，换句话说，活动主持人参与了第i个活动，那么该主持人在$start_i,end_i$这个时间段不能参与其他任何活动。求为了成功举办这n个活动，最少需要多少名主持人。

示例1

输入

复制

1
2,[[1,2],[2,3]]

返回值

复制

1
1

说明

1
只需要一个主持人就能成功举办这两个活动

示例2

输入

复制

1
2,[[1,3],[2,4]]

返回值

复制

1
2

说明

1
需要两个主持人才能成功举办这两个活动

备注:

$1 \leq n \leq 10^5$
$start_i,end_i$在int范围内

排序+堆

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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算成功举办活动需要多少名主持人
     * @param n int整型 有n个活动
     * @param startEnd int整型二维数组 startEnd[i][0]用于表示第i个活动的开始时间，startEnd[i][1]表示第i个活动的结束时间
     * @return int整型
     */
    public int minmumNumberOfHost (int n, int[][] startEnd) {
        // write code here
        Arrays.sort(startEnd,new Comparator<int[]>(){
            public int compare(int []o1,int []o2){
                // 按照开始时间排序，如果开始时间相同那么按照结束时间排序
                return o1[0]-o2[0]== 0? o1[1]-o2[1]:o1[0]-o2[0];
            }
        });

        PriorityQueue<Integer> pq=new PriorityQueue<Integer>();
        pq.offer(Integer.MIN_VALUE);
		
        for(int i=0;i<n;i++){
            // 如果某个开始时间大于前面的结束时间，那么有一个主持人可以空出来
            if(startEnd[i][0]>=pq.peek()){
                pq.poll();
            }
            // 继续添加下一个主持任务
            pq.offer(startEnd[i][1]);
        }
        // 最后队列中剩余的数量即为同时需要进行的数量
        return pq.size();
    }
}

循环遍历

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
import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算成功举办活动需要多少名主持人
     * @param n int整型 有n个活动
     * @param startEnd int整型二维数组 startEnd[i][0]用于表示第i个活动的开始时间，startEnd[i][1]表示第i个活动的结束时间
     * @return int整型
     */
    public int minmumNumberOfHost (int n, int[][] startEnd) {
        // write code here
        int[] starts = new int[startEnd.length];
        int[] ends = new int[startEnd.length];
        for(int i = 0 ;i < startEnd.length;i++){
            starts[i] = startEnd[i][0];
            ends[i] = startEnd[i][1];
        }
        Arrays.sort(starts);
        Arrays.sort(ends);

        int count = 0;
        int end = 0;
        for(int start = 0;start< startEnd.length;start++){
            if(starts[start] >= ends[end]){
                end++;
            }else{
                count++;
            }
        }
        return count;
    }
}

题解用户：https://www.nowcoder.com/profile/973419228

展开全文 >>

序列和

题目描述

给出一个正整数N和长度L，找出一段长度大于等于L的连续非负整数，他们的和恰好为N。答案可能有多个，我我们需要找出长度最小的那个。
例如 N = 18 L = 2：
5 + 6 + 7 = 18
3 + 4 + 5 + 6 = 18
都是满足要求的，但是我们输出更短的 5 6 7

输入描述:

1
输入数据包括一行： 两个正整数N(1 ≤ N ≤ 1000000000),L(2 ≤ L ≤ 100)

输出描述:

1
从小到大输出这段连续非负整数，以空格分隔，行末无空格。如果没有这样的序列或者找出的序列长度大于100，则输出No

示例1

输入

复制

1
18 2

输出

复制

1
5 6 7

等差数组求和

遍历数字的个数，然后求出首项，然后利用数字的个数和首项输出答案

等差数列求和公式：

$S_{n}=\frac{\left(a_{1}+a_{n}\right) n}{2}, n \in N^{*}$

$S_{n}=\frac{\left[2 a_{1}+(n-1) d\right] n}{2}, n \in 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
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int L = sc.nextInt();
        
        for (int i = L; i < 101; i++) {
            // 判断是否可以整除，题目中的等差数列的每一项都是自然数
            if ((2 * N - i * (i - 1)) % (2 * i) == 0)
                // 题目条件中的每一项都是大于等于0的数字
                if ((2 * N - i * (i - 1)) / (2 * i) >= 0) {
                    // 上面的公式变形得到首项
                    int a1  = (2 * N - i * (i - 1)) / (2 * i);
                    // 输出数字
                    for (int j = 0; j < i - 1; j++) {
                        System.out.print(a1 + j + " ");
                    }
                    // 输出最后一个数字（没有空格）
                    System.out.print(a1 + (i - 1));
                    return;
                }
        }
        // 输出不可以分解的结果
        System.out.print("No");

    }
}

展开全文 >>

挖地雷动态规划

题目描述

在一个地图上有$N$N个地窖$(N \le 20)$(N≤20)，每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径。当地窖及其连接的数据给出之后，某人可以从任一处开始挖地雷，然后可以沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，使某人能挖到最多的地雷。

输入格式

有若干行。

第1行只有一个数字，表示地窖的个数N。

第2行有$N$个数，分别表示每个地窖中的地雷个数。

第3行至第$N+1$行表示地窖之间的连接情况：

第3行有$n-1$个数（00或11），表示第一个地窖至第2个、第3个、…、第n个地窖有否路径连接。如第3行为1 1 0 0 0 … 0，则表示第1个地窖至第2个地窖有路径，至第3个地窖有路径，至第4个地窖、第5个、…、第n个地窖没有路径。

第4行有n-2个数，表示第二个地窖至第3个、第4个、…、第n个地窖有否路径连接。

… …

第n+1行有1个数，表示第$n-1$个地窖至第n个地窖有否路径连接。（为0表示没有路径，为1表示有路径）。

输出格式

有两行

第一行表示挖得最多地雷时的挖地雷的顺序，各地窖序号间以一个空格分隔，不得有多余的空格。

第二行只有一个数，表示能挖到的最多地雷数。

输入输出样例

输入 #1复制

1
2
3
4
5
6
5
10 8 4 7 6
1 1 1 0
0 0 0
1 1
1

输出 #1复制

1
2
1 3 4 5
27

说明/提示

【题目来源】

NOIP 1996 提高组第三题

自顶向下的动态规划

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
import java.util.*;

class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int[] val = new int[n];
        for (int i = 0; i < n; i++) {
            val[i] = sc.nextInt();
        }

        int road[][] = new int[n][];
        for (int i = 0; i < n - 1; i++) {
            road[i] = new int[n - i - 1];
            for (int j = 0; j < n - i - 1; j++) {
                road[i][j] = sc.nextInt();
            }
        }

        mem = new int[n];
        next = new int[n];
        int max = 0;
        for (int i = 0; i < n; i++) {
            max = Math.max(dfs(val, road, i), max);
        }

        int ans = 0, start = 0;
        for (int i = 0; i < n; i++) {
            if (mem[i] > ans) {
                ans = mem[i];
                start = i;
            }
        }
        // 回放动态规划的过程
        Deque<Integer> stack = new LinkedList<>();
        stack.push(start);
        while (!stack.isEmpty()) {
            int nextIndex = stack.pop();
            System.out.print((nextIndex + 1) + " ");
            if (next[nextIndex] != 0) stack.push(next[nextIndex]);
        }
        System.out.println();
        System.out.println(max);
    }
	
	// 动态规划表格
    static int[] mem;
    // 记录当前位置的下一个位置，用来回放动态规划的过程
    static int[] next;

    public static int dfs(int[] val, int[][] road, int index) {
        if (index > road.length - 1) return 0;

        if (mem[index] != 0) return mem[index];
        if (index == road.length - 1) {
            mem[index] = val[index];
            return val[index];
        }

        int n = road[index].length;
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (road[index][i] != 0) {
                int temp = res;
                res = Math.max(res, dfs(val, road, index + i + 1));
                // 记录回放的过程
                if (res != temp) next[index] = index + i + 1;
            }
        }
        mem[index] = res + val[index];
        return res + val[index];
    }
}

自底向上的动态规划

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
#include<bits/stdc++.h>
#define MAXN 100005
using namespace std;
int dp[MAXN];
int a[MAXN];
int pre[MAXN];
int main()
{
    int n;
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i];
        dp[i]=a[i];
    }
    for(int i=1; i<=n-1; i++)
    {
        for(int j=i+1; j<=n; j++)
        {
            int b;
            cin>>b;
            if(b)
                if(dp[j]<dp[i]+a[j])
                {
                    dp[j]=dp[i]+a[j];
                    pre[j]=i;
                }
        }
    }
    int ans=0,start=0;
    for(int i=1; i<=n; i++)
    {
        if(ans<dp[i])
        {
            start=i;
            ans=dp[i];
        }
    }
    stack<int> stk;
    stk.push(start);
    while(pre[start])
    {
        stk.push(pre[start]);
        start=pre[start];
    }
    while(stk.size())
    {
        cout<<stk.top()<<' ';
        stk.pop();
    }
    cout<<endl<<ans;
}

展开全文 >>

滑雪动态规划

[ 展开](javascript:void 0)

题目描述

Michael 喜欢滑雪。这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael 想知道在一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子：

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

一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度会减小。在上面的例子中，一条可行的滑坡为 24－17－16－1（从 24 开始，在 1 结束）。当然 25－24－23－$\ldots…$－3－2－1 更长。事实上，这是最长的一条。

输入格式

输入的第一行为表示区域的二维数组的行数 R 和列数 C。下面是 R 行，每行有 C 个数，代表高度(两个数字之间用 1 个空格间隔)。

输出格式

输出区域中最长滑坡的长度。

输入输出样例

输入 #1复制

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

输出 #1复制

1
25

说明/提示

对于 $100%$ 的数据，$1\leq R,C\leq 100$

记忆化搜索

深度优先搜索，每一个格子的初始值都是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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();

        int[][] val = new int[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                val[i][j] = sc.nextInt();
            }
        }
        mem = new int[m][n];
        int max = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                max = Math.max(dfs(val, i, j), max);
            }
        }
        System.out.println(max);
    }

    static int[][] road = new int[][]{{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
    static int[][] mem;

    public static int dfs(int[][] val, int y, int x) {
        if (y >= val.length || y < 0 || x >= val[0].length || x < 0) return 0;
        if (mem[y][x] != 0) return mem[y][x];
		
        // res保存当前格子的值
        int res = 0;
        for (int i = 0; i < 4; i++) {
            int y1 = y + road[i][0];
            int x1 = x + road[i][1];
            if (y1 >= val.length || y1 < 0 || x1 >= val[0].length || x1 < 0) continue;
            // 计算当前格子的相邻格子的最大值
            if (val[y1][x1] > val[y][x]) {
                int value = dfs(val, y1, x1);
                res = Math.max(value, res);
            }
        }
        // 相邻格子的最大值加上当前格子的值，就是当前格子的最大值
        mem[y][x] = res + 1;
        // 返回当前格子的最大值
        return res + 1;
    }
}

展开全文 >>

两数相加

445. 两数相加 II

难度中等355收藏分享切换为英文接收动态反馈

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

进阶：

如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。

示例：

1
2
输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 8 -> 0 -> 7

使用栈

官方题解的思路是栈，不过原地的话应该也可以就是很麻烦

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Deque<Integer> stack1=new LinkedList<>();
        Deque<Integer> stack2=new LinkedList<>();

        for(;l1!=null;l1=l1.next) 
            stack1.push(l1.val);
 
        for(;l2!=null;l2=l2.next) 
            stack2.push(l2.val);
        
        ListNode dummyNode =new ListNode(0);

        // ListNode head=null;
        // dummyNode.next= head;
        int advancement=0;
        while(!stack1.isEmpty()||!stack2.isEmpty()){
            int v1=0;
            int v2=0;
            if(!stack1.isEmpty()){
                v1=stack1.pop();
            }
            if(!stack2.isEmpty()){
                v2=stack2.pop();
            }
            int sum=v1+v2+advancement;
            if(sum>=10){
                advancement=1;
            }else{
                advancement=0;
            }
            ListNode temp = new ListNode(sum%10);
            temp.next=dummyNode.next;
            dummyNode.next=temp;
        }
        if(advancement>0){
            ListNode temp = new ListNode(1);
            temp.next=dummyNode.next;
            dummyNode.next=temp;
        }

        return dummyNode.next;
    }
}

展开全文 >>

翻转链表

92. 反转链表 II

难度中等768收藏分享切换为英文接收动态反馈

给你单链表的头节点 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

示例 1：

img

1
2
输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

示例 2：

1
2
输入：head = [5], left = 1, right = 1
输出：[5]

提示：

  • 链表中节点数目为 n
  • 1 <= n <= 500
  • -500 <= Node.val <= 500
  • 1 <= left <= right <= n

进阶： 你可以使用一趟扫描完成反转吗？

使用dummyNode解决边界问题

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
/**
 * Definition for singly-linked list.
 * 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; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        

        ListNode dummyNode=new ListNode(0);
        dummyNode.next=head;
        ListNode pre=dummyNode;

        for(int i=1;i<left;i++){
            pre=pre.next;
        }

        ListNode cur=pre.next;

        for(int i=left;i<right;i++){
            // 获取当前节点的下一个节点nex
            ListNode nex=cur.next;
            // 当前节点的下一个节点指向当前节点的下一个节点的下一个节点即nex.next
            cur.next=nex.next;
            // 当前节点的下一个节点的下一个节点指向替换处的下一个节点
            nex.next=pre.next;
            // 替换处的下一个节点指向当前节点的下一个节点
            pre.next=nex;
        }
        // 返回虚拟节点的下一个节点，这样可以消除头尾交换时丢失节点。
        return dummyNode.next;
    }
}

展开全文 >>

缺失的第一个正数

41. 缺失的第一个正数

难度困难1008

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

进阶：你可以实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案吗？

示例 1：

1
2
输入：nums = [1,2,0]
输出：3

示例 2：

1
2
输入：nums = [3,4,-1,1]
输出：2

示例 3：

1
2
输入：nums = [7,8,9,11,12]
输出：1

提示：

  • 0 <= nums.length <= 300
  • -231 <= nums[i] <= 231 - 1

遍历标志位

使用哈希遍历标志，遍历过就置为true，从1开始找第一个为false的index

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int firstMissingPositive(int[] nums) {
        int n=nums.length;
        if(n==0)return 1;
        boolean[] flag=new boolean[n+1];
        for(int i=0;i<n;i++){
            if(nums[i]>0&&nums[i]<=n){
                flag[nums[i]]=true;
            }
        }
        for(int i=1;i<=n;i++){
            if(!flag[i])return i;
        }
        return n+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
class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            // 如果当前的值不是当前的位置，那么一直交换（否则的话会有乱序）
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }
}

// 作者：LeetCode-Solution
// 链接：https://leetcode-cn.com/problems/first-missing-positive/solution/que-shi-de-di-yi-ge-zheng-shu-by-leetcode-solution/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

数字三角形

题目描述

观察下面的数字金字塔。

写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。

1
2
3
4
5
        7 
      3   8 
    8   1   0 
  2   7   4   4 
4   5   2   6   5

在上面的样例中,从 7 \to 3 \to 8 \to 7 \to 57→3→8→7→5 的路径产生了最大

输入格式

第一个行一个正整数 rr ,表示行的数目。

后面每行为这个数字金字塔特定行包含的整数。

输出格式

单独的一行,包含那个可能得到的最大的和。

输入输出样例

输入 #1复制

1
2
3
4
5
6
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

输出 #1复制

1
30

说明/提示

【数据范围】
对于 $100%$ 的数据，$1\le r \le 1000$，所有输入在 [0,100]范围内。

题目翻译来自NOCOW。

USACO Training Section 1.5

IOI1994 Day1T1

动态规划

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

import java.util.*;

class Main{
//     5
// 7
// 3 8
// 8 1 0
// 2 7 4 4
// 4 5 2 6 5
    public static void main(String args[]){
        Scanner sc =new Scanner(System.in);
        int m=sc.nextInt();

        int tri[][]=new int[m+1][];

        for(int i=0;i<m;i++){
            tri[i] = new int[i+1];
            for(int j=0;j<=i;j++){
                tri[i][j]=sc.nextInt();
            }
        }

		// 转移方程
        // dp[i][j]=dp[i-1][j]+tri[i][j]; when j==0;
        // dp[i][j]=Math.max(dp[i-1][j-1],dp[i-1][j])+tri[i][j]; when j>0;
        
        int [][]dp=new int[m][m];

        dp[0][0] = tri[0][0];
        for(int i=1;i<m;i++){
            // 最左边的一列只能由最上面的那个转移过来
            dp[i][0] = dp[i-1][0]+tri[i][0];
        }

        for(int i=1;i<m;i++){
            for(int j=1;j<tri[i].length;j++){
                // 不是最左边的那一列可以由同列的和左边那一列的上面转移而来
                dp[i][j]=Math.max(dp[i-1][j-1],dp[i-1][j])+tri[i][j];
            }
        }

        int res=0;
        // 答案在底部的那一行的最大值
        for(int i=0;i<tri[m-1].length;i++){
            res=Math.max(res,dp[m-1][i]);
        }
        System.out.println(res);
    }
}

展开全文 >>

摆花动态规划

题目描述

小明的花店新开张，为了吸引顾客，他想在花店的门口摆上一排花，共m盆。通过调查顾客的喜好，小明列出了顾客最喜欢的n种花，从1到n标号。为了在门口展出更多种花，规定第i种花不能超过$a_i$盆，摆花时同一种花放在一起，且不同种类的花需按标号的从小到大的顺序依次摆列。

试编程计算，一共有多少种不同的摆花方案。

输入格式

第一行包含两个正整数n和m，中间用一个空格隔开。

第二行有n个整数，每两个整数之间用一个空格隔开，依次表示$a_1$,$a_2$,…,$a_n$。

输出格式

一个整数，表示有多少种方案。注意：因为方案数可能很多，请输出方案数对1000007取模的结果。

输入输出样例

输入 #1

1
2
2 4
3 2

输出 #1复制

1
2

说明/提示

【数据范围】

对于20%数据，有0<n≤8,0<m≤8,0≤a_i≤80<n≤8,0<m≤8,0≤a*i*≤8；

对于50%数据，有0<n≤20,0<m≤20,0≤a_i≤200<n≤20,0<m≤20,0≤a*i*≤20；

对于100%数据，有0<n≤100,0<m≤100,0≤a_i≤1000<n≤100,0<m≤100,0≤a*i*≤100。

NOIP 2012 普及组 第三题

自顶向下的动态规划

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

import java.util.*;

class Main{
    
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        int limit[]=new int[n];
        for(int i=0;i<n;i++){
            limit[i]=sc.nextInt();
        }
        
        dp=new int[m+1][n+1];
        System.out.println(dfs(limit,n,m,0)%mod);
        
    }
    static int [][]dp;
    static int mod=1000007;
    public static int dfs(int []limit,int n,int left,int cur){
        if(left<0)return 0;
        if(left==0)return 1;
        if(cur>=n)return 0;
        if(dp[left][cur]!=0)return dp[left][cur];
        
        int val=limit[cur];
        int count=0;
        
        while(val>=0){
            if(left-val>=0){
                count+=dfs(limit,n,left-val,cur+1)%mod;
            }
            val--;
        }
        dp[left][cur]=count;
        
        return count;
    }
    
}

展开全文 >>

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

我是一只<br>又水又笨又菜的<br>菜狗子<br>希望有一天被领走