LeetCode·每日一题·679.最大交换·贪心
LeetCode 最大 每日 贪心 交换
2023-09-27 14:26:29 时间
题目
思路
解题思路
【模拟】
- 1.首先通过sprintf()函数将数字转换为字符串为了后续操作方便。
- 2.将转换为字符串中的数字进行逐一交换。
- 3.将此时得到的字符串转换为数字进行取大处理并保留较大值。
- 4.将字符串进行复原,使得后续的比较每次都是在原字符串的基础上进行的。
- 5.所有的情况都比较完成,返回最大值,即为结果。
【贪心】
贪心法一句话总结:每一位数字应该不小于所有排它后面的数字,否则找最大的且排最后面的数字与之交换
直观看就是,寻找第一个上升位置之后的最大数位置,并尽量与前面的数互换,互换的原则是:比自己小
作者:xun-ge-v
链接:https://leetcode.cn/problems/maximum-swap/solution/-by-xun-ge-v-bfjf/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
代码
【模拟】
void swap(char *nums, int i, int j) { // 通过函数实现字符串中数字的交换。
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
return ;
}
int maximumSwap(int num){
char str[10];
sprintf(str, "%d", num); // 将数字转换为字符串,便于后续的操作。
int len = strlen(str);
int i;
int j;
int max = num;
for (i = 0; i < len; i++) {
for (j = len - 1; j > 0; j--) {//枚举所有交换可能保存最大值
swap(str, i, j); // 交换字符串中的两个值的位置。
max = fmax(max, atoi(str));
swap(str, i, j); // 复原字符串中两个值的位置,为了后续的重新比较。
}
}
return max;
}
作者:xun-ge-v
链接:https://leetcode.cn/problems/maximum-swap/solution/-by-xun-ge-v-bfjf/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
【贪心】
void swap(char *nums, int i, int j) { // 通过函数实现字符串中数字的交换。
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
return ;
}
int maximumSwap(int num){
char str[10];
sprintf(str, "%d", num); // 将数字转换为字符串,便于后续的操作。
int len = strlen(str);
int max;//保存最大数位置位置,当然必须是上升位之后的最大数
bool logo = false;//记录是否有上升位
for (int i = 1; i < len; i++) {//遍历判断是否存在上升位
if(logo == false && str[i-1] < str[i])如果存在上升位就记录当前位置
//并且后序不需要再比较有没有上升位了,应该有一个就必须有换位
{
max = i;
logo = true;
}
if(logo)//存在上升位,保存上升位之后的最大数下标
{
if(str[max] <= str[i])
max = i;
}
}
if(logo)//排出开始位置相同数
{
int i = 0;
while(str[max] <= str[i]) i++;
swap(str, max, i);//交换位置
}
sscanf(str, "%d", &num);//输出
return num;
}
作者:xun-ge-v
链接:https://leetcode.cn/problems/maximum-swap/solution/-by-xun-ge-v-bfjf/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
相关文章
- LeetCode每日一练 —— 20. 有效的括号
- 【LeetCode】实现 Trie (前缀树) [M](前缀树)
- 【LeetCode】二叉树中的最大路径和 [H](递归)
- 【LeetCode】按公因数计算最大组件大小 [H](并查集)
- 【LeetCode】最大间距 [H](基数排序)
- 【LeetCode】最大矩形(单调栈)
- LeetCode_二叉树_中等_剑指 Offer 26.树的子结构
- LeetCode_单调栈_中等_1019.链表中的下一个更大节点
- LeetCode_动态规划_中等_813.最大平均值和的分组
- LeetCode_数据结构设计_困难_895. 最大频率栈
- LeetCode_二叉搜索树_困难_1373.二叉搜索子树的最大键值和
- LeetCode_单调栈_困难_85.最大矩形
- LeetCode_排序_困难_164.最大间距
- LeetCode_排序_中等_148.排序链表
- leetcode 73. 矩阵置零
- LeetCode·每日一题·1798.你能构造出连续值的最大数目·贪心
- LeetCode·每日一题·1769.移动所有球到每一个盒子所需的最小操作数·模拟
- LeetCode·每日一题·1710.卡车上的最大单元数·贪心
- LeetCode·每日一题·902.最大为 N 的数字组合·数学
- LeetCode·每日一题·998,最大二叉树 || ·递归
- LeetCode·每日一题·662.二叉树最大宽度·递归·迭代
- LeetCode·每日一题·1224.最大相等频率·哈希
- LeetCode·每日一题·952.按公因数计算最大组件大小·并查集
- LeetCode·每日一题·1331.数组序号转换·离散化
- LeetCode·49.字母异位词分组·hash
- LeetCode·84.柱状图中最大的矩形·单调递增栈
- [LeetCode] 769. Max Chunks To Make Sorted 可排序的最大块数
- [LeetCode] 689. Maximum Sum of 3 Non-Overlapping Subarrays 三个非重叠子数组的最大和
- [LeetCode] 53. Maximum Subarray 最大子数组
- [LeetCode] 127. Word Ladder 单词阶梯
- leetcode x 的平方根 python
- LeetCode 01:有人相爱,有人夜里开车看海,有人LeetCode第一题都做不出来
- leetcode 827 最大人工岛