判断是否是完全平方数
给定一个正整数 num,编写一个函数,如果 num 是一个完全平方数,则返回 True,否则返回 False。
说明:不要使用任何内置的库函数,如 sqrt。
示例 1:
输入:16输出:True示例 2:
输入:14输出:False
最开始想到的是使用sqrt()直接判断,什么?不能使用sqrt()?
不能使用任何内置的库函数,所以使用math.log的方案也挂掉了,老老实实去凑吧
12345678910def func(num): if(num<0): return False if(num<=2): return True for i in range(1,num//2): if(i*i==num): return True if(i*i>num): return False
虽然我觉得他肯定要卡你时间复杂度
果然后面他给我报错,MemoryError不过是发生在Line 7也就是for i in range(1,num//2):这一 ...
各个位上的数字相加
给定一个非负整数 num,反复将各个位上的数字相加,直到结果为一位数。
示例:
输入: 38输出: 2解释: 各位相加的过程为:3 + 8 = 11, 1 + 1 = 2。 由于 2 是一位数,所以返回 2。
这个直接用循环来做非常快,题目进阶要求说不使用循环和递归,且要求时间复杂度O(1)之内解决
直接上很秀的解法
12def func(num): return (num%9) or (9*bool(num))
假设原来的数是abcd即,1000*a+100*b+10*c+d之后我们需要的数字是a+b+c+d
所以a+b+c+d=(1000*a+100*b+10*c+d)-(999*a+99*b+9*c)='abcd'-9*(111*a+11*b+c) 就相当于a+b+c+d=num%9
如果num是9的倍数怎么办呢?num是0怎么办呢?
9的倍数的各位数的和就是9,而此时num%9==0,所以直接使用9*bool(num)
最后一个or 把句子缩写到一行,leecode大神写的代码真是太优雅了
重新分组密钥
给定一个密钥字符串S,只包含字母,数字以及 ‘-‘(破折号)。N 个 ‘-‘ 将字符串分成了 N+1 组。给定一个数字 K,重新格式化字符串,除了第一个分组以外,每个分组要包含 K 个字符,第一个分组至少要包含 1 个字符。两个分组之间用 ‘-‘(破折号)隔开,并且将所有的小写字母转换为大写字母。
给定非空字符串 S 和数字 K,按照上面描述的规则进行格式化。
示例 1:
输入:S = “5F3Z-2e-9-w”, K = 4
输出:”5F3Z-2E9W”
解释:字符串 S 被分成了两个部分,每部分 4 个字符; 注意,两个额外的破折号需要删掉。示例 2:
输入:S = “2-5g-3-J”, K = 2
输出:”2-5G-3J”
解释:字符串 S 被分成了 3 个部分,按照前面的规则描述,第一部分的字符可以少于给定的数量,其余部分皆为 2 个字符。
只能说这个题目没有解释清楚,一开始我以为是第一组保持不变,然后后面的转大写然后去按照K个字母来进行分组,思路就是先读取这个字符串第一个’-‘的位置,然后把后面的’-‘全部去除掉,然后根据K来进行插入’-‘即可
python代码如下 ...
两元素去重
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
说明:
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?
示例 1:
输入: [2,2,1]输出: 1示例 2:
输入: [4,1,2,1,2]输出: 4
一开始我的想法是暴力枚举,python代码如下:
123for i in nums: if(nums.count(i)==1): return i
后来一想,要求具有线性时间复杂度,对python的list.count() 不是很了解,万一这玩意本身的时间复杂度是O(n),然后一来不就O(n^n)了?
随后想到先把这个数组排个序,然后模拟栈来实现(需要使用2个int的空间来存放结果)
12345678910111213def func(nums): nums = sorted(nums) cnt = 2 stack = nums[0] for i in nums: if(i==stack): cnt = cnt-1 el ...
相同元素下标之差
给定一个整数数组和一个整数 k,判断数组中是否存在两个不同的索引 i 和 j,使得 nums [i] = nums [j],并且 i 和 j 的差的绝对值最大为 k。
这个题目花费了我不少时间,
首先暴力找他肯定要爆你的时间复杂度,所以我一开始的想法就是:
如果数组里面由两个相同的值,这两个相同的值的下标之差j-i<=k就能达到要求,那么我要是存在一个k+1的能满足要求呢,k+2的呢?如果我在k+1,k+2……之后找到了相同元素不就可以了吗,不过这样的时间复杂度也不小,一个元素至少1次
于是看看官方题解,说是建立一个长度为k的容器,然后装元素,一旦找到,就return true,如果没找到就return false
我的python代码如下
123456789101112def func(nums,k): a = [] for i in nums: if((i not in a) and (len(a)<k)): a.append(i) elif((i not in a) and len(a)==k): ...