# Python3刷题系列（八）

1，Leetcode-242

2，Leetcode-232

3，Leetcode-160

4，Leetcode-260

5，Leetcode-169

6，Leetcode-409

7，Leetcode-378

8，Leetcode-462

9，Leetcode-504

1，Leetcode-242：

```# leetcode-242：哈希表
class Solution:  # 利用数组实现，战胜了57.81%
def isAnagram(self, s: str, t: str) -> bool:
arr = [0] * 26
for c in s:
arr[ord(c) - ord('a')] += 1  # 给对应字母计数；ord()函数：返回对应的ASCII码数值(是一个整数)
for c in t:
arr[ord(c) - ord('a')] -= 1  # 给对应字母减数
for i in arr:
if i != 0:
return False  # 不为零，证明不是有效字谜
return True

class Solution:  # 和上面的解题思想完全一致，只是利用字典实现，战胜了57.81%
def isAnagram(self, s: str, t: str) -> bool:
dic = {}
for c in s:
dic[c] = dic.get(c, 0) + 1  # dict.get(key, default=None):返回指定键的值，如果值不在字典中返回默认值
for c in t:
dic[c] = dic.get(c, 0) - 1
for key in dic:
if dic[key] != 0:
return False
return True

class Solution:  # 和上面两个解题思路完全一致，细节不同而已，战胜了57.81%
def isAnagram(self, s: str, t: str) -> bool:
dic1, dic2 = {}, {}
for item in s:
dic1[item] = dic1.get(item, 0) + 1
for item in t:
dic2[item] = dic2.get(item, 0) + 1
return dic1 == dic2

class Solution:  # 和上面三个解题思路完全一致，细节与上一个一致，战胜了57.81%
def isAnagram(self, s: str, t: str) -> bool:
dic1, dic2 = [0]*26, [0]*26
for item in s:
dic1[ord(item)-ord('a')] += 1
for item in t:
dic2[ord(item)-ord('a')] += 1
return dic1 == dic2

class Solution:  # 使用python内置函数，一行代码搞定，战胜了50.56%
def isAnagram(self, s: str, t: str) -> bool:
return sorted(s) == sorted(t)```

2，Leetcode-232：

```# leetcode-232: 栈，队列
# 把python中的list看做栈，然后实现队列，战胜了77.82%
class MyQueue:

def __init__(self):
"""
"""
self.stack_in = []
self.stack_out = []

def push(self, x: int) -> None:
"""
Push element x to the back of queue.
"""
self.stack_in.append(x)

def pop(self) -> int:
"""
Removes the element from in front of queue and returns that element.
"""
if self.stack_out:  # stack_out非空判断
return self.stack_out.pop()
else:
while self.stack_in:  # 将stack_in中的元素全部倒入stack_out后,stack_in为空,结束while循环
self.stack_out.append(self.stack_in.pop())
return self.stack_out.pop()

def peek(self) -> int:
"""
Get the front element.
"""
if self.stack_out:
return self.stack_out[-1]
else:
while self.stack_in:
self.stack_out.append(self.stack_in.pop())
return self.stack_out[-1]

def empty(self) -> bool:
"""
Returns whether the queue is empty.
"""
return not self.stack_in and not self.stack_out

# 实际上，python中的list既可以用作栈，也可以直接用作队列
class MyQueue:

def __init__(self):
"""
"""
self.stack = []

def push(self, x: int) -> None:
"""
Push element x to the back of queue.
"""
self.stack.append(x)

def pop(self) -> int:
"""
Removes the element from in front of queue and returns that element.
"""
return self.stack.pop(0)

def peek(self) -> int:
"""
Get the front element.
"""
return self.stack[0]

def empty(self) -> bool:
"""
Returns whether the queue is empty.
"""
return self.stack == []```

3，Leetcode-160：

```# leetcode-160：链表
class Solution(object):  # 战胜了16.30%
"""
:rtype: ListNode
"""
return None
while l1 != l2:
if l1 is not None:
l1 = l1.next
else:
if l2 is not None:
l2 = l2.next
else:
return l1
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None```

4，Leetcode-260：

```# leetcode-260:位运算
class Solution(object):  # 战胜了30.88%
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
diff = 0
for num in nums:
diff = diff ^ num
diff = diff & (-diff)
ret = [0, 0]
for num in nums:
if (diff & num == 0):
ret[0] = ret[0] ^ num
else:
ret[1] = ret[1] ^ num
return ret```

5，Leetcode-169：

```# leetcode-169：
# O(n):多数投票问题
class Solution(object):  # 只战胜了26.62%,还不如python内置函数效率高
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
cnt = 0
majority = nums[0]
for num in nums:
if cnt == 0:
majority = num
if majority == num:  # 众数的cnt一定大于等于零，因为the element that appears more than ⌊ n/2 ⌋ times
cnt += 1
else:
cnt -= 1
return majority

# 使用python内置函数，战胜了 45.13%
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
nums = sorted(nums)
return nums[len(nums) // 2]```

6，Leetcode-409：

```#leetcode-409：回文
class Solution(object):  # 战胜了84.78%
def longestPalindrome(self, s):
"""
:type s: str
:rtype: int
"""
cnts = {}
for c in s:
if c in cnts:
cnts[c] += 1
else:
cnts[c] = 1
ret = 0
for (key, value) in cnts.items():
ret += (value // 2) * 2  # 出现偶数次，就可以分列回文的两侧
if ret < len(s):
ret += 1  # 回文的中间元素可以是出现一次的元素
return ret```

7，Leetcode-378：

```# leetcode-378：堆
class Solution(object):  # 最小堆思想，战胜了37.89%
def kthSmallest(self, matrix, k):
"""
:type matrix: List[List[int]]
:type k: int
:rtype: int
"""
from heapq import *
m, n = len(matrix), len(matrix[0])
h = []
for i in range(n):
heapq.heappush(h, (matrix[0][i], 0, i))
for i in range(k-1):
item = heapq.heappop(h)
if item[1] + 1 < m:
heapq.heappush(h, (matrix[item[1] + 1][item[2]], item[1] + 1, item[2]))
return heapq.heappop(h)[0]

# 暴力解法：战胜了41.12%
class Solution(object):
def kthSmallest(self, matrix, k):
"""
:type matrix: List[List[int]]
:type k: int
:rtype: int
"""
l = []
for i in range(len(matrix)):
for j in range(len(matrix[0])):
l.append(matrix[i][j])
l = sorted(l)
return l[k-1]```

8，Leetcode-462：

```# leetcode-462：双指针，快排
class Solution(object):  # O(NlogN),战胜了48.89%
def minMoves2(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
nums = sorted(nums)  # python内置函数sort使用的是快排，时间复杂度是O(NlogN)
res = 0
left, right = 0, len(nums)-1
while left < right:  # 双指针，这里的时间复杂度是O(N)
res += nums[right] - nums[left]
left += 1
right -= 1
return res```

9，Leetcode-504：

```# leetcode-504：进制转换，七进制
class Solution(object):
def convertToBase7(self, num):
"""
:type num: int
:rtype: str
"""
if num == 0:
return '0'

res = ''
is_negative = (num < 0)
if is_negative:
num = -num
while num > 0:
res += str(num % 7)
num //= 7
res = res[::-1]
if is_negative:
res = '-' + res
return res```

0 条评论