[leetcode] 1, 2, 3, 7

1. Two Sum

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

My Answer 1: Accepted (Runtime: 652 ms - 37.24% / Memory Usage: 14.9 MB - 80.43%)

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

target - nums[i] 이 있으면 index 찾아서 return

Solution 1: Accepted (Runtime: 60 ms - 23.57% / Memory Usage: 15.6 MB - 9.55%)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dic = {}
        
        for i in range(len(nums)):
            if nums[i] in dic:
                return [dic[nums[i]], i]
            else:
                dic[target - nums[i]] = i 

저번에 풀었던 방식...ㅎ

dic 에 target - nums[i] 이름으로 대응하는 값의 인덱스를 넣어줌

---

7. Reverse Integer

https://leetcode.com/problems/reverse-integer/

My Answer 1: Accepted (Runtime: 32 ms - 71.26% / Memory Usage: 14.1 MB - 90.67%)

class Solution:
    def reverse(self, x: int) -> int:
        string = list(str(x))
        negative = 0
        if string[0] == "-":
            negative = 1
            string = string[1:]
        
        string.reverse()
        ans = int(''.join(string))
        if negative:
            ans *= -1
        if ans < -2 ** 31 or ans > 2 ** 31 - 1:
            return 0
        return ans

string 으로 구성된 list 로 바꿔서 음수 처리해주고 reverse()
다시 숫자로 바꾼 후 음수면 * 1 & 범위 체크

---

2. Add Two Numbers

https://leetcode.com/problems/add-two-numbers/

My Answer 1: Accepted (Runtime: 72 ms - 57.08% / Memory Usage: 14.2 MB - 72.59%)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        carry = 0
        two = 0
        a = 1
        while l1 and l2:
            if l1.val + l2.val + carry > 9:
                two += ((l1.val + l2.val + carry) % 10) * a
                carry = 1
            else:
                two += (l1.val + l2.val + carry) * a
                carry = 0
            a *= 10
            l1 = l1.next
            l2 = l2.next
        
        l = l1 if l1 else l2
        while l:
            if l.val + carry > 9:
                two += ((l.val + carry) % 10) * a
                carry = 1
            else:
                two += (l.val + carry) * a
                carry = 0
            a *= 10
            l = l.next
        if carry:
            two += 1 * a
        
        two = reversed(list(str(two)))
        two = ''.join(two)
        
        ans = ListNode(0)
        h = ans
        i = 0
        while i < len(two):
            ans.next = ListNode(int(two[i]) % 10)
            i += 1
            ans = ans.next
            
        return h.next

l1, l2 둘 다 존재할 경우의 더하기 처리
둘 중 남은 하나 값 처리
string 으로 바꿔주고 하나씩 ListNode 로 만들어주기

---

3. Longest Substring Without Repeating Characters

https://leetcode.com/problems/longest-substring-without-repeating-characters/

My Answer 1: Accepted (Runtime: 404 ms - 17.05% / Memory Usage: 14.2 MB - 93.12%)

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        ans = 0
        tmp = ""
        for i in range(len(s)):
            tmp = s[i]
            for j in range(i+1, len(s)):
                if s[j] in tmp:
                    ans = max(ans, len(tmp))
                    break
                tmp += s[j]
            ans = max(ans, len(tmp))
        return ans

tmp 에 보던 문자들을 쭉 넣어주고 겹치면 ans 에 최댓값 update & tmp 초기화

Solution 1: Accepted (Runtime: 60 ms - 78.76% / Memory Usage: 14.2 MB - 94.27%)

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        dic = {}
            
        cnt = 0
        start = -1
        
        for i in range(len(s)):
            if s[i] in dic and start < dic[s[i]]:
                start = dic[s[i]]
            dic[s[i]] = i
            cnt = max(cnt, i-start)
        
        return cnt

저번에 풀었던 방식...^^

dic 에 가장 최신 인덱스 값을 넣어줌

중복이 없으면 cnt = 처음부터 지금 인덱스까지의 길이
중복을 만나면 start 는 이전 중복값의 위치 인덱스로 설정해서
중복과 중복 사이의 길이를 cnt 에 update