一、扑克牌中的顺子
题目描述
- 从扑克牌中随机抽5张牌,判断是不是一个顺子,即这5张牌是不是连续的。
- 2~10为数字本身,A为1,J为11,Q为12,K为13,而大、小王为 0 ,可以看成任意数字。A 不能视为 14。
示例
- 示例 1:
-
- 输入: [1,2,3,4,5]
- 输出: True
-
-
- 示例 2:
-
- 输入: [0,0,1,2,5]
- 输出: True
解题
- class Solution:
- def isStraight(self, nums: List[int]) -> bool:
- nums.sort()
- zero_count = 0
- for i in range(4):
- if nums[i] == 0:
- zero_count += 1
- elif nums[i] == nums[i + 1]:
- return False
- return nums[4] - nums[zero_count] < 5
这题对于不玩牌的人来说,咋一看理解可能比较费劲。其实可以转为,给你随机5个数,看看是不是顺子,比如12345。然后
这其中如果有0,可以看做任意数,0数量最多2个。
此题的关键点是:
- 知道0的数量
- 判断是否有0以外重复的数,如果有,就直接返回False
- 最关键的,还是 当 最大数-最小数 总是要小于 5
二、实现 strStr()
题目描述
- 实现 strStr() 函数。
-
- 给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 needle 字符串出现的第一个位置(下标从 0 开始)。
- 如果不存在,则返回 -1 。
-
- 说明:
-
- 当 needle 是空字符串时,我们应当返回什么值呢?这是一个在面试中很好的问题。
-
- 对于本题而言,当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。
示例
- 示例 1:
-
- 输入:haystack = "hello", needle = "ll"
- 输出:2
- 示例 2:
-
- 输入:haystack = "aaaaa", needle = "bba"
- 输出:-1
- 示例 3:
-
- 输入:haystack = "", needle = ""
- 输出:0
解题
- class Solution:
- def strStr(self, haystack: str, needle: str) -> int:
- m = len(haystack)
- n = len(needle)
- if n == 0:
- return 0
- for i in range(m):
- if haystack[i:i+n] == needle:
- return i
- return -1
直接暴力破解吧。
比如haystack="hello"
,needle="ll"
, 可以知道needle
长度是2,那么就for循环hello
,看下长度是2子串跟needle
是不是相等。
注意下判断空字符串的情况。
三、验证回文串
题目描述
- 给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。
-
- 说明:本题中,我们将空字符串定义为有效的回文串。
示例
- 示例 1:
-
- 输入: "A man, a plan, a canal: Panama"
- 输出: true
- 示例 2:
-
- 输入: "race a car"
- 输出: false
解题
- class Solution:
- def isPalindrome(self, s: str) -> bool:
- if s == "":
- return True
- temp_list = []
- for i in s:
- if i.isdigit():
- temp_list.append(i)
- if i.isalpha():
- temp_list.append(i.lower())
- return temp_list == temp_list[::-1]
思想就是判断输入的字符串和它的反序是不是相等,但是题目中给出了其他的情况需要考虑:
- 只考虑字母和数字字符
- 可以忽略字母的大小写
- 空字符串定义为有效的回文串
可以遍历字符串,然后把字符放到列表里,注意等于字母时候的处理,统一转成小写,最后与列表的反序相比。
四、字符串相加
题目描述
给定两个字符串形式的非负整数 num1 和num2 ,计算它们的和。
示例
- 提示:
-
- num1 和num2 的长度都小于 5100
- num1 和num2 都只包含数字 0-9
- num1 和num2 都不包含任何前导零
- 你不能使用任何內建 BigInteger 库, 也不能直接将输入的字符串转换为整数形式
解题
- class Solution:
- def addStrings(self, num1: str, num2: str) -> str:
- cur1 = len(num1) - 1
- cur2 = len(num2) - 1
- carry = 0
- res = ""
-
- while cur1 >= 0 or cur2 >= 0:
- if cur1 >= 0:
- n1 = int(num1[cur1])
- else:
- n1 = 0
- if cur2 >= 0:
- n2 = int(num2[cur2])
- else:
- n2 = 0
- temp = n1 + n2 + carry
- carry = temp // 10
- res = str(temp % 10) + res
- cur1 -= 1
- cur2 -= 1
- if carry:
- return "1" + res
- else:
- return res
实现竖向相加的过程。
- 11 // 入参1
- + 123 // 入参2
- 从个位开始向左,所以定义2个指针分别指到2个输入字符串的末尾。
- 两数相加,逢10进1。定义变量
carry
表示是否进1,初始化为0,循环中通过carry = temp // 10
赋值。 - 临时相加的和
temp
等于n1 + n2 + carry
,注意这里n1、n2
遍历是字符串,要用int()
转下,
才可以与carry
相加。 - 初始化空字符
res = ""
,每次相加的结果除以10,取余数添加到res的前面,res = str(temp % 10) + res
- 每次循环后,2个指针分别 -1,也就是向左移动 1。
- 当2个指针任意一个小于0了,就把当前的索引值为0,方便计算。
- 直到2个指针都小于0,跳出循环。
- 此时,如果carry!=0,说明进1,结果前面需要加上1,
"1" + res
,否则直接返回res
。
五、移动零
题目描述
给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。
示例
- 示例:
-
- 输入: [0,1,0,3,12]
- 输出: [1,3,12,0,0]
- 说明:
-
- 必须在原数组上操作,不能拷贝额外的数组。
- 尽量减少操作次数。
解题
- class Solution:
- def moveZeroes(self, nums: List[int]) -> None:
- """
- Do not return anything, modify nums in-place instead.
- """
- n = len(nums)
- right = left = 0
- while right < n:
- if nums[right] != 0:
- nums[right], nums[left] = nums[left], nums[right]
- left += 1
- right += 1
只能原地移动,考虑使用双指针right
和left
,例如输入了[0,1,0,3,12]
:
- 初始化
right = left = 0
。 right
一直向右移动,并且找到非0的元素,找到之后就跟left
所在的元素交换位置。- 交换位置后,
left
向右移动1。