Python - Algorithm #58

Python Algorithm

LeetCode

2600. K Items With the Maximum Sum

• There is a bag that consists of items, each item has a number 1, 0, or -1 written on it.
• You are given four non-negative integers numOnes, numZeros, numNegOnes, and k.
• The bag initially contains:
  • numOnes items with 1s written on them.
  • numZeroes items with 0s written on them.
  • numNegOnes items with -1s written on them.
• We want to pick exactly k items among the available items. Return the maximum possible sum of numbers written on the items.
• Constraints
  
  • 0 ≤ numOnes, numZeros, numNegOnes ≤ 50
  • 0 ≤ k ≤ numOnes + numZeros + numNegOnes

class Solution:
    def kItemsWithMaximumSum(self, numOnes: int, numZeros: int, numNegOnes: int, k: int) -> int:
        # 1. k값이 numsOnes 보다 같거나 작을 때
        # 2. k값이 numsOnes 보다 크고 numOnes + numZeros 보다 같거나 작을 때
        # 3. 그보다 클 때
        return min(k, numOnes) if k <= numOnes + numZeros else numOnes - (k - (numOnes + numZeros))

class Solution:
    def kItemsWithMaximumSum(self, numOnes: int, numZeros: int, numNegOnes: int, k: int) -> int:
        if k <= numOnes:
            return k
        elif k <= numOnes + numZeros:
            return numOnes
        else:
            return numOnes - (k - (numOnes + numZeros))

---

2210. Count Hills and Valleys in an Array

• You are given a 0-indexed integer array [nums]. An index i is part of a hill in [nums] if the closest non-equal neighbors of i are smaller than nums[i]. Similarly, an index i is part of a valley in [nums] if the closest non-equal neighbors of i are larger than nums[i]. Adjacent indices i and j are part of the same hill or valley if nums[i] == nums[j].
• Note that for an index to be part of a hill or valley, it must have a non-equal neighbor on both the left and right of the index.
• Return the number of hills and valleys in [nums].
• Constraints
  • 3 ≤ nums.length ≤ 100
  • 1 ≤ nums[i] ≤ 100

class Solution:
    def countHillValley(self, nums: List[int]) -> int:
        # 중복은 먼저 제거하고 hill, valley 카운팅 해볼 것
        new_nums = []
        for i in range(len(nums)):
            if i == 0:
                new_nums.append(nums[i])
            elif nums[i] != nums[i-1]:
                new_nums.append(nums[i])
        answer = 0
        for i in range(1, len(new_nums)-1):
            if new_nums[i-1] < new_nums[i] >new_nums[i+1]:
                answer += 1
            if new_nums[i-1] > new_nums[i] < new_nums[i+1]:
                answer += 1
        return answer

class Solution:
    def countHillValley(self, nums: List[int]) -> int:
        answer = 0
        for i in range(1, len(nums)-1):
            if nums[i] == nums[i+1]:
                nums[i] = nums[i-1]
            if nums[i-1] < nums[i] and nums[i] > nums[i+1]:
                answer += 1
            if nums[i-1] > nums[i] and nums[i] < nums[i+1]:
                answer += 1
        return answer

---

https://leetcode.com/problems/k-items-with-the-maximum-sum/

https://leetcode.com/problems/count-hills-and-valleys-in-an-array/