LeetCode 1662. 检查两个字符串数组是否相等 / 795. 区间子数组个数 / 剑指 Offer 47. 礼物的最大价值

1662. 检查两个字符串数组是否相等

2022.11.1 新的一月又开始了

题目描述

给你两个字符串数组 word1 和 word2 。如果两个数组表示的字符串相同，返回 true ；否则，返回 false 。

数组表示的字符串 是由数组中的所有元素 按顺序 连接形成的字符串。

示例 1：

输入：word1 = [“ab”, “c”], word2 = [“a”, “bc”]
输出：true
解释：
word1 表示的字符串为 “ab” + “c” -> “abc”
word2 表示的字符串为 “a” + “bc” -> “abc”
两个字符串相同，返回 true

示例 2：

输入：word1 = [“a”, “cb”], word2 = [“ab”, “c”]
输出：false

示例 3：

输入：word1 = [“abc”, “d”, “defg”], word2 = [“abcddefg”]
输出：true

提示：

1 <= word1.length, word2.length <= 10^3
1 <= word1[i].length, word2[i].length <= 10^3
1 <= sum(word1[i].length), sum(word2[i].length) <= 10^3
word1[i] 和 word2[i] 由小写字母组成

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/check-if-two-string-arrays-are-equivalent
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

主要记住join

class Solution:def arrayStringsAreEqual(self, word1: List[str], word2: List[str]) -> bool:return ''.join(word1) == ''.join(word2)

class Solution {public boolean arrayStringsAreEqual(String[] word1, String[] word2) {return String.join("", word1).equals(String.join("", word2));}
}

795. 区间子数组个数

2022.11.24 每日一题

题目描述

给你一个整数数组 nums 和两个整数：left 及 right 。找出 nums 中连续、非空且其中最大元素在范围 [left, right] 内的子数组，并返回满足条件的子数组的个数。

生成的测试用例保证结果符合 32-bit 整数范围。

示例 1：

输入：nums = [2,1,4,3], left = 2, right = 3
输出：3
解释：满足条件的三个子数组：[2], [2, 1], [3]

示例 2：

输入：nums = [2,9,2,5,6], left = 2, right = 8
输出：7

提示：

1 <= nums.length <= 10^5
0 <= nums[i] <= 10^9
0 <= left <= right <= 10^9

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/number-of-subarrays-with-bounded-maximum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

如注释所写，我第一反应是找区间，找一个数左右第一个比他大的数，用单调栈
但是写的时候发现不知道怎么处理两个数相同的情况，所以感觉行不通
但是在题解区看到了这个写法，具体见第二个代码

class Solution:def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:# 想想该怎么写，对于一个在这个范围内的数字而言，# 它和其余比它小数字组成的子数组肯定是满足条件的# 那么找到一个数，左右比他大的数# 在这个区间内，所有包含他的子数组都是满足条件的# 那么会不会重复呢，比它大的数它肯定不包含，比他小的数的区间不会包含它# 所以不会重复，但是相等的时候怎么处理呢，不知道怎么做了# 看了一下标签，是双指针# 那么就想想双指针，遇到第一个满足条件的数，就开始，# 左边指针放在第一个满足条件区间的最左边# idx1 表示上一个出现合理数字的位置# idx2 表示上一个出现过大数字的位置idx1, idx2 = -1, -1res = 0for i, n in enumerate(nums):# 对于当前右端点i来说,idx2到idx1之间都可以是他的左端点if n > right:idx2 = ielif left <= n <= right:idx1 = iif idx1 - idx2 > 0:res += idx1 - idx2return res

这个是单调栈的思路，处理相同元素的方法就是一边包含相同元素，一边不包含
例如在找右边最大值的时候，不包含等于的；左边最大值的时候，包含等于的

class Solution:def numSubarrayBoundedMax(self, nums: List[int], a: int, b: int) -> int:n, ans = len(nums), 0l, r = [-1] * n, [n] * nstk = []for i in range(n):while stk and nums[stk[-1]] < nums[i]:r[stk.pop()] = istk.append(i)stk = []for i in range(n - 1, -1, -1):while stk and nums[stk[-1]] <= nums[i]:l[stk.pop()] = istk.append(i)for i in range(n):if a <= nums[i] <= b:ans += (i - l[i]) * (r[i] - i)return ans

第三个方法，区间的计数，找在left到right之间的，那么可以找小于right的，和小于left的，然后相减，就是中间的
而找小于一个数的区间很简单，就是对大于的不处理，小于等于的一直累加就可以了

class Solution:def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:def count(lower: int) -> int:res = cur = 0for x in nums:if x <= lower:cur += 1else:cur = 0res += curreturn resreturn count(right) - count(left - 1)

剑指 Offer 47. 礼物的最大价值

2023.3.8 每日一题

题目描述

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

示例 1:

输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物

提示：

0 < grid.length <= 200
0 < grid[0].length <= 200

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

最简单的动态规划，好久不练了

class Solution {public int maxValue(int[][] grid) {//这种最简单的动态规划都不会写了int m = grid.length;int n = grid[0].length;int[][] dp = new int[m][n];dp[0][0] = grid[0][0];for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(i > 0){dp[i][j] = dp[i - 1][j] + grid[i][j];}if(j > 0){dp[i][j] = Math.max(dp[i][j], dp[i][j - 1] + grid[i][j]);}}}return dp[m - 1][n - 1];}
}

滚动数组+多开一行

class Solution:def maxValue(self, grid: List[List[int]]) -> int:m, n = len(grid), len(grid[0])# 多创建一行一列，省去判断dp = [[0] * (n + 1) for _ in range(2)]for i in range(1, m + 1):for j in range(1, n + 1):pos = i % 2dp[pos][j] = max(dp[1 - pos][j] + grid[i - 1][j - 1], dp[pos][j - 1] + grid[i - 1][j - 1])return dp[m % 2][n]

一个数组

class Solution:def maxValue(self, grid: List[List[int]]) -> int:m, n = len(grid), len(grid[0])dp = [0] * (n + 1)for row in grid:for j, x in enumerate(row):dp[j + 1] = max(dp[j], dp[j + 1]) + xreturn dp[n]