阅读视图

发现新文章,点击刷新页面。

每日一题-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 。

前端实现自动检测项目部署更新

概述 用户在访问单页面网站时,如果生产环境已经发布了新的版本(有功能上的变化),由于单页面中路由特性或浏览器缓存的原因,并不会重新加载前端资源,此时用户浏览器所并非加载是最新的代码,从而可能遇到一些

监听设备网络状态

概述 在前端应用中监听网络状态是一个常见的需求,可以用于优化离线体验、提示用户网络变化等。 场景 移动端项目,有大量的图片需要访问,在4g或者wifi的网络状态下做不同的优化 在后台系统访问,有时候会

两种方法:用字符串/不用字符串(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$:

  1. 初始化 $x=\textit{num}$。
  2. 通过 $x\bmod 10$ 取到个位数 $9$,然后把 $x$ 除以 $10$(下取整),得到 $x=966$。
  3. 再次 $x\bmod 10$ 取到十位数 $6$,然后把 $x$ 除以 $10$(下取整),得到 $x=96$。
  4. 再次 $x\bmod 10$ 取到百位数 $6$,然后把 $x$ 除以 $10$(下取整),得到 $x=9$。
  5. 最后 $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)$。

思考题

  1. 改成求最小数字。
  2. 额外输入一个正整数 $k$,至多翻转 $k$ 个数,返回可以得到的最大数字。
  3. 给定正整数 $\textit{low}$ 和 $\textit{high}$,计算闭区间 $[\textit{low},\textit{high}]$ 中的所有整数 $x$ 的 $\texttt{maximum69Number}(x)$ 之和。

欢迎在评论区分享你的思路/代码。

专题训练

见下面贪心题单的「§3.1 字典序最小/最大」。

分类题单

如何科学刷题?

  1. 滑动窗口与双指针(定长/不定长/单序列/双序列/三指针/分组循环)
  2. 二分算法(二分答案/最小化最大值/最大化最小值/第K小)
  3. 单调栈(基础/矩形面积/贡献法/最小字典序)
  4. 网格图(DFS/BFS/综合应用)
  5. 位运算(基础/性质/拆位/试填/恒等式/思维)
  6. 图论算法(DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流)
  7. 动态规划(入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望)
  8. 常用数据结构(前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树)
  9. 数学算法(数论/组合/概率期望/博弈/计算几何/随机算法)
  10. 贪心与思维(基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造)
  11. 链表、二叉树与回溯(前后指针/快慢指针/DFS/BFS/直径/LCA/一般树)
  12. 字符串(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);
}

Threejs源码系列- Object3D

Object3D three.js核心类 _v1:V通用向量临时存储,例如在 translateOnAxis 方法中计算平移向量,或在坐标转换时临时存储中间结果。 _q1:临时存储旋转四元数,例如在
❌