每日coding_代码007(未授权)

本文介绍: 这道题目因为只有十的8次方，因此就算是两两交换，也就28种交换，因此很方便的用两层for循环，但是这道题目很明显是贪心的题目，我们只需要把大的往前移就行了。可以交换一次数字中的任意两位。返回你能得到的最大值。交换数字2和数字7。给定一个非负整数，你。

670. 最大交换

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

示例 1 :

输入: 2736
输出: 7236
解释: 交换数字2和数字7。

示例 2 :

输入: 9973
输出: 9973
解释: 不需要交换。

注意:

这道题目因为只有十的8次方，因此就算是两两交换，也就28种交换，因此很方便的用两层for循环，

class Solution {
public:
    int maximumSwap(int num) {
        string str = to_string(num);
        int n = str.length(), maxNum = 0;
        for(int i = 0;i < n;i++){
            for(int j = i;j < n;j++){
                swap(str[i], str[j]);
                maxNum = max(maxNum, stoi(str));
                swap(str[i], str[j]);
            }
        }
        return maxNum;
    }
};

class Solution {
public:
    int maximumSwap(int num) {
        string str = to_string(num);
        int n = str.length();
        int maxIndex = n - 1, p = -1, q = 0;
        for(int i = n - 2;i >= 0;i--){
            if(str[i] > str[maxIndex]){
                maxIndex = i;
            } else if(str[i] < str[maxIndex]){
                p = maxIndex;
                q = i;
            }
        }
        if(p == -1) return num;
        swap(str[p], str[q]);
        return stoi(str);
    }
};

给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

输入：nums = [1], target = 1
输出：1

这道题目最巧妙的地方是转换成动态规划问题，其实就是给定正数和，然后从num中找出满足正数和的组合。

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        target += accumulate(nums.begin(), nums.end(), 0);
        if(target < 0 || target % 2) return 0;
        target /= 2;
        vector<int> dp(target + 1, 0);
        dp[0] = 1;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = target; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[target];
    }
};

显示所有内容

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。