2562.找出数组的串联值

【LetMeFly】2562.找出数组的串联值:模拟(双指针)

力扣题目链接:https://leetcode.cn/problems/find-the-array-concatenation-value/

给你一个下标从 0 开始的整数数组 nums

现定义两个数字的 串联 是由这两个数值串联起来形成的新数字。

  • 例如,15 和 49 的串联是 1549

nums 的 串联值 最初等于 0 。执行下述操作直到 nums 变为空:

  • 如果 nums 中存在不止一个数字,分别选中 nums 中的第一个元素和最后一个元素,将二者串联得到的值加到 nums 的 串联值 上,然后从 nums 中删除第一个和最后一个元素。
  • 如果仅存在一个元素,则将该元素的值加到 nums 的串联值上,然后删除这个元素。

返回执行完所有操作后 nums 的串联值。

 

示例 1:

输入:nums = [7,52,2,4]
输出:596
解释:在执行任一步操作前,nums 为 [7,52,2,4] ,串联值为 0 。
 - 在第一步操作中:
我们选中第一个元素 7 和最后一个元素 4 。
二者的串联是 74 ,将其加到串联值上,所以串联值等于 74 。
接着我们从 nums 中移除这两个元素,所以 nums 变为 [52,2] 。
 - 在第二步操作中: 
我们选中第一个元素 52 和最后一个元素 2 。 
二者的串联是 522 ,将其加到串联值上,所以串联值等于 596 。
接着我们从 nums 中移除这两个元素,所以 nums 变为空。
由于串联值等于 596 ,所以答案就是 596 。

示例 2:

输入:nums = [5,14,13,8,12]
输出:673
解释:在执行任一步操作前,nums 为 [5,14,13,8,12] ,串联值为 0 。 
- 在第一步操作中: 
我们选中第一个元素 5 和最后一个元素 12 。 
二者的串联是 512 ,将其加到串联值上,所以串联值等于 512 。 
接着我们从 nums 中移除这两个元素,所以 nums 变为 [14,13,8] 。
- 在第二步操作中:
我们选中第一个元素 14 和最后一个元素 8 。
二者的串联是 148 ,将其加到串联值上,所以串联值等于 660 。
接着我们从 nums 中移除这两个元素,所以 nums 变为 [13] 。 
- 在第三步操作中:
nums 只有一个元素,所以我们选中 13 并将其加到串联值上,所以串联值等于 673 。
接着我们从 nums 中移除这个元素,所以 nums 变为空。 
由于串联值等于 673 ,所以答案就是 673 。

 

提示:

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 104

方法一:模拟(双指针)

使用两个指针$l$和$r$分别指向数组中的第一个和最后一个元素。

两个指针不断向中间移动,在$l<r$时,累加$nums[l]\times len(nums[r]) + nums[r]$。

最后,如果$l=r$,则累加一个$nums[l]$。

  • 时间复杂度$O(len(nums))$
  • 空间复杂度$O(1)$

AC代码

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
long long findTheArrayConcVal(vector<int>& nums) {
long long ans = 0;
int l = 0, r = nums.size() - 1;
while (l < r) {
int t = nums[r];
long long mul = 1;
while (t) {
t /= 10;
mul *= 10;
}
ans += nums[l] * mul + nums[r];
l++, r--;
}
if (l == r) {
ans += nums[l];
}
return ans;
}
};

Python

1
2
3
4
5
6
7
8
9
10
11
12
# from typing import List

class Solution:
def findTheArrayConcVal(self, nums: List[int]) -> int:
l, r = 0, len(nums) - 1
ans = 0
while l < r:
ans += int(str(nums[l]) + str(nums[r]))
l, r = l + 1, r - 1
if l == r:
ans += nums[l]
return ans

同步发文于CSDN,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/133797249


2562.找出数组的串联值
https://blog.letmefly.xyz/2023/10/12/LeetCode 2562.找出数组的串联值/
作者
Tisfy
发布于
2023年10月12日
许可协议