DATA STRUCTURE1 DAY1

1. Contains-Duplicate

class Solution(object):
    def containsDuplicate(self, nums):
        nums.sort()
        for i in range(len(nums)):
            if i>0 and nums[i-1]==nums[i]:
                return True
        return False

1.nums.sort()를 통해 오름차순 정렬한다.
2.배열을 순회하면서 배열과 그 전의 배열이 같으면 TRUE, 다 순회했으면 FALSE 리턴

2.Maximum-Subarray

문제가 수학적 영역을 조금 생각해야 했던 것 같다
문제의 초점을 나는 처음부터 배열을 더하면서 만약 음수가 되면은 다시 0이상 양수인 요소부터 더하기를 시작하면 된다는 생각을 했다

now는 배열을 순회하면서 현재의 배열 요소를 나타내는 것이고
sum은 now의 값과 이전의 sum값에 now를 더한 값을 비교해서 더 큰 값을 획득한다
result는 sum과 비교하여 sum이 result보다 크면은 result의 값을 sum으로 둔다 (변수명을 max로 두는 것이 좋았겠네)

예외처리

예외를 생각하는 것이 너무나도 어려운 것 같다
아직도 테스트 케이스 몇 개만 보고 알고리즘을 짜는 습관을 가지는데 좀 크게 케이스를 생각하게 바꿔야 겠다.

예외1. 배열의 요소가 하나 일때=> array[0]을 리턴해주면 된다.
예외2. 배열들이 모두 음수 일때 => 배열의 요소중 제일 큰 값을 리턴

class Solution(object):
    def maxSubArray(self, nums):
        #배열의 길이가 1개
        if len(nums)==1:
            return nums[0]
        #배열이 모두 음수일 때
        for i in range(len(nums)) :
            if nums[i] >=0:
                break
            else:
                if i==len(nums)-1:
                    return max(nums)
        sum=0
        result=0
        #배열에 0 이상인 원소가 있을 때
        for i in range(len(nums)):
            now=nums[i]
            sum=max(now,sum+nums[i])
            if (sum<0):
                sum=0
            result=max(sum,result)
        return result

좋은 웹페이지 즐겨찾기