最近在看leetcode,并且正在上面刷一些简单级别的题目(不过说真的,这些题真的简单吗??或许是我太菜,有些感觉也很难
本篇记录5道题的解题思路,可能都是最笨的方法
No.1 判断字符是否唯一
题目描述:
实现一个算法,确定一个字符串 s 的所有字符是否全都不同
示例 1:
输入: s = "leetcode"
输出: false
示例 2:
输入: s = "abc"
输出: true
限制:
0 <= len(s) <= 100
原题链接:
https://leetcode-cn.com/problems/is-unique-lcci/
解决思路:
python中有一个内置函数set(),它的一个特性就是->可以利用已有列表、字符串、元组或字典的内容来创建集合,其中重复的值会被丢弃;
所以就可以通过set()来得到一个剔除重复值后的集合,并且比较两者的长度,如果长度相等,则证明字符唯一;如果长度不等,则字符不唯一
代码如下:
class Solution(object):
def isUnique(self, astr):
"""
:type astr: str
:rtype: bool
"""
len_1 = len(astr) # 获取传入字符串的长度
b = set(astr) # 使用set()函数将传入字符串转为一个集合,该集合剔除了重复的元素
len_2 = len(b) # 获取集合的长度
if len_1 == len_2: # 对比原字符串和集合的长度,如果两者相等,表明字符串无重复;否则表示有重复元素
print("true")
return True
else:
print("false")
return False
No.2 两数之和
题目描述:
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。
示例: 给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
原题链接:
https://leetcode-cn.com/problems/two-sum/
解决思路:
用第1个数字依次与其后面的数字相加,判断结果是否为目标值;
然后用第2个数字依次与其后面数字相加,判断结果是否为目标值;
依此类推,用第n个数,与其后的数字相加,这样就做到了任意2个数字(不重复)的叠加求和
代码如下:
class Solution(object):
def twoSum(self, nums, target):
"""
思路:用第1个数字依次与其后面的数字相加,判断结果是否为目标值;然后用第2个数字依次与其后面数字相加,判断结果是否为目标值
依次类推,用第n个数,与其后的数字相加,这样就做到了任意2个数字的不重复叠加求和
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
for i in range(0, len(nums)): # 定义第一个for循环,从第一个数字开始,深度为字符串列表的长度
for j in range(i + 1, len(nums)): # 内嵌一个for循环,从第二个数字开始,深度为字符串列表长度,
if nums[i] + nums[j] == target: # 先用第一个数字(nums[i]代表加号左侧数字)分别与其后的数字(nums[j]加号右侧数字)叠加,判断结果是否为目标值
return i, j # 如果相加得到目标值,则返回下角标组合的列表
else:
continue # 如果不是,则继续循环
No.3 回文数
题目描述:
判断一个整数是否是回文数。
回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。
示例 1:
输入: 121
输出: true
示例 2:
输入: -121
输出: false
解释: 从左向右读, 为 -121 。从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。
进阶:
你能不将整数转为字符串来解决这个问题吗?
原题链接:
https://leetcode-cn.com/problems/palindrome-number/
解决思路:
把输入的数字先转换成列表,反向取出来,也就是从最后一个开始提取,
然后依次追加到一个新的列表并组合成一个新的字符串,
最后与原字符串判断是否相等
代码如下:
class Solution(object):
def isPalindrome(self, x):
"""
解决思路:把输入字符串转换成列表,反向取出来,也就是从最后一个开始提取,然后依次追加到一个新的列表并组合成一个新的字符串,然后与原字符串判断是否相等
:type x: int
:rtype: bool
"""
string = str(x) # 将输入的整数转为字符串
s_list = list(string) # 将字符串转为列表
n_list = [] # 定义一个空列表,用于存储下面反向输出的列表
for t in range(0, len(s_list)):
n_list.append(s_list[len(s_list)-t-1])
n_string = "".join(n_list) # 将新的列表转为字符串
if string == n_string: # 判断2个字符串的值是否相等(注意⚠️:不要用is判断,is是用来判断其id值是否相等,==判断其值是否相等)
return True
else:
return False
另一种写法更简单些,把输入数字转换成字符串后,直接通过切片的方法,反向输出得到一个新的字符串
def isPalindrome_2(self, x):
string = str(x)
new_string = string[::-1]
if string == new_string:
return True
else:
return False
No.4 整数反转
题目描述:
给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。
示例 1:
输入: 123
输出: 321
示例 2:
输入: -123
输出: -321
示例 3:
输入: 120
输出: 21
注意:
假设我们的环境只能存储得下 32 位的有符号整数,则其数值范围为 [−231, 231 − 1]。请根据这个假设,如果反转后整数溢出那么就返回 0
原题链接:
https://leetcode-cn.com/problems/reverse-integer/
解决思路:
先把整数转换为字符串,然后利用字符串切片的方法将其进行反转(注意:如果传入的是负数,需要保留"-"前缀,只将后面的字符反转)
代码如下:
class Solution(object):
def reverse(self, x):
"""
:type x: int
:rtype: int
"""
l = str(x) # 把输入的数字转换为字符串
if l[0] == "-": # 如果首位字符是"-"(也就是说输入一个负数)
s = l[1:] # 截取"-"之后的部分
new = s[::-1] # 将"-"之后的部分进行反转,得到一个新字符串
i = "" # 定义一个空字符串
for t in new:
i += t # 遍历新列表中的值,并将结果一个个追加到空字符串中
i = "-" + i # 将"-"与最终的字符串i组合,得到最终的字符串
else:
new = l[::-1] # 如果首位字符不是"-",则直接进行反转
i = ""
for t in new:
i += t
if -2 ** 31 <= int(i) <= 2 ** 31 - 1:
return int(i) # 将反转后的字符串i转换为整型数字,并判断结果是否在允许范围内,如果在,则将其返回;如果不在,则返回0
else:
return 0
No.5 最长公共前缀
题目描述:
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 ""。
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"
示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
说明:所有输入只包含小写字母 a-z 。
原题链接:
https://leetcode-cn.com/problems/longest-common-prefix/
解决思路:
这个把我难住了,后来看了官方题解,里面有一个横向扫描法和一个纵向扫描法,下面根据自己的理解来实现了一下
代码如下:
横向扫描法
class Solution(object):
def longestCommonPrefix(self, strs):
"""
横向扫描法
:type strs: List[str]
:rtype: str
"""
if not strs:
return ""
else:
prefix = strs[0] # 把字符串列表中的第一个字符串赋给一个变量
length = len(strs) # 获取整个字符串列表的长度
for t in range(1, length):
prefix = self.common_start(prefix, strs[t])
# 调用common_start方法比较2个字符串,提取公共前缀,然后将获取到的公共前缀再与后一个字符串比较
if not prefix: # 当在后续比较中没有公共前缀(即公共前缀为空时,退出循环)
break
return prefix # 循环完成后,返回最终的公共前缀
@staticmethod
def common_start(str1, str2):
"""
获取2个字符的公共前缀
:param str1:
:param str2:
:return:
"""
length = min(len(str1), len(str2)) # 获取2个字符串的最小长度
if length == 0: # 如果最小字符串长度为0,则意味着有空字符串,所以公共前缀为""
return ""
else:
common = "" # 定义一个空字符串,用来存储公共前缀
for i in range(0, length): # 以最小长度字符串的长度作为遍历深度
common += str1[i] # 把字符串1的第i个字符追加到common中
if str2.startswith(common): # 利用自带的startswith()函数,判断字符串2是否以common为前缀,如果以common为前缀,则继续循环
continue
else: # 如果字符串2不是以common为前缀,则返回common除掉最后一个字符外的部分
return common[:-1]
return common # 如果一直满足if条件,则说明字符串2是以common为前缀,所以当循环走完后,返回最后的common字符串
纵向扫描法
class Solution(object):
@staticmethod
def longestCommonPrefix2(strs):
"""
纵向扫描法
:param strs:
:return:
"""
if not strs: # 如果传入空列表,则返回空字符串
return ""
for i in range(0, len(strs[0])): # 获取第一个字符串的长度,并以此作为循环深度
c = strs[0][i] # 获取第一个字符串,并且从其第一个字符开始遍历(以第一个字符串为纵向扫描依据,判断第一个字符串的各列是否与后续字符串的各列相同)
for j in range(1, len(strs)): # 获取整个字符串列表的长度,从第二个字符串开始分别与第一个字符串比对
if i <= len(strs[j])-1: # 在把第二个字符串的字符与第一个字符串的字符比对前,先判断后续字符串的长度是否大于等于第一个字符串的长度(防止提取后续字符串的字符时,出现溢出)
if strs[j][i] == c: # 从第二个字符串开始,依次判断后续字符串的第i个字符是否与第1个字符串的第i个字符相等,如果相等,则通过,继续下一轮判断;
pass
else: # 如果不相等,则退出循环,返回第一个字符串的前i个字符
print("第1个return")
return strs[0][:i]
else: # 如果后续字符串的长度比第一个字符串短,则strs[j][i]最终会溢出,此时退出循环,返回第一个字符串的前i个字符
print("第2个return")
return strs[0][:i]
print("第3个return")
return strs[0] # 如果一直满足所有if条件,则说明第一个字符串的字符都是公共前缀,最终返回第一个字符串