Python3刷题系列(七)

目录:

1,Leetcode-241

2,Leetcode-69

3,Leetcode-1

4,Leetcode-347

5,Leetcode-455

6,Leetcode-215

7,Leetcode-75

8,Leetcode-167

1,Leetcode-241:

https://leetcode.com/problems/different-ways-to-add-parentheses/

# leetcode-241:分治思想
class Solution:  # 使用递归实现分治思想,战胜了 63.59% 
    def diffWaysToCompute(self, input: str) -> List[int]:
        return_list = []
        for i in range(len(input)):
            c = input[i]
            if c in ['+','-','*']:
                left = self.diffWaysToCompute(input[:i])
                right = self.diffWaysToCompute(input[i+1:])
                for l in left:
                    for r in right:
                        if c == '+':
                            return_list.append(l+r)
                        elif c == '-':
                            return_list.append(l-r)
                        elif c == '*':
                            return_list.append(l*r)
        if not return_list:
            return_list.append(int(input))  # return_list为空时,显然input只有一个整数

        return return_list

2,Leetcode-69:

https://leetcode.com/problems/sqrtx/

# leetcode-69: 二分查找, O(lgn), 战胜了 84.44%
class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 0:
            return 0
        
        l = 1
        r = x
        
        while l <= x:
            res = (l + r) // 2
            s = res ** 2
            
            if s <= x < (res + 1)**2:
                return res
            if s < x:
                l = res
            if s > x:
                r = res

class Solution(object):  # 同样是二分查找,这种写法超时
    def mySqrt(self, x):
        if x <= 1:
            return x  # 考虑到0,1的情况
        l = 0
        h = x
        while l <= h:
            m = l + (h - 1) / 2  # 中值:防止溢出,等于(l + h) / 2,后者容易溢出
            if x > m**2:
                l = m+1
            elif x < m**2:
                h = m-1
            elif x == m**2:
                return int(m)
        return int(h)

3,Leetcode-1:

https://leetcode.com/problems/two-sum/

# keetcode-1:哈希表
class Solution:   # 战胜了87.27%
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dict = {}
        for i in range(len(nums)):
            if nums[i] in dict:
                return [dict[nums[i]], i]
            dict[target - nums[i]] = i

# 和上面阶梯思想一致,细节不同而已
class Solution:   # 战胜了87.27%
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        my_dict = {}
        for i in range(len(nums)):
            if target - nums[i] in my_dict:
                return [my_dict[target - nums[i]], i]
            my_dict[nums[i]] = i

4,Leetcode-347:

https://leetcode.com/problems/top-k-frequent-elements/

# leetcode-347:桶排序
class Solution:  # 战胜了32.06%
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        di = {}
        for num in nums:
            if num not in di:
                di[num] = 1
            else:
                di[num] += 1
        bucket = [[] for _ in range(len(nums) + 1)]
        for key, value in di.items():
            bucket[value].append(key)
        ans = []
        for i in range(len(nums), -1, -1):
            if bucket[i]:
                ans.extend(bucket[i])
            if len(ans) >= k:
                break
        return ans[:k]

class Solution:  # 战胜了24.62%
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        frequent_of_number = {}
        for num in nums:
            frequent_of_number[num] = frequent_of_number.get(num, 0) + 1
        buckets = [[] for i in range(len(nums) + 1)]
        for key, value in frequent_of_number.items():
            buckets[value].append(key)
        print(buckets)
        result = []
        for x in range(len(nums), -1, -1):
            if k > 0 and buckets[x]:
                result += buckets[x]
                k -= len(buckets[x])
            if k == 0:
                return result

5,Leetcode-455:

https://leetcode.com/problems/assign-cookies/

# leetcode-455:贪心算法
class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g = sorted(g)
        s = sorted(s)
        cnt_g = 0
        cnt_s = 0
        while cnt_g < len(g) and cnt_s < len(s):
            if g[cnt_g] <= s[cnt_s]:
                cnt_g += 1
            cnt_s += 1
        return cnt_g

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()
        child = 0
        cookies = 0

        while len(g) > child and len(s) > cookies:
          if g[child] <= s[cookies]:
            child += 1
          cookies += 1
        return child

6,Leetcode-215:

https://leetcode.com/problems/kth-largest-element-in-an-array/

# leetcode-215:快排:时间复杂度-O(N), 空间复杂度-O(1).
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        return self.quick_sort(nums, k)
    
    def quick_sort(self, nums, k):
        k = len(nums) -k
        left = 0
        right = len(nums) - 1
        while left < right:
            j = self.partition(nums, left, right)
            if j == k:
                break
            elif j < k:
                left = j + 1
            else:
                right = j -1
        return nums[k]
    
    def partition(self, nums, left, right):
        while True:
            while nums[left] < nums[right]:
                right -= 1
            else:
                nums[left], nums[right] = nums[right], nums[left]
                if left >= right:
                    break
                left += 1
                
            while nums[left] < nums[right]:
                left += 1
            else:
                nums[left], nums[right] = nums[right], nums[left]
                if left >= right:
                    break
                right -= 1
        return left


# 堆排:时间复杂度-O(NlogK), 空间复杂度-O(K).
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        return self.heap_sort(nums, k)
    
    def heap_sort(self, nums, k):
        for i in range(len(nums)//2 - 1, -1, -1):
            self.heap_adjust(nums, i, len(nums))
            
        cnt = 0
        for i in range(len(nums) - 1, 0, -1):
            self.heap_swap(nums, 0, i)
            cnt += 1
            if cnt == k:
                return nums[i]
            self.heap_adjust(nums, 0, i)
        return nums[0]
        
    def heap_adjust(self, nums, start, length):
        tmp = nums[start]
        k = start * 2 + 1
        while k < length:
            left = start * 2 + 1
            right = left + 1
            
            if right < length and nums[right] > nums[left]:
                k = right
                
            if nums[k] > tmp:
                nums[start] = nums[k]
                start = k
            else:
                break
            k = k*2 + 1
        nums[start] = tmp
    
    def heap_swap(self, nums, i, j):
        nums[i], nums[j] = nums[j], nums[i]
        return nums

# 递归解法:
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
      if len(nums) == 0:
        return
      nums = self.quicksort(nums)
      return nums[-k]

    def quicksort(self, nums):
      if len(nums) == 0:
        return []
      pivot = nums[0]
      left = self.quicksort([x for x in nums[1:] if x < pivot])
      right = self.quicksort([x for x in nums[1:] if x >= pivot])
      return left + [pivot] + right

# 暴力解法:
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        return sorted(nums)[-k]

7,Leetcode-75:

https://leetcode.com/problems/sort-colors/

# 三向切分快速排序思想:
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        head, now, tail = 0, 0, len(nums) - 1
        while now <= tail:
            if nums[now] == 0:
                nums[now], nums[head] = nums[head], nums[now]
                now += 1
                head += 1
            elif nums[now] == 2:
                nums[now], nums[tail] = nums[tail], nums[now]
                tail -= 1
            else:
                now += 1

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        zero, two = -1, len(nums)
        i = 0
        while i < two:
          if nums[i] == 1:
            i += 1
          elif nums[i] == 2:
            two -= 1
            nums[two], nums[i] = nums[i], nums[two]
          else:
            zero += 1
            nums[zero], nums[i] = nums[i], nums[zero]
            i += 1

# 暴力解法:
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        nums.sort()

8,Leetcode-167:

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

# 双指针:
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        i = 0
        j = len(numbers) - 1
        while i < j:
            if numbers[i] + numbers[j] > target:
                j -= 1
            elif numbers[i] + numbers[j] < target:
                i += 1
            else:
                return [i+1, j+1]

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        a = 0
        b = len(numbers) -1

        while a < b:
            if numbers[a] + numbers[b] < target:
                a += 1
            elif numbers[a] + numbers[b] > target:
                b -= 1
            elif numbers[a] + numbers[b] == target:
                return [a+1, b+1]
        else:
            return None

class Solution:
  def twoSum(self, numbers: List[int], target: int) -> List[int]:
    length = len(numbers)
    for i in range(0, length-1):
      for j in range(i+1, length):
        a = numbers[i]
        b = numbers[j]
        sum = a +b
        if sum == target:
          break
      if sum == target:
        break
    return i+1, j+1

本文分享自微信公众号 - MiningAlgorithms(gh_d0cc50d1ed34)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-05-04

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏卯金刀GG

NGINX 配置文件 fastcgi_pass

语法:fastcgi_pass fastcgi-server 默认值:none 使用字段:http, server, location 指定FastCGI...

30830
来自专栏卯金刀GG

handler模块(100%)

相信大家在看了前一章的模块概述以后,都对nginx的模块有了一个基本的认识。基本上作为第三方开发者最可能开发的就是三种类型的模块,即handler,filter...

6710
来自专栏卯金刀GG

利用java自带的MD5加密

使用混淆的字符串是:{'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'}

24320
来自专栏卯金刀GG

Nginx proxy_set_header 理解

用户认证接口:根据客户端IP和port,进行IP反查和端口范围确认,如符合则用户认证通过。 当前使用的是Nginx负载均衡,从客户端到Nginx端 ip和po...

16160
来自专栏木二天空

002.NFS相关配置项

<输出目录> [客户端1 选项(访问权限,用户映射,其他)] [客户端2 选项(访问权限,用户映射,其他)]

7420
来自专栏卯金刀GG

nginx proxy_set_header设置、自定义header

允许重新定义或者添加发往后端服务器的请求头。value可以包含文本、变量或者它们的组合。 当且仅当当前配置级别中没有定义proxy_set_header指令时,...

17720
来自专栏卯金刀GG

springmvc整合axis2 过程

项目需要使用springmvc发布一个对外的服务,原来使用spring+cxf的结合,使用axis2的客户端调用,没有任何问题,但是使用pb9的客户端调用,一直...

13730
来自专栏木二天空

002.SMB安装与端口

8220
来自专栏木二天空

002.DNS-BIND简介

Bind是Berkeley Internet Name Domain Service的简写,它是一款实现DNS服务器的开放源码软件。已经成为世界上使用最为广泛的...

12830
来自专栏木二天空

001.RAID简介

独立磁盘冗余数组(RAID, Redundant Array of Independent Disks),旧称廉价磁盘冗余数组(RAID,Redundant A...

8530

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励