不想写第二遍的刷题笔记

世界级打野都是rush大龙的

Pascals Triangle

LeetCode 118

Given a non-negative integer numRows, generate the first numRows of Pascal’s triangle.

In Pascal’s triangle, each number is the sum of the two numbers directly above it.

Example:

Input: 5
Output:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]

Solution

class Solution(object):
def generate(self, numRows):
"""
:type numRows: int
:rtype: List[List[int]]
"""
if numRows == 0:
return []
row_p = [1]
triangle = [[1]]
for i in range(1, numRows):
row = [1]
for j in range(1, i):
row.append(row_p[j-1] + row_p[j])
row.append(1)
triangle.append(row)
row_p = row
return triangle

Balanced Binary Tree

LeetCode 110

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example 1:

Given the following tree [3,9,20,null,null,15,7]:

  3
/ \
9 20
/ \
15 7

Return true.

Example 2:

Given the following tree [1,2,2,3,3,null,null,4,4]:

      1
/ \
2 2
/ \
3 3
/ \
4 4

Return false.

Solution

class Solution(object):
def isBalanced(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if root == None:
return True
else:
return False if abs(self.getHeight(root.left)-self.getHeight(root.right))>1 else (self.isBalanced(root.left) and self.isBalanced(root.right))

def getHeight(self, root):
return 0 if not root else max(self.getHeight(root.left)+1, self.getHeight(root.right)+1)

Pairs of Songs With Total Durations Divisible by 60

LeetCode 1013

In a list of songs, the i-th song has a duration of time[i] seconds.

Return the number of pairs of songs for which their total duration in seconds is divisible by 60. Formally, we want the number of indices i < j with (time[i] + time[j]) % 60 == 0.

Example 1:

Input: [30,20,150,100,40]
Output: 3
Explanation: Three pairs have a total duration divisible by 60:
(time[0] = 30, time[2] = 150): total duration 180
(time[1] = 20, time[3] = 100): total duration 120
(time[1] = 20, time[4] = 40): total duration 60

Example 2:

Input: [60,60,60]
Output: 3
Explanation: All three pairs have a total duration of 120, which is divisible by 60.

Note:

  • 1 <= time.length <= 60000
  • 1 <= time[i] <= 500

Solution

class Solution(object):
def numPairsDivisibleBy60(self, time):
"""
:type time: List[int]
:rtype: int
"""
s = 0
time_s = {}
for i in time:
if i%60 in time_s:
time_s[i%60] += 1
else:
time_s[i%60] = 1
for i in time_s:
if i==0:
s += time_s[i]*(time_s[i]-1)
elif 60-i in time_s:
if i==30:
s += time_s[i]*(time_s[i]-1)
else:
s += time_s[i]*time_s[60-i]
return s/2

Complement of Base 10 Integer

LeetCode 1012

Every non-negative integer N has a binary representation. For example, 5 can be represented as "101" in binary, 11 as "1011" in binary, and so on. Note that except for N = 0, there are no leading zeroes in any binary representation.

The complement of a binary representation is the number in binary you get when changing every 1 to a 0 and 0 to a 1. For example, the complement of "101" in binary is "010" in binary.

For a given number N in base-10, return the complement of it’s binary representation as a base-10 integer.

Example 1:

Input: 5
Output: 2
Explanation: 5 is "101" in binary, with complement "010" in binary, which is 2 in base-10.

Example 2:

Input: 7
Output: 0
Explanation: 7 is "111" in binary, with complement "000" in binary, which is 0 in base-10.

Example 3:

Input: 10
Output: 5
Explanation: 10 is "1010" in binary, with complement "0101" in binary, which is 5 in base-10.

Note:

  • 0 <= N < 10^9

Solution

class Solution(object):
def bitwiseComplement(self, N):
"""
:type N: int
:rtype: int
"""
return 2**(len(bin(N))-2)-1-N

Your order, please

CoderWars 6kyu

Your task is to sort a given string. Each word in the string will contain a single number. This number is the position the word should have in the result.

Note: Numbers can be from 1 to 9. So 1 will be the first word (not 0).

If the input string is empty, return an empty string. The words in the input String will only contain valid consecutive numbers.

object Text {
def order(str: String): String = str.split(" ").sortBy(_.find(_.isDigit)).mkString(" ")
}

Sum of the first nth term of Series

CodeWars 7kyu

Task:

Your task is to write a function which returns the sum of following series upto nth term(parameter).

Series: 1 + 1/4 + 1/7 + 1/10 + 1/13 + 1/16 +...

Rules:

You need to round the answer to 2 decimal places and return it as String.

If the given value is 0 then it should return 0.00

You will only be given Natural Numbers as arguments.

Examples:

SeriesSum(1) => 1 = "1.00"
SeriesSum(2) => 1 + 1/4 = "1.25"
SeriesSum(5) => 1 + 1/4 + 1/7 + 1/10 + 1/13 = "1.57"

Solution

object Sol {

def seriesSum(n: Int): String = {
def loop(a: Int): Double =
if (a==n) 0
else 1.0 / (1+3*a) + loop(a+1)

loop(0).formatted("%.2f")
}
}

You only need one - Beginner

CodeWars 8kyu

You will be given an array a and a value x. All you need to do is check whether the provided array contains the value.

Array can contain numbers or strings. X can be either.

Return true if the array contains the value, false if not.

solution

object Solution {
def check(seq:List[Any], elem: Any) = seq contains elem
}