leetcode258. 各位相加(简单题,但是你不看答案想不出来)

举报
兔老大 发表于 2021/04/24 01:28:03 2021/04/24
1.9k+ 0 0
【摘要】 给定一个非负整数 num,反复将各个位上的数字相加,直到结果为一位数。 示例: 输入: 38 输出: 2  解释: 各位相加的过程为:3 + 8 = 11, 1 + 1 = 2。 由于 2 是一位数,所以返回 2。 进阶: 你可以不使用循环或者递归,且在 O(1) 时间复杂度内解决这个问题吗? 思路:我想的是给的int是有范围的,我就重复很多次即可。...

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

示例:

输入: 38
输出: 2 
解释: 各位相加的过程为:3 + 8 = 11, 1 + 1 = 2。 由于 2 是一位数,所以返回 2。
进阶:
你可以不使用循环或者递归,且在 O(1) 时间复杂度内解决这个问题吗?

思路:我想的是给的int是有范围的,我就重复很多次即可。


      class Solution {
      public int addDigits(int num) {
       num = num % 10 + num / 10;
       num = num % 10 + num / 10;
       num = num % 10 + num / 10;
       num = num % 10 + num / 10;
       num = num % 10 + num / 10;
       num = num % 10 + num / 10;
       num = num % 10 + num / 10;
       num = num % 10 + num / 10;
       num = num % 10 + num / 10;
       num = num % 10 + num / 10;
       num = num % 10 + num / 10;
       num = num % 10 + num / 10;
       num = num % 10 + num / 10;
       num = num % 10 + num / 10;
       num = num % 10 + num / 10;
       num = num % 10 + num / 10;
       num = num % 10 + num / 10;
       num = num % 10 + num / 10;
       num = num % 10 + num / 10;
       num = num % 10 + num / 10;
       num = num % 10 + num / 10;
      return num;
       }
      }
  
 

这是所谓正解,确实开阔了思路:

除了传统的单纯循环,还可以找规律。假如一个三位数'abc',其值大小为s1 = 100 * a + 10 * b + 1 * c,经过一次各位相加后,变为s2 = a + b + c,减小的差值为(s1 -s2) = 99 * a + 9 * b,差值可以被9整除,每一个循环都这样,缩小了9的倍数。当num小于9,即只有一位时,直接返回num,大于9时,如果能被9整除,则返回9(因为不可能返回0也不可能返回两位数及以上的值),如果不能被整除,就返回被9除的余数。


      class Solution:
      def addDigits(self, num: int) -> int:
      if num > 9:
       num = num % 9
      if num == 0:
      return 9
      return num
  
 

文章来源: fantianzuo.blog.csdn.net,作者:兔老大RabbitMQ,版权归原作者所有,如需转载,请联系作者。

原文链接:fantianzuo.blog.csdn.net/article/details/114321839

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

作者其他文章

评论(0

抱歉,系统识别当前为高风险访问,暂不支持该操作

    全部回复

    上滑加载中

    设置昵称

    在此一键设置昵称,即可参与社区互动!

    *长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

    *长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。