专栏首页MiningAlgorithmsPython3刷题系列(三)

Python3刷题系列(三)

一),二分法思想:

1,leetcode-69:Sqrt(x) (x 的平方根)

英文版:https://leetcode.com/problems/sqrtx/

中文版:https://leetcode-cn.com/problems/sqrtx/

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
                

2,leetcode-167:双指针

双指针主要用于数组,两个指针指向不同的元素,从而协同完成任务。

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]

3,leetcode-215:练习排序方法:快排、堆排

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

# 快排:时间复杂度-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

4,leetcode-347:桶排序

class Solution:
    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.item():
            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-75:三向切分快排

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

# 三向切分快速排序思想:
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

6,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

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

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

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • c# 利用AForge.NET组件操作摄像头

    private FilterInfoCollection videoDevices;

    用户5640963
  • 001.网络TCP/IP工程知识点

    木二
  • 001.LVS简介及算法

    LVS是linux virtual server的简写linux虚拟服务器,是一个虚拟的服务器集群系统,可以再unix/linux平台下实现负载均衡集群功能。

    木二
  • JSONObject put,accumulate,element的区别

    public Object put (Object key, Object value) 将value映射到key下。如果此JSONObject对象之前存在一个...

    用户5640963
  • jQuery 下拉查询筛选插件Combo Select

    插件描述:Combo Select 是一款友好的 jQuery 下拉框插件,在 PC 浏览器上它能模拟一个简单漂亮的下拉框,在 iPad 等移动设备上又能回退到...

    用户5640963
  • webuploader java版本

    网上一些webuploader上传的资料,有php版和java版本的,做了一下整合,现分享以下成果,可以讨论,不喜勿碰。说一下过程。

    用户5640963
  • linux应用之wget命令详解

    wget是linux最常用的下载命令, 一般的使用方法是: wget + 空格 + 要下载文件的url路径

    用户5640963
  • Json(Json-lib)中使用JSONObject.toBean(JSONObject jsonObject, Class beanClass)日期保存了当前时间

    1、问题:使用Json-lib,转换数据的方法JSONObject.toBean(JSONObject jsonObject, Class beanClass)...

    用户5640963
  • 【ionic+angularjs】angularjs ui-router路由简介($urlRouter、$state、$stateProvider、ui-sref....)

    之前有写过一篇关于Angular自带的路由:ngRoute。今天来说说Angular的第三方路由:ui-router。那么有人就会问:为什么Ang...

    用户5640963
  • JSONObject.fromObject 转换JSON字符串Map及javabean时间处理的问题

    这几天的项目开发过程中遇到一个比较棘手的问题,主要是通用导出类中,使用了一个javabean转换成json字符串的问题,javabean中一个日期格式是“yyy...

    用户5640963

扫码关注云+社区

领取腾讯云代金券