본문 바로가기

🏃 algorithm/leetcode93

LeetCode 118 - Pascal's Triangle (Easy) 문제 LeetCode - 118번 풀이 과정 파스칼 삼각형을 구현하는 문제입니다. 1번째 행과 2번째 행은 각각 [1] 과 [1, 1] 로 따로 처리해주고 나머지 경우는 마지막 행의 인접한 요소들을 더해서 새로운 행을 만들면 됩니다. 코드 /** * @param {number} numRows * @return {number[][]} */ var generate = function (numRows) { const answer = []; let walker = 1; while (walker 2021. 3. 3.

LeetCode 19 - Remove Nth Node From End of List (Medium) 문제 LeetCode - 19번 풀이 과정 링크드 리스트에서 뒤에서 n 번째 노드를 삭제하는 연산을 구현하는 문제입니다. 뒤에서 n 번째 노드를 찾기 위해서 우선 리스트의 전체 크기를 알아낸 다음, 이동해야 하는 offset 을 계산합니다. 이후 두 개의 포인터를 활용해서 next 속성을 재지정하면 됩니다. 코드 /** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @param {number} n * @r.. 2021. 3. 3.

LeetCode 79 - Word Search (Medium) 문제 LeetCode - 79번 풀이 과정 이차원 배열에서 인접한 문자들을 이용해서 특정 단어를 만들 수 있는지 판단하는 문제입니다. 백트래킹 을 활용해서 문자가 일치하지 않으면 다음 위치를 찾도록 탐색을 하면 됩니다. 또한 원하는 단어를 찾으면 다른 문자들은 탐색하지 않고 바로 true 를 반환하도록 하였습니다. 코드 /** * @param {character[][]} board * @param {string} word * @return {boolean} */ var exist = function (board, word) { const dx = [0, 0, 1, -1]; const dy = [1, -1, 0, 0]; function dfs(x, y, depth, visit) { if (board[x][.. 2021. 3. 3.

LeetCode 771 - Jewels and Stones (Easy) 문제 LeetCode - 771번 풀이 과정 특정 문자열에 포함된 문자의 개수를 찾는 문제입니다. 문자 탐색의 기준이 되는 문자열 J 를 해싱해서 저장한 다은 S 를 하나씩 순회하며 해당 문자가 J 에 존재하는지 찾습니다. 이렇게 하면 O(N) 에 탐색을 수행할 수 있습니다. 코드 /** * @param {string} J * @param {string} S * @return {number} */ var numJewelsInStones = function (J, S) { const hashTable = {}; [...J].forEach((c) => (hashTable[c] = 1)); const answer = [...S].filter((c) => hashTable[c]); return answer.le.. 2021. 3. 3.

LeetCode 5 - Longest Palindromic Substring (Medium) 문제 LeetCode - 5번 풀이 과정 가장 긴 팰린드롬을 구하는 문제입니다. 만약 dp(i, j) = i에서 j까지의 가장 긴 팰린드롬의 길이 라고 정의한다면 다음과 같은 점화식을 세울 수 있습니다. dp(i, j) = if dp[i] == dp[j] & dp(i+1, j-1) is palindrome, dp(i+1, j-1) + 2 else 0 기저 사례로 각 문자는 길이가 1인 팰린드롬이라는 것에 유의하여 구현하였습니다. 코드 /** * @param {string} s * @return {string} */ var longestPalindrome = function (s) { let answer = ""; const dp = new Array(s.length) .fill(null) .map((x).. 2021. 3. 3.

LeetCode 206 - Reverse Linked List (Easy) 문제 LeetCode - 206번 풀이 과정 연결 리스트 의 포인터를 뒤집는 연산을 구현하는 문제입니다. 가장 직관적인 방법으로 재귀 호출 을 이용해서 구현하였습니다. 각각의 재귀 호출은 다음 노드부터 끝 노드까지의 뒤집힌 결과를 기대하며 해당 결과를 토대로 현재 노드의 포인터 값을 변경합니다. 코드 /** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @return {ListNode} */ var rev.. 2021. 3. 3.

이전 1 ··· 5 6 7 8 9 10 11 ··· 16 다음

티스토리툴바