Leetcode 문제풀이

태그

연구

최종 편집

Jan 3, 2022 7:44 AM

발행일

October 27, 2021

재미 없어서 + ROI가 낮은 듯하여 중단.

2021.10.27

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

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
  if (l1 === null && l2 === null) {
    return null;
  }
  
  let listNode1 = l1;
  let listNode2 = l2;
  
  const resultList = new ListNode();
  let currentNode = resultList;
  let passOver = 0;
  
  while(true) {
    let sum = passOver + (listNode1?.val ?? 0) + (listNode2?.val ?? 0);
    if (sum >= 10) {
      passOver = 1;
      sum -= 10;
    } else {
      passOver = 0;
    }
    
    currentNode.val = sum;
    
    if (!(listNode1?.next) && !(listNode2?.next) && passOver === 0) {
      return resultList;
    }
    
    currentNode.next = new ListNode();
    currentNode = currentNode.next;
    listNode1 = listNode1?.next ?? null;
    listNode2 = listNode2?.next ?? null;
  }
}

처음에 테스트 케이스 돌릴 때 마지막 자릿수 처리가 잘 안 됐다.
로직이 아주 깔끔하지는 않지만 시간복잡도나 가독성 면에서 큰 문제라고 생각하지는 않음.

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

Given a string s, find the length of the longest substring without repeating characters.

function lengthOfLongestSubstring(s: string): number {
  let result = '';
  let compare = '';
  
  for (let i = 0; i < s.length; i++) {
    const charIndex = compare.indexOf(s[i]);
    if (charIndex !== -1) {
      if (compare.length > result.length) {
        result = compare;
      }
      compare = compare.slice(charIndex + 1)
    }   
    compare += s[i];
  }
  
  return Math.max(result.length, compare.length);
};

결과

Runtime: 80 ms, faster than 100.00% of TypeScript online submissions for Longest Substring Without Repeating Characters.
Memory Usage: 45.8 MB, less than 29.79% of TypeScript online submissions for Longest Substring Without Repeating Characters.

O(n^2) 가 아닌 방법으로 푸는 걸 고민하고 코딩을 시작해서인지 만족스럽게 나왔다. 메모리는 많이 썼네.

2021.10.26

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

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

function twoSum(nums: number[], target: number): number[] {
  let firstIndex, secondIndex;
  for (let i = 0; i < nums.length; i++) {
    firstIndex = i;
    for (let j = firstIndex + 1; j < nums.length; j++) {
      secondIndex = j;
      
      if ((nums[firstIndex] + nums[secondIndex]) === target) {
        return [firstIndex, secondIndex];
      }
    }
  }
};

처음에 같은 엘리먼트를 두 번 쓸 수 없다는 말을 제대로 못보고, j를 1부터 시작하게 해서 실패.
O(n^2)인데 더 나은 방법이 당장 생각나지 않았음.

‣

Discussion에 O(n)으로 하는 방법이 있었음. 괜찮아 보였다. 나도 difference를 생각하긴 했는데 이 방법은 생각하지 못했다.

function twoSum(nums: number[], target: number): number[] {
    let visited: {[key: number]: number} = {};
    
    for (let i = 0; i < nums.length; i++) {
        let difference = target - nums[i];
        if (difference in visited) return [i, visited[difference]];
        visited[nums[i]] = i;
    }
};