学校网站建设目的是什么意思,网络营销工具的特点,网站设计公司 北京,java 做直播网站有哪些软件下载1662. 检查两个字符串数组是否相等
2022.11.1 新的一月又开始了
题目描述
给你两个字符串数组 word1 和 word2 。如果两个数组表示的字符串相同#xff0c;返回 true #xff1b;否则#xff0c;返回 false 。
数组表示的字符串 是由数组中的所有元素 按顺序 连接形成的…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]
