Leetcode
- Leetcode 外观数列
- Leetcode 搜索插入位置
- Leetcode 实现 StrStr
- Leetcode 移除元素
- Leetcode 删除排序数组中的重复项
- Leetcode 合并两个有序链表
- Leetcode 有效的括号
- Leetcode 最长公共前缀
- Leetcode 罗马数字转整数
- Leetcode 回文数
- Leetcode 整数反转
- Leetcode 两数之和
Leetcode 外观数列
外观数列
给定一个正整数 n（1 ≤ n ≤ 30），输出外观数列的第 n 项。
注意：整数序列中的每一项将表示为一个字符串。
「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。前五项如下：
1. 1
2. 11
3. 21
4. 1211
5. 111221
第一项是数字 1
描述前一项，这个数是 1 即 “一个 1 ”，记作 11
描述前一项，这个数是 11 即 “两个 1 ” ，记作 21
描述前一项，这个数是 21 即 “一个 2 一个 1 ” ，记作 1211
描述前一项，这个数是 1211 即 “一个 1 一个 2 两个 1 ” ，记作 111221
示例 1:
输入: 1
输出: "1"
解释：这是一个基本样例。
示例 2:
输入: 4
输出: "1211"
解释：当 n = 3 时，序列是 "21"，其中我们有 "2" 和 "1" 两组，"2" 可以读作 "12"，也就是出现频次 = 1 而 值 = 2；类似 "1" 可以读作 "11"。所以答案是 "12" 和 "11" 组合在一起，也就是 "1211"。
解题思路
定义变量res=“1”, 当n=1时, 返回res
定义lst=[], 保存过程数据
从2-n开始循环, 每次循环 对res逐一位判断
当lst为空时, lst数组保存[1, 当前位数字]
当lst不为空时, 如果当前位数字和lst最后一个元素相等, 则lst倒数第二位+1, 不相等则 lst扩展[1, 当前位数字]
最后lst中所有元素转为字符, 并连接到一起返回
Answer
1#
2# @lc app=leetcode.cn id=38 lang=python3
3#
4# [38] 外观数列
5#
6
7# @lc code=start
8class Solution:
9 def countAndSay(self, n: int) -> str:
10 res = "1"
11 if n == 1:
12 return res
13 for i in range(2, n+1):
14 lst = []
15 for m in res:
16 if not lst:
17 lst.extend([1, m])
18 else:
19 if m == lst[-1]:
20 lst[-2] = lst[-2] + 1
21 else:
22 lst.extend([1, m])
23 res = ''.join([str(r) for r in lst])
24 return res
25# @lc code=end
Accepted
18/18 cases passed (36 ms)
Your runtime beats 97.67 % of python3 submissions
Your memory usage beats 6.67 % of python3 submissions (13.7 MB)
Leetcode 搜索插入位置
搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:
输入: [1,3,5,6], 5
输出: 2
示例 2:
输入: [1,3,5,6], 2
输出: 1
示例 3:
输入: [1,3,5,6], 7
输出: 4
示例 4:
输入: [1,3,5,6], 0
输出: 0
解题思路
二分查找
求出最小和最大索引的取整中间值, 判断该索引的value是否等于target, 如果相等返回索引位置
如果value大于target, 则查找的目标在中间索引值左侧, 将现在的最大索引值重置为中间值
如果value小于target, 则查找的目标在中间索引值右侧, 将现在的最小索引值重置为中间值
重新取中间索引值继续比较, 直到找到或找不到退出
则元素应该插入的位置为最后最小索引值+1
Answer
1#
2# @lc app=leetcode.cn id=35 lang=python3
3#
4# [35] 搜索插入位置
5#
6
7# @lc code=start
8class Solution:
9 def searchInsert(self, nums: List[int], target: int) -> int:
10 m = 0
11 n = len(nums)-1
12 while m <= n:
13 k = (m + n) // 2
14 if target == nums[k]:
15 return k
16 elif target > nums[k]:
17 m = k + 1
18 else:
19 n = k - 1
20 return n+1
21# @lc code=end
Accepted
62/62 cases passed (32 ms)
Your runtime beats 97.37 % of python3 submissions
Your memory usage beats 7.14 % of python3 submissions (14.3 MB)
Leetcode 实现 StrStr
实现 strStr()
实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
示例 1:
输入: haystack = "hello", needle = "ll"
输出: 2
示例 2:
输入: haystack = "aaaaa", needle = "bba"
输出: -1
说明:
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
解题思路
如果查找字符串为空或者两个字符串相同,直接返回0
定义两个变量i=needle长度, k=haystack长度
从0到k-i+1遍历haystack, 以i长度截取字符串对比needle, 如果找到返回当前索引
找不到返回-1
Answer
1#
2# @lc app=leetcode.cn id=28 lang=python3
3#
4# [28] 实现 strStr()
5#
6
7# @lc code=start
8class Solution:
9 def strStr(self, haystack: str, needle: str) -> int:
10 if not needle or haystack == needle:
11 return 0
12 j = len(needle)
13 k = len(haystack)
14 for i in range(k-j+1):
15 if haystack[i:i+j] == needle:
16 return i
17 return -1
18# @lc code=end
Accepted
74/74 cases passed (36 ms)
Your runtime beats 91.04 % of python3 submissions
Your memory usage beats 6.67 % of python3 submissions (13.5 MB)
Leetcode 移除元素
移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1:
给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素。
示例 2:
给定 nums = [0,1,2,2,3,0,4,2], val = 2,
函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
注意这五个元素可为任意顺序。
你不需要考虑数组中超出新长度后面的元素。
说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
解题思路
定义两个变量i=0, j=0
i指向结果集, j从头到尾遍历数组
如果num[j]<>val, num[i]=num[j] 然后i=i+1, j=j+1
如果num[j]==val, 则j=j+1, 继续判断下一个元素
Answer
1#
2# @lc app=leetcode.cn id=27 lang=python3
3#
4# [27] 移除元素
5#
6
7# @lc code=start
8class Solution:
9 def removeElement(self, nums: List[int], val: int) -> int:
10 i = 0
11 j = 0
12 while True:
13 if j >= len(nums):
14 break
15 if nums[j] == val:
16 j = j + 1
17 else:
18 nums[i] = nums[j]
19 i = i + 1
20 j = j + 1
21 return i
22# @lc code=end
Accepted
113/113 cases passed (36 ms)
Your runtime beats 87.21 % of python3 submissions
Your memory usage beats 7.14 % of python3 submissions (13.8 MB)
Leetcode 删除排序数组中的重复项
删除排序数组中的重复项
给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例 1:
给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
你不需要考虑数组中超出新长度后面的元素。
示例 2:
给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
你不需要考虑数组中超出新长度后面的元素。
说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
解题思路
定义两个变量作为指针
i=0, j=1
i 作为结果指针, j 作为游标指向后面的元素, 用来跟结果比较
如果nums[i]==nums[j], 则j游标后移, 比较结果和下一个元素的值
如果nums[i]<>nums[j], 则nums[i+1] = nums[j], 然后i = i+1结果集后移一个, j游标后移
Answer
1#
2# @lc app=leetcode.cn id=26 lang=python3
3#
4# [26] 删除排序数组中的重复项
5#
6
7# @lc code=start
8class Solution:
9 def removeDuplicates(self, nums: List[int]) -> int:
10 i = 0
11 j = 1
12 while True:
13 if j >= len(nums):
14 break
15 if nums[j] != nums[i]:
16 nums[i+1] = nums[j]
17 i = i + 1
18 j = j + 1
19 return i + 1
20# @lc code=end
Accepted
161/161 cases passed (40 ms)
Your runtime beats 95.72 % of python3 submissions
Your memory usage beats 8.16 % of python3 submissions (14.7 MB)
Leetcode 合并两个有序链表
合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
解题思路
初始化一个新的链表want节点, 并用head变量保存头部
当l1和l2都不为空时, 比较两个链表的头部元素, 较小的赋值给新链接want, 并将链接指针后移
当l1或l2有一个为空时, 将不为空的链接剩余节点追加到want
最后返回head->next(即真正的链接第一个元素)
Answer
1#
2# @lc app=leetcode.cn id=21 lang=python3
3#
4# [21] 合并两个有序链表
5#
6
7# @lc code=start
8# Definition for singly-linked list.
9# class ListNode:
10# def __init__(self, val=0, next=None):
11# self.val = val
12# self.next = next
13class Solution:
14 def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
15 want = ListNode(0)
16 head = want
17 while l1 and l2:
18 if l1.val <= l2.val:
19 tmp = ListNode(l1.val)
20 l1 = l1.next
21 else:
22 tmp = ListNode(l2.val)
23 l2 = l2.next
24 want.next = tmp
25 want = want.next
26 if l1:
27 want.next = l1
28 if l2:
29 want.next = l2
30 return head.next
31# @lc code=end
Accepted
208/208 cases passed (44 ms)
Your runtime beats 78.91 % of python3 submissions
Your memory usage beats 7.14 % of python3 submissions (13.8 MB)
Leetcode 有效的括号
有效的括号
给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
解题思路
将给定字符串打散成数组
初始化字典, 右侧括号为键, 左侧括号为值
循环数组中的每个字符如果当前字符不是字典的键(即不是右侧括号), 将当前字符追加到一个空数组stack
否则(即当前字符是右侧括号),判断stack不为空的情况下, 最后一个元素是否等于字典中当前字符键的值
相等则继续判断下一个字符
不相等即返回False,
最后判断stack, 非空返回False
Answer
1#
2# @lc app=leetcode.cn id=20 lang=python3
3#
4# [20] 有效的括号
5#
6
7# @lc code=start
8class Solution:
9 def isValid(self, s: str) -> bool:
10 s = list(s)
11 dic = {")":"(","]":"[","}":"{"}
12 stack = []
13 for i in s:
14 if not i in dic:
15 stack.append(i)
16 else:
17 if stack and stack.pop() == dic[i]:
18 pass
19 else:
20 return False
21 return True if not stack else False
22# @lc code=end
Accepted
76/76 cases passed (36 ms)
Your runtime beats 90.49 % of python3 submissions
Your memory usage beats 5.22 % of python3 submissions (13.8 MB)
Leetcode 最长公共前缀
最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “"。
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"
示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
说明:
所有输入只包含小写字母 a-z 。
解题思路
原始数组转为set,再转为list, 去重
如果只有一个元素, 最长公共前缀就是该元素
设置初始最长公共前缀为”"
对数组各元素同步截取前n个字符. 放入set去重, 如果set长度为1, 则公共前缀为集合的元素
继续对各元素同步截取, 直到set长度不为1, 返回保存的公共前缀
Answer
1#
2# @lc app=leetcode.cn id=14 lang=python3
3#
4# [14] 最长公共前缀
5#
6
7# @lc code=start
8class Solution:
9 def longestCommonPrefix(self, strs: List[str]) -> str:
10 strs = list(set(strs))
11 if len(strs) == 1:
12 return strs[0]
13 idx = 1
14 prefix = ""
15 while True:
16 ary = [i[0:idx] for i in strs]
17 if len(set(ary))==1:
18 prefix = ary[0]
19 idx = idx + 1
20 else:
21 break
22 return prefix
23
24# @lc code=end
Accepted
118/118 cases passed (40 ms)
Your runtime beats 80.45 % of python3 submissions
Your memory usage beats 6.15 % of python3 submissions (13.7 MB)
Leetcode 罗马数字转整数
罗马数字转整数
罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边， 所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。
示例 1:
输入: "III"
输出: 3
示例 2:
输入: "IV"
输出: 4
示例 3:
输入: "IX"
输出: 9
示例 4:
输入: "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.
示例 5:
输入: "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.
解题思路
初始化一个字典, 包含所有字符到数字的情况,
注意顺序先特殊情况处理, 防止后面单字符转换后特殊情况消失
将给定的字符串用字典的key-value替换, 再分割成数组, 剔除空值, 每个元素转为数字
用sum求和数组返回
Answer
1#
2# @lc app=leetcode.cn id=13 lang=python3
3#
4# [13] 罗马数字转整数
5#
6
7# @lc code=start
8class Solution:
9 def romanToInt(self, s: str) -> int:
10 dic = {
11 "IV": "+4+",
12 "IX": "+9+",
13 "XL": "+40+",
14 "XC": "+90+",
15 "CD": "+400+",
16 "CM": "+900+",
17 "I": "+1+",
18 "V": "+5+",
19 "X": "+10+",
20 "L": "+50+",
21 "C": "+100+",
22 "D": "+500+",
23 "M": "+1000+",
24 }
25 for k,v in dic.items():
26 s = s.replace(k,v)
27 return sum([int(i) for i in s.split("+") if i])
28
29# @lc code=end
Accepted
3999/3999 cases passed (68 ms)
Your runtime beats 40.85 % of python3 submissions
Your memory usage beats 6.45 % of python3 submissions (13.7 MB)
Leetcode 回文数
回文数
判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
示例 1:
输入: 121
输出: true
示例 2:
输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。
进阶: 你能不将整数转为字符串来解决这个问题吗？
解题思路
判断是否负数, 是负数直接返回False
正数的时候, 转化字符串再转为数组,
取数组长度的一半取整, 然后对数组前后各一半对比, 有一个不同则返回False, 否则返回True
Answer
1#
2# @lc app=leetcode.cn id=9 lang=python3
3#
4# [9] 回文数
5#
6
7# @lc code=start
8class Solution:
9 def isPalindrome(self, x: int) -> bool:
10 if x < 0:
11 return False
12 else:
13 ary = list(str(x))
14 lens = len(ary)
15 half = lens // 2
16 for i in range(0,half):
17 if ary[i] != ary[ -1 * (i + 1)]:
18 return False
19 return True
20
21# @lc code=end
Accepted
11509/11509 cases passed (84 ms)
Your runtime beats 71.7 % of python3 submissions
Your memory usage beats 5.88 % of python3 submissions (13.8 MB)
进阶思考
首先判断负数, 直接返回False
正数的话, 原始x除10取余数赋值给y, x除10商赋值给s
如果s不为0, 则将商s赋值给x, 继续除10, 余数赋值给y = y*10 + 本次余数, 商继续赋值给s
知道商s为0, 此时判断 y==s 返回判断结果
进阶 Answer
1#
2# @lc app=leetcode.cn id=9 lang=python3
3#
4# [9] 回文数
5#
6
7# @lc code=start
8class Solution:
9 def isPalindrome(self, x: int) -> bool:
10 if x < 0:
11 return False
12 k = x
13 y = 0
14 while True:
15 y = x % 10 if y == 0 else y * 10 + x % 10
16 s = x // 10
17 if not s:
18 break
19 x = s
20 return y == k
21# @lc code=end
11509/11509 cases passed (88 ms)
Your runtime beats 60.61 % of python3 submissions
Your memory usage beats 5.88 % of python3 submissions (13.7 MB)
Leetcode 整数反转
整数反转
给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
示例 1:
输入: 123
输出: 321
示例 2:
输入: -123
输出: -321
示例 3:
输入: 120
输出: 21
注意:
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−2^31, 2^31 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。
解题思路
判断是否负数, 转为正整数
将正整数转为字符串, 再转换为列表, 使用reverse函数翻转, 最后用join组合起来
还原给出的正负符号
最后输出前判断是否超出32 位的有符号整数
Answer
1#
2# @lc app=leetcode.cn id=7 lang=python3
3#
4# [7] 整数反转
5#
6
7# @lc code=start
8class Solution:
9 def reverse(self, x: int) -> int:
10 if x < 0:
11 x = list(str(-1 * x))
12 x.reverse()
13 y = -1 * int(''.join(x))
14 else:
15 x = list(str(x))
16 x.reverse()
17 y = int(''.join(x))
18 if y < -1 * 2 ** 31 or y > 2 ** 31 -1:
19 return 0
20 else:
21 return y
22# @lc code=end
Accepted
1032/1032 cases passed (48 ms)
Your runtime beats 44.33 % of python3 submissions
Your memory usage beats 6.67 % of python3 submissions (13.8 MB)
Leetcode 两数之和
两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
解题思路
从列表头部开始每次取出一个数字: A, 并记录取数的索引: k,
在剩余的数组: ary[k+1:] 中查找: target - A 的索引 j,
如果找到返回: [k,j], 没有找到就从头部继续往后取出数字.
Answer
1#
2# @lc app=leetcode.cn id=1 lang=python3
3#
4# [1] 两数之和
5#
6
7# @lc code=start
8class Solution:
9 def twoSum(self, nums: List[int], target: int) -> List[int]:
10 cnt = 0
11 while len(nums):
12 a = nums.pop(0)
13 want = target - a
14 if want in nums:
15 idx = nums.index(want)
16 return [cnt, idx+cnt+1]
17 cnt = cnt + 1
18
19# @lc code=end
1#
2# @lc app=leetcode.cn id=1 lang=python3
3#
4# [1] 两数之和
5#
6
7# @lc code=start
8class Solution:
9 def twoSum(self, nums: List[int], target: int) -> List[int]:
10 cnt = 0
11 lens = len(nums)
12 while cnt < lens - 1:
13 a = nums[cnt]
14 if target - a in nums[cnt + 1:]:
15 return [cnt,nums.index(target - a, cnt + 1)]
16 cnt = cnt + 1
17
18# @lc code=end
Accepted
29/29 cases passed (768 ms)
Your runtime beats 43.42 % of python3 submissions
Your memory usage beats 13.41 % of python3 submissions (14.6 MB)