继续上一篇文章，继续刷刷题。
存在重复元素
这边实际上是两个题目：
第一个比较简单
题目描述：
给定一个整数数组，判断是否存在重复元素。
如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。
输入: [1,2,3,1]
输出: true
答案如下：
class Solution(object):
def containsDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
newnums=list(set(nums))
return sorted(nums) != sorted(newnums)
用到了set去重和sorted排序
第二题
题目描述：
给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的绝对值最大为 k。
输入: nums = [1,2,3,1], k = 3
输出: true
一开始的没有读题仔细，以为必须要满足i和j的差为K，增加了难度
答案如下：
class Solution(object):
def containsNearbyDuplicate(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: bool
"""
length = len(nums)
dic_num={}
for i in range(length):
if nums[i] not in dic_num:
dic_num[nums[i]]=i
else:
if i - dic_num[nums[i]] <=k:
return True
else:
dic_num[nums[i]] = i
return False
新增了一个字段，用来key为 nums[i] 的值，value为 index值，如果已经存在字典中则检查 i和j的差值小于k，则返回true
字典和列表的读取速度
期间有一次提答案提示我超时，原因是：
if nums[i] not in dic_num:
这一句，我写成了
if nums[i] not in dic_num.keys():
第二段代码 dic_num.keys()变成了list，python在检索list的时候是比较慢的，第一段代码 dic_num是字典，python在检索字典的时候速度是比较快的
总的来说就是：
字典生成慢,查找快。 列表生成快,查找慢
检测大写字母
题目描述：
给定一个单词，你需要判断单词的大写使用是否正确。
我们定义，在以下情况时，单词的大写用法是正确的：
- 全部字母都是大写，比如"USA"。
- 单词中所有字母都不是大写，比如"leetcode"。
- 如果单词不只含有一个字母，只有首字母大写， 比如 "Google"。
输入: "USA"
输出: True
答案如下：
class Solution(object):
def detectCapitalUse(self, word):
"""
:type word: str
:rtype: bool
"""
if (word[0].upper()+word[1:].lower())==word or word==word.upper() or word == word.lower():
return True
else:
return False
三种场景满足其中一种即返回True:
- 1.全是小写字母
- 2.全是大写字母
- 3.首字母大写
缺失数字
题目描述：
给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。
输入: [9,6,4,2,3,5,7,0,1]
输出: 8
解题思路：
将列表中所有数相加得到一个数n
将列表中最大的数，求0 1 2 3...到n的和，得到m
m-n的差即为缺失的数字
答案：
class Solution(object):
def missingNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
num=0
for i in nums:
num = i+num
n=0
for i in range(max(len(nums)+1,sorted(nums)[-1]+1)):
n=n+i
return(n-num)
删除排序数组中的重复项
题目描述：
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
思路：
对比num[i] 和 num[i+1]的值，相同则删去一个
答案：
class Solution(object):
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
i=0
while i < len(nums)-1:
if nums[i] == nums[i+1]:
del(nums[i])
continue
i+=1
print nums
重复的子字符串
题目描述：
给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000
输入: "abcabcabcabc"
输出: True
解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)
思路
既然是重复字符串，可以理解是sn= s*n
遍历sn的一半（节约时间），如果找到 sn[:i] * length/i == sn即满足重复字符串
答案：
class Solution(object):
def repeatedSubstringPattern(self, s):
"""
:type s: str
:rtype: bool
"""
length = len(s)
for i in range(1,length/2+1):
if length % i == 0:
if s==(s[:i] * (length/i)):
return True
break
else:
return False
重复叠加字符串匹配
题目描述：
给定两个字符串 A 和 B, 寻找重复叠加字符串A的最小次数，使得字符串B成为叠加后的字符串A的子串，如果不存在则返回 -1。
举个例子，A = "abcd"，B = "cdabcdab"。
答案为 3， 因为 A 重复叠加三遍后为 “abcdabcdabcd”，此时 B 是其子串；A 重复叠加两遍后为"abcdabcd"，B 并不是其子串
思路
- 如果A比B长：
- A包含B，返回1
- A不包含B，A*2，如果还不包含B ，那就永远不可能包含了，返回-1
- 如果A比B短或者一样长
假设B的A长的n倍，那么 至少A*n才有可能包含B的话
答案：
class Solution(object):
def repeatedStringMatch(self, A, B):
"""
:type A: str
:type B: str
:rtype: int
"""
lenA=len(A)
lenB=len(B)
i=lenB // lenA
if B not in A:
for n in range(i,2*(i+2)):
if B in A * n:
return n
break
else:
return -1
else:
return 1
更多答案，请参考 Github ，欢迎批评指正，交流学习。
网友评论