Leetcode-귀속&분치
pow(x, n), 즉 x의 n차멱 함수를 계산하는 것을 실현한다.
설명:
-100.0 x < 100.0
n은 32비트의 기호 정수로 그 수치 범위는 [−231,231−1]이다.
해:
직접 라이브러리 함수를 조정하지만 면접에서는 틀림없이 안 된다.
폭력, 순환을 써서 바로 곱하기, O(N).
분할, y = x**(n/2).n은 짝수이다. 두 부분은 똑같이 한쪽만 계산하면 된다.res=y*y.n은 홀수,res = y*x*y입니다.x**1 또는 x**0까지 계산합니다.시간 복잡도는 O(logN)입니다.
차례로 실현되다
class Solution:
def myPow(self, x: float, n: int) -> float:
if not n:
return 1
if n < 0:
return 1 / self.myPow(x, -n)
if n % 2:
return x * self.myPow(x, n-1) # n ， n-1
return self.myPow(x*x, n/2) # n
교체가 이루어지고 분치의 최소 계산 곱자는 x이다.예를 들어, x**(7) = x* x**(6) = x* (x* *2) **(3) = x* (x* *2) *1
class Solution:
def myPow(self, x: float, n: int) -> float:
if not n:
return 1
if n < 0: # n 0 n 0 ， x 1/x
x = 1/x
n = -n
res = 1
while n: # 1
if n & 1: # n ， x
res *= x
x *= x # x x**2
n >>= 1 # n = floor(n/2)
return res
169. 중수를 구하다https://leetcode-cn.com/problems/majority-element/
크기가 n인 그룹을 지정하여 그 중의 중수를 찾습니다.중수는 수조에서
⌊ n/2 ⌋보다 많이 나타나는 원소를 가리킨다.너는 수조가 비어 있지 않다고 가정할 수 있으며, 주어진 수조는 항상 중수가 존재한다.
해:
폭력, 두 겹의 삽입 순환, 모든 x를 하나하나 열거하고 특정한 x를 대상으로 수를 계산한다.O(N2)
직접 정렬한 후 중간 원소를 취하면 틀림없이 중수일 것이다.O(NlogN)
class Solution:
def majorityElement(self, nums: List[int]) -> int:
nums.sort()
n = len(nums)
return nums[int((n-1)/2)]
한 번 훑어보면hashmap으로 원소를 계수하고 마지막으로 맵에 가서 계수가 가장 큰 원소가 무엇인지 보십시오.O(N)
class Solution:
def majorityElement(self, nums: List[int]) -> int:
count = dict()
for x in nums:
count[x] = count.get(x, 0) + 1
max_count = 0
for key, value in count.items():
if value > max_count:
max_count = value
res = key
return res # get ， return max(count, key=count.get)
모든 하위 문제가 길이가 1인 수조가 될 때까지 분할 치료는 차례로 해답을 구한다.전송 서브 그룹은 별도의 시간과 공간을 필요로 하기 때문에 우리는 실제로 서브 구간의 좌우 바늘low와high만 전송하여 해당 구간의 좌우 하표를 표시한다.
길이가 1인 하위 그룹 중 유일한 수는 중수인 것이 분명하니 직접 되돌아오면 된다.
만약 거슬러 올라간 후 어떤 구간의 길이가 1보다 크면 반드시 좌우 하위 구간의 값을 합쳐야 한다.만약 그것들의 중수가 같다면, 분명히 이 구간의 중수는 그것들의 같은 값이다.그렇지 않으면 두 개의 중수가 전체 구간에서 나타나는 횟수를 비교하여 이 구간의 중수를 결정해야 한다.
원래 문제의 답은 아래에 0과 n 사이에 표시된 중수라는 문제이다.
시간 복잡도는 O(NlogN)
class Solution:
def majorityElement(self, nums: List[int]) -> int:
return self.helper(nums, 0, len(nums)-1)
def helper(self, nums, low, high):
if low == high: # 1 ，
return nums[low]
# 1，
mid = low + (high - low) // 2
left = self.helper(nums, low, mid)
right = self.helper(nums, mid+1, high)
if left == right: # ， ，
return left
# ， count
left_count, right_count = 0, 0
for i in range(low, high+1):
if nums[i] == left:
left_count += 1
elif nums[i] == right:
right_count += 1
return left if left_count > right_count else right
53. 최대 하위 시퀀스 및https://leetcode-cn.com/problems/maximum-subarray/
정수 그룹
nums을 지정하고 최대 및 연속 하위 그룹(자수 그룹은 최소 하나의 원소를 포함)을 찾아 최대 및 를 되돌려줍니다.진급:
만약 당신이 이미 복잡도가 O(n)인 해법을 실현했다면, 더욱 정교한 분치법으로 해답을 구해 보세요.
해:
동적 기획, 수조를 두루 훑어보는데 현재 최대 연속 서열과sum이고 결과는 ans입니다.만약sum>0이면 앞의 하위 서열이 전체에 이득이 있음을 설명하고 보류합니다.그렇지 않으면 앞의 하위 서열은 필요 없고 현재의 횟수만 유지됩니다.매번 sum과 ans의 크기를 비교할 때마다 ans가 최대치를 취합니다.O(N)
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
if not nums:
return 0
res = nums[0]
sum_ = 0
for i in range(len(nums)):
if sum_ > 0:
sum_ += nums[i]
else:
sum_ = nums[i]
if sum_ > res:
res = sum_
return res
가장 큰 하위 서열과 왼쪽에 있거나 오른쪽에 있거나 왼쪽을 건너거나 분리합니다.좌우 양쪽의 상황은 직접 귀속적으로 해답을 구한다. 중간의 경우 서열이 연속되고mid점을 뛰어넘는 것은 좌우 양쪽이 모두 연속적이라는 것을 의미한다. 각각 오른쪽에서 왼쪽으로, 오른쪽에서 왼쪽으로 최대 연속 서열을 찾는다.O(N*logN)
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
if len(nums) == 1:
return nums[0]
n = len(nums)
#
mid = (n-1) // 2
left = self.maxSubArray(nums[: mid+1])
right = self.maxSubArray(nums[mid+1:])
# ， ， ，
medium_l = nums[mid]
tmp = 0
for i in range(mid, -1, -1):
tmp += nums[i]
medium_l = max(medium_l, tmp)
medium_r = nums[mid+1]
tmp = 0
for i in range(mid+1, n):
tmp += nums[i]
medium_r = max(medium_r, tmp)
medium = medium_l + medium_r
return max(left, right, medium) # ，
438. 문자열의 모든 알파벳의 이위어를 찾습니다.https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/
문자열 s와 비공식 문자열 p를 지정합니다. s에서 p의 자모 이위어인 모든 하위 문자열을 찾아서 하위 문자열의 시작 인덱스를 되돌려줍니다.
문자열은 소문자만 포함하고 문자열 s와 p의 길이는 20100을 넘지 않습니다.
설명:
알파벳 이위어는 알파벳이 같지만 배열이 다른 문자열을 가리킨다.답안 출력 순서를 고려하지 않습니다.
해:
폭력, 모든 가능한 하위 직렬 시작 색인을 열거하고 이위어 여부를 직접 판단, O(N*K)
슬라이딩 창 + 해시 테이블, 아니면 해시 테이블로 p의 문자를 저장하고, 가능한 모든 하위 인덱스를 일일이 열거하고, 해시 테이블로 판단하고, O(N)
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
if not s:
return []
def build_map(p):
aph_map = dict()
for c in p:
aph_map[c] = aph_map.get(c, 0) + 1
return aph_map
p_map = build_map(p)
s = list(s)
n, k = len(s), len(p)
base_map = build_map(s[:k]) # ， hashmap
res = []
for i in range(n-k+1):
if base_map == p_map:
res.append(i)
if i != n-k:
# s[i]
tmp = base_map.get(s[i])-1
if tmp:
base_map[s[i]] = tmp
else:
base_map.pop(s[i])
base_map[s[i+k]] = base_map.get(s[i+k], 0) + 1 # s[i+k]
return res
437. 경로 총 iiihttps://leetcode-cn.com/problems/path-sum-iii/
두 갈래 나무를 정해 주면 결점마다 정수치가 저장되어 있다.
경로와 주어진 수치와 같은 경로의 총수를 찾아라.
경로는 루트 노드에서 시작할 필요도 없고 잎 노드에서 끝날 필요도 없지만 경로 방향은 아래쪽이어야 합니다 (부모 노드에서 하위 노드까지만).
두 갈래 나무는 1000개의 노드를 초과하지 않고 노드의 수치 범위는 [-1000000, 10000000]의 정수이다.
해:
이 문제의 경로의 시작점과 끝점은 모두 임의의 것이므로 dfs에서 직접 계산하기가 쉽지 않습니다. 아니면 특정한 노드 node를 훑어볼 때 이전의 모든 가능한 경로와list로 전송해야 합니다. 새로운 경로와 원래의 경로와 node를 포함합니다.val, 그리고 node에서 시작하는 새로운 경로, 그리고 node입니다.val.그리고 좌우 노드 dfs를 누르면 됩니다.
class Solution:
def pathSum(self, root: TreeNode, sum: int) -> int:
if root is None:
return 0
# sums node ， node
def dfs(node, sums):
left = right = 0 # 0
# node ， ， ，
tmp = [num + node.val for num in sums] + [node.val]
if node.left:
left = dfs(node.left, tmp) # dfs
if node.right:
right = dfs(node.right, tmp)
return tmp.count(sum) + left + right
return dfs(root, [])
비교적 좋은 귀속 함수를 설계하다.쌍귀속.
pathSum 함수, 노드와 목표 값을 정하고 이 노드를 루트로 하는 트리와 목표 값으로 하는 경로 총수를 되돌려줍니다.
count 함수, 노드와 목표 값을 정하고 이 노드를 루트로 하는 트리로 되돌려줍니다. 이 노드를 경로로 시작하고 목표 값을 위한 경로 총수입니다.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def pathSum(self, root: TreeNode, sum: int) -> int:
if root is None:
return 0
return self.count(root, sum) + self.pathSum(root.left, sum) + self.pathSum(root.right, sum) # root = root + root
def count(self, node, sum):
if node is None:
return 0
tmp = 0
if node.val == sum:
tmp += 1
tmp += self.count(node.left, sum - node.val) + self.count(node.right, sum - node.val)
return tmp
4. 두 개의 질서수 그룹의 중위수 찾기https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
두 개의 크기가 m와 n인 질서수 그룹nums1과nums2를 지정합니다.
이 두 질서수 그룹의 중위수를 찾아내고 알고리즘의 시간 복잡도를 O (log (m + n) 로 요구하십시오.
너는nums1과nums2가 동시에 비어 있지 않다고 가정할 수 있다.
예 1:
nums1 = [1, 3]nums2 = [2]
중위는 2.0입니다.
예 2:
nums1 = [1, 2]nums2 = [3, 4]
중간 값은 (2 + 3)/2 = 2.5입니다.
해:
시간의 복잡도 요구를 고려하지 않고 두 바늘이 두루 흐르는 방법.하나의 수조res를 중위수mid와 뒷수mid+1에 저장하고 중위수가 한 수라면res[-2]로 되돌려줍니다.2로 나누려면 (res[-1]+res[-2])/2로 돌아갑니다.비교적 짜증나는 것은nums가 비어 있는 상황을 주의하고res에 원소를 추가해야 하는지 판단하는 조건이다.
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
if not nums1 and not nums2:
return 0.
elif not nums1:
n = len(nums2)
return float(nums2[n//2]) if n%2 != 0 else (nums2[(n//2)-1]+nums2[(n//2)])/2
elif not nums2:
n = len(nums1)
return float(nums1[n//2]) if n%2 != 0 else (nums1[(n//2)-1]+nums1[(n//2)])/2
m, n = len(nums1), len(nums2)
target_len = (m+n)//2 + 1 if (m+n) % 2 == 0 else (m+n)//2 + 2
i, j = 0, 0
res = []
while i < m and j < n:
if nums1[i] < nums2[j]:
res.append(nums1[i])
i += 1
else:
res.append(nums2[j])
j += 1
if len(res) == target_len:
break
if i < m:
while i < m:
if len(res) == target_len:
break
res.append(nums1[i])
i += 1
if j < n:
while j < n:
if len(res) == target_len:
break
res.append(nums2[j])
j += 1
if (m+n) % 2 == 0:
return (res[-1]+res[-2])/2
return float(res[-2])
중위수를 찾으려면 A와 B를 어느 위치에서 i와 j를 두 부분으로 잘라야 한다, left_A 및 left_B 공통 구성 left, right_A 및 right_B는 right를 공동으로 구성하는데 left와 right의 길이가 같고 max(left)<=min(right)만 같으면 중위수는 (max(left)+min(right)/2와 같다.어떻게 경계값을 찾는지 이분법으로 할 수 있습니다. 먼저num1이 m1개의 수의 왼쪽을 찾으면num2는 m2=(m+n+1)/2-m1의 왼쪽을 찾으면 적당한 m1을 찾으면 이분법으로 찾습니다.
[[a1], [b1, b2, b3] | [a2,.an], [b4,...bn]]
b3과 a2의 관계의 크기만 비교하면 이런 분법이 정확한지 알 수 있다
예:nums1 = [-1,1,3,5,7,9],nums2 = [2,4,6,8,10,12,14,16]
m1=4, m2=3, 그 중위수는 median=(num1[m1]+num2[m2])/2
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
n1, n2 = len(nums1), len(nums2)
if n1 > n2:
nums1, nums2, n1, n2 = nums2, nums1, n2, n1 # n2 >= n1，
k = (n1 + n2 + 1) // 2 # left right
left = 0
right = n1-1
while left <= right: # nums1 m1， nums1[m1] == nums2[k-m1-1]
m1 = left + (right - left) // 2
m2 = k - m1
if nums1[m1] < nums2[m2-1]:
left = m1 + 1
else:
right = m1 - 1
m1 = left # ，nums1[left] nums[k-left] left=n1
m2 = k - m1
c1 = max(nums1[m1-1] if m1 > 0 else float("-inf"), nums2[m2-1] if m2 > 0 else float("-inf") )
if (n1 + n2) % 2 == 1:
return c1
c2 = min(nums1[m1] if m1 < n1 else float("inf"), nums2[m2] if m2
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
