내 맘대로 알고리즘/LeetCode 2020 May
May LeetCoding Challenge[Day22] - Sort Characters By Frequency
Given a string, sort it in decreasing order based on the frequency of characters. Input: "tree" Output: "eert" Explanation: 'e' appears twice while 'r' and 't' both appear once. So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer. 1. 알고리즘을 해결하기 위해서 생각한 방법 - 우선, 정말 단순하게 생각했다. - 앞에서부터 counting을 하고, counting한 문자에 대한 max를 찾아서 하나씩 retunr하는 것이다. - t:1, r:1, e:2와 같이 map을..
May LeetCoding Challenge[Day21] - Count Square Submatrices with All Ones
Given a m * n matrix of ones and zeros, return how many square submatrices have all ones. Input: matrix = [ [0,1,1,1], [1,1,1,1], [0,1,1,1] ] Output: 15 Explanation: There are 10 squares of side 1. There are 4 squares of side 2. There is 1 square of side 3. Total number of squares = 10 + 4 + 1 = 15. 1. 알고리즘을 해결하기 위해서 생각한 방법 - 해당 문제는 0과 1로 이루어진 m * n 매트릭스가 주어질 때, 사각형이 몇 개인지 찾는 문제이다. - 길이가 1인 사각형부..
May LeetCoding Challenge[Day20] - Kth Smallest Element in a BST
Given a binary search tree, write a function kthSmallest to find the kth smallest element in it. Input: root = [3,1,4,null,2], k = 1 3 1 4 2 Output: 1 1. 알고리즘을 해결하기 위해서 생각한 방법 - BST가 주어질 때, k번째로 작은 숫자를 찾는 문제 - 잘 모르겠으니, 보고 풀어보자. https://www.youtube.com/watch?v=xBkzsYbLjAA 2. 알고리즘 작성 중, 어려운 점 & 깨달은 점 - 어느 정도, 재귀함수를 사용해서 풀으려고 했는데, 답을 찾고 어떻게 return 해야할 지, 카운트를 어떤 방식으로 누적해야할 지, 왼쪽과 오른쪽 노드로 이동할 때, 체크해..
May LeetCoding Challenge[Day19] - Online Stock Span
Write a class StockSpanner which collects daily price quotes for some stock, and returns the span of that stock's price for the current day. The span of the stock's price today is defined as the maximum number of consecutive days (starting from today and going backwards) for which the price of the stock was less than or equal to today's price. For example, if the price of a stock over the next 7..
May LeetCoding Challenge[Day18] - Permutation in String
Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string's permutations is the substring of the second string. Input: s1 = "ab" s2 = "eidbaooo" Output: True Explanation: s2 contains one permutation of s1 ("ba"). 1. 알고리즘을 해결하기 위해서 생각한 방법 - 해당 문제는 s1의 짧은 문자열과 s2의 긴 문자열이 있을 때, anagram이 성립되면 true, 그렇지 않으면 flase를 반환 값으로..
May LeetCoding Challenge[Day17] - Find All Anagrams in a String
Given a string s and a non-empty string p, find all the start indices of p's anagrams in s. Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100. The order of output does not matter. Input: s: "cbaebabacd" p: "abc" Output: [0, 6] Explanation: The substring with start index = 0 is "cba", which is an anagram of "abc". The substrin..
May LeetCoding Challenge[Day16] - Odd Even Linked List
Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes. You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity. The relative order inside both the even and odd groups should remain as it was in the input. The first node is cons..
May LeetCoding Challenge[Day15] - Maximum Sum Circular Subarray
Given a circular array C of integers represented by A, find the maximum possible sum of a non-empty subarray of C. Here, a circular array means the end of the array connects to the beginning of the array. (Formally, C[i] = A[i] when 0 = 0.) Also, a subarray may only include each element of the fixed buffer A at most once. (Formally, for a subarray C[i], C[i+1], ..., C[j], there does not exist i