找出数组的串联值

You are given a 0-indexed integer array nums.

The concatenation of two numbers is the number formed by concatenating their numerals.

• For example, the concatenation of 15, 49 is 1549.

The concatenation value of nums is initially equal to 0. Perform this operation until nums becomes empty:

• If there exists more than one number in nums, pick the first element and last element in nums respectively and add the value of their concatenation to the concatenation value of nums, then delete the first and last element from nums.
• If one element exists, add its value to the concatenation value of nums, then delete it.

Return the concatenation value of the nums.

 

Example 1:

Input: nums = [7,52,2,4]
Output: 596
Explanation: Before performing any operation, nums is [7,52,2,4] and concatenation value is 0.
 - In the first operation:
We pick the first element, 7, and the last element, 4.
Their concatenation is 74, and we add it to the concatenation value, so it becomes equal to 74.
Then we delete them from nums, so nums becomes equal to [52,2].
 - In the second operation:
We pick the first element, 52, and the last element, 2.
Their concatenation is 522, and we add it to the concatenation value, so it becomes equal to 596.
Then we delete them from the nums, so nums becomes empty.
Since the concatenation value is 596 so the answer is 596.

Example 2:

Input: nums = [5,14,13,8,12]
Output: 673
Explanation: Before performing any operation, nums is [5,14,13,8,12] and concatenation value is 0.
 - In the first operation:
We pick the first element, 5, and the last element, 12.
Their concatenation is 512, and we add it to the concatenation value, so it becomes equal to 512.
Then we delete them from the nums, so nums becomes equal to [14,13,8].
 - In the second operation:
We pick the first element, 14, and the last element, 8.
Their concatenation is 148, and we add it to the concatenation value, so it becomes equal to 660.
Then we delete them from the nums, so nums becomes equal to [13].
 - In the third operation:
nums has only one element, so we pick 13 and add it to the concatenation value, so it becomes equal to 673.
Then we delete it from nums, so nums become empty.
Since the concatenation value is 673 so the answer is 673.

 

Constraints:

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

 

/*
 * 使用 Java Stream 实现上述算法。
 */
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class ConcatenationValueStream {
    public static int findConcatenationValue(List<Integer> nums) {
        int concatenationValue = 0;
        while (nums.size() > 0) {
            if (nums.size() == 1) {
                concatenationValue += nums.remove(0);
            } else {
                String first = String.valueOf(nums.remove(0));
                String last = String.valueOf(nums.remove(nums.size() - 1));
                concatenationValue += Integer.parseInt(first + last);
            }
        }
        return concatenationValue;
    }
    public static void main(String[] args) {
        List<Integer> nums1 = Arrays.asList(7, 52, 2, 4);
        List<Integer> nums2 = Arrays.asList(5, 14, 13, 8, 12);
        System.out.println(findConcatenationValue(new ArrayList<>(nums1))); // 输出: 596
        System.out.println(findConcatenationValue(new ArrayList<>(nums2))); // 输出: 673
    }
}

该题解通过双指针的方式从数组的两端开始操作。指针i初始化在数组的开头，指针j初始化在数组的末尾。在每次循环中，首先检查两个指针是否相遇。如果没有相遇，分别取出指针i和j所指向的数组元素，计算这两个数的串联值。为了计算串联值，首先需要确定将j所指元素拼接到i所指元素后面时，需要在i元素后面添加多少个零。这是通过不断地将j元素整除10直到为0来计算。然后将得到的串联值累加到最终答案中，并将两个指针向中心移动。当两个指针相遇时，如果数组长度为奇数，则将该中心元素直接累加到结果中。这样直到数组被完全遍历完毕。

O(n)

O(1)