2023-07-15：给你一个 非递减 的正整数数组 nums 和整数 K，
判断该数组是否可以被分成一个或几个 长度至少 为 K 的 不相交的递增子序列。
输入：nums = [1,2,2,3,3,4,4], K = 3。
输出：true。
答案 2023-07-15：
大体步骤如下：
1.初始化计数变量 cnt 和最大计数变量 maxCnt，初始值都为 1。
2.从索引 1 开始遍历数组 nums：
3.遍历结束后，再次更新 maxCnt 为最后一个递增序列的计数 cnt 和 maxCnt 中的较大值。
4.判断长度为 len(nums) 除以 maxCnt 后是否大于等于 k，如果是，返回 true；否则，返回 false。
5.在 main 函数中，定义数组 nums 和整数 k。
6.调用函数 canDivideIntoSubsequences(nums, k) 并将结果赋给变量 result。
7.输出结果 Result: true。
时间复杂度：遍历数组 nums 的时间复杂度为 O(n)，其中 n 是数组 nums 的长度。因此，整个算法的时间复杂度为 O(n)。
空间复杂度：算法使用了常数级别的额外空间，不随输入规模变化，所以空间复杂度为 O(1)。
go 完整代码如下：
package main
import ( "fmt")
func canDivideIntoSubsequences(nums []int, k int) bool { cnt := 1 maxCnt := 1
for i := 1; i < len(nums); i++ { if nums[i-1] != nums[i] { maxCnt = max(maxCnt, cnt) cnt = 1 } else { cnt++ } }
maxCnt = max(maxCnt, cnt) return len(nums)/maxCnt >= k}
func max(a, b int) int { if a > b { return a } return b}
func main() { nums := []int{1, 2, 2, 3, 3, 4, 4} k := 3
result := canDivideIntoSubsequences(nums, k) fmt.Println("Result:", result)}
复制代码
rust 完整代码如下：
fn can_divide_into_subsequences(nums: &[i32], k: i32) -> bool { let mut cnt = 1; let mut max_cnt = 1;
for i in 1..nums.len() { if nums[i - 1] != nums[i] { max_cnt = max_cnt.max(cnt); cnt = 1; } else { cnt += 1; } }
max_cnt = max_cnt.max(cnt); nums.len() as i32 / max_cnt >= k}
fn main() { let nums = vec![1, 2, 2, 3, 3, 4, 4]; let k = 3;
let result = can_divide_into_subsequences(&nums, k); println!("Result: {}", result);}
复制代码
c++完整代码如下：
#include <iostream>#include <vector>#include <algorithm>
using namespace std;
bool canDivideIntoSubsequences(vector<int>& nums, int k) { int cnt = 1; int maxCnt = 1;
for (int i = 1; i < nums.size(); i++) { if (nums[i - 1] != nums[i]) { maxCnt = max(maxCnt, cnt); cnt = 1; } else { cnt++; } }
maxCnt = max(maxCnt, cnt); return nums.size() / maxCnt >= k;}
int main() { vector<int> nums = { 1, 2, 2, 3, 3, 4, 4 }; int k = 3;
bool result = canDivideIntoSubsequences(nums, k); cout << "Result: " << boolalpha << result << endl;
return 0;}
复制代码
c 完整代码如下：
#include <stdio.h>
int canDivideIntoSubsequences(int nums[], int length, int k) { int cnt = 1; int maxCnt = 1;
for (int i = 1; i < length; i++) { if (nums[i - 1] != nums[i]) { if (maxCnt < cnt) { maxCnt = cnt; } cnt = 1; } else { cnt++; } }
if (maxCnt < cnt) { maxCnt = cnt; }
return (length / maxCnt) >= k;}
int main() { int nums[] = { 1, 2, 2, 3, 3, 4, 4 }; int length = sizeof(nums) / sizeof(nums[0]); int k = 3;
int result = canDivideIntoSubsequences(nums, length, k); printf("Result: %s\n", result ? "true" : "false");
return 0;}
复制代码
评论