当前位置:网站首页>LeetCode Daily Question (321. Create Maximum Number)
LeetCode Daily Question (321. Create Maximum Number)
2022-08-09 22:07:00 【wangjun861205】
You are given two integer arrays nums1 and nums2 of lengths m and n respectively. nums1 and nums2 represent the digits of two numbers. You are also given an integer k.
Create the maximum number of length k <= m + n from digits of the two numbers. The relative order of the digits from the same array must be preserved.
Return an array of the k digits representing the answer.
Example 1:
Input: nums1 = [3,4,6,5], nums2 = [9,1,2,5,8,3], k = 5
Output: [9,8,6,5,3]
Example 2:
Input: nums1 = [6,7], nums2 = [6,0,4], k = 5
Output: [6,7,6,0,4]
Example 3:
Input: nums1 = [3,9], nums2 = [8,9], k = 3
Output: [9,8,9]
Constraints:
- m == nums1.length
- n == nums2.length
- 1 <= m, n <= 500
- 0 <= nums1[i], nums2[i] <= 9
- 1 <= k <= m + n
对于任意一个数组 nums, any fixed length length Must correspond to a unique largest array, So go down this way, Suppose the final array length to be obtained is k, That final array must be max_array(nums1, length)与 max_array(nums2, k-length)组合而成的, So we just need to iterate through these cases and put max_array1 与 max_array2 Combined into a maximum length of k 的数组就可以了.
impl Solution {
fn max_with_fixed_length(mut nums: Vec<i32>, length: usize) -> Vec<i32> {
let mut stack = Vec::new();
'outer: while stack.len() + nums.len() > length && nums.len() > 0 {
if stack.is_empty() {
stack.push(nums.remove(0));
continue;
}
let curr = nums.remove(0);
while let Some(last) = stack.pop() {
if last >= curr {
stack.push(last);
stack.push(curr);
continue 'outer;
}
if stack.len() + nums.len() + 1 == length {
break;
}
}
stack.push(curr);
}
stack.append(&mut nums);
if stack.len() > length {
stack = stack[..length].to_vec();
}
stack
}
fn is_greater(mut nums1: Vec<i32>, mut nums2: Vec<i32>) -> bool {
while nums1.len() < nums2.len() {
nums1.push(0);
}
while nums1.len() > nums2.len() {
nums2.push(0);
}
for (n1, n2) in nums1.into_iter().zip(nums2.into_iter()) {
if n1 == n2 {
continue;
}
if n1 > n2 {
return true;
}
return false;
}
false
}
fn merge(nums1: &[i32], nums2: &[i32]) -> Vec<i32> {
let mut res = Vec::new();
let mut i = 0;
let mut j = 0;
while i < nums1.len() && j < nums2.len() {
if nums1[i] == nums2[j] {
if Solution::is_greater(nums1[i + 1..].to_vec(), nums2[j + 1..].to_vec()) {
res.push(nums1[i]);
i += 1;
continue;
}
res.push(nums2[j]);
j += 1;
continue;
}
if nums1[i] > nums2[j] {
res.push(nums1[i]);
i += 1;
continue;
}
res.push(nums2[j]);
j += 1;
}
if i < nums1.len() {
res.append(&mut nums1[i..].to_vec());
}
if j < nums2.len() {
res.append(&mut nums2[j..].to_vec());
}
res
}
pub fn max_number(nums1: Vec<i32>, nums2: Vec<i32>, k: i32) -> Vec<i32> {
let mut ans = vec![0; k as usize];
for i in 1..=(k as usize).min(nums1.len()) {
if k as usize - i <= nums2.len() {
let max1 = Solution::max_with_fixed_length(nums1.clone(), i);
let max2 = Solution::max_with_fixed_length(nums2.clone(), k as usize - i);
let curr = Solution::merge(&max1, &max2);
if Solution::is_greater(curr.clone(), ans.clone()) {
ans = curr;
}
}
}
ans
}
}
边栏推荐
- Characteristics and Development Prospects of Korea's Cyber Security System
- How are data integration APIs key to enterprise digital transformation?
- 数据集成API如何成为企业数字化转型的关键?
- 一种基于连接和安全熵的网络空间整体安全认识和方法
- Openharmony Lightweight System Experiment--GPIO Lighting
- 2.3 监督学习-2
- 力扣 899. 有序队列
- Acrel5000web能耗系统在某学院的应用-Susie 周
- leetcode 二叉树的公共近祖先
- 阿里二面:没有 accept,能建立 TCP 连接吗?
猜你喜欢
渗透测试-对新型内存马webshell的研究
鲜花线上销售管理系统的设计与实现
钢材行业供应链协同管理系统提升企业上下游密切度,精细化企业内部管理
How are data integration APIs key to enterprise digital transformation?
poj 1182 食物链(带权并查集)
[] free column Android run Android, her - as command of safety
[Deep learning] pix2pix GAN theory and code implementation
线性表的定义和基本操作
嵌入式开发:使用FILL提高代码完整性
安科瑞无线物联网智能电表ADW300指导性技术要求-Susie 周
随机推荐
Js查找字符串中出现最多次数的字母和单词
[Free column] Xposed plug-in development for Android security [from scratch] tutorial
What to do if Windows 11 can't find Internet Explorer
An overall security understanding and method of cyberspace based on connection and security entropy
MySQL, which is asked on both sides of the byte, almost didn't answer well
力扣383-赎金信——哈希映射数组法
3D感知(二):单目3D物体检测
毕昇编译器优化:Lazy Code Motion
如何在WPF中设置Grid ColumnDefinitions的样式
【NOI模拟赛】防AK题(生成函数,单位根,Pollard-Rho)
倍福CX5120实现温度控制例程详细解析
继承关系下构造方法的访问特点
下秒数据:湖仓一体带来的现代数据堆栈变革开始了
嵌入式开发:使用FILL提高代码完整性
Toronto Research Chemicals盐酸乙环胺应用说明
CMake installation upgrade higher version
pytest框架之mark标记功能详细介绍
DSPE-PEG-Azide,DSPE-PEG-N3,磷脂-聚乙二醇-叠氮可和DBCO直接反应
华为云创新中心助力启泰智能 补齐中小模具企业数字化能力短板
Access control knowledge