[Book Review] Python Algorithm Interview (4)

9009 ワード

[Book Review] Python Algorithm Interview テキストリンク

[Book Review]Python Algorithm Interview(4):配列

1.配列

배열

値or変数セグメントの集合からなる構造

1つまたは複数のインデックスまたはキーによって識別される

자료구조 분류1)メモリ容量ベースの連続性(アレイ)
2)ポインタベースの接続方式ADT(abstract data type) 추상자료형実際の実装の多くは、配列または接続リストに基づいている.
(ex.スタック:接続リスト/キュー:配列)通常배열 자료형配列は、サイズを指定し、連続メモリ領域を割り当てるデータ型です.
アレイの場合、クエリはO(1)동적배열アレイのサイズを自動的に変更する動的アレイ=アレイを自動的に再調整する動的アレイ
原理:小さい初期値を設定して配列を作成し、データを追加するときに埋め尽くし、拡大してすべてコピーします./普通は2倍で、どの言語の割合も2倍になります.파이썬의 경우初期再割当率(Growth Factor)は初期値の1.125倍(初期値4倍)
JavaのArrayList:1.5
C++std:Vector/Ruby:2倍
ダイナミックアレイの場合、サイズを指定する必要はなく、クエリーはO(1)でもかまいません.ただし、スペースが十分大きい場合は、新しいメモリ領域により大きなアレイを割り当て、既存のデータをコピーする必要があるため、コストはO(n)です.
すなわち,最悪の場合,挿入時はO(n)であるが,頻繁に発生しない->分割返済分析による入力時間はO(1)である.
ㅤㅤ
ㅤㅤ
ㅤㅤ
ㅤㅤ
ㅤㅤ

Q7. 二つの数の和

Q. 덧셈하여 타겟을 만들 수 있는 배열 두 숫자 인덱스르 리턴入力

nums = [2,7,11,15], target = 9

しゅつりょく

[0,1]

ex) nums[0] + nums[1] = 9

1)歌のクラス

def twoSum(self, nums: List[int], target: int) -> List[int]:
  for i in range(len(nums)):
    for j in range(i+1, len(nums)):
      if nums[i] + nums[j] == target:
       return [i,j]

時間複雑度:O(n^2)
遅すぎる
2)inによるナビゲーション
ナビゲーションターゲットに、すべての組合せを比較しないターゲットから最初の値を減算するtarget-nがあるかどうか

def twoSum(self, nums: List[int], target: int) -> List[int] :
  for i, n in enumerate(nums) :
     complement = target-n
ㅤ
  if complement in nums[i+1:]:
    return [nums.index(n), nums[i+1].index(complement) + (i+1)]

O(n^2)ですが、in演算速度はもっと速いです
3)最初の数値を問い合わせる結果キー

def twoSum(self, nums: List[int], target: int) -> List[int]:
  nums_map = {}
  for i, num in enumerate(nums):
    nums_map[num] = i
ㅤ
  for i,num in enumerate(nums):
    if target – num in num_map and i != nums_map[target-num]:
      return [i, nums_map[target-num]]

O(n)可能
4)クエリー構造の改善(プール3の改善)

def twoSum(self, nums: List[int], target: int) -> List[int]:
  nums_map = {}
  for i,num in enumerate(nums):
    if target-num in nums_map:
      return [nums_map[target-num], i]
   nums_map[num] = i

5)二重ポインタの使用
ありえない!(numsはソートされていないため、ソートするとインデックスがねじれ、質問がインデックスに尋ねられるため不可能です)
ㅤㅤ
ㅤㅤ
ㅤㅤ
ㅤㅤ
ㅤㅤ

Q8. 雨水輸送

Q>높이를 입력받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산入力

[0,1,0,2,1,0,1,3,2,1,2,1]

しゅつりょく

1)ダブルポインタを最大値に移動

def trap(self, height: List[int]) -> int:
  if not height:
    return 0
ㅤ
  volume = 0
  left, right = 0, len(height)-1
  left_max, right_max = height[left], height[right]
ㅤ
  while left < right
    left_max, right_max = max(height[left], left_max), max(height[right], right_max)
    if left_max <= right_max:
      volume += left_max – height[left]
      left+=1
    else:
      volulme += right_max – height[right]
      right -= 1
  return volume

に答える

[0,1,0,2,1,0,1,3,2,1,2,1]
(left, right) : (leftmax, rightmax)
(0,11)        : (0,1) -> volume : 0 + 0 - 0 / left + 1
(1,11)        : (1,1) -> volume : 0 + 1 - 1 / left + 1
(2,11)        : (1,1) -> volume : 0 + 1 - 0 / left + 1
(3,11)        : (2,1) -> volume : 1 + 1 - 1 / right - 1
(3,10)        : (2,2) -> volume : 1 + 2 - 2 / left + 1
(4,10)        : (2,2) -> volume : 1 + 2 - 1 / left + 1
(5,10)        : (2,2) -> volume : 2 + 2 - 0 / left + 1
(6,10)        : (2,2) -> volume : 4 + 2 - 1 / left + 1
(7,10)        : (3,2) -> volume : 5 + 2 - 2 / right -1
(7,9)          : (3,2) -> volume : 5 + 2 - 1 / right -1
(7,8)          : (3,2) -> volume : 6 + 2 - 2 / right -1
(7,7) //끝
return volume = 6

2)スタック

def trap(self, height: List[int]) -> int:
  stack = []
  volume = 0
ㅤ
  for i in range(len(height)):
    while stack and height[i] > height[stack[-1]]:
      top = stack.pop()
ㅤ
      if not len(stack):
        break
   ㅤ 
      distance = i – stack[-1] – 1
      waters = min(height[i], height[stack[-1]]) – height[top]
ㅤ
      volume += distance * waters
ㅤ
      stack.append()
  return volume

ㅤㅤ
ㅤㅤ
ㅤㅤ
ㅤㅤ
ㅤㅤ

Q9. 3つの数の和

Q.배열을 입력받아 합으로 0을 만들 수 있는 3개의 엘리먼트 출력入力

nums = [-1, 0, 1, 2, -1, -4]

しゅつりょく

[
 [-1, 0, 1],
 [-1, -1, 2]
]

1)歌のクラス

def threeSum(self, nums: List[int]) -> List[List[int]]:
  results = []
  nums.sort()
ㅤ
  for i in range(len(nums) – 2):
    if i > 0 and nums[i] == nums[i – 1]:
      continue
    for j in range(i+1, len(nums) – 1):
      if j > i + 1 and nums[j] == nums[j-1]:
        continue
      for k in range(j+1, len(nums)):
        if k>j + 1 and nums[k] == nums[k-1]:
          continue
        if nums[i] + nums[j] + nums[k] == 0:
          results.append( [nums[i], nums[j], nums[k]]
return results

->タイムアウト
2)ダブルポインタ

def threeSum(self, nums: List[int]) -> List[List[int]]:
  results = []
  nums.sort()
ㅤ
  for i in range(len(nums) – 2):
    if i > 0 and nums[i] == nums[i-1] : 
      continue
ㅤ
    left, right = i+1, len(nums) -1
    while left < right: 
      sum = nums[i] + nums[left] + nums[right]
      if sum < 0 :
        left +=1
      elif sum > 0 :
        right -=1
      else: 
        results.append( [nums[i], nums[left], nums[right]]
    ㅤ  
        while left < right and nums[left] == nums[left+1]:
          left += 1
        while left < right and nums[right] == nums[right -1]:
          right -= 1
        // 중복제거
        left += 1
        right -= 1 // 나머지 값 찾기 위해
  return results

に答える

i = 0~3
ㅤ
[-4, -1, -1, 0, 1, 2]
ㅤ
1) i = 0
left, right = (1, 5)
sum = -4 + -1 + 2 = -3
left + 1
ㅤ
left,right = (2,5)
sum = -4, -1 + 2 = -3
left + 1
ㅤ
left,right = (3,5)
sum = -4, 0, +2 = -2
ㅤ
left, right = (4,5)
sum = -4, 1, 2 = -1
ㅤ
left, right (5,5)
ㅤ
ㅤ
[-4, -1, -1, 0, 1, 2]
ㅤ
2) i = 1
left, right = (2,5)
sum = -1, -1, 2 = 0
append (-1,-1,2)
ㅤ
left + 1 / right -1 / (3,4)
sum = -1, 0, 1
append(-1,0,1)
ㅤ
3) i = 2 // 생략
ㅤ
4) i = 3
left, right (4,5)
sum = 3
// 끝
ㅤ
ㅤ
-> 투 포인터 슬라이딩윈도우랑 비슷

ㅤㅤ
ㅤㅤ
ㅤㅤ
ㅤㅤ
ㅤㅤ

Q10. アレイパーティション1

Q.n개의 페어를 이용한 min(a,b)의 합으로 만들 수 있는 가장 큰 수入力

[1,4,3,2]

しゅつりょく

[4]

説明:

n = 2 / 최대합 4
min(1,2), min(3,4) = 4

1)昇順に並べる

def arrayPairSum(self, nums: List[int]) -> int:
  sum = 0
  pair = []
  nums.sort()
ㅤ
  for n in nums:
    pair.append(n)
    if len(pair) == 2:
      sum += min(pair)
      pair = []
ㅤ
  return sum

2)偶数次値の計算

def arrayPairSum(self, nums: List[int] ) -> int:
  sum = 0
  nums.sort()
ㅤ
  for i, n in enumerate(nums):
    if i % 2 == 0:
     sum += n
  return sum

3)Pythonダウンロード方式

def arrayPairSum(self, nums: List[int]) -> int:
  return sum(sorted(nums)[::2])

ㅤㅤ
ㅤㅤ
ㅤㅤ
ㅤㅤ
ㅤㅤ

Q11. 非自己配列の積

Q. 배열을 입력받아 output[i]가 자신을 제외한 나머지 모든 요소의 곱셈 결과가 되도록 출력入力

[1,2,3,4]

しゅつりょく

[24,12,8,6]

*주의 : 나눗셈을 하지 않고 O(n)에 풀이

1)左の乗算結果に右の値を順番に乗じる

def productExceptSelf(self, nums: List[int]) -> List[int]
  out = []
  p = 1
ㅤ
  for i in range(0,len(nums)):
    out.append(p)
    p = p * nums[i]
  p = 1
ㅤ
  for i in range(len(nums) – 1, -1, -1):
    out[i] = out[i] * p
    p = p* nums[i]
  return out

ㅤㅤ
ㅤㅤ
ㅤㅤ
ㅤㅤ
ㅤㅤ

Q12. 株を売買するのに最適なタイミング

Q. 한 번의 거래로 낼 수 있는 최대 이익을 산출入力

[7,1,5,3,6,4]

しゅつりょく

[5]

설명 : 1일 때 사서 6일 때 팔면 5의 이익을 얻음

1)サブウーファ
ㅤㅤ

def maxProfit(self, prices: List[int]) -> int:
  max_price = 0
ㅤ
  for i, price in enumerate(prices):
    for j in range(i, len(prices)):
      max_price = max(prices[j] – price, max_price)
ㅤ
  return max_price

->タイムアウト
2)計算点と現在値の差異

def maxProfit(self, prices: List[int]) -> int:
  profit = 0
  min_price = sys.maxsize
ㅤ
  for price in prices:
    min_price = min(min_price, price)
    profit = max(profit, price-min_price)
ㅤ
  return profit

Reference

この問題について([Book Review] Python Algorithm Interview (4)), 我々は、より多くの情報をここで見つけました https://velog.io/@anthony16/Book-Review-Python-Algorithm-Interview-4-ungnj9gf

テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。

Collection and Share based on the CC Protocol

スマートポインタ、並列プログラミング、レーヨン

TIL. 34リアクション-条件レンダリング