Python3刷题系列（八）

# 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)

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

    def __init__(self):
        """
        Initialize your data structure here.
        """
        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):
        """
        Initialize your data structure here.
        """
        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 == []

# leetcode-160：链表
class Solution(object):  # 战胜了16.30%
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        if headA is None or headB is None:
            return None
        l1 = headA
        l2 = headB
        while l1 != l2:
            if l1 is not None:
                l1 = l1.next
            else:
                l1 = headB
            if l2 is not None:
                l2 = l2.next
            else:
                l2 = headA
        return l1
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

# 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

# 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]

#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

# 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]

# 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

# 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