【 이벤트 카드 】 【 Datawhale 】 제1 6 기 프로 그래 밍 실천 (LeetCode 분류 연습) Task 01: 분할 치료

(이틀 동안 놀 러 나 갔 는데 쓸 시간 이 없어 서 억지로 카드 를 찍 을 수 밖 에 없 었 다. 시간 이 있 으 면 상세 한 코드 주석 과 치료 방향 을 보충 했다)
분 치 법
컴퓨터 과학 에서 분 치 법 은 여러 가지 분기 재 귀 를 바탕 으로 하 는 매우 중요 한 알고리즘 패 러 다 임 을 구축 하 는 것 이다.글자 의 해석 은 '나 누 어 다스 리 는 것' 이다. 바로 복잡 한 문 제 를 두 개 이상 의 똑 같 거나 비슷 한 서브 문제 로 나 누 어 마지막 까지 서브 문 제 를 간단하게 직접 해결 할 수 있다. 원래 문제 의 해 는 바로 서브 문제 의 해 의 합병 이다.
이 기 교 는 많은 효율 적 인 알고리즘 의 기초 이다. 예 를 들 어 정렬 알고리즘 (정렬, 빠 른 정렬), 부 립 엽 변환 (빠 른 부 립 엽 변환) 이다.
분 치 알고리즘 은 보통 수학 귀납법 으로 검증 된다.그 계산 원 가 는 대부분 재 귀 관계 식 으로 판단 된다.
예제
50. Pow(x, n)
원 제 전송: 링크 기타 해법: 링크
pow (x, n), 즉 x 의 n 차 멱 함 수 를 계산 합 니 다.
예시 1:

  : 2.00000, 10
  : 1024.00000

예시 2:

  : 2.10000, 3
  : 9.26100

예시 3:

  : 2.00000, -2
  : 0.25000
  : 2^(-2) = 1/(2^2) = 1/4 = 0.25

설명:

-100.0 < x < 100.0

n 은 32 비트 의 기호 정수 로 그 수치 범 위 는 [- 2 31, 2 31 - 1] [- 2 ^ {31}, 2 ^ {31} - 1] [- 231 - 231 - 1] 이다.

생각:
쾌속 멱 을 사용 하 다.(분할 치료 재 귀 실현)
Python:

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n < 0:
            x = 1 / x
            n = -n
        if n == 0:
            return 1
        if n & 1:
            ans = x * self.myPow(x, n-1)
            return ans
        return self.myPow(x*x, n//2)

53. 최대 하위 순서 와
원 제 전송: 링크 기타 해법: 링크
정수 배열 nums 을 지정 하고 최대 와 연속 적 인 하위 배열 (하위 배열 은 최소 하나의 요 소 를 포함) 을 찾 아 최대 와 합 을 되 돌려 줍 니 다.
예시:

  : [-2,1,-3,4,-1,2,1,-5,4]
  : 6
  :       [4,-1,2,1]     ，  6。

진급:
만약 당신 이 복잡 도가 O (n) 인 해법 을 실현 했다 면 더욱 정교 한 분 치 법 으로 구 해 를 시도 해 보 세 요.
생각:
분 치 법, 최대 서브 순서 와 왼쪽 에 있 거나 오른쪽 에 있 거나 중간 을 지나 갑 니 다.좌우 변 의 서열 에 대해 서도 상황 이 같 기 때문에 재 귀적 으로 처리 할 수 있다.중간 부분 은 계산 을 통 해 얻 을 수 있다.
Python:

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
        else:
            max_left = self.maxSubArray(nums[:len(nums)//2])
            max_right = self.maxSubArray(nums[len(nums)//2:])
        max_l = nums[len(nums)//2-1]
        temp = 0
        for i in range(len(nums)//2-1, -1, -1):
            temp += nums[i]
            max_l = max(temp, max_l)
        max_r = nums[len(nums)//2]
        temp = 0
        for i in range(len(nums)//2, len(nums)):
            temp += nums[i]
            max_r = max(temp, max_r)
        return max(max_right, max_left, max_l+max_r)

169. 다수 원소
원 제 전송: 링크 기타 해법: 링크
n 크기 의 배열 을 지정 하여 대부분의 요 소 를 찾 습 니 다.대부분의 요 소 는 배열 에서 나타 난 횟수 가 ⌊ n/2 ⌋ 보다 많은 요 소 를 말한다.
배열 이 비어 있 지 않다 고 가정 할 수 있 고 주어진 배열 에는 항상 다수의 요소 가 존재 합 니 다.
예시 1:

  : [3,2,3]
  : 3

예시 2:

  : [2,2,1,1,1,2,2]
  : 2

생각:
분 치 법.
Python:

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
        left = self.majorityElement(nums[:len(nums)//2])
        right = self.majorityElement(nums[len(nums)//2:])
        if left == right:
            return left
        if nums.count(left) > nums.count(right):
            return left
        else:
            return right

참고 문장

제1 6 기 Datawhale 팀 학습 활동

Datawhale 과정 - 분 치

분 치 법 - 위 키 백과