不想写第二遍的刷题笔记

世界级打野都是rush大龙的

Persistent Bugger

CodeWars 6kyu

Write a function, persistence, that takes in a positive parameter num and returns its multiplicative persistence, which is the number of times you must multiply the digits in num until you reach a single digit.

For example:

// because 3*9 = 27, 2*7 = 14, 1*4=4 and 4 has only one digit:
persistence(39) == 3

// because 9*9*9 = 729, 7*2*9 = 126, 1*2*6 = 12, and finally 1*2 = 2
persistence(999) == 4

// because 4 is already a one-digit number:
persistence(4) == 0

Solution

object Multiplication {

def persistence(n: Int): Int = {
def loop(a: Int, times: Int): Int =
if (a < 10) times
else loop(a.toString.map(_.asDigit).product, times+1)

loop(n, 0)
}
}

Count Odd Numbers below n

CodeWars 8kyu

Given a number n, return the number of positive odd numbers below n, EASY!

oddCount(7) //=> 3, i.e [1, 3, 5]
oddCount(15) //=> 7, i.e [1, 3, 5, 7, 9, 11, 13]

Solution

object OddCount {

def oddCount(n: Long): Long = n / 2
}

My head is at the wrong end!

CodeWars 8kyu

You’re at the zoo… all the meerkats look weird. Something has gone terribly wrong - someone has gone and switched their heads and tails around!

Save the animals by switching them back. You will be given an array which will have three values (tail, body, head). It is your job to re-arrange the array so that the animal is the right way round (head, body, tail).

Same goes for all the other arrays/lists that you will get in the tests: you have to change the element positions with the same exact logics - simples!

Solution

object Lists {

def fixTheMeerkat(arr: List[String]): List[String] = {
arr.reverse
}
}

Century From Year

CodeWars 8kyu

Introduction

The first century spans from the year 1 up to and including the year 100, The second - from the year 101 up to and including the year 200, etc.

Task :

Given a year, return the century it is in.

Input , Output Examples ::

centuryFromYear(1705)  returns (18)
centuryFromYear(1900) returns (19)
centuryFromYear(1601) returns (17)
centuryFromYear(2000) returns (20)

Solution

object CenturyYear {
def centuryFromYear(year: Int): Int = (year - 1) / 100 + 1
}

Trapping Rain Water

LeetCode 42

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Example

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Solution

class Solution(object):
def trap(self, height):
"""
:type height: List[int]
:rtype: int
"""
if len(height)<3:
return 0
res = 0
left = 0
right = len(height)-1
left_max = height[left]
right_max = height[right]
while left<=right:
if height[left]<height[right]:
if left_max>height[left]:
res += left_max - height[left]
else:
left_max = height[left]
left+=1
else:
if right_max>height[right]:
res += right_max - height[right]
else:
right_max = height[right]
right-=1
return res

Binary Tree Level Order Traversal

LeetCode 102

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7],

  3
/ \
9 20
/ \
15 7

return its level order traversal as:

[
[3],
[9,20],
[15,7]
]

Solution

class Solution(object):
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
queue = [[], []]
if root:
queue[0].append(root)
else:
return []
res = []
i = 0
while len(queue[0]) + len(queue[1])!=0:
level = []
while len(queue[i])!=0:
node = queue[i].pop(0)
level.append(node.val)
if node.left:
queue[1-i].append(node.left)
if node.right:
queue[1-i].append(node.right)
res.append(level)
i = 1-i
return res

Excel Sheet Column Number

LeetCode 171

Given a column title as appear in an Excel sheet, return its corresponding column number.

For example:

A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28
...

Example 1

Input: "A"
Output: 1

Example 2

Input: "AB"
Output: 28

Example 3

Input: "ZY"
Output: 701

Solution

class Solution(object):
def titleToNumber(self, s):
"""
:type s: str
:rtype: int
"""
times = 1
number = 0
for i in range(len(s)-1, -1, -1):
number += (ord(s[i])-ord('A') + 1)*times
times *= 26
return number