목록알고리즘 (178)

매일 조금씩

Leet code (Hard): 124. Binary Tree Maximum Path Sum - Java

어떻게 풀어야할지 모르겠었던 문제. 리프 노드부터 돌며,현재 노드를 최고 높은 루트 노드로 하여 순회한다고 할 때의 최댓값을 구하면 된다. 아래 두가지를 생각했다. 1) 재귀식과 리턴값 정하기그럼 재귀식이 필요한데.재귀식이 return 하는 값은 현재 노드까지의 최대값을 리턴하면 된다.그 값은 ~자식 노드가 left, right 두개이니,left 자식 노드까지의 값 (leftSum)right 자식 노드까지의 값 (rightSum)두 값 중 최대값에 현재 노드(root)의 value를 더한값을 리턴하면 된다. 2) 전체 최댓값 갱신 어떻게 할지 정하기그리고 매 root 마다,위 값 말고 현재 노드(root)가 최상위 노드가 될 경우에 대한 값(left 자식노드 합 + right 자식 노드 합 + 자기 자신..
알고리즘/Tree 2024. 10. 29. 01:03
Leet code (Easy): 226. Invert Binary Tree - Java

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public TreeNode invertTree(TreeNod..
알고리즘/Tree 2024. 10. 28. 20:39
Leet code (Easy): 100. Same Tree - Java

같은 트리인지를 판별하는 아주 기본적인 문제이다. /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public..
알고리즘/Tree 2024. 10. 28. 17:58
String 탐색 문제 분석

문자열이 하나 주어지고 조건에 만족하는 결과를 도출하도록 하는 문제의 유형은 매우 다양하다.대충 정리해보자면 다음과 같다.슬라이딩 윈도우 최대/최소길이start, end 투 포인터 활용anagram 판별s.toCharArray() 로 char[] 변환 후Arrays.sort() 사용palindrome 판별, 최대/최소길이start, end 투 포인터 활용중심확장법Character의 스태틱 함수 사용 (숫자 or 문자 인지 확인)Character.isLetter(), Character.isLetterOrDigit()여기서 가장 어려웠던 유형은 1번의 슬라이딩 윈도우였다.문제의 난이도가 어려워질수 있는 가능성이 더 많아 보였다.HashMap과 투 포인터, 적절한 변수들을 선언하여 풀어내야한다. 다음은 슬라이..
알고리즘/** 개념 ** 2024. 10. 28. 16:20
Leet code (Medium): 647. Palindromic Substrings (중심확장법) - Java

이 또한 중간 확장법을 사용해서문자열의 문자하나를 기준점으로 찍으면서각각에 홀수, 짝수로 나눠서 팰린드롬 갯수를 카운트 했다. class Solution { private int count = 0; // 팰린드롬 수 public int countSubstrings(String s){ if(s.length() = 0 && end
알고리즘/String 2024. 10. 28. 15:03
Leet code (Medium): 5. Longest Palindromic Substring (중심확장법)- Java

이것 또한 투포인터를 사용해야하는 문제이다.다만 최대 길이의 palindrome 문자열을 찾아야한다. 난두가지 방법을 생각했다.첫번째 문자부터 마지막 문자를 가리키는 포인터를 앞당기며 찾음. (가장자리 -> 가운데 방향으로 palindrome 탐색)문자 하나씩을 기준으로 삼고 양쪽으로 확장하며 찾음. (가운데 -> 가장자리 방향으로 palindrome 탐색)1번은 시간복잡도 O(n^3), 2번은 시간복잡도 O(n^2)이다.따라서, 2번의 중심확장방식이 더 효율적이다. 팰린드롬(palindrome) 문제는 '좌우대칭'이라는 팰린드롬의 특성에 따라, 시간복잡도를 줄이기 위해 최대길이 문제는 가운데 기준점을 찍으며 찾아가는 2번 방식이 효율적이다. 1번 방식)class Solution { public S..
알고리즘/String 2024. 10. 28. 14:24
이전 Prev 1 2 3 4 5 ··· 30 Next 다음