2206. 将数组划分成相等数对-简单
题目描述:
给你一个整数数组 nums ,它包含 2 * n 个整数。
你需要将 nums 划分成 n 个数对,满足:
每个元素 只属于一个 数对。
同一数对中的元素 相等 。
如果可以将 nums 划分成 n 个数对,请你返回 true ,否则返回 false
题解:
哈希表统计各元素数量,如果有不能被2整除的就返回false
代码(Go):文章来源:https://www.toymoban.com/news/detail-513039.html
func divideArray(nums []int) bool {
dict := map[int]int{}
for _,v := range nums{
dict[v]++
}
for _,v := range dict{
if v%2 == 1{
return false
}
}
return true
}
1920. 基于排列构建数组-简单
题目描述:
给你一个 从 0 开始的排列 nums(下标也从 0 开始)。请你构建一个 同样长度 的数组 ans ,其中,对于每个 i(0 <= i < nums.length),都满足 ans[i] = nums[nums[i]] 。返回构建好的数组 ans 。
从 0 开始的排列 nums 是一个由 0 到 nums.length - 1(0 和 nums.length - 1 也包含在内)的不同整数组成的数组。
题解:
按描述模拟即可
代码(Go):
func buildArray(nums []int) []int {
ans := make([]int,len(nums))
for i,v := range nums{
ans[i] = nums[v]
}
return ans
}
1253. 重构 2 行二进制矩阵-中等
题目描述:
给你一个 2 行 n 列的二进制数组:
矩阵是一个二进制矩阵,这意味着矩阵中的每个元素不是 0 就是 1。
第 0 行的元素之和为 upper。
第 1 行的元素之和为 lower。
第 i 列(从 0 开始编号)的元素之和为 colsum[i],colsum 是一个长度为 n 的整数数组。
你需要利用 upper,lower 和 colsum 来重构这个矩阵,并以二维整数数组的形式返回它。
如果有多个不同的答案,那么任意一个都可以通过本题。
如果不存在符合要求的答案,就请返回一个空的二维数组。
题解:
优先从行元素之和更大的一行开始放,如果等于2就直接放,放完2再遍历一遍放1,直到这一行放不下,换另一行放1,如果放不下或者没放完就返回空数组
代码(Go):
func reconstructMatrix(upper int, lower int, colsum []int) [][]int {
flag := 1
if upper < lower{
upper,lower = lower,upper
flag = 0
}
re := make([][]int,2)
for i,_ := range re{
temp := make([]int,len(colsum))
re[i] = temp
}
sum := upper + lower
for j := 0;j < len(colsum);j++{
if colsum[j] == 2 && sum > lower{
re[0][j] = 1
colsum[j]--
sum--
}
}
for j := 0;j < len(colsum);j++{
if colsum[j] == 1 && sum > lower && re[0][j] == 0{
re[0][j] = 1
colsum[j]--
sum--
}
}
if sum != lower{
return [][]int{}
}
for j := 0;j < len(colsum);j++{
if colsum[j] > 0 && sum > 0{
re[1][j] = 1
sum--
}else if colsum[j] > 0{
return [][]int{}
}
}
if sum != 0{
return [][]int{}
}
if flag == 0{
re[0],re[1] = re[1],re[0]
}
return re
}
673. 最长递增子序列的个数-中等
题目描述:
给定一个未排序的整数数组 nums , 返回最长递增子序列的个数 。
注意 这个数列必须是 严格 递增的。
题解:
在昨天那道题的基础上增加了统计数量,方法就是把一维dp变成二维,增加一位用来记录当前长度递增子序列的数目,其实就相当于同时进行了两个动态规划,最后找出最长的长度并统计数量即可
代码(Go):
func findNumberOfLIS(nums []int) int {
dp := make([][]int,len(nums))
for i,_ := range dp{
temp := make([]int,2)
dp[i] = temp
}
dp[0][0] = 1
dp[0][1] = 1
for i := 1;i < len(nums);i++{
for j := 0;j < i;j++{
if nums[i] > nums[j]{
if dp[i][0] == dp[j][0]{
dp[i][1] += dp[j][1]
}else if dp[i][0] < dp[j][0]{
dp[i][0] = dp[j][0]
dp[i][1] = dp[j][1]
}
}
}
dp[i][0]++
if dp[i][0] == 1{
dp[i][1] = 1
}
}
max := 0
for _,v := range dp{
if v[0] > max{
max = v[0]
}
}
re := 0
for _,v := range dp{
if v[0] == max{
re += v[1]
}
}
return re
}
总结
今天比较顺利,两道中等题都不难,动态规划是昨天题的加强版,但是动态规划这种题知道状态怎么转移就很好做了文章来源地址https://www.toymoban.com/news/detail-513039.html
到了这里,关于从零开始的力扣刷题记录-第七十二天的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!