求在计算平方根的时候,最早让0~9的数字全部出现的最小整数。注意这里只求平方根为正数的情况,并且请分别求包含整数部分的情况和只看小数部分的情况。
例)2的平方根:1.414213562373095048...(0~9全部出现需要19位)
这道题目比较含糊。
其实是找平方根(含整数部分或不含整数部分的)前十位数字正好让 0~9的数字全部出现(且不重复)的最小整数—即构成0~9的一个排列(permutation)。
关键在于题目要求既要求“最早”又要求“最小”。
假定按自然数从小到大遍历,只有找到了一个平方根前十位数字正好让 0~9 的数字全部出现的数,你才能确信找到了满足题目条件的最小整数。
在没有找到满足“平方根前十位数字正好让 0~9的数字全部出现”的数之前,你无法确定后面是不是存在满足“平方根前十位数字正好让0~9的数字全部出现”的数,所以你只能继续找下去。
所幸,满足“平方根前十位数字正好让 0~9的数字全部出现”的数是存在的。
代码中用以下判断前十个字符是否满足题设条件:
- len(set(list(first10))) == 10
这是因为set会自动删除重复元素,因此如果set的长度是10而其可能的元素又只能是0~9的话,那就必然满足条件。
- # -*- coding: utf-8 -*-
- """
- Created on Sat Sep 4 08:51:51 2021
-
- @author: chenxy
- """
-
- import sys
- import time
- import datetime
- import math
- # import random
- from typing import List
- # from queue import Queue
- # from collections import deque
-
- class Solution:
- def squareRoot1(self, sel:int) -> tuple:
- """
- Find the first interger, for which, either the first 10 digits of its square root,
- or the first 10 digits of the decimal part of its square root,
- includes all of 0~9.
-
- sel: 0--including integer part; 1: not including integer part
- ret:
- """
- i = 1
- while(1):
- i_sqrt = math.sqrt(i)
- i_sqrt_str = str(i_sqrt)
-
- # Find the position of decimal point
- for k in range(len(i_sqrt_str)):
- if i_sqrt_str[k] == '.':
- break
-
- if sel == 0:
- first10 = i_sqrt_str[0:k] + i_sqrt_str[k+1:11]
- else:
- first10 = i_sqrt_str[k+1:k+11]
- # print(first10,list(first10),set(list(first10)))
-
- if len(set(list(first10))) == 10:
- return i, i_sqrt
-
- i = i+1
-
- def squareRoot2(self) -> tuple:
- '''
- Find the first interger, for which, the first 10 digits of the decimal part of its square root,
- includes all of 0~9.
-
- ret:
- '''
- num=1
- str_num='1.000000000000000'
- while len(set(list(str_num.split('.')[1][:10])))!=10:
- num+=1
- str_num=str(num**0.5)
- return num, num**0.5
-
- if __name__ == '__main__':
-
- sln = Solution()
-
- tStart = time.time()
- num1,num1_sqrt = sln.squareRoot1(0) # including integer part
- num2,num2_sqrt = sln.squareRoot1(1) # Only considering fractional part
- tCost = time.time() - tStart
- print('num1={0}, num1_sqrt={1:.10f}, tCost = {2:6.3f}(sec)'.format(num1,num1_sqrt,tCost))
- print('num2={0}, num2_sqrt={1:.10f}, tCost = {2:6.3f}(sec)'.format(num2,num2_sqrt,tCost))
-
- tStart = time.time()
- num3,num3_sqrt = sln.squareRoot2() # Only considering fractional part
- tCost = time.time() - tStart
- print('num3={0}, num3_sqrt={1:.10f}, tCost = {2:6.3f}(sec)'.format(num3,num3_sqrt,tCost))
运行结果:
num1=1362, num1_sqrt=36.9052841745, tCost = 0.003(sec)
num2=143, num2_sqrt=11.9582607431, tCost = 0.003(sec)
num3=143, num3_sqrt=11.9582607431, tCost = 0.000(sec)
[2021-09-05]
Bijfah提示了利用字符串方法split()的更间接的代码,作为squareRoot2()追加到以上代码中了。善用python内置函数确实能让代码和运行效率都有脱胎换骨的效果。谢谢Bijfah的指点!但是squareRoot2()目前只能对付只考虑小数部分的情况,要对付含整数部分的情况的话还需要略修改造一下。