Re: [閒聊] 每日LeetCode已回收
※ 引述《Rushia (みけねこ的鼻屎)》之銘言：
: https://leetcode.com/problems/number-of-longest-increasing-subsequence/description/
: 673. Number of Longest Increasing Subsequence
: 給你一個陣列找出這個陣列的最長遞增子序列共有幾個，遞增為嚴格遞增。
: 思路：
: 1. [300. Longest Increasing Subsequence] 這題的延伸版本，原題目只要求長度
: 現在要求有幾個，dp 的思路是如果我們知道 i 之前的所有最長遞增子序列長度，
: 則 dp[i] 的最長子序列長度只需要找滿足 nums[j] < nums[i] 且 j < i 的 j
: 並取 dp[j] 的最大值加一就是 dp[i] 的 LIS。
: 2.只需要把原題目在算 dp 的時候順便統計這個長度的序列有幾個即可，當遇到更大
: 的長度就更新長度並重置當前計數，遇到一樣的長度則累加。
寫完了感覺還是只懂一半
知道在幹嘛但要我自己寫可能會卡住
:(
Code:
impl Solution
{
pub fn find_number_of_lis(nums: Vec<i32>) -> i32
{
let nums_size = nums.len();
if nums_size == 0
{
return 0;
}
let mut LIS_lengths: Vec<i32> = vec![1; nums_size];
let mut LIS_nums: Vec<i32> = vec![1; nums_size];
let mut max_LIS_lengths: i32 = 1;
for i in 0..nums_size
{
for j in 0..i
{
if nums[i] > nums[j]
{
if (LIS_lengths[j] + 1) > LIS_lengths[i]
{
LIS_lengths[i] = LIS_lengths[j] + 1;
LIS_nums[i] = LIS_nums[j];
}
else if (LIS_lengths[j] + 1) == LIS_lengths[i]
{
LIS_nums[i] += LIS_nums[j];
}
}
}
max_LIS_lengths = max_LIS_lengths.max(LIS_lengths[i]);
}
let mut result: i32 = 0;
for i in 0..nums_size
{
if LIS_lengths[i] == max_LIS_lengths
{
result += LIS_nums[i];
}
}
return result;
}
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.248.143.163 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1689933357.A.283.html
推
07/21 18:00,
2年前
, 1F
07/21 18:00, 1F
→
07/21 18:00,
2年前
, 2F
07/21 18:00, 2F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 377 之 719 篇)：