Qeuroal's Blog

静幽正治

发表于 更新于 分类于

串的定义

  1. 定义：由零个或多个字符组成的有限序列，又名叫字符串
  2. 所谓的序列，说明串的相邻字符之间具有前驱和后继的关系
  3. 子串在主串中的位置就是子串的第一个字符在主串种的序号

串的比较

  1. 串的比较是通过组成串的字符之间的编码来进行的
  2. 字符的编码指的是字符再对应字符集中的序号
  3. 类似于：查字典就是在比较字符串大小的过程

串的抽象数据类型

  1. 字符串与线性表的差别：
    1. 线性表更关注的是单个元素的操作，比如查找一个元素，插入或删除一个元素
    2. 串中更多的是查找子串的位置、得到指定位置子串、替换子串等操作

朴素的模式匹配算法

  1. 子串的定位操作通常称作串的模式匹配
  2. 简单的说，就是对主串的每一个字符作为子串开头，与要匹配的字符串进行匹配。对主串做大循环，每个字符开头做T长度的小循环，指导匹配成功或全部遍历完成为止。
  3. S的长度放在S[0]中，T的长度放在T[0]中
  4. 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int Index(string S, string T, int pos) 
{
      int i = pos;
      int j = 1;
      while (i <= S[0] && j <= T[0]) {
         if (S[i] == T[j]) {
               i++;
               j++;
         }
         else {
               i = i - j + 2;
               j = 1;
         }

      }
      if (j > T[0]) return i - T[0];
      else return 0;
}

KMP模式匹配算法

发表于 更新于 分类于

题目

解析

  1. 类似于 30. 三角形最小路径和
  2. 不同点：比 30. 三角形最小路径和难，难于： 都是一排排的数，而不是三角形，但是思路是一样的，最后看dp[0][6]的值（整体向右挪了一位，并且删除边缘效应，且从上到下，第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
26
27
28
29
30
31
32
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;

const int N = 100010;
int dp[N][13];


int main() {
    int n;
    while(~scanf("%d",&n)) {
        if (n == 0) break;
        int maxt = 0;
        memset(dp, 0, sizeof(dp)); // 为什么不加这个会报错????
        for (int i = 0; i < n; i++) {
            int x, t;
            scanf("%d%d", &x, &t);
            dp[t][x + 1]++;
            maxt = max(maxt, t);
        }

        for (int i = maxt - 1; i >= 0; i--) {
            for (int j = 1; j < 12; j++) {
                dp[i][j] += max(dp[i + 1][j - 1], max(dp[i + 1][j], dp[i + 1][j + 1]));
            }
        }

        cout << dp[0][6] << endl;
    }

    return 0;
}

发表于 更新于 分类于

题目

解析

  1. 从第一个到最后一个字母进行遍历，父循环循环变量(i)决定子串的右端
  2. 其次，子循环循环变量(j)决定子串的左端
  3. 然后，若是j左侧不可拆分，那么就跳过（因为左边无法拆分，即便右边可以拆分也没有意义）
  4. 输出dpn

【释】：dp 负责记录 第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
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>

using namespace std;

int main()
{
    string s;
    int n, nn;
    cin >> s >> nn;
    n = s.size();
    vector<bool> dp(n + 1, false);
    set<string> ss;
    for (int i = 0; i < nn; i++) {
        string t;
        cin >> t;
        ss.insert(t);
    }

    dp[0] = true;
    for (int i = 0; i <= n; i++) {
        for (int j = i; j > 0; j--) {
            if (!dp[j - 1])
                continue;
            if (ss.find(s.substr(j - 1, i - j + 1)) != ss.end()) {
                dp[i] = true;
                break;
            }
        }
    }

    cout << boolalpha << dp[n];
    return 0;
}

发表于 更新于 分类于

基本术语

二叉树性质

  1. 在二叉树得第i(i >= 1)层最多有$2^{i-1}$个节点
  2. 深度为k(k>=1)的二叉树上至多含$2^k-1$个节点
  3. 对任何一颗二叉树，若它含有$n_0$个叶子节点、$n_2$个度为2得节点，则必存在关系式：$n_0=n_2+1$
  4. 具有n个节点的完全二叉树的深度为$\lfloor{\log{_2n}+1} \rfloor$
  5. 若对含n个节点的完全二叉树从上到下且从左到右进行1至n的编号，则对完全二叉树中任意一个编号为i的结点（简称为结点i），有以下关系：
    1. 若i=1，则结点i是二叉树的根，无双亲节点；若i>1,则结点$\lfloor{i/2} \rfloor $为其双亲结点
    2. 若2i>n，则节点i无左孩子;否则结点2i为其左孩子；
    3. 若2i+1>n，则结点i无右孩子；否则，结点2i+1为其右孩子。

定义

  1. 树（Tree）是n(n >= 0 )个结点的有限集。n = 0时称为空树。在任意一棵非空树中：（1）有且仅有一个特定的称为根（root）的结点；（2）在 n > 1 时，其余结点可分为m（m > 0）个互不相交的有限集 $T_1, T_2, T_3 … T_m$，其中每一个集合本身又是一颗树，并且称为根的子树（SubTree）。

  2. n > 0时根结点是唯一的，不可能存在多个根结点。

  3. m > 0时，子树的个数没有限制，但他们一定是互不相交的。

  4. 结点用用改的子树数称为结点的度。

  5. 度为0的结点称为叶子结点或终端结点；度不为0的结点称为非终端结点或分支结点。

  6. 除根结点之外，分支结点称为内部节点。

  7. 树的度是树内各结点度的最大值。

为什么$n$个结点的树，有$n - 1$条边

  1. 假设有1个结点时，则有0条边
  2. 有2个结点时，若是连通的且不能为环，所以就得有$1$条边将这两个结点连接在一起
  3. 若有3个结点时，将前两个看为一个整体，则必须有$1$条边，将这两个部分连接在一起
  4. 以此类推

【释】：整体化一思想

发表于 更新于 分类于
  1. 内存单元从0开始编号，称为内存地址。每个内存单元可以看作一间房间，内存地址就是门牌号。

数据类型

基本数据类型/原始类型（primitive type）

  1. 用于保存简单的单个数据

  2. 首字母一般小写

  3. 基本数据类型：

    1. int (4B)
      Java的整型数字中间可以加入下划线以便用户识别。
    2. short (2B)
    3. long (8B)
    4. byte (1B)
    5. float (4B)
      1. 对于float类型，需要加上f后缀,如: float f = 3.14e5f;
      2. float类型可最大表示 $3.4 \times 10^{38}$
    6. double (8B)
      float类型可最大表示 $1.79 \times 10^{308}$
    7. boolean (1B)

      Java语言对布尔类型的存储并没有做规定，因为理论上存储布尔类型只需要1 bit，但是通常JVM内部会把boolean表示为4字节整数。

    8. char (2B)
      1. 布尔类型boolean只有true和false两个值
      2. 字符类型char表示一个字符。Java的char类型除了可表示标准的ASCII外，还可以表示一个Unicode字符，如： char a = '中';
      3. 注意char类型使用单引号’，且仅有一个字符，要和双引号”的字符串类型区分开。

  4. 引用类型

    1. 除了上述基本类型的变量，剩下的都是引用类型。例如，引用类型最常用的就是String字符串: String s = "hello";
    2. 引用类型的变量类似于C语言的指针，它内部存储一个“地址”，指向某个对象在内存的位置.

    通俗的解释：引用类型的变量赋值，先申请内存存放内容，然后变量再指向它，若改变变量的值，则会再重新申请内存，放入内容，再将变量指向这块内存，原来的内存还在只不过无法通过变量指向它罢了。

  5. 常量

> 1. 定义变量的时候，如果加上final修饰符，这个变量就变成了常量

   
1
2
3
4
final double PI = 3.14; // PI是一个常量
double r = 5.0;
double area = PI * r * r;
PI = 300; // compile error!

> 2. 常量在定义时进行初始化后就不可再次赋值，再次赋值会导致编译错误。
> 3. 常量的作用是用有意义的变量名来避免魔术数字（Magic number），例如，不要在代码中到处写3.14，而是定义一个常量。如果将来需要提高计算精度，我们只需要在常量的定义处修改，例如，改成3.1416，而不必在所有地方替换3.14。
> 4. 根据习惯，常量名通常全部大写。
  1. var关键字
> 1. 有些时候，类型的名字太长，写起来比较麻烦。例如：`StringBuilder sb = new StringBuilder();`, 这个时候，如果想省略变量类型，可以使用var关键字： `var sb = new StringBuilder();`,编译器会根据赋值语句自动推断出变量sb的类型是StringBuilder。对编译器来说，语句：`var sb = new StringBuilder();`,实际上会自动变成：`StringBuilder sb = new StringBuilder();`
> 2. 使用var定义变量，仅仅是少写了变量类型而已。

  1. 定义变量时，要遵循作用域最小化原则，尽量将变量定义在尽可能小的作用域，并且，不要重复使用变量名。

  2. 整数运算

    1. 整数的数值表示不但是精确的，而且整数运算永远是精确的，即使是除法也是精确的，因为两个整数相除只能得到结果的整数部分
    2. 特别注意：整数的除法对于除数为0时运行时将报错，但编译不会报错
    3. 要特别注意，整数由于存在范围限制，如果计算结果超出了范围，就会产生溢出，而溢出不会出错，却会得到一个奇怪的结果
    4. 自增/自减、+=，-=，*=，/=：同C++
    5. 移位运算
      1. >>: 根据符号位来补充
      2. 无符号的右移运算>>>: 它的特点是不管符号位，右移后高位总是补0
    6. 位运算
      1. 与运算: &
      2. 或运算: |
      3. 非运算: ~
      4. 异或运算: ^

  3. 运算优先级

    • ()
    • ! ~ ++ --
    • * / %
    • + -
    • << >> >>>
    • &
    • |
    • += -= *= /=

  4. 浮点数运算

    1. 浮点数运算会产生误差

      浮点数运算和整数运算相比，只能进行加减乘除这些数值计算，不能做位运算和移位运算。在计算机中，浮点数虽然表示的范围大，但是，浮点数有个非常重要的特点，就是浮点数常常无法精确表示。

      举个栗子：

      浮点数0.1在计算机中就无法精确表示，因为十进制的0.1换算成二进制是一个无限循环小数，很显然，无论使用float还是double，都只能存储一个0.1的近似值。但是，0.5这个浮点数又可以精确地表示。

      因为浮点数常常无法精确表示，因此，浮点数运算会产生误差:

      1
      2
      3
      4
      5
      6
      7
      8
      9
      public class Main {
          public static void main(String[] args) {
              double x = 1.0 / 10;
              double y = 1 - 9.0 / 10;
              // 观察x和y是否相等:
              System.out.println(x);
              System.out.println(y);
          }
      }

      结果为：

      1
      2
      0.1
      0.09999999999999998

    2. 溢出

      整数运算在除数为0时会报错，而浮点数运算在除数为0时，不会报错，但会返回几个特殊值：

      1. NaN表示Not a Number
      2. Infinity表示无穷大
      3. Infinity表示负无穷大
        如：
      1
      2
      3
      double d1 = 0.0 / 0; // NaN
      double d2 = 1.0 / 0; // Infinity
      double d3 = -1.0 / 0; // -Infinity

  5. 布尔运算

    1. 布尔运算是一种关系运算，包括以下几类：
      • 比较运算符：>，>=，<，<=，==，!=
      • 与运算 &&
      • 或运算 ||
      • 非运算 !
    2. 关系运算符的优先级从高到低依次是
      • !
      • >，>=，<，<=
      • ==，!=
      • &&
      • ||
    3. 短路运算、三元运算符：同C++

  6. 字符与字符串

    1. 字符类型

      Java在内存中总是使用Unicode表示字符，所以，一个英文字符和一个中文字符都用一个char类型表示，它们都占用两个字节。要显示一个字符的Unicode编码，只需将char类型直接赋值给int类型即可

      1
      2
      int n1 = 'A'; // 字母“A”的Unicodde编码是65
      int n2 = '中'; // 汉字“中”的Unicode编码是20013

    2. 字符串类型

      和char类型不同，字符串类型String是引用类型，我们用双引号"..."表示字符串。一个字符串可以存储0个到任意个字符：

      1. 常见的转义字符包括：

        • \" 表示字符"
        • \' 表示字符'
        • \\ 表示字符\
        • \n 表示换行符
        • \r 表示回车符
        • \t 表示Tab
        • \u#### 表示一个Unicode编码的字符

      2. 字符串连接

        Java的编译器对字符串做了特殊照顾，可以使用+连接任意字符串和其他数据类型，这样极大地方便了字符串的处理。例如：

        1
        2
        3
        4
        5
        6
        7
        8
        public class Main {
            public static void main(String[] args) {
                String s1 = "Hello";
                String s2 = "world";
                String s = s1 + " " + s2 + "!";
                System.out.println(s);
            }
        }

        如果用+连接字符串和其他数据类型，会将其他数据类型先自动转型为字符串，再连接：

        1
        2
        3
        4
        5
        6
        7
        public class Main {
            public static void main(String[] args) {
                int age = 25;
                String s = "age is " + age;
                System.out.println(s);
            }
        }

      3. 多行字符串

        如果我们要表示多行字符串，使用+号连接会非常不方便：

        从Java 13开始，字符串可以用”””…”””表示多行字符串（Text Blocks）了。举个例子：

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        public class Main {
            public static void main(String[] args) {
                String s = """
                           SELECT * FROM
                             users
                           WHERE id > 100
                           ORDER BY name DESC
                           """; // 因为""" 换行了，所以相当于在 DESC 后面加了一个\n
                System.out.println(s);
            }
        }

        如果多行字符串的排版不规则，总是以最短的行首空格为基准。

      4. 不可变特性

        String s = “hello”;时，JVM虚拟机先创建字符串”hello”，然后，把字符串变量s指向它：紧接着，执行s = “world”;时，JVM虚拟机先创建字符串”world”，然后，把字符串变量s指向它：原来的字符串”hello”还在，只是我们无法通过变量s访问它而已。因此，字符串的不可变是指字符串内容不可变。

        理解了引用类型的“指向”后，试解释下面的代码输出：

        1
        2
        3
        4
        5
        6
        7
        8
        public class Main {
            public static void main(String[] args) {
                String s = "hello";
                String t = s;
                s = "world";
                System.out.println(t); // t是"hello"还是"world"?
            }
        }

      5. 空值null

        引用类型的变量可以指向一个空值null，它表示不存在，即该变量不指向任何对象。例如：

        1
        2
        3
        4
        String s1 = null; // s1是null
        String s2; // 没有赋初值值，s2也是null
        String s3 = s1; // s3也是null
        String s4 = ""; // s4指向空字符串，不是null

        注意要区分空值null和空字符串””，空字符串是一个有效的字符串对象，它不等于null。

  7. 数组

    1. 定义一个数组类型的变量，使用数组类型 类型[]，例如，int[]。和单个基本类型变量不同，数组变量初始化必须使用new int[5]表示创建一个可容纳5个int元素的数组。

    2. Java的数组有几个特点：

      • 数组所有元素初始化为默认值，整型都是0，浮点型是0.0，布尔型是false；
      • 数组一旦创建后，大小就不可改变。

    3. 数组大小：数组变量.length

    4. 数组是引用类型，在使用索引访问数组元素时，如果索引超出范围，运行时将报错

    5. 在定义数组时直接指定初始化的元素，这样就不必写出数组大小，而是由编译器自动推算数组大小

    6. 对于数组ns来说，执行ns = new int[] { 68, 79, 91, 85, 62 };时，它指向一个5个元素的数组；再执行ns = new int[] { 1, 2, 3 };时，它指向一个新的3个元素的数组：但是，原有的5个元素的数组并没有改变，只是无法通过变量ns引用到它们而已。

    7. 字符串数组

      1
      2
      3
      String[] names = {
          "ABC", "XYZ", "zoo"
      };

      对names[1]进行赋值，例如names[1] = "cat";，原来names[1]指向的字符串”XYZ”并没有改变，仅仅是将names[1]的引用从指向”XYZ”改成了指向”cat”，其结果是字符串”XYZ”再也无法通过names[1]访问到了。

      相当于引用嵌套引用

    8. 遍历数组

      1. 方法1

        1
        2
        3
        4
        for (int i=0; i<ns.length; i++) {
            int n = ns[i];
            System.out.println(n);
        }

      2. 方法2: for each 循环

        1
        2
        3
        4
        int[] ns = { 1, 4, 9, 16, 25 };
        for (int n : ns) {
            System.out.println(n);
        }

        变量n直接拿到ns数组的元素，而不是索引。

        若想直接打印ns，可以这么做：System.out.println(Arrays.toString(ns));

    9. 排序数组

      1. 冒泡排序

      2. Java的标准库已经内置了排序功能: Arrays.sort()，例如：

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        import java.util.Arrays;

        public class Main {
            public static void main(String[] args) {
                int[] ns = { 28, 12, 89, 73, 65, 18, 96, 50, 8, 36 };
                // 排序前:
                System.out.println(Arrays.toString(ns));
                // 排序
                Arrays.sort(ns);
                // 排序后：
                System.out.println(Arrays.toString(ns));
            }
        }
        1. 当我们调用Arrays.sort(ns);后，变量ns指向的数组内容已经被改变了
        2. 如果对一个字符串数组(String[] ns = { "banana", "apple", "pear" };)进行排序，原来的3字符串在内存中均没有任何变化，但是ns数组的每个元素指向变化了

    10. 多维数组

      1. 例子

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        public class Main {
            public static void main(String[] args) {
                int[][] ns = {
                    { 1, 2, 3, 4 },
                    { 5, 6, 7 },
                    { 9, 10, 11, 12 }
                };
                int[] arr1 = ns[1];
                System.out.println(arr0.length); // 4
            }
        }

        实际上arr1就获取了ns数组的第1个元素。因为ns数组的每个元素也是一个数组，因此，arr1指向的数组就是{ 5, 6, 7 }

      2. 遍历

        1
        2
        3
        4
        5
        6
        7
        for (int[] arr : ns) {
            for (int n : arr) {
                System.out.print(n);
                System.out.print(', ');
            }
            System.out.println();
        }

      3. 小结

        • 二维数组就是数组的数组，三维数组就是二维数组的数组；
        • 多维数组的每个数组元素长度都不要求相同；
        • 打印多维数组可以使用Arrays.deepToString()；
        • 最常见的多维数组是二维数组，访问二维数组的一个元素使用array[row][col]

  8. 命令行参数

    Java程序的入口是main方法，而main方法可以接受一个命令行参数，它是一个String[]数组。

    这个命令行参数由JVM接收用户输入并传给main方法：

    1
    2
    3
    4
    5
    6
    7
    public class Main {
        public static void main(String[] args) {
            for (String arg : args) {
                System.out.println(arg);
            }
        }
    }

    我们可以利用接收到的命令行参数，根据不同的参数执行不同的代码。例如，实现一个-version参数，打印程序版本号：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    public static void main(String[] args) {
        for (String arg : args) {
            System.out.println(arg);
            if ("-version".equals(arg)) {
                System.out.println("v 1.0");
            } else if ("-test".equals(arg)) {
                System.out.println("test");
            }
        }
    }

    上面这个程序必须在命令行执行，我们先编译它： javac Main.java

    然后，执行的时候，给它传递一个-version参数：java Main -version -version -test

  9. I/O

    1. 输出

      1. 输出语句
        • System.out.println()
        • System.out.printf()
      2. 占位符
        占位符 说明
        %d 格式化输出整数
        %x 格式化输出十六进制整数
        %f 格式化输出浮点数
        %e 格式化输出科学计数法表示的浮点数
        %s 格式化字符串

        注意，由于%表示占位符，因此，连续两个%%表示一个%字符本身。

      占位符本身还可以有更详细的格式化参数。下面的例子把一个整数格式化成十六进制，并用0补足8位：

    2. 输入

      1. import语句导入java.util.Scanner，import是导入某个类的语句，必须放到Java源代码的开头
      2. 创建 Scanner 对象并传入 System.in。System.out 代表标准输出流，而System.in代表标准输入流。直接使用System.in读取用户输入虽然是可以的，但需要更复杂的代码，而通过Scanner就可以简化后续的代码。
      3. Scanner对象后，要读取用户输入的字符串，使用scanner.nextLine()，要读取用户输入的整数，使用scanner.nextInt()。Scanner会自动转换数据类型，因此不必手动转换。
        例如：
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      import java.util.Scanner;

      public class Main {
          public static void main(String[] args) {
              Scanner scanner = new Scanner(System.in); // 创建Scanner对象
              System.out.print("Input your name: "); // 打印提示
              String name = scanner.nextLine(); // 读取一行输入并获取字符串
              System.out.print("Input your age: "); // 打印提示
              int age = scanner.nextInt(); // 读取一行输入并获取整数
              System.out.printf("Hi, %s, you are %d\n", name, age); // 格式化输出
          }
      }

    3. 使用占位符构建字符串，并打印

      1
      2
      String <name> = String.format("%-10d%d", 20, 25)
      System.out.println(<name>)

发表于 更新于 分类于

sort() —— 排序

  • 导入头文件：#include <algorithm>

  • 使用模板

    1. sort(start, end)
    2. sort(start, end, cmp)

      Ps:

  1. 符号说明
符号 说明
start 起始地址
end 终止地址
cmp 自定义函数
  1. sort()函数，若没有cmp（第三个参数），则默认从小到大排序
  2. start和end，也可以传入迭代器的始末地址

  • cmp函数如何写

  1. 从大到小排序

代码

1
2
3
4
bool cmp(int a, int b)
{
    return a > b;
}
  1. 自定义排序，以两门成绩（假设第一门成绩为语文，第二门成绩为数学）为例，语文成绩以从小到大排序，若语文成绩相同，则数学成绩从小到大排序

代码

1
2
3
4
5
6
7
bool cmp(pair<int, int>& a, pair<int, int>& b)
{
    if(a.first != b.first)
        return a.first < b.first;
    else
        return a.second > b.second;
}

发表于 更新于 分类于

题目

示例

解析

  1. 令f[i][j]存储：从 (0, 0) 到 (i, j) 的路径个数
  2. 而一步到 (i, j) 最多只有两个路径：从左面或者从上面
  3. 那么，接下来判断，是否能从左面或者上面到 (i, j)，如果可以，那么 f(i, j) 加上左面或者上面的路径个数即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    int m = obstacleGrid.size(), n = obstacleGrid[0].size();
    if(obstacleGrid[0][0])
        return 0;
    vector<vector<long long> > f(m, vector<long long>(n));
    f[0][0] = 1;
    for(int i = 0; i < m; i++)
        for(int j = 0; j < n; j++) {
            // if(i || j) f[i][j] = 0; （可有，可无，因为 ：f默认都是0）
            if(!obstacleGrid[i][j]) {
                if(i) f[i][j] += f[i - 1][j];
                if(j) f[i][j] += f[i][j - 1];
            }
        }
    return f[m - 1][n - 1];
}

疑问

f为int型， 为什么会报错 ？？？ 

1
Line 27: Char 65: runtime error: signed integer overflow: 1053165744 + 1579748616 cannot be represented in type 'int' (solution.cpp)`

发表于 更新于 分类于

题目

解析

DFS

  1. 首先判断是否为image是否为空，如果是，则返回image
  2. 然后，保存老的颜色值，即为 old，并判断 old 是否与 newColor 相同，如果是，则返回image
  3. 接着，对周围的这些点进行遍历，符合条件的，进入递归
  4. 最后，返回image

BFS

  1. 首先判断是否为image是否为空，如果是，则返回image
  2. 然后，保存老的颜色值，即为 old，并判断 old 是否与 newColor 相同，如果是，则返回image
  3. 创建队列，类型为 pair<int, int> 类型，将image[sr][sc]入队；
  4. 对队列 q 进行遍历，将 q.front() 变为 newColor，然后，遍历周围的点，符合条件的入队
  5. 最后，返回image

代码

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<vector<int> > floodFill(vector<vector<int> >& image, int sr, int sc, int newColor) {
    if(image.empty() || image[0].empty())
        return image;
    int old = image[sr][sc];
    if(old == newColor)
        return image;
    int next[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
    image[sr][sc] = newColor;
    for(int i = 0; i < 4; i++) {
        int nSr = sr + next[i][0], nSc = sc + next[i][1];
        if(nSr >= 0 && nSr < image.size() && nSc >= 0 && nSc < image[0].size() && image[nSr][nSc] == old)
            floodFill(image, nSr, nSc, newColor);
    }
    return image;
}

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<vector<int> > floodFill(vector<vector<int> >& image, int sr, int sc, int newColor) {
    if(image.empty() || image[0].empty())
        return image;
    int old = image[sr][sc];
    if(old == newColor) {
        return image;
    }
    int next[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
    queue<pair<int, int> > q;
    q.push(pair<int, int>(sr, sc));
    while(q.size()) {
        pair<int, int> t = q.front();
        q.pop();
        image[t.first][t.second] = newColor;
        for(int i = 0; i < 4; i++) {
            int nx = t.first + next[i][0], ny = t.second + next[i][1];
            if(nx >= 0 && nx < image.size() && ny >= 0 && ny < image[0].size() && image[nx][ny] == old) {
                q.push(pair<int, int>(nx, ny));
            }
        }
    }
    return image;
}

发表于 更新于 分类于

题目

解析

  1. 最小路径就是和相邻的两行有关系
  2. 由于，从上往下有些麻烦，所以，从下往上
  3. 首先，把最后一行的数据，存入 vector<int> f 中，并且 vector<int> g 保存：两行中，上面一行与下面相邻两个元素相加之和的最小数组
  4. 比如：以最后两行为例
  5. f 此时为 [4, 1, 8, 3]
    g 此时为 [0, 0, 0, 0]
  6. 然后，g 就更新为 [7, 6, 10, 0]
  7. f 也就更新为 g，即为： [7, 6, 10, 0]
  8. 依次类推
  9. 最后，f[0]就是，第一个数，与下面最小的数相加的和，即为最短路径

Note

  1. 如果不懂，就自己调试一下吧
  2. 这里是动态规划，更新的是g和f（首先更新g，接着将g赋值给f）
  3. 其中f，总是为最后一行最小数的数组：
    1. 比如：一开始为 [4, 1, 8, 3] ，后来状态转移为：[7, 6, 10, 0]
    2. 那么 [7, 6, 10, 0] 可以看成最后一行（替换后面两行，依次类推）

代码

1
2
3
4
5
6
7
8
9
10
11
12
int minimumTotal(vector<vector<int> > &triangle)
{
   int n = triangle.size();
   vector<int> f(triangle[n - 1].begin(), triangle[n - 1].end()), g(n);
   for(int i = n - 2; i >= 0; i--) {
      for(int j = 0; j <= i; j++) {
            g[j] = min(f[j], f[j + 1]) + triangle[i][j];
      }
      f = g;
   }
   return f[0];
}

简化

1
2
3
4
5
6
7
8
9
10
11
12
int minimumTotal(vector<vector<int>>& triangle) {
   int n = triangle.size();
   vector<int> f(triangle[n - 1].begin(), triangle[n - 1].end());

   for(int i = n - 2; i >= 0; i--) {
         for(int j = 0; j <= i; j++) {
            f[j] = min(f[j], f[j + 1]) + triangle[i][j];
         }

   }
   return f[0];
}

Note

  1. 相比于上面的代码，下面的代码删除了 g
  2. 原因：因为 f[j] 改变，对 f[j + 1] 并没有影响，所以就不需要 g 了。

发表于 更新于 分类于

题目

解析

同 733. 图像渲染

代码

DFS

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
void dfs(vector<vector<char>>& grid, int x, int y)
{
    int next[4][2] = { {0, 1}, {1, 0},  {0, -1}, {-1, 0} };
    grid[x][y] = '0';
    for(int i = 0; i < 4; i++) {
        int nx = x + next[i][0];
        int ny = y + next[i][1];
        if(nx >= 0 && nx < grid.size() && ny >= 0 && ny < grid[0].size() && grid[nx][ny] == '1')
            dfs(grid, nx, ny);
    }

}

int numIslands(vector<vector<char>>& grid) {
    if(grid.empty() || grid[0].empty())
        return 0;
    int res = 0;
    int m = grid.size(), n = grid[0].size();
    for(int i = 0; i < m; i++) 
        for(int j = 0; j < n; j++) 
            if(grid[i][j] == '1') {
                res++;
                dfs(grid, i, j);
            }

    return res;
}

BFS

RE?

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
int numIslands(vector<vector<char>>& grid) {
    if(grid.empty() || grid[0].empty())
        return 0;
    int next[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
    int landCount = 0;
    for(int i = 0; i < grid.size(); i++) {
        for(int j = 0; j < grid[0].size(); j++) {

            if(grid[i][j] == '1') {
                landCount++;
                queue<pair<int, int> > q;
                q.push(pair<int, int> (i, j));
                while(q.size()) {
                    pair<int, int> t = q.front();
                    q.pop();
                    grid[t.first][t.second] = '0';
                    for(int k = 0; k < 4; k++) {
                        int ni = t.first + next[k][0], nj = t.second + next[k][1];
                        if(ni >= 0 && ni < grid.size() && nj >= 0 && nj < grid[0].size() && grid[ni][nj] == '1')
                            q.push(pair<int, int> (ni, nj));
                    }
                }
            }
        }
    }
    return landCount;
}
0%