바위타는 두루미

376. Wiggle Subsequence A sequence of numbers is called a wiggle sequenceif the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence. For example, [1,7,4,9,2,5] is a wiggle sequence because the differences (6,-3,5,-7,3..

134. Gas Station There are N gas stations along a circular route, where the amount of gas at station i is gas[i]. You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations. Return the starting gas station's index if you can travel around the circuit once in the cloc..

43. Multiply Strings Given two non-negative integers num1 and num2represented as strings, return the product of num1and num2, also represented as a string. Example 1: Input: num1 = "2", num2 = "3" Output: "6" Example 2: Input: num1 = "123", num2 = "456" Output: "56088" Note: The length of both num1 and num2 is < 110. Both num1 and num2 contain only digits 0-9. Both num1 and num2 do not contain a..

1140. Stone Game II Alex and Lee continue their games with piles of stones. There are a number of piles arranged in a row, and each pile has a positive integer number of stones piles[i]. The objective of the game is to end with the most stones. Alex and Lee take turns, with Alex starting first. Initially, M = 1. On each player's turn, that player can take all the stones in the first X remaining ..

1143. Longest Common Subsequence Given two strings text1 and text2, return the length of their longest common subsequence. A subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, "ace" is a subsequence of "abcde" while "aec" is not). A common subsequence of two str..

31. Next Permutation Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order). The replacement must be in-place and use only constant extra memory. Here are some examples. Inputs are in the left-hand column and its corr..

29. Divide Two Integers Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator. Return the quotient after dividing dividend by divisor. The integer division should truncate toward zero. Example 1: Input: dividend = 10, divisor = 3 Output: 3 Example 2: Input: dividend = 7, divisor = -3 Output: -2 class Solution(object): def divide(self..

120. Triangle Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below. For example, given the following triangle [ [2], [3,4], [6,5,7], [4,1,8,3] ] The minimum path sum from top to bottom is 11(i.e., 2 + 3 + 5 + 1 = 11). Note: Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows..

문제 다량의 널빤지를 이어 붙여서 다이빙 보드를 만들려고 한다. 널빤지는 길이가 긴 것과 짧은 것 두가지 종류가 있는데 정확히 K개의 널빤지를 사용하여 다이빙 보드를 만들어야 한다. 가능한 다이빙 보드의 길이를 모두 구하는 메서드를 작성하라 해결법 1. 재귀적 해법 재귀적으로 K번의 널빤지를 선택하면 다이빙 보드를 완성할 수 있고 완성된 보드를 리스트에 추가하면 된다. + 메모이제이션 def getAllLengths(k, long, short): memo = set() lengths = set() def allLengths(k, lengths , total, long, short, memo): if k == 0: lengths.add(total) key = (total, k) if key in memo ..

문제 사람의 태어난 연도와 사망한 연도가 리스트로 주어졌을때, 가장 많은 사람이 동시에 살았던 연도를 찾는 메서드를 작성하라. 모든사람이 1900년도에서 2000년도 사이에서 태어났다고 가정해도 좋다. 또한 해당 연도의 일부만 살았더라도 해당 년도에 살아있었다고 봐야한다. 예르르들어 어떤 사람이 1908년에 태어나서 1909년에 사망했다면 이 사람은 1908년과 1909년 모두에 삶을 살았던 사람이된다. 해결법 1. 무식한 방법 각 년도를 순회하면서 각 년도에 살아있는 사람들을 카운트한다. R이 가능한 연도의 범위이고 P가 사람의 수라고 했을때 시간 복잡도는 O(RP)가 된다. 2. 무식하지만 조금 나은 방법 해마다 태어난 인구수를 기록하는 배열을 만들고, 사람을 순회하면서 배열에 기록한다. (배열을 잡..