23.02.23 Today’s Leetcode

502. IPO (hard)

Algorithm 수업때 배운 Example.
Greedy Algorithm Approach, 구매할 수 있는 최대 profits를 구매하면 Capital을 maximize 할 수 있다.

class Solution:
    def findMaximizedCapital(self, k: int, w: int, profits: List[int],
                             capital: List[int]) -> int:
        n = len(profits)
        projects = list(zip(capital, profits))
        projects.sort()
        # heapq is a min heap, but we need a max heap
        # so we will store negated elements
        q = []
        ptr = 0
        for i in range(k):
            while ptr < n and projects[ptr][0] <= w:
                # push a negated element
                heappush(q, -projects[ptr][1])
                ptr += 1
            if not q:
                break
            # pop a negated element
            w += -heappop(q)
        return w

283. Move Zeroes (easy)

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        pos = 0
        n = len(nums)
        for i in range(n):
            num = nums[i]
            if num != 0:
                nums[pos] = num
                pos += 1

        while pos < n:
            nums[pos] = 0
            pos += 1

167. Two Sum II - Input Array Is Sorted (medium)

Two Pointer Approach

class Solution:
    def twoSum(self, numbers, target):
        l, r = 0, len(numbers) - 1
        while l < r:
            s = numbers[l] + numbers[r]
            if s == target:
                return [l + 1, r + 1]
            elif s < target:
                l += 1
            else:
                r -= 1