普通视图
鸿蒙音频播放方式总结
每日一题-6 和 9 组成的最大数字🟢
给你一个仅由数字 6 和 9 组成的正整数 num
。
你最多只能翻转一位数字,将 6 变成 9,或者把 9 变成 6 。
请返回你可以得到的最大数字。
示例 1:
输入:num = 9669 输出:9969 解释: 改变第一位数字可以得到 6669 。 改变第二位数字可以得到 9969 。 改变第三位数字可以得到 9699 。 改变第四位数字可以得到 9666 。 其中最大的数字是 9969 。
示例 2:
输入:num = 9996 输出:9999 解释:将最后一位从 6 变到 9,其结果 9999 是最大的数。
示例 3:
输入:num = 9999 输出:9999 解释:无需改变就已经是最大的数字了。
提示:
1 <= num <= 10^4
-
num
每一位上的数字都是 6 或者 9 。
来看看Trae生成的粒子效果是怎么样的
前端实现自动检测项目部署更新
两种方法:用字符串/不用字符串(Python/Java/C++/C/Go/JS/Rust)
分析
要想把数字变大,只能把 $6$ 改成 $9$。
比如 $\textit{num}=9669$:
- 改高位的 $6$,得到 $9969$。
- 改低位的 $6$,得到 $9699$。
- $9969 > 9699$。
改高位的 $6$ 比改低位的 $6$ 更好。由于至多改一次,所以改最高位的 $6$。若 $\textit{num}$ 无 $6$,则 $\textit{num}$ 不变。
方法一:用字符串
###py
class Solution:
def maximum69Number(self, num: int) -> int:
s = str(num).replace('6', '9', 1) # 替换第一个 6
return int(s)
###py
class Solution:
def maximum69Number(self, num: int) -> int:
s = str(num)
i = s.find('6')
if i < 0:
return num
return int(s[:i] + '9' + s[i + 1:])
###java
class Solution {
public int maximum69Number(int num) {
String s = String.valueOf(num).replaceFirst("6", "9"); // 替换第一个 6
return Integer.parseInt(s);
}
}
###java
class Solution {
public int maximum69Number(int num) {
String s = Integer.toString(num);
int i = s.indexOf('6');
if (i < 0) {
return num;
}
s = s.substring(0, i) + "9" + s.substring(i + 1);
return Integer.parseInt(s);
}
}
###cpp
class Solution {
public:
int maximum69Number(int num) {
string s = to_string(num);
int i = s.find('6');
if (i == string::npos) {
return num;
}
s[i] = '9';
return stoi(s);
}
};
###c
int maximum69Number(int num) {
char s[6];
sprintf(s, "%d", num);
char* p = strchr(s, '6');
if (p == NULL) {
return num;
}
*p = '9';
return atoi(s);
}
###go
func maximum69Number(num int) int {
s := strconv.Itoa(num)
s = strings.Replace(s, "6", "9", 1) // 替换第一个 6
ans, _ := strconv.Atoi(s)
return ans
}
###js
var maximum69Number = function(num) {
const s = String(num).replace('6', '9'); // 替换第一个 6
return parseInt(s);
};
###rust
impl Solution {
pub fn maximum69_number(num: i32) -> i32 {
num.to_string()
.replacen("6", "9", 1) // 替换第一个 6
.parse()
.unwrap()
}
}
复杂度分析
- 时间复杂度:$\mathcal{O}(\log \textit{num})$。
- 空间复杂度:$\mathcal{O}(\log \textit{num})$。
方法二:不用字符串
可以不用转成字符串处理,而是不断取最低位(模 $10$),去掉最低位(除以 $10$),直到数字为 $0$。
例如 $\textit{num}=9669$:
- 初始化 $x=\textit{num}$。
- 通过 $x\bmod 10$ 取到个位数 $9$,然后把 $x$ 除以 $10$(下取整),得到 $x=966$。
- 再次 $x\bmod 10$ 取到十位数 $6$,然后把 $x$ 除以 $10$(下取整),得到 $x=96$。
- 再次 $x\bmod 10$ 取到百位数 $6$,然后把 $x$ 除以 $10$(下取整),得到 $x=9$。
- 最后 $x\bmod 10$ 取到千位数 $9$,然后把 $x$ 除以 $10$(下取整),得到 $x=0$。此时完成了遍历 $\textit{num}$ 的每个数位,退出循环。
在这个过程中,维护一个变量 $\textit{base}$,初始值为 $1$,在循环末尾把 $\textit{base}$ 乘以 $10$。每当我们遍历到一个等于 $6$ 的数位,就保存此刻的 $\textit{base}$,即更新 $\textit{maxBase} = \textit{base}$。其中 $\textit{maxBase}$ 初始值为 $0$。由于我们从低位往高位遍历,所以最终的 $\textit{maxBase}$ 就是最高位的 $6$ 对应的 $\textit{base}$。在上面的例子中,我们可以得到 $\textit{maxBase} = 100$。
最终答案为
$$
\textit{num} + \textit{maxBase}\cdot 3
$$
在上面的例子中,答案为 $9669 + 100\cdot 3 = 9969$。
注:如果 $\textit{num}$ 中没有 $6$,由于我们初始化 $\textit{maxBase}=0$,最终答案为 $\textit{num}$。
###py
class Solution:
def maximum69Number(self, num: int) -> int:
max_base = 0
base = 1
x = num
while x:
x, d = divmod(x, 10)
if d == 6:
max_base = base
base *= 10
return num + max_base * 3
###java
class Solution {
public int maximum69Number(int num) {
int maxBase = 0;
int base = 1;
for (int x = num; x > 0; x /= 10) {
if (x % 10 == 6) {
maxBase = base;
}
base *= 10;
}
return num + maxBase * 3;
}
}
###cpp
class Solution {
public:
int maximum69Number(int num) {
int max_base = 0;
int base = 1;
for (int x = num; x > 0; x /= 10) {
if (x % 10 == 6) {
max_base = base;
}
base *= 10;
}
return num + max_base * 3;
}
};
###c
int maximum69Number(int num) {
int max_base = 0;
int base = 1;
for (int x = num; x > 0; x /= 10) {
if (x % 10 == 6) {
max_base = base;
}
base *= 10;
}
return num + max_base * 3;
}
###go
func maximum69Number(num int) int {
maxBase := 0
base := 1
for x := num; x > 0; x /= 10 {
if x%10 == 6 {
maxBase = base
}
base *= 10
}
return num + maxBase*3
}
###js
var maximum69Number = function(num) {
let maxBase = 0;
let base = 1;
for (let x = num; x > 0; x = Math.floor(x / 10)) {
if (x % 10 === 6) {
maxBase = base;
}
base *= 10;
}
return num + maxBase * 3;
};
###rust
impl Solution {
pub fn maximum69_number(num: i32) -> i32 {
let mut max_base = 0;
let mut base = 1;
let mut x = num;
while x > 0 {
if x % 10 == 6 {
max_base = base;
}
base *= 10;
x /= 10;
}
num + max_base * 3
}
}
复杂度分析
- 时间复杂度:$\mathcal{O}(\log \textit{num})$。
- 空间复杂度:$\mathcal{O}(1)$。
思考题
- 改成求最小数字。
- 额外输入一个正整数 $k$,至多翻转 $k$ 个数,返回可以得到的最大数字。
- 给定正整数 $\textit{low}$ 和 $\textit{high}$,计算闭区间 $[\textit{low},\textit{high}]$ 中的所有整数 $x$ 的 $\texttt{maximum69Number}(x)$ 之和。
欢迎在评论区分享你的思路/代码。
专题训练
见下面贪心题单的「§3.1 字典序最小/最大」。
分类题单
- 滑动窗口与双指针(定长/不定长/单序列/双序列/三指针/分组循环)
- 二分算法(二分答案/最小化最大值/最大化最小值/第K小)
- 单调栈(基础/矩形面积/贡献法/最小字典序)
- 网格图(DFS/BFS/综合应用)
- 位运算(基础/性质/拆位/试填/恒等式/思维)
- 图论算法(DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流)
- 动态规划(入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望)
- 常用数据结构(前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树)
- 数学算法(数论/组合/概率期望/博弈/计算几何/随机算法)
- 贪心与思维(基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造)
- 链表、二叉树与回溯(前后指针/快慢指针/DFS/BFS/直径/LCA/一般树)
- 字符串(KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机)
欢迎关注 B站@灵茶山艾府
6 和 9 组成的最大数字
方法一:贪心 + 字符串
思路与算法
此题要求将一个由数字 $6$ 和 $9$ 构成的十进制数 $\textit{num}$ 进行至多一次 $6$ 和 $9$ 之间的翻转得到的最大数字。由十进制数的性质易知:贪心的选择数位最高的一个 $6$ 变成 $9$,得到的答案就是最大的。如果不存在这样的 $6$,则说明这个数字全由数字 $9$ 构成。根据题意,此时不对 $\textit{num}$ 做任何更改即为最优解。
对于算法实现,我们使用字符数组来处理 $\textit{num}$ 较为方便。首先将 $\textit{num}$ 转为字符数组,然后从左到遍历字符,按上述算法处理。最后将修改后的字符数组转回数字即为所求。
代码
###C++
class Solution {
public:
int maximum69Number (int num) {
string s = to_string(num);
for (char &c : s) {
if (c == '6') {
c = '9';
break;
}
}
return stoi(s);
}
};
###Java
public class Solution {
public int maximum69Number (int num) {
char[] chars = Integer.toString(num).toCharArray();
for (int i = 0; i < chars.length; i++) {
if (chars[i] == '6') {
chars[i] = '9';
break;
}
}
return Integer.parseInt(new String(chars));
}
}
###C#
public class Solution {
public int Maximum69Number (int num) {
char[] chars = num.ToString().ToCharArray();
for (int i = 0; i < chars.Length; i++) {
if (chars[i] == '6') {
chars[i] = '9';
break;
}
}
return int.Parse(new string(chars));
}
}
###Go
func maximum69Number(num int) int {
s := strconv.Itoa(num)
chars := []byte(s)
for i := 0; i < len(chars); i++ {
if chars[i] == '6' {
chars[i] = '9'
break
}
}
result, _ := strconv.Atoi(string(chars))
return result
}
###Python
class Solution:
def maximum69Number (self, num: int) -> int:
s = list(str(num))
for i in range(len(s)):
if s[i] == '6':
s[i] = '9'
break
return int(''.join(s))
###C
int maximum69Number(int num) {
char s[20];
sprintf(s, "%d", num);
for (int i = 0; s[i] != '\0'; i++) {
if (s[i] == '6') {
s[i] = '9';
break;
}
}
return atoi(s);
}
###Rust
impl Solution {
pub fn maximum69_number (num: i32) -> i32 {
let mut s = num.to_string().chars().collect::<Vec<char>>();
for i in 0..s.len() {
if s[i] == '6' {
s[i] = '9';
break;
}
}
s.iter().collect::<String>().parse().unwrap()
}
}
###JavaScript
var maximum69Number = function (num) {
let charArray = [...num.toString()];
for (let i = 0; i < charArray.length; i++) {
if (charArray[i] === '6') {
charArray[i] = '9';
break;
}
}
return Number(charArray.join(''));
};
###TypeScript
function maximum69Number(num: number): number {
let charArray = [...num.toString()];
for (let i = 0; i < charArray.length; i++) {
if (charArray[i] === '6') {
charArray[i] = '9';
break;
}
}
return Number(charArray.join(''));
};
复杂度分析
-
时间复杂度:$O(\log \textit{num})$。
-
空间复杂度:$O(\log \textit{num})$。
方法二:贪心 + 数学
思路与算法
思想同方法一,但是不依赖字符串操作,而是通过纯数学的方式找到最高位的 $6$ 并更改为 $9$。
首先初始化一个基数 $\textit{digitBase} = 10^{\lfloor \log_{10}(\textit{num}) \rfloor}$,这个基数代表了 $\textit{num}$ 的最高位。然后从高位向低位遍历,每次将 $\textit{digitBase}$ 除以 $10$。在每一次循环中,通过 $\lfloor \textit{num} \div \textit{digitBase} \rfloor \bmod 10$ 来获取当前基数 $\textit{digitBase}$ 所在的十进制位上的数字。一旦这个数字等于 $6$,我们就可以确定这就是需要修改的最高位的 $6$。此时,我们将 $\textit{num}$ 加上 $3 \times \textit{digitBase}$,即可将该位的 $6$ 修改为 $9$,结果即为所求。
代码
###C++
class Solution {
public:
int maximum69Number (int num) {
int digitBase = pow(10, (int)log10(num));
while (digitBase > 0) {
if ((num / digitBase) % 10 == 6) {
num += 3 * digitBase;
return num;
}
digitBase /= 10;
}
return num;
}
};
###Java
public class Solution {
public int maximum69Number (int num) {
int digitBase = (int)Math.pow(10, (int)Math.log10(num));
while (digitBase > 0) {
if ((num / digitBase) % 10 == 6) {
num += 3 * digitBase;
return num;
}
digitBase /= 10;
}
return num;
}
}
###C#
public class Solution {
public int Maximum69Number (int num) {
int digitBase = (int)Math.Pow(10, (int)Math.Log10(num));
while (digitBase > 0) {
if ((num / digitBase) % 10 == 6) {
num += 3 * digitBase;
return num;
}
digitBase /= 10;
}
return num;
}
}
###Go
func maximum69Number(num int) int {
digitBase := int(math.Pow10(int(math.Log10(float64(num)))))
for digitBase > 0 {
if (num / digitBase) % 10 == 6 {
num += 3 * digitBase
return num
}
digitBase /= 10
}
return num
}
###Python
class Solution:
def maximum69Number (self, num: int) -> int:
digit_base = 10 ** int(math.log10(num)) if num != 0 else 0
while digit_base > 0:
if (num // digit_base) % 10 == 6:
num += 3 * digit_base
return num
digit_base = digit_base // 10
return num
###C
int maximum69Number(int num) {
int digitBase = pow(10, (int)log10(num));
while (digitBase > 0) {
if ((num / digitBase) % 10 == 6) {
num += 3 * digitBase;
return num;
}
digitBase /= 10;
}
return num;
}
###Rust
impl Solution {
pub fn maximum69_number (num: i32) -> i32 {
let mut digit_base = 10i32.pow((num as f32).log10() as u32);
let mut num = num;
while digit_base > 0 {
if (num / digit_base) % 10 == 6 {
num += 3 * digit_base;
return num;
}
digit_base /= 10;
}
num
}
}
###JavaScript
var maximum69Number = function (num) {
let digitBase = Math.pow(10, Math.trunc(Math.log10(num)));
while (digitBase > 0) {
if (Math.trunc(num / digitBase) % 10 === 6) {
num += 3 * digitBase;
return num;
}
digitBase = Math.trunc(digitBase / 10);
}
return num;
};
###TypeScript
function maximum69Number(num: number): number {
let digitBase = Math.pow(10, Math.trunc(Math.log10(num)));
while (digitBase > 0) {
if (Math.trunc(num / digitBase) % 10 === 6) {
num += 3 * digitBase;
return num;
}
digitBase = Math.trunc(digitBase / 10);
}
return num;
};
复杂度分析
-
时间复杂度:$O(\log \textit{num})$。
-
空间复杂度:$O(1)$。
C 不转换字符串
解题思路
循环看看哪个6最靠前,然后加上3的x次幂即可
(4ms, 61.64%; 6.8MB, 100.00%)
代码
###c
#include <Math.h>
int maximum69Number (int num){
int count = 0, th = 0; // count 记录除了多少次,th记录最大的6在第几位
int re = num;
while(re){
count++;
if(re%10==6)
th = count;
re /= 10;
}
return num+3*pow(10,th-1);
}