Python의 LeetCode - 1일 차

https://leetcode.com/problems/two-sum/

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

https://leetcode.com/problems/plus-one/

https://leetcode.com/problems/move-zeroes/

1. 투썸
정수 nums의 배열과 정수 target이 주어지면 두 숫자의 인덱스를 반환하여 합계가 target이 되도록 합니다.

각 입력에 정확히 하나의 솔루션이 있다고 가정할 수 있으며 동일한 요소를 두 번 사용할 수 없습니다.

어떤 순서로든 답변을 반환할 수 있습니다.

예 1:

입력: 숫자 = [2,7,11,15], 대상 = 9
출력: [0,1]
설명: nums[0] + nums[1] == 9이므로 [0, 1]을 반환합니다.
예 2:

입력: 숫자 = [3,2,4], 대상 = 6
출력: [1,2]
예 3:

입력: 숫자 = [3,3], 대상 = 6
출력: [0,1]

제약:

2 <= 숫자.길이 <= 104
-109 <= 숫자[i] <= 109
-109 <= 대상 <= 109
하나의 유효한 답변만 존재합니다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        #BruteForce

        for i in range(len(nums)):
            for j in range(i+1,len(nums)):
                if nums[i]+nums[j]==target:
                    return [i,j]
        return [-1,-1]      

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        #optimal---->TC O(N)----->SC=O(N)
        pair_check={}
        count=0
        for i in range(len(nums)):
            b=target-nums[i]
            if b  in pair_check:
                return[pair_check[b],i]
            else:
                pair_check[nums[i]]=i
        return []        

2. 주식을 사고 파는 최적의 시간

price[i]가 i번째 날의 주어진 주식 가격인 배열 price가 주어집니다.

특정 주식을 매수하기 위해 하루를 선택하고 해당 주식을 매도하기 위해 미래의 다른 날을 선택하여 이익을 극대화하려고 합니다.

이 트랜잭션에서 얻을 수 있는 최대 이익을 반환합니다. 이익을 얻을 수 없으면 0을 반환합니다.

예 1:

입력: 가격 = [7,1,5,3,6,4]
출력: 5
설명: 2일에 매수(가격 = 1)하고 5일에 매도(가격 = 6), 이익 = 6-1 = 5.
판매하기 전에 구매해야 하므로 2일 구매 및 1일 판매는 허용되지 않습니다.
예 2:

입력: 가격 = [7,6,4,3,1]
출력: 0
설명: 이 경우 트랜잭션이 수행되지 않으며 최대 이익 = 0입니다.

제약:

1 <= 가격.길이 <= 105
0 <= 가격[i] <= 104

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        #TC--->O(N)  SC--->O(1)
        buy=prices[0]
        profit=0
        for i in range(1,len(prices)):
            diff=prices[i]-buy
            buy=min(buy,prices[i])
            profit=max(profit,diff)
        return profit  

3. 플러스원

정수 배열 숫자로 표시되는 큰 정수가 주어집니다. 여기서 각 숫자[i]는 정수의 i번째 숫자입니다. 숫자는 왼쪽에서 오른쪽 순서로 가장 중요한 것부터 가장 중요하지 않은 것까지 정렬됩니다. 큰 정수에는 선행 0이 포함되지 않습니다.

큰 정수를 1씩 증가시키고 결과 숫자 배열을 반환합니다.

예 1:

입력: 숫자 = [1,2,3]
출력: [1,2,4]
설명: 배열은 정수 123을 나타냅니다.
1씩 증가하면 123 + 1 = 124가 됩니다.
따라서 결과는 [1,2,4]여야 합니다.
예 2:

입력: 숫자 = [4,3,2,1]
출력: [4,3,2,2]
설명: 배열은 정수 4321을 나타냅니다.
1씩 증가하면 4321 + 1 = 4322가 됩니다.
따라서 결과는 [4,3,2,2]여야 합니다.
예 3:

입력: 숫자 = [9]
출력: [1,0]
설명: 배열은 정수 9를 나타냅니다.
1씩 증가하면 9 + 1 = 10이 됩니다.
따라서 결과는 [1,0]이어야 합니다.

제약:

1 <= 숫자.길이 <= 100
0 <= 숫자[i] <= 9
숫자는 선행 0을 포함하지 않습니다.

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        #TC--->O(N)  SC---->O(1)
        dig_len=len(digits)
        for i in reversed(range(dig_len)):
            digits[i]+=1
            if digits[i]<10:
                return digits
            else:
                digits[i]=0
        digits.insert(0,1)
        return digits

4. 0 이동

정수 배열 nums가 주어지면 0이 아닌 요소의 상대적인 순서를 유지하면서 모든 0을 끝으로 이동합니다.

배열의 복사본을 만들지 않고 이 작업을 제자리에서 수행해야 합니다.

예 1:

입력: 숫자 = [0,1,0,3,12]
출력: [1,3,12,0,0]
예 2:

입력: 숫자 = [0]
출력: [0]

제약:

1 <= 숫자.길이 <= 104
-231 <= 숫자[i] <= 231 - 1

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        #TC=O(N) SC=O(1)
        """
        Do not return anything, modify nums in-place instead.
        """
        prev_index=0
        for i in range(len(nums)):
            if nums[i]!=0:
                nums[i],nums[prev_index]=nums[prev_index],nums[i]
                prev_index+=1

Saipavan Seelamsetty의 개선 사항에 대한 피드백에 감사드립니다.