Skip to content

Commit ca1869b

Browse files
linwtlinwt
authored
Add files via upload
1 parent e340cc4 commit ca1869b

File tree

83 files changed

+1093
-0
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

83 files changed

+1093
-0
lines changed

‎leetcode/012.整数转罗马数字.py

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
class Solution(object):
2+
def intToRoman(self, num):
3+
res = ''
4+
d = {'M': 1000, 'CM': 900, 'D': 500, 'CD': 400, 'C': 100, 'XC': 90,
5+
'L': 50, 'XL': 40, 'X': 10, 'IX': 9, 'V': 5, 'IV': 4, 'I': 1}
6+
# 字典无序，需要先排序，再逆转
7+
for char, val in sorted(d.items(), key = lambda x: x[1])[::-1]:
8+
while num >= val:
9+
res += char
10+
num -= val
11+
return res

‎leetcode/013.罗马数字转整数.py

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
# 字符的值比后面小则可以合并，即先减当前数，再加后面数
2+
class Solution(object):
3+
def romanToInt(self, s):
4+
d = {'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000}
5+
res = 0
6+
for i in range(len(s)):
7+
if i<len(s)-1 and d[s[i]] < d[s[i+1]]:
8+
res -= d[s[i]]
9+
else:
10+
res += d[s[i]]
11+
return res

‎leetcode/014.最长公共前缀.py

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
# 方法一
2+
class Solution(object):
3+
def longestCommonPrefix(self, strs):
4+
if not strs:
5+
return ''
6+
# 遍历索引
7+
for i in range(len(strs[0])):
8+
# 遍历每个字符串
9+
for str in strs:
10+
# 索引超过字符串长度或字符不相等
11+
if len(str) <= i or strs[0][i] != str[i]:
12+
return strs[0][:i]
13+
return strs[0]
14+
15+
# 方法二：使用python函数
16+
class Solution(object):
17+
def longestCommonPrefix(self, strs):
18+
return os.path.commonprefix(strs)

‎leetcode/017.电话号码的字母组合.py

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
# 递归
2+
class Solution(object):
3+
def letterCombinations(self, digits):
4+
d = {'2':'abc', '3':'def', '4':'ghi', '5':'jkl', '6':'mno', '7':'pqrs', '8':'tuv', '9':'wxyz'}
5+
6+
def combine(s, digits):
7+
# 终止条件，数字为空时把字符串添加到数组中
8+
if not digits:
9+
res.append(s)
10+
else:
11+
for char in d[digits[0]]:
12+
combine(s+char, digits[1:])
13+
14+
res = []
15+
if not digits:
16+
return res
17+
combine('', digits)
18+
return res

‎leetcode/020.有效的括号.py

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
# 利用栈找对应括号，遇到左括号则进栈，遇到右括号则出栈，判断两个括号是否匹配
2+
class Solution(object):
3+
def isValid(self, s):
4+
left, right = '([{', '}])'
5+
stack = []
6+
for i in s:
7+
if i in left:
8+
stack.append(i)
9+
if i in right:
10+
if not stack:
11+
return False
12+
res = stack.pop()
13+
if (i==')' and res!='(') or (i==']' and res!='[') or (i=='}' and res!='{'):
14+
return False
15+
return not stack

‎leetcode/022.括号生成.py

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
class Solution(object):
2+
def generateParenthesis(self, n):
3+
self.res = []
4+
self.generate('', 0, 0, n)
5+
return self.res
6+
7+
def generate(self, s, left, right, n):
8+
# 左右括号用完时，添加该括号字符串
9+
if left == n and right == n:
10+
self.res.append(s)
11+
# 左括号未完时，添加左括号，再递归
12+
if left < n:
13+
self.generate(s+'(', left+1, right, n)
14+
# 右括号少于左括号时，可添加右括号，再递归
15+
if right < left:
16+
self.generate(s+')', left, right+1, n)

‎leetcode/026.删除排序数组中的重复项.py

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
# 遍历数组，遇到不重复的值就按顺序复制到前面
2+
class Solution(object):
3+
def removeDuplicates(self, nums):
4+
if not nums:
5+
return 0
6+
j = 0
7+
for i in range(len(nums)):
8+
if nums[i] != nums[j]:
9+
nums[j+1] = nums[i]
10+
j += 1
11+
return j+1

‎leetcode/027.移除元素.py

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
# 将非val的值复制到数组前，最后一个复制完后，返回的索引即前面数组的长度
2+
class Solution(object):
3+
def removeElement(self, nums, val):
4+
j = 0
5+
for i in range(len(nums)):
6+
if nums[i] != val:
7+
nums[j] = nums[i]
8+
j += 1
9+
return j

‎leetcode/028.实现strStr().py

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
# 方法一
2+
class Solution(object):
3+
def strStr(self, haystack, needle):
4+
if not needle:
5+
return 0
6+
elif needle not in haystack:
7+
return -1
8+
else:
9+
return haystack.index(needle)
10+
11+
# 方法二
12+
class Solution(object):
13+
def strStr(self, haystack, needle):
14+
return haystack.find(needle)

‎leetcode/035.搜索插入位置.py

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
class Solution(object):
2+
def searchInsert(self, nums, target):
3+
if target in nums:
4+
return nums.index(target)
5+
for i in range(len(nums)):
6+
if nums[i] > target:
7+
return i
8+
return i+1

‎leetcode/038.报数.py

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
class Solution(object):
2+
def countAndSay(self, n):
3+
res = '1'
4+
for i in range(n-1):
5+
res = ''.join([str(len(list(group))) + key for key, group in itertools.groupby(res)])
6+
return res

‎leetcode/049.字母异位词分组.py

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
# 将排序后字符串相同的字符串添加到字典数组中
2+
class Solution(object):
3+
def groupAnagrams(self, strs):
4+
d = {}
5+
for s in strs:
6+
S = ''.join(sorted(list(s)))
7+
if S in d:
8+
d[S].append(s)
9+
else:
10+
d[S] = [s]
11+
return d.values()

‎leetcode/053.最大子序和.py

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
# 方法一：累加判断
2+
class Solution(object):
3+
def maxSubArray(self, nums):
4+
sum = 0
5+
max_sum = nums[0]
6+
for num in nums:
7+
sum += num
8+
if sum > max_sum:
9+
max_sum = sum
10+
if sum < 0:
11+
sum = 0
12+
return max_sum
13+
14+
# 方法二：动态规划，用数组保存当前最大值
15+
class Solution(object):
16+
def maxSubArray(self, nums):
17+
n = len(nums)
18+
max_sum = [nums[0] for _ in range(n)]
19+
for i in range(1, n):
20+
max_sum[i] = max(max_sum[i-1] + nums[i], nums[i])
21+
return max(max_sum)

‎leetcode/058.最后一个单词的长度.py

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,4 @@
1+
class Solution(object):
2+
def lengthOfLastWord(self, s):
3+
s = s.split()
4+
return len(s[-1]) if s else 0

‎leetcode/067.二进制求和.py

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,4 @@
1+
# 转化为十进制求和，再将结果转为二进制，要去除开头的‘0b’
2+
class Solution(object):
3+
def addBinary(self, a, b):
4+
return bin(int(a, 2) + int(b, 2))[2:]

‎leetcode/070.爬楼梯.py

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
# 规律：1,2,3,5,8
2+
# 方法一：递推
3+
class Solution(object):
4+
def climbStairs(self, n):
5+
if n<3:
6+
return n
7+
a, b = 1, 2
8+
while n>2:
9+
a, b = b, a+b
10+
n -= 1
11+
return b
12+
13+
# 方法二：递归
14+
class Solution(object):
15+
def climbStairs(self, n):
16+
if n in [1, 2]:
17+
return n
18+
return self.climbStairs(n-1) + self.climbStairs(n-2)
19+
20+
# 方法三：动态规划
21+
class Solution(object):
22+
def climbStairs(self, n):
23+
res = [1] * (n+1)
24+
for i in range(2, n+1):
25+
res[i] = res[i-1] + res[i-2]
26+
return res[-1]

‎leetcode/118.杨辉三角.py

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
# 每次先初始化当前行的数组，再将求和结果代入
2+
class Solution(object):
3+
def generate(self, numRows):
4+
res = []
5+
for i in range(numRows):
6+
cur = [1]*(i+1)
7+
if i >= 2:
8+
for j in range(1, i):
9+
cur[j] = pre[j] + pre[j-1]
10+
res.append(cur)
11+
pre = cur
12+
return res

‎leetcode/119.杨辉三角II.py

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
class Solution(object):
2+
def getRow(self, rowIndex):
3+
for k in range(rowIndex+1):
4+
cur = [1]*(k+1)
5+
if k >= 2:
6+
for i in range(1, k):
7+
cur[i] = pre[i] + pre[i-1]
8+
pre = cur
9+
return cur

‎leetcode/125.验证回文串.py

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
# 方法一：直接判断并提取字母数字
2+
class Solution(object):
3+
def isPalindrome(self, s):
4+
res = ''
5+
for i in s:
6+
if 'a' <= i <= 'z' or 'A' <= i <= 'Z' or '0' <= i <= '9':
7+
res += i
8+
res = res.lower()
9+
return res == res[::-1]
10+
11+
# 方法二：由方法isalnum()提取字母数字
12+
class Solution(object):
13+
def isPalindrome(self, s):
14+
s = ''.join(i for i in s if i.isalnum()).lower()
15+
return s == s[::-1]

‎leetcode/197.最大数.py

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
class Solution(object):
2+
def largestNumber(self, nums):
3+
nums = map(str, nums)
4+
# 两两相加比较，大于则交换位置
5+
nums.sort(cmp = lambda x, y: cmp(y+x, x+y))
6+
# 结果需要先去除最左边的0
7+
return ''.join(nums).lstrip('0') if ''.join(nums).lstrip('0') else '0'

‎leetcode/198.打家劫舍.py

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
# 动态规划，求出打劫到每间房屋时能偷窃到的最高金额
2+
class Solution(object):
3+
def rob(self, nums):
4+
n = len(nums)
5+
if n==0:
6+
return 0
7+
elif n==1 or n==2:
8+
return max(nums)
9+
dp = [0] * n
10+
dp[0], dp[1] = nums[0], max(nums[0], nums[1])
11+
for i in range(2, n):
12+
dp[i] = max(dp[i-2] + nums[i], dp[i-1])
13+
return dp[-1]

‎leetcode/219.存在重复元素II.py

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
# 使用字典，如果元素不在字典中，则更新字典。若在字典中，则计算索引距离，若距离≤k则为True，否则更新字典
2+
class Solution(object):
3+
def containsNearbyDuplicate(self, nums, k):
4+
d = {}
5+
for i, num in enumerate(nums):
6+
if num not in d:
7+
d[num] = i
8+
else:
9+
if i-d[num] <= k:
10+
return True
11+
d[num] = i
12+
return False

‎leetcode/242.有效的字母异位词.py

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
# 使用字典，判断两个字符串中字符的个数是否相同
2+
class Solution(object):
3+
def isAnagram(self, s, t):
4+
s = collections.Counter(s)
5+
t = collections.Counter(t)
6+
return s == t
7+
8+
# 排序
9+
class Solution(object):
10+
def isAnagram(self, s, t):
11+
return sorted(s) == sorted(t)

‎leetcode/268.缺失数字.py

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
# 方法一：求出差集
2+
class Solution(object):
3+
def missingNumber(self, nums):
4+
nums2 = [i for i in range(len(nums)+1)]
5+
return int(list(set(nums2).difference(set(nums)))[0])
6+
7+
# 方法二：等差数列前n项和：n(n-1)/2
8+
class Solution(object):
9+
def missingNumber(self, nums):
10+
return len(nums) * (len(nums) + 1) / 2 - sum(nums)

‎leetcode/283.移动零.py

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
# 先将非0元素按顺序赋值到数组前，最后再补0
2+
class Solution(object):
3+
def moveZeroes(self, nums):
4+
j = 0
5+
for i in range(len(nums)):
6+
if nums[i] != 0:
7+
nums[j] = nums[i]
8+
j += 1
9+
while j < len(nums):
10+
nums[j] = 0
11+
j += 1

‎leetcode/344.反转字符串.py

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,3 @@
1+
class Solution(object):
2+
def reverseString(self, s):
3+
return s[::-1]

‎leetcode/345.反转字符串中的元音字母.py

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
# 方法一：利用左右索引寻找元音字符交换
2+
class Solution(object):
3+
def reverseVowels(self, s):
4+
list_s = list(s)
5+
vowels = 'aeiouAEIOU'
6+
l, r = 0, len(s)-1
7+
while l <= r:
8+
if list_s[l] not in vowels:
9+
l += 1
10+
elif list_s[r] not in vowels:
11+
r -= 1
12+
else:
13+
list_s[l], list_s[r] = list_s[r], list_s[l]
14+
l += 1
15+
r -= 1
16+
return ''.join(list_s)
17+
18+
# 方法二：正则表达式
19+
class Solution(object):
20+
def reverseVowels(self, s):
21+
vowels = re.findall(r'[aeiouAEIOU]', s)
22+
return re.sub('[aeiouAEIOU]', lambda m: vowels.pop(), s)

‎leetcode/349.两个数组的交集.py

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
# 方法一
2+
class Solution(object):
3+
def intersection(self, nums1, nums2):
4+
res = []
5+
for i in set(nums1):
6+
if i in nums2:
7+
res.append(i)
8+
return res
9+
10+
# 方法二
11+
class Solution(object):
12+
def intersection(self, nums1, nums2):
13+
return list(set(nums1).intersection(set(nums2)))

0 commit comments

Comments
 (0)