展开

关键词

divid

相关内容

云服务器

云服务器

稳定、安全、弹性、高性能的云端计算服务,实时满足您的多样性业务需求
  • Data Structures and Algorithms Basics(005):Divid conquer

    分治算法: 在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础,如二分搜索,排序算法(快速排序,归并排序),傅立叶变换(快速傅立叶变换)...... 任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小,越容易直接求解,解题所需的计算时间也越少。例如,对于n个元素的排序问题,当n=1时,不需任何计算。n=2时,只要作一次比较即可排好序。n=3时只要作3次比较即可,…。而当n较大时,问题就不那么容易处理了。要想直接解决一个规模较大的问题,有时是相当困难的。 分治法的设计思想是:将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。  分治策略是:对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。  如果原问题可分割成k个子问题,1 nums: # exchange elements, time consuming nums, nums = nums, nums t = time.time() - start return nums, len(nums), t # O(n) time, quick selectiondef findKthLargest(nums, k): # convert the kth largest to smallest start = time.time() rst = findKthSmallest(nums, len(nums)+1-k) t = time.time() - start return rst, len(nums), t def findKthSmallest(nums, k): if nums: pos = partition(nums, 0, len(nums)-1) if k > pos+1: return findKthSmallest(nums, k-pos-1) elif k < pos+1: return findKthSmallest(nums, k) else: return nums # choose the right-most element as pivot def partition(nums, l, r): low = l while l < r: if nums < nums: nums, nums = nums, nums low += 1 l += 1 nums, nums = nums, nums return low if __name__ == __main__: import random from random import randint import sys import matplotlib.pyplot as plt def generate_random_array(n): return # 单元检测 l = generate_random_array(1000000) r = findKthLargest(l, len(l)2) print(r) # 画图:时间复杂度 # random_lists = # rst = # x = list(zip(*rst)) # y = list(zip(*rst)) # plt.plot(x, y) # plt.show() # 2,快速指数:def fast_power1_flaw(x, n): if n alist: return start return end mid = (start + end) 2 if alist > alist and alist > alist: return mid if alist > alist and alist > alist: return peak_helper(alist, start, mid - 1) return peak_helper(alist, mid + 1, end) # 4, 给定两个排好序的数组, 只有一个不同的地方:在第一个数组某个位置上多一个元素,查找该元素index# Input : {3, 5, 7, 9, 11, 13} {3, 5, 7, 11, 13},Output : 3def find_extra(arr1, arr2): for i in range(len(arr2)): if (arr1 != arr2): return i return len(arr1)-1 def find_extra_fast(arr1, arr2): index = len(arr2) # left and right are end points denoting # the current range. left, right = 0, len(arr2) - 1 while (left result: result = sum return result # O(n lgn)def subarray2(alist): return subarray2_helper(alist, 0, len(alist)-1) def subarray2_helper(alist, left, right): if (left == right): return alist mid = (left + right) 2 return max(subarray2_helper(alist, left, mid), subarray2_helper(alist, mid+1, right), maxcrossing(alist, left, mid, right)) def maxcrossing(alist, left, mid, right): sum = 0 left_sum = -sys.maxsize for i in range (mid, left-1, -1): sum += alist if (sum > left_sum): left_sum = sum sum = 0 right_sum = -sys.maxsize for i in range (mid+1, right+1): sum += alist if (sum > right_sum): right_sum = sum return left_sum + right_sum # O(n)def subarray3(alist): result = -sys.maxsize local = 0 for i in alist: local = max(local + i, i) result = max(result, local) return result if __name__ == __main__: alist = print(subarray1(alist)) print(subarray2(alist)) print(subarray3(alist)) # 6, 查找逆序对: 如果有两个元素a, a,如果a > a 且 i < j,那么a, a构成一个逆序对# 法1:O(n^2)def countInv(arr): n = len(arr) inv_count = 0 for i in range(n): for j in range(i+1, n): if (arr > arr): inv_count += 1 return inv_count # 法2:def merge(left,right): result = list() i,j = 0,0 inv_count = 0 while i < len(left) and j < len(right): if left < right: result.append(left) i += 1 elif right < left: result.append(right) j += 1 inv_count += (len(left)-i) result += left result += right return result,inv_count # O(nlgn)def countInvFast(array): if len(array) < 2: return array, 0 middle = len(array) 2 left,inv_left = countInvFast(array) right,inv_right = countInvFast(array) merged, count = merge(left,right) count += (inv_left + inv_right) return merged, count if __name__ == __main__: arr = print(Number of inversions are, countInv(arr)) print(Number of inversions are, countInvFast(arr)) # 7,奇-偶数换序 :input:{ a1, a2, a3, a4, ….., an, b1, b2, b3, b4, …., bn },output:{a1, b1, a2, b2, a3, b3, ……, an, bn }# O(n^2):def shuffleArray1(a, n): # Rotate the element to the left i, q, k = 0, 1, n while(i < n): j = k while(j > i + q): # print(i, j, q, k) a, a = a, a j -= 1 # for ii in range(0, 2 * n): # print(a, end = ) # print() i += 1 k += 1 q += 1 return a # O(n log n):def shuffleArray2(a, left, right): # If only 2 element, return if (right - left == 1): return # Finding mid to divide the array mid = (left + right) 2 # Using temp for swapping first # half of second array temp = mid + 1 # Mid is use for swapping second # half for first array mmid = (left + mid) 2 # Swapping the element for i in range(mmid + 1, mid + 1): (a, a) = (a, a) temp += 1 # Recursively doing for # first half and second half shuffleArray2(a, left, mid) shuffleArray2(a, mid + 1, right) return a def shuffleArray3(a): n = len(a) 2 start = n + 1 j = n + 1 done = 0 while (done < 2 * n - 2): #print(done, start, j) if (start == j): start = start - 1 j = j - 1 done += 1 i = j - n if j > n else j j = 2 * i if j > n else 2 * i - 1 a, a = a, a return a if __name__ == __main__: a = print(shuffleArray1(a, len(a) 2)) print(shuffleArray2(a, 0, len(a) - 1)) b = shuffleArray3(b) for i in range(1, len(b)): print(b, end = ) # 8, 元素右边最小的元素:input: , output: # O(n^2):def countSmaller1(nums): # 法1 n = len(nums) count = * n for i in range(n): for j in range(i + 1, n): if nums > nums: count += 1 return count # O(n^2):def countSmaller2(nums): # 法2 snums = * len(nums) for i in range(len(nums) - 1, -1, -1): index = findIndex(snums, nums) ans = index snums.insert(index, nums) return ans def findIndex(snums, target): start = 0 end = len(snums) - 1 if len(snums) == 0: return 0 while start mb: return kth1(a, b, k) else: return kth1(a, b, k) def find2(nums1, s1, e1, nums2, s2, e2, k): if e1 < s1: return nums2 if e2 < s2: return nums1 if k < 1: return min(nums1, nums2) ia, ib = (s1 + e1) 2 , (s2 + e2) 2 ma, mb = nums1, nums2 if (ia - s1) + (ib - s2) < k: if ma > mb: return find2(nums1, s1, e1, nums2, ib + 1, e2, k - (ib - s2) - 1) else: return find2(nums1, ia + 1, e1, nums2, s2, e2, k - (ia - s1) - 1) else: if ma > mb: return find2(nums1, s1, ia - 1, nums2, s2, e2, k) else: return find2(nums1, s1, e1, nums2, s2, ib - 1, k) def findMedianSortedArrays2(nums1, nums2): l = len(nums1) + len(nums2) if l % 2 == 1: return find2(nums1, 0, len(nums1) - 1, nums2, 0, len(nums2) - 1, l 2) else: return (find2(nums1, 0, len(nums1) - 1, nums2, 0, len(nums2) - 1, l 2) + find2(nums1, 0, len(nums1) - 1, nums2, 0, len(nums2) - 1, l 2 - 1)) 2.0 if __name__ == __main__: A = B = print(findMedianSortedArrays1(A, B)) print(findMedianSortedArrays2(A, B)) # 10,快速整数乘法:# 法一:def karatsuba(x,y): Function to multiply 2 numbers in a more efficient manner than the grade school algorithm if len(str(x)) == 1 or len(str(y)) == 1: return x*y else: n = max(len(str(x)),len(str(y))) nby2 = n 2 a = x 10**(nby2) b = x % 10**(nby2) c = y 10**(nby2) d = y % 10**(nby2) ac = karatsuba(a,c) bd = karatsuba(b,d) ad_plus_bc = karatsuba(a+b,c+d) - ac - bd # this little trick, writing n as 2*nby2 takes care of both even and odd n prod = ac * 10**(2*nby2) + (ad_plus_bc * 10**nby2) + bd return prod # 法二: # third_grade_algorithm.pyimport functoolsdef prod(x, y): # x, y are strings --> returns a string of x*y return str(eval(%s * %s % (x, y))) def plus(x, y): # x, y are strings --> returns a string of x+y return str(eval(%s + %s % (x, y))) def one_to_n_product(d, x): d is a single digit, x is n-digit --> returns a string of d*x #print(d, x) result = carry = 0 for i, digit in enumerate(reversed(x)): #print(d: , d, digit: , digit) r = plus(prod(d, digit), carry) #print(r: , r) if (len(r) == 1): carry = 0 else: carry = r digit = r #print( c: , carry, d: , digit) result = digit + result return carry + result def sum_middle_products(middle_products): # middle_products is a list of strings --> returns a string max_length = max() for i, md in enumerate(middle_products): middle_products = 0 * (max_length - len(md)) + md #print(middle_products) carry = 0 result = for i in range(1, max_length + 1): row = + for md in middle_products] r = functools.reduce(plus, row) carry, digit = r, r result = digit + result return carry + result def algorithm(x, y): x, y = str(x), str(y) middle_products = * (m + n - 1) for i in range (m): for j in range(n): result += A * B return result def printPoly(poly): n = len(poly) show = for i in range(n-1, -1, -1): show += str(poly) if (i != 0): show = show + x^ + str(i) if (i != 0): show = show + + print(show) if __name__ == __main__: A = B = r = mults(A, B) printPoly(r) from numpy import convolve A = B = print(convolve(A, B)) # 12, 水槽问题:# Utility method to get# sum of first n numbersdef getCumulateSum(n): return (n * (n + 1)) 2 # Method returns minimum number of days# after which tank will become emptydef minDaysToEmpty(C, l): # if water filling is more than # capacity then after C days only # tank will become empty if (C = (C - l)): hi = mid # if (C - l) is more then # search on right side else: lo = mid + 1 # Final answer will be obtained by # adding l to binary search result return (l + lo) import math # 法二:def solve(a, b, c): r = pow(b, 2) - 4 * a * c if (r < 0): raise ValueError(No Solution) return (-b + math.sqrt(r)) (2 * a) def minDaysToEmpty2(C, l): co = -2 * (C - l) return math.ceil(solve(1, 1, co)) + l if __name__ == __main__: C, l = 5, 2 print(minDaysToEmpty(C, l)) C, l = 5, 2 print(minDaysToEmpty2(C, l)) # 13,用最少步数收集所有硬币:def minSteps(height): def minStepHelper(height, left, right, h): if left >= right: return 0 m = left for i in range(left, right): if height < height: m = i return min(right - left, minStepHelper(height, left, m, height) + minStepHelper(height, m + 1, right, height) + height - h) return minStepHelper(height, 0, len(height), 0) if __name__ == __main__: height = print(minSteps(height))
    来自:
    浏览:155
  • GPU 云服务器

    腾讯GPU 云服务器是提供 GPU 算力的弹性计算服务,具有超强的并行计算能力,作为 IaaS 层的尖兵利器,服务于深度学习训练、科学计算、图形图像处理、视频编解码等场景……
    来自:
  • FPGA 云服务器

    腾讯FPGA云服务器是基于FPGA硬件可编程加速的弹性计算服务,您只需几分钟就可以获取并部署您的FPGA实例。结合IP市场提供的图片,视频,基因等相关领域的计算解决方案,提供无与伦比的计算加速能力……
    来自:
  • 广告
    关闭

    腾讯极客挑战赛-寻找地表最强极客

    报名比赛即有奖,万元礼品和奖金,等你来赢!

  • 专用宿主机

    专用宿主机(CDH)提供用户独享的物理服务器资源,满足您资源独享、资源物理隔离、安全、合规需求。专用宿主机搭载了腾讯云虚拟化系统,购买之后,您可在其上灵活创建、管理多个自定义规格的云服务器实例,自主规划物理资源的使用。
    来自:
  • 黑石物理服务器2.0

    腾讯黑石物理服务器2.0(CPM)是一种包年包月的裸金属云服务,为您提供云端独享的高性能、无虚拟化的、安全隔离的物理服务器集群。使用该服务,您只需根据业务特性弹性伸缩物理服务器数量,获取物理服务器的时间将被缩短至分钟级。
    来自:
  • 容器服务

    腾讯云容器服务(Tencent Kubernetes Engine ,TKE)基于原生kubernetes提供以容器为核心的、高度可扩展的高性能容器管理服务。腾讯云容器服务完全兼容原生 kubernetes API ,扩展了腾讯云的云硬盘、负载均衡等 kubernetes 插件,为容器化的应用提供高效部署、资源调度、服务发现和动态伸缩等一系列完整功能,解决用户开发、测试及运维过程的环境一致性问题,提高了大规模容器集群管理的便捷性,帮助用户降低成本,提高效率。容器服务提供免费使用,涉及的其他云产品另外单独计费。
    来自:
  • 弹性伸缩

    腾讯弹性伸缩(AS)为您提供高效管理计算资源的策略。您可设定时间周期性地执行管理策略或创建实时监控策略,来管理 CVM 实例数量,并完成对实例的环境部署,保证业务平稳顺利运行。弹性伸缩策略不仅能够让需求稳定规律的应用程序实现自动化管理,同时告别业务突增或CC攻击等带来的烦恼,对于每天、每周、每月使用量不停波动的应用程序还能够根据业务负载分钟级扩展。
    来自:
  • 云函数

    云函数(Serverless Cloud Function,SCF)是腾讯云为企业和开发者们提供的无服务器执行环境,帮助您在无需购买和管理服务器的情况下运行代码。您只需使用平台支持的语言编写核心代码并设置代码运行的条件,即可在腾讯云基础设施上弹性、安全地运行代码。SCF 是实时文件处理和数据处理等场景下理想的计算平台。
    来自:
  • 批量计算

    批量计算(Batch)是为有大数据计算业务的企业、科研单位等提供高性价比且易用的计算服务。批量计算可以根据用户提供的批处理规模,智能地管理作业和调动所其需的最佳资源……
    来自:
  • 消息队列 CMQ

    腾讯云消息队列(CMQ)是一种分布式消息队列服务,它能够提供可靠的基于消息的异步通信机制,能够将分布式部署的不同应用(或同一应用的不同组件)之间的收发消息,存储在可靠有效的 CMQ 队列中,防止消息丢失。CMQ 支持多进程同时读写,收发互不干扰,无需各应用或组件始终处于运行状态。
    来自:
  • 消息队列 CKafka

    CKafka(Cloud Kafka)是一个分布式的、高吞吐量、高可扩展性的消息系统,100%兼容开源 Kafka API(0.9版本)。Ckafka 基于发布/订阅模式,通过消息解耦,使生产者和消费者异步交互,无需彼此等待。Ckafka 具有数据压缩、同时支持离线和实时数据处理等优点,适用于日志压缩收集、监控数据聚合等场景。
    来自:
  • API 网关

    腾讯云 API 网关(API Gateway)是腾讯云推出的一种 API 托管服务,能提供 API 的完整生命周期管理,包括创建、维护、发布、运行、下线等。您可使用 API 网关封装自身业务,将您的数据、业务逻辑或功能安全可靠的开放出来,用以实现自身系统集成、以及与合作伙伴的业务连接。
    来自:
  • 微服务平台 TSF

    腾讯微服务平台(TSF)是一个围绕应用和微服务的 PaaS 平台,提供一站式应用全生命周期管理能力和数据化运营支持,提供多维度应用和服务的监控数据,助力服务性能优化。
    来自:
  • 对象存储

    腾讯云对象存储数据处理方案主要针对于存储于腾讯云对象存储COS中的数据内容进行处理加工,满足压缩、转码、编辑、分析等多种诉求,激活数据价值。
    来自:
  • 文件存储

    文件存储(Cloud File Storage,CFS)为您提供安全可靠、可扩展的共享文件存储服务。CFS 可与腾讯云服务器、容器服务、批量计算等服务搭配使用,为多个计算节点提供容量和性能可弹性扩展的高性能共享存储。腾讯云 CFS 的管理界面简单、易使用,可实现对现有应用的无缝集;按实际用量付费,为您节约成本,简化 IT 运维工作。
    来自:
  • 归档存储

    腾讯云归档存储(Cloud Archive Storage, CAS)是面向企业和个人开发者提供的低成本、高可靠且易于管理的云端离线存储服务,适用于海量、非结构化数据长时间备份,实现数据的容灾和c。归档存储采用分布式云端存储,您可以通过 RESTful API 对存储的数据进行访问。归档存储易于管理,您无需关心硬件维护及容量扩展;按实际使用量付费,为您节省额外成本。
    来自:
  • 存储网关

    存储网关(CSG)是一种混合云存储方案,旨在帮助企业或个人实现本地存储与公有云存储的无缝衔接。您无需关心多协议本地存储设备与云存储的兼容性,只需要在本地安装云存储网关即可实现混合云部署,并拥有媲美本地性能的海量云端存储。
    来自:
  • 云硬盘

    云硬盘(CBS)为您提供云服务器的持久性块存储服务。云硬盘中的数据自动地在可用区内以多副本冗余方式存储,避免数据的单点故障风险,提供高达99.9999999% 的数据可靠性。云硬盘提供多种类型及规格的磁盘实例,满足稳定低延迟的存储性能要求。
    来自:
  • 云数据迁移

    云数据迁移(Cloud Data Migration)是腾讯云提供的 TB ~ PB 级别的数据迁移上云服务。本服务提供了安全可靠的离线迁移专用设备,满足本地数据中心进行大规模数据迁移上云的需求,解决本地数据中心通过网络传输时间长、成本高、安全性低的问题。
    来自:

扫码关注云+社区

领取腾讯云代金券