代码拉取完成,页面将自动刷新
同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
给你一个下标从 0 开始的整数数组 nums
。请你从 nums
中找出和 最大 的一对数,且这两个数数位上最大的数字相等。
返回最大和,如果不存在满足题意的数字对,返回 -1
。
示例 1:
输入:nums = [51,71,17,24,42] 输出:88 解释: i = 1 和 j = 2 ,nums[i] 和 nums[j] 数位上最大的数字相等,且这一对的总和 71 + 17 = 88 。 i = 3 和 j = 4 ,nums[i] 和 nums[j] 数位上最大的数字相等,且这一对的总和 24 + 42 = 66 。 可以证明不存在其他数对满足数位上最大的数字相等,所以答案是 88 。
示例 2:
输入:nums = [1,2,3,4] 输出:-1 解释:不存在数对满足数位上最大的数字相等。
提示:
2 <= nums.length <= 100
1 <= nums[i] <= 104
我们先初始化答案变量 $ans = -1$。接下来,直接枚举所有的数对 $(nums[i], nums[j])$,其中 $i \lt j$,并计算它们的和 $v = nums[i] + nums[j]$。如果 $v$ 比 $ans$ 更大,并且 $nums[i]$ 和 $nums[j]$ 的最大数字相同,那么我们就用 $v$ 更新 $ans$。
时间复杂度 $O(n^2 \times \log M)$,其中 $n$ 是数组的长度,而 $M$ 是数组中的最大值。
class Solution:
def maxSum(self, nums: List[int]) -> int:
ans = -1
for i, x in enumerate(nums):
for y in nums[i + 1 :]:
v = x + y
if ans < v and max(str(x)) == max(str(y)):
ans = v
return ans
class Solution {
public int maxSum(int[] nums) {
int ans = -1;
int n = nums.length;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
int v = nums[i] + nums[j];
if (ans < v && f(nums[i]) == f(nums[j])) {
ans = v;
}
}
}
return ans;
}
private int f(int x) {
int y = 0;
for (; x > 0; x /= 10) {
y = Math.max(y, x % 10);
}
return y;
}
}
class Solution {
public:
int maxSum(vector<int>& nums) {
int ans = -1;
int n = nums.size();
auto f = [](int x) {
int y = 0;
for (; x; x /= 10) {
y = max(y, x % 10);
}
return y;
};
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
int v = nums[i] + nums[j];
if (ans < v && f(nums[i]) == f(nums[j])) {
ans = v;
}
}
}
return ans;
}
};
func maxSum(nums []int) int {
ans := -1
f := func(x int) int {
y := 0
for ; x > 0; x /= 10 {
y = max(y, x%10)
}
return y
}
for i, x := range nums {
for _, y := range nums[i+1:] {
if v := x + y; ans < v && f(x) == f(y) {
ans = v
}
}
}
return ans
}
function maxSum(nums: number[]): number {
const n = nums.length;
let ans = -1;
const f = (x: number): number => {
let y = 0;
for (; x > 0; x = Math.floor(x / 10)) {
y = Math.max(y, x % 10);
}
return y;
};
for (let i = 0; i < n; ++i) {
for (let j = i + 1; j < n; ++j) {
const v = nums[i] + nums[j];
if (ans < v && f(nums[i]) === f(nums[j])) {
ans = v;
}
}
}
return ans;
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。