CTF of Z2BNS
0%

各位相加

发表于 分类于 ，
| 阅读次数： |
Valine：
本文字数： 810 阅读时长 ≈ 1 分钟

题目地址

难度：⭐

题目描述：

给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。

示例：

1
2
3
输入: 38
输出: 2 
解释: 各位相加的过程为：3 + 8 = 11, 1 + 1 = 2。 由于 2 是一位数，所以返回 2。

进阶:

你可以不使用循环或者递归，且在 O(1) 时间复杂度内解决这个问题吗？

🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️解题过程🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️
解题过程：

思路：

递归，将各个位上数字相加，直到结果为一位数。

c++代码：(执行用时0ms，击败100.00%，内存消耗6.2M，击败14.00%）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int addDigits(int num) {
        int sum=0;
        while(num){
            sum+=num%10;
            num/=10;
        }
        if(sum/10!=0){
            sum=addDigits(sum);
        }
        return sum;
    }
};
💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎官 方 题 解💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎
官方题解:

方法一： 模拟

我们可以不使用额外的（非常数）空间来完成翻转和反转操作。对于 A[i][j]​，我们将它和 A[i][c - j - 1]​ 进行交换（即翻转），其中 c 是数组 A 的列数。在交换的同时，我们可以将这两个数进行反转。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int[][] flipAndInvertImage(int[][] A) {
        int C = A[0].length;
        for (int[] row: A)
            for (int i = 0; i < (C + 1) / 2; ++i) {
                int tmp = row[i] ^ 1;
                row[i] = row[C - 1 - i] ^ 1;
                row[C - 1 - i] = tmp;
            }
        return A;
    }
}

复杂度分析

  • 时间复杂度：$O(M*N)$，其中 $M$ 和 $N$ 分别为数组 A 的行数和列数。
  • 空间复杂度：$O(1)$。
⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳总 结⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳
总结：

官方题解和我的思路一样，不过对于特殊情况比我处理的好，也不算特殊情况吧，只是我自己把它当作特殊情况处理了，主要在于我使用了vector容器中的swap成员函数来交换两个元素，这样必须反转后覆盖原值，对于奇数行数矩阵的每行中间元素反转了两次，而采用tmp辅助变量来进行交换两个元素值不涉及到覆盖问题。其实就是太执着于STL模板库中的成员函数了，自己实现交换元素的功能也挺好，相当于对源码根据实际情况进行了改进，这样才能更灵活地处理问题。

------------- THE END! THANKS! -------------