Leetcode每日一题

基本知识

关于二维数组的操作：

一个二维数组Matrix分为很多个一维子数组。

例如：int[][] matrix = { {0, -1, 2}, {-1, 5, 6}, {7, 8, -1} }; 分为三个子数组{0 -1 2} {-1 5 6} {7 8 -1}

如何确定二维数组的列和行？ 列：matrix[0].length //意味着第0个子数组有几个元素 行：matrix.length //意味着有几个子数组。

如何遍历一个二维数组？for (int[] row: matrix) {} //它表示对于 matrix中的每一个 row（每一个子数组），执行循环体内的操作

题目：修改矩阵 3033

给你一个下标从 0 开始、大小为 m x n 的整数矩阵 matrix ，新建一个下标从 0 开始、名为 answer 的矩阵。使 answer 与 matrix 相等，接着将其中每个值为 -1 的元素替换为所在列的 最大 元素。

返回矩阵 answer 。

pkRIdLF.png

1
2
3
4
5
输入：matrix = [[1,2,-1],[4,-1,6],[7,8,9]]
输出：[[1,2,9],[4,8,6],[7,8,9]]
解释：上图显示了发生替换的元素（蓝色区域）。
- 将单元格 [1][1] 中的值替换为列 1 中的最大值 8 。
- 将单元格 [0][2] 中的值替换为列 2 中的最大值 9 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[][] modifiedMatrix(int[][] matrix) {
        for (int j = 0; j < matrix[0].length; j++) {
           int flag = 0;
           for (int[] row: matrix) {
               flag = Math.max(flag,row[j]);
           }
           for (int[] row: matrix) {
               if (row[j] == -1) {
                   row[j] = flag;
               }
           }
        }
        return matrix;
    }
}

题目：交替子数组计数 3101

给你一个

二进制数组

nums 。

如果一个

子数组

中 不存在 两个 相邻 元素的值 相同 的情况，我们称这样的子数组为 交替子数组 。

返回数组 nums 中交替子数组的数量。

示例 1：

输入： nums = [0,1,1,1]

输出： 5

解释：

以下子数组是交替子数组：[0] 、[1] 、[1] 、[1] 以及 [0,1] 。

示例 2：

输入： nums = [1,0,1,0]

输出： 10

解释：

数组的每个子数组都是交替子数组。可以统计在内的子数组共有 10 个。

提示：

  • 1 <= nums.length <= 105
  • nums[i] 不是 0 就是 1 。

思路：遍历数组统计右端点下标i，如果一个子数组元素均不相等，那这个子数组统计结果就是其本身的元素个数

例如：

pkWQiIf.png

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public long countAlternatingSubarrays(int[] nums) {
      int count = 0;
        long ans = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] != nums[i - 1]) count += 1;
            else count = 1;
            ans +=count;
        }
        
        return ans;
    }
}

题目：最大公共子序列 1143

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

  • 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：

1
2
3
输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。

示例 2：

1
2
3
输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。

示例 3：

1
2
3
输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。

提示：

  • 1 <= text1.length, text2.length <= 1000
  • text1 和 text2 仅由小写英文字符组成。

思路：这是一个经典的动态规划问题，首先在这里我们把动态规划问题说清楚

动态规划三要素：重叠子问题、最优子结构、状态转移方程

动态规划是为了解决最值而产生的算法，动态规划的本质就是穷举，但是穷举是有特点的穷举，就是找到重叠子问题的穷举，利用DP Table和备忘录来优化穷举，也要找出状态转移方程

状态转移方程：

  • 这个问题最简单的情况（base case）是什么

  • 这个问题会有什么“状态”

  • 对于每一“状态”，可以做出什么选择使之改变。

  • 如何定义dp数组/函数来表现“状态”和“选择”。

模板如下：

1
2
3
4
5
6
//初始化最简单的情况（base case）
dp[0][0] = base case
for 状态1 in 状态1所有的取值
    for 状态2 in 状态2所有的取值
        ....
        dp[状态1][状态2] = 求最值(选择1，选择2)

对这个题进行一个定义描述

第一个Text1 定义一个数组s1[i]

第二个Text2 定义一个数组s2[j]

dp数组定义：dp[i] [j] 就是s1数组前i个字符和s2数组前j个字符的最长公共子序列

先寻找以下这道题的状态转移方程

  1. 如果两个Text的最后一个字母相同，那么我们的最终答案就是d[i] [j] = 1+ d[i]-1 [j-1]
  2. 如果两个Text的最后一个字母不相同，则答案就是去掉s1的最后一个字母的公共子序列或者是去掉s2的最后一个字母的公共子序列 d[i] [j] = max(d[i-1] [j], d[i] [j-1])

再分析以下初始情况

d[0] [0] = 0 d[0] [j] = 0 d[i] [0] = 0

最后我们分析以下DP Table

pkhnkuR.png

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
       public int longestCommonSubsequence(String text1, String text2) {
           char[] s1 = text1.toCharArray();
           char[] s2 = text2.toCharArray();
           int m = s1.length;
           int n = s2.length;
           int[][] dp = new int[m + 1][n + 1];
           for (int i = 1; i <= m; i++) {
               for (int j = 1; j <= n; j++) {
                   if (s1[i - 1] == s2[j - 1]) dp[i][j] = (1 + dp[i - 1][j - 1]);
                   else dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
               }
           }
           return dp[m][n];
       }
   }