用java编写代码 实现给定一个非负整数，你可以至多交换一次数字中的任意两位，返回你得到的最大值。

请给出解答。

可以将数字转化为字符数组，从左到右找到第一个比后面数字小的位置，然后再从右到左找到第一个比该位置数字大的位置，交换两个位置上的数字即可。

以下是Java代码实现：

public int maximumSwap(int num) {
char[] nums = String.valueOf(num).toCharArray();
int len = nums.length;
int[] cnts = new int[10];
for (int i = 0; i < len; i++) {
cnts[nums[i] - '0'] = i;
}
for (int i = 0; i < len; i++) {
for (int j = 9; j > nums[i] - '0'; j--) {
if (cnts[j] > i) {
char tmp = nums[i];
nums[i] = nums[cnts[j]];
nums[cnts[j]] = tmp;
return Integer.parseInt(new String(nums));
}
}
}
return num;
}

相关问题

给定一个非负整数，你可以至多交换一次数字中的任意两位，返回你得到的最大值。 java

好的，这是一个非常好的问题。这个问题的解法比较简单，我们可以使用贪心算法来解决它。

具体来说，我们可以将这个非负整数转化为字符串，然后逐一比较相邻的字符，如果前面的字符比后面的字符小，那么就交换它们，然后再将整个字符串转化为整数。这样做的原理是，我们通过交换数字可以让高位上的数字变大，从而得到更大的整数。

下面是一个基于贪心算法的 Java 代码实现：

public int maximumSwap(int num) {
char[] digits = Integer.toString(num).toCharArray();
int[] last = new int[10];
for (int i = 0; i < digits.length; i++) {
last[digits[i] - '0'] = i;
}
for (int i = 0; i < digits.length; i++) {
for (int j = 9; j > digits[i] - '0'; j--) {
if (last[j] > i) {
char tmp = digits[i];
digits[i] = digits[last[j]];
digits[last[j]] = tmp;
return Integer.parseInt(new String(digits));
}
}
}
return num;
}

这个算法的时间复杂度是 O(n)，其中 n 是这个非负整数的位数。

C++怎么写给定一个长度为 n 的序列 a1,a2,…,an ，你可以将其中至多 k 个元素修改为任意整数，目标是最小化相邻元素之差的绝对值的最大值。这道题

这是一道典型的动态规划问题，可以使用C++来解决。我们可以将其命名为“最小化最大差距”（Minimize Maximum Difference）。以下是解决这个问题的一个步骤：

1. **状态定义**：设dp[i][j]表示前i个元素中，最多修改j个元素后，剩余部分最大差距的最小值。

2. **状态转移方程**：
- 当j = 0 时（未修改任何元素），dp[i][j] = |ai - ai+1| （如果 i > 0，否则就是0，因为没有后续元素来影响差距）
- 对于j > 0的情况，我们需要遍历所有可能的修改位置m (0 <= m < i)，然后取两个子情况的最小值：
- 不修改第m+1个元素，即 dp[m][j-1]
- 修改第m+1个元素使其尽可能接近其他元素，这可以通过寻找前后元素中较小的那个来实现，更新为 min(dp[m][j-1], abs(ai - other))，where other 是ai的邻居。

3. **边界条件**：
- 初始化dp[0][0] = 0（空序列的差距是0）
- dp[i][k] = INT_MAX (极大值) 当 i == 0 或者 k < 0，防止意外溢出

4. **结果计算**：最终的答案是 dp[n][k]

#include <vector>
using namespace std;

int minimizeDifference(vector<int>& nums, int k) {
    int n = nums.size();
    vector<vector<int>> dp(n + 1, vector<int>(k + 1));
    
    // 基础情况
    dp[0][0] = 0;
    
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= k; ++j) {
            if (j > 0) {
                dp[i][j] = numeric_limits<int>::max();
                for (int m = 0; m < i; ++m) {
                    int diff = nums[i - 1] - (m > 0 ? nums[m - 1] : nums[0]);
                    dp[i][j] = min(dp[i][j], min(dp[m][j - 1], abs(diff)));
                }
            } else {
                dp[i][j] = abs(nums[i - 1] - (i > 0 ? nums[i - 2] : nums[0]));
            }
        }
    }

    return dp[n][k];
}