跳转至

4070. 拨号的最少旋转次数 I

来源第 522 场周赛 Q1难度简单分数1156

题目描述

给你一个长度为 10、由数字组成的字符串 s。

拨号盘上的数字 0 到 9 按顺序排列，且拨号盘是环形的，因此 0 和 9 相邻。指针最初指向 0。

要按顺序拨出 s 中的每个数字，需要旋转指针，直到它指向该数字。每次旋转都会将指针移动到一个相邻的数字，你可以向任一方向旋转。如果指针已经指向要拨出的数字，则无需旋转。

返回拨出 s 中所有数字所需的最少总旋转次数。

 

示例 1：

输入： s = "0192837465"

输出： 25

解释：

步骤 起始数字 目标数字 旋转次数
1 0 0 0
2 0 1 1
3 1 9 2
4 9 2 3
5 2 8 4
6 8 3 5
7 3 7 4
8 7 4 3
9 4 6 2
10 6 5 1

总旋转次数为 0 + 1 + 2 + 3 + 4 + 5 + 4 + 3 + 2 + 1 = 25，这是最少的总旋转次数。

示例 2：

输入： s = "1200210200"

输出： 12

解释：

步骤 起始数字 目标数字 旋转次数
1 0 1 1
2 1 2 1
3 2 0 2
4 0 0 0
5 0 2 2
6 2 1 1
7 1 0 1
8 0 2 2
9 2 0 2
10 0 0 0

总旋转次数为 1 + 1 + 2 + 0 + 2 + 1 + 1 + 2 + 2 + 0 = 12，这是最少的总旋转次数。

 

提示：

  • s.length == 10
  • s 仅由数字 '0' 到 '9' 组成

解法

方法一

思考

每次拨号只关心当前指针位置和目标数字，其余历史不会影响后续选择，因此可以按顺序贪心处理每一位。

从数字 \(a\) 转到数字 \(b\) 时，顺时针和逆时针两条路径的步数分别互补为 \(10\)。设两者的数字差为 \(d=|a-b|\)，那么最少旋转次数就是 \(\min(d, 10-d)\)。

初始指针在 \(0\)，依次累加相邻两次拨号之间的最小代价即可。

设上一位所在数字为 \(\textit{pre}\)，当前要拨到的数字为 \(\textit{cur}\)。由于拨号盘是环形的，从 \(\textit{pre}\) 走到 \(\textit{cur}\) 的最短距离为

\[ \min\bigl(|\textit{cur}-\textit{pre}|, 10-|\textit{cur}-\textit{pre}|\bigr). \]

从初始位置 \(0\) 开始遍历字符串中的每个字符，计算这一段最短距离并累加到答案中，然后更新 \(\textit{pre}\) 即可。

时间复杂度 \(O(n)\)，空间复杂度 \(O(1)\)。其中 \(n\) 为字符串 \(s\) 的长度。

1
2
3
4
5
6
7
8
class Solution:
    def minRotations(self, s: str) -> int:
        ans = pre = 0
        for cur in map(int, s):
            diff = abs(cur - pre)
            ans += min(diff, 10 - diff)
            pre = cur
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    public int minRotations(String s) {
        int ans = 0;
        int pre = 0;
        for (int i = 0; i < s.length(); ++i) {
            int cur = s.charAt(i) - '0';
            int diff = Math.abs(cur - pre);
            ans += Math.min(diff, 10 - diff);
            pre = cur;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    int minRotations(string s) {
        int ans = 0;
        int pre = 0;
        for (int i = 0; i < s.size(); ++i) {
            int cur = s[i] - '0';
            int diff = abs(cur - pre);
            ans += min(diff, 10 - diff);
            pre = cur;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
func minRotations(s string) int {
    ans := 0
    pre := 0
    for i := 0; i < len(s); i++ {
        cur := int(s[i] - '0')
        diff := abs(cur - pre)
        ans += min(diff, 10-diff)
        pre = cur
    }
    return ans
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function minRotations(s: string): number {
    let ans = 0;
    let pre = 0;
    for (let i = 0; i < s.length; ++i) {
        const cur = s.charCodeAt(i) - 48;
        const diff = Math.abs(cur - pre);
        ans += Math.min(diff, 10 - diff);
        pre = cur;
    }
    return ans;
}

评论