Monday, October 30, 2017

[LeetCode]Base 7


进制转化的问题,我们一般用除k取余法。假设输入数字为n(十进制),我们要把它转化为k进制数m,具体的做法是:

  1. 我们求d = n % k,d就是我们要求的当前位。如果m为空,k就为m的最低位;否则k就为当前已求的m的最高位
  2. 我们更新n为n = n / k
  3. 重复以上两步直到n为0
这个方法其实很好理解。对于一个数n,如果我们要求其当前对应k进制的最低位,我们只需要对其模k,这个是显而易见的。那么我们要求其第二低的位的话,我们需要把对应k进制的数m砍去最后一位,求得m',m'的最低位就是我们要求的m的第二低位。如果对于n我们除k,那么就相当于把m的最后一位砍去了(想象一下十进制的数除以10),这也就是第二步的含义。
举个例子,我们把十进制的100转化为七进制m:
  1. d = 100 % 7 = 2,所以m的最低位是2,当前m = 2
  2. 100 / 7 = 14,我们去掉了100转化为7进制后的最低位,接下来处理14
  3. d = 14 % 7 = 0, m变为02
  4. 14 / 7 = 2,我们接下来处理2
  5. d = 2 % 7 = 2, m = 202
  6. 2 / 7 = 0,算法结束,202就是十进制100对应的七进制
不仅仅是十进制转化成k进制,除k取余法适用于任何进制到任何进制,比如我们从十六进制转化为十进制,我们自然可以把每一位乘以其对应十进制的表示来算出最后十进制的值。但我们这里用除k取余法算一遍。假设十六进制为ABC,我们这里除法对应的是16进制,进制虽然变了,但是乘除法本质的规则还是一样的,只是进退位不一样了,比如在16进制当中,9 * 9 = 51而不是十进制当中的81:
  1. d = ABC % A(10) = 8, 当前m = 8
  2. ABC / A(10) = 112
  3. d = 112 % A(10) = 4, m = 48
  4. 112(16进制) / A(10) = 1B
  5. d = 1B % A(10) = 7, m = 748
  6. 1B / A(10) = 2
  7. d = 2 % A(10) = 2, m = 2748
  8. 2 / A(10) = 0,算法结束,ABC对应的十进制为2748
我们最后再举一个非十进制的例子,比如九进制28到五进制m,这里对应的都是九进制的乘除法:
  1. 28(9进制) % 5 = 1, m = 1
  2. 28(9进制) / 5 = 5
  3. 5(9进制) % 5 = 0, m = 01
  4. 5 (9进制)/ 5 = 1
  5. 1(9进制) % 5 = 1,m = 101
  6. 1 / 5 = 0,101就是我们要求的五进制的值

 这套题我们套用除k取余法即可,时间复杂度O(n),n为输入数字的位数,代码如下:


递归:


循环:

No comments:

Post a Comment