本文介绍: 这道题目因为只有十的8次方,因此就算是两两交换,也就28种交换,因此很方便的用两层for循环,但是这道题目很明显是贪心的题目,我们只需要把大的往前移就行了。可以交换一次数字中的任意两位。返回你能得到的最大值。交换数字2和数字7。给定一个非负整数,你。
给定一个非负整数,你至多可以交换一次数字中的任意两位。返回你能得到的最大值。
示例 1 :
输入: 2736 输出: 7236 解释: 交换数字2和数字7。
示例 2 :
输入: 9973 输出: 9973 解释: 不需要交换。
注意:
- 给定数字的范围是 [0, 10^8]
这道题目因为只有十的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
。
向数组中的每个整数前添加 '+'
或 '-'
,然后串联起所有整数,可以构造一个 表达式 :
- 例如,
nums = [2, 1]
,可以在2
之前添加'+'
,在1
之前添加'-'
,然后串联起来得到表达式"+2-1"
。
返回可以通过上述方法构造的、运算结果等于 target
的不同 表达式 的数目。
示例 1:
输入: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
示例 2:
输入:nums = [1], target = 1 输出:1
提示:
1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000
这道题目最巧妙的地方是转换成动态规划问题,其实就是给定正数和,然后从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];
}
};
原文地址:https://blog.csdn.net/fzx12138/article/details/135752119
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_60781.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。