Leetcode笔记

发表于

这篇博文用来记录我做过的leetcode的题目和当时的一些思路，太简单的题就不列出来了，持续更新…

#17.Letter Combinations of a Phone Number [Medium]

Description

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.
Phone Number 

1
2
Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:

Although the above answer is in lexicographical order, your answer could be in any order you want.

Idea

用递归可以很快解决。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def __init__(self):
        self.ret = []
        self.digit2char = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
        
    def Helper(self, rest_digits, prefix):
        if len(rest_digits) == 0:
            self.ret.append(prefix)
        else:
            for x in self.digit2char[int(rest_digits[0])]:
                self.Helper(rest_digits[1:], prefix + x)
            
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if digits == "":
            return []
        else:
            self.Helper(digits, "")
            return self.ret

#136.Single Number [Easy]

Description

Given an array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Idea

这道题竟然是Easy，不敢相信，如果不知道“两个相同的数按位异或等于0”和“按位异或符合交换率”这两条性质，想破脑袋都想不出来，但是一旦知道，就几行代码搞定。

Solution

1
2
3
4
5
6
7
8
9
10
class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ret = 0
        for x in nums:
            ret ^= x
        return ret

#226.Invert Binary Tree [Easy]

Description

nvert a binary tree. 

1
2
3
4
5
     4
   /   \
  2     7
 / \   / \
1   3 6   9

to

1
2
3
4
5
     4
   /   \
  7     2
 / \   / \
9   6 3   1

Trivia:

This problem was inspired by this original tweet by Max Howell:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

Idea

反转二叉树其实很简单，就是递归，但是因为Homebrew作者在谷歌面试的遭遇而引人关注。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
import numpy as np
class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        x = np.array([1,2,3])
        if root != None:
            root.left, root.right = root.right, root.left
            self.invertTree(root.left)
            self.invertTree(root.right)
        return root

#258.Add Digits [Easy]

Description

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

For example:

Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

Follow up:

Could you do it without any loop/recursion in O(1) runtime?

Idea

这道题用递归很简单，但是偏偏不让你用递归，我想了半天没明白还有什么办法，一看别人的解答发现原来是有规律的。

1
2
1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20  
1	2	3	4	5	6	7	8	9	1	2	3	4	5	6	7	8	9	1	2

原来这个结果会在1-9循环，那我们对9取模就好了，不过要让9和9的倍数出的结果是9而且还要考虑0的情况。

Solution

1
2
3
4
5
6
7
8
9
10
class Solution(object):
    def addDigits(self, num):
        """
        :type num: int
        :rtype: int
        """
        if num == 0:
            return 0
        else:
            return (num - 1) % 9 + 1

#260.Single Number III [Medium]

Description

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:

The order of the result is not important. So in the above example, [5, 3] is also correct.
Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

Idea

这道题相比于#136要复杂一些，找两个single number的话用异或的方法只能求出这两个数有哪些位不同，我们可以通过这一点将原数组的分成两组，且这两个数分在不同组，这样的话我们再通过异或的方法分别找出这两个数。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        diff = 0
        for x in nums:
            diff ^= x
        diff &= -diff
        ret = [0] * 2
        for x in nums:
            if x & diff:
                ret[0] ^= x
            else:
                ret[1] ^= x
        return ret

#283.Move Zeroes [Easy]

Description

Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:

  1. You must do this in-place without making a copy of the array.
  2. Minimize the total number of operations.

Idea

两个指针，两个指针都先放在开头，然后第二个指针向后找非0的数，放到第一个指针处，第一个指针向后走，然后再把0填上。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        pos = 0
        for i in range(len(nums)):
            if nums[i] != 0:
                nums[pos] = nums[i]
                pos += 1
        while pos < len(nums):
            nums[pos] = 0
            pos += 1

#338.Counting Bits [Medium]

Description

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.

Example:

For num = 5 you should return [0,1,1,2,1,2].

Follow up:

  • It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
  • Space complexity should be O(n).

  • Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.

    Idea

    这道题找规律找了好久，找到了规律后编程又编了好久。只要是$2^n$的数，1的个数都是1个，以它们为分界线，中间数字的1的个数会出现“复现”规律。先把32以内的数的1的个数列出来观察一下就明白了。

    1
    2
    3
    4
    5
    6
    7
    分界线2^n	1的个数
    0			0
    1			1
    2			1	2
    4			1	2	2	3
    8			1	2	2	3	2	3	3	4
    16			1	2	2	3	2	3	3	4	2	3	3	4	3	4	4	5

看明白规律了么？就是每到一个新的分段，前一半是上一分段的复现，后一半是上一分段复现再加1。知道了规律就按照这个规律编程就行了，但是也不简单，挺恶心的。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import math
class Solution(object):
    @staticmethod
    def generate(log_num, dest):
        dest[1] = 1
        dest[2**log_num] =1
        for i in range(1,log_num):
            for j in range(2**i, 2**i+2**(i-1)):
                dest[j] = dest[j-2**(i-1)]
                dest[j+2**(i-1)] = dest[j-2**(i-1)]+1
        return dest
    @staticmethod
    def fillRest(num, log_num, dest):
        if num < 2**log_num + 2**(log_num-1):
            for i in range(2**log_num+1, num+1):
                dest[i] = dest[i-2**(log_num-1)]
        else:
            for i in range(2**log_num+1, 2**log_num+2**(log_num-1)):
                dest[i] = dest[i-2**(log_num-1)]
            for i in range(2**log_num+2**(log_num-1), num+1):
                dest[i] = dest[i-2**(log_num-1)]+1
        return dest
    
    def countBits(self, num):
        """
        :type num: int
        :rtype: List[int]
        """
        if num == 0:
            return [0]
        log_num = int(math.log(num, 2))
        dest = [0] * (num+1)
        dest = Solution.generate(log_num, dest)
        dest = Solution.fillRest(num, log_num, dest)
        return dest

#371.Sum of Two Integers [Easy]

Description

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

Example:
Given a = 1 and b = 2, return 3.

Idea

这道题看起来很简单，但是我并不觉得很好编程，尤其是在Python上。思路就是用位操作去做，相当于把它看作二进制数，然后通过异或操作^可以得到各个位上加法的结果，与操作&可以判断是否进位，让异或的结果和与操作并且移位的结果不停的相加直到没有进位了停止。在Python上int型变量并没有固定位数，只有通过对0x100000000取模来构造一个32位的int型整数了，挺恶心的。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def getSum(self, a, b):
        """
        :type a: int
        :type b: int
        :rtype: int
        """
        tmp_a = self.add(a, b)
        return tmp_a if tmp_a <= 0x7FFFFFFF else tmp_a | (~0x100000000+1)
    
    def add(self, a, b):
        return a if b == 0 else self.add((a ^ b) % 0x100000000, ((a & b) << 1) % 0x100000000)

#406.Queue Reconstruction by Height [Medium]

Description

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.

Example: 

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

Idea

这道题看起来简单，我一开始通过最常规的解法一个个去判断排哪一个人符合题目要求，然后一个个去构造队伍，这样做解法超时了。然后看了大神的思路，真是强，完全没想到可以这么做。思路是先将这些人按照一定规则排序（感觉很多题目通过先排序就可以降低时间复杂度），规则是身高高的在前，如果身高一样就把人数少的放在前面。排好序之后，再逐个把人插入到这个队的第i个，i指的是后面那个人数，然后神奇的事情就发生了，队列就构造好了。Amazing！

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import sys
def cmp(x,y):
    if x[0] > y[0]:
        return -1
    if x[0] < y[0]:
        return 1
    if x[0]==y[0] and x[1]<y[1]:
        return -1
    if x[0]==y[0] and x[1]>y[1]:
        return 1
    if x[0]==y[0] and x[1]==y[1]:
        return 0
    
class Solution(object):
    def reconstructQueue(self, people):
        """
        :type people: List[List[int]]
        :rtype: List[List[int]]
        """
        people = sorted(people, lambda x,y: cmp(x,y))
        ret = []
        for x in people:
            ret.insert(x[1], x)
        return ret

#413.Arithmetic Slices [Medium]

Description

A sequence of number is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

For example, these are arithmetic sequence: 

1
2
3
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9

The following sequence is not arithmetic.

1
1, 1, 2, 5, 7

A zero-indexed array A consisting of N numbers is given. A slice of that array is any pair of integers (P, Q) such that 0 <= P < Q < N.

A slice (P, Q) of array A is called arithmetic if the sequence:
A[P], A[p + 1], …, A[Q - 1], A[Q] is arithmetic. In particular, this means that P + 1 < Q.

The function should return the number of arithmetic slices in the array A.

Example:

1
2
3
A = [1, 2, 3, 4]
return: 3, for 3 arithmetic slices in A: [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.

Idea

这道题就是先判断哪一段是等差数列，等差数列多长，然后再统计等差子数列个数。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution(object):
    def calcHelper(self, size):
        if size < 3:
            return 0
        elif size == 3:
            return 1
        else:
            return (1 + size - 2) * (size - 2) / 2 
    
    def checkHelper(self, A):
        index = 2
        count = 2
        ret = []
        diff = A[1] - A[0]
        while index < len(A):
            if A[index] - A[index-1] == diff:
                count += 1
                index += 1
            else:
                ret.append(count)
                if index + 1 <len(A):
                    diff = A[index] - A[index-1]
                    count = 2
                    index += 1
                else:
                    count = 1
                    break
        ret.append(count)
        return ret
                    
    def numberOfArithmeticSlices(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        if len(A) < 3:
            return 0
        else:
            ret = self.checkHelper(A)
            sum = 0
            for x in ret:
                sum += self.calcHelper(x)
            return sum

#419.Battleships in a Board [Medium]

Description

Given an 2D board, count how many battleships are in it. The battleships are represented with ‘X’s, empty slots are represented with ‘.’s. You may assume the following rules:

  • You receive a valid board, made of only battleships or empty slots.
  • Battleships can only be placed horizontally or vertically. In other words, they can only be made of the shape 1xN (1 row, N columns) or Nx1 (N rows, 1 column), where N can be of any size.
  • At least one horizontal or vertical cell separates between two battleships - there are no adjacent battleships.

Example:

1
2
3
X..X
...X
...X

In the above board there are 2 battleships.

Invalid Example:

1
2
3
...X
XXXX
...X

This is an invalid board that you will not receive - as battleships will always have a cell separating between them.
Follow up:
Could you do it in one-pass, using only O(1) extra memory and without modifying the value of the board?

Idea

我们可以从战舰的布局中找出计数的技巧，我们扫描一边棋盘，如果是战舰就判断它的下方和右方是否有战舰，如果有则先不计数，如果没有则计数加1，这样不会重复计数。只要稍加注意边界就行了，把边界当成空槽来处理。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def countBattleships(self, board):
        """
        :type board: List[List[str]]
        :rtype: int
        """
        sum = 0
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == 'X':
                    if i+1 >= len(board) or board[i+1][j] == '.':
                        if j+1 >= len(board[0]) or board[i][j+1] == '.':
                            sum += 1
        return sum

#442.Find All Duplicates in an Array [Medium]

Description

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements that appear twice in this array.

Could you do it without extra space and in O(n) runtime?

Example: 

1
2
3
4
5
Input:
[4,3,2,7,8,2,3,1]
Output:
[2,3]

Idea

这道题是微软实习生面试被问到的题目，思路见微软实习生面试小记第二轮的扩展题。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def findDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        ret = []
        for i in range(len(nums)):
            if nums[(nums[i]-len(nums) if nums[i]>len(nums) else nums[i]) - 1] > len(nums):
                ret.append(nums[i]-len(nums) if nums[i]>len(nums) else nums[i])
            else:
                nums[(nums[i]-len(nums) if nums[i]>len(nums) else nums[i]) - 1] += len(nums)
        return ret

#461.Hamming Distance [Easy]

Desciprtion

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, calculate the Hamming distance.

Note: $0\leq x,y\leq2^{31}$.

Example:

1
2
3
4
5
6
7
8
9
10
Input: x = 1, y = 4
Output: 2
Explanation:
1   (0 0 0 1)
4   (0 1 0 0)
       ?   ?
The above arrows point to positions where the corresponding bits are different.

Idea

按照定义去计算就行了，Python中可以通过bin函数将十进制转换成二进制。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def hammingDistance(self, x, y):
        """
        :type x: int
        :type y: int
        :rtype: int
        """
        bin_x = [int(ch) for ch in bin(x).replace('0b','')[::-1]]
        bin_y = [int(ch) for ch in bin(y).replace('0b','')[::-1]]
        if len(bin_x) > len(bin_y):
            for i in range(len(bin_x)-len(bin_y)):
                bin_y.append(0)
        else:
            for i in range(len(bin_y)-len(bin_x)):
                bin_x.append(0)
        return sum([abs(j) for j in [bin_x[i]-bin_y[i] for i in range(len(bin_x))]])

#462.Minimum Moves to Equal Array Elements II [Medium]

Description

Given a non-empty integer array, find the minimum number of moves required to make all array elements equal, where a move is incrementing a selected element by 1 or decrementing a selected element by 1.

You may assume the array’s length is at most 10,000.

Example: 

1
2
3
4
5
6
7
8
9
10
Input:
[1,2,3]
Output:
2
Explanation:
Only two moves are needed (remember each move increments or decrements one element):
[1,2,3]  =>  [2,2,3]  =>  [2,2,2]

Idea

这道题就是要先找到大家往哪个数字移动，当然往中位数移动总次数最少，因为无论往中位数加减1的数字移动，都会增加总次数，所以中位数就是我们要找的数，排序之后中位数就很好找了。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def minMoves2(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0:
            return 0
        else:
            nums =  sorted(nums)
            if len(nums) % 2 == 0:
                mid = nums[len(nums) / 2 -1]
            else:
                mid = nums[(len(nums) - 1) / 2]
            ret = 0
            for x in nums:
                ret += abs(x - mid)
            return ret

#463.Island Perimeter [Easy]

Description

You are given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water. Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells). The island doesn’t have “lakes” (water inside that isn’t connected to the water around the island). One cell is a square with side length 1. The grid is rectangular, width and height don’t exceed 100. Determine the perimeter of the island.
Example: 

1
2
3
4
5
6
[[0,1,0,0],
 [1,1,1,0],
 [0,1,0,0],
 [1,1,0,0]]
Answer: 16

Explanation

Idea

这道题就是扫描一遍，将相邻方格如果是水就计数加1。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def islandPerimeter(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        ret = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    countZeros = 0
                    if i-1<0  or grid[i-1][j]==0:
                        countZeros += 1
                    if i+1>=len(grid) or grid[i+1][j]==0:
                        countZeros += 1
                    if j-1<0 or grid[i][j-1]==0:
                        countZeros += 1
                    if j+1>=len(grid[0]) or grid[i][j+1]==0:
                        countZeros += 1
                    ret += countZeros
        return ret

#466.Count The Repetitions [Hard]

Description

Define S = [s,n] as the string S which consists of n connected strings s. For example, [“abc”, 3] =”abcabcabc”.

On the other hand, we define that string s1 can be obtained from string s2 if we can remove some characters from s2 such that it becomes s1. For example, “abc” can be obtained from “abdbec” based on our definition, but it can not be obtained from “acbbe”.

You are given two non-empty strings s1 and s2 (each at most 100 characters long) and two integers $0 ≤ n1 ≤ 10^6$ and $1 ≤ n2 ≤ 10^6$. Now consider the strings S1 and S2, where S1=[s1,n1] and S2=[s2,n2]. Find the maximum integer M such that [S2,M] can be obtained from S1.

Example: 

1
2
3
4
5
6
Input:
s1="acb", n1=4
s2="ab", n2=2
Return:
2

Idea

这是做的第一道Hard的题目，想了很久做的还是不对。最后找到这个discuss里的解答才明白该怎么做，结题思路还是挺复杂的，我就不复制粘贴了。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution(object):
    def getMaxRepetitions(self, s1, n1, s2, n2):
        """
        :type s1: str
        :type n1: int
        :type s2: str
        :type n2: int
        :rtype: int
        """
        repeat_count = [0] * (len(s2) + 1)
        next_index = [0] * (len(s2) + 1)
        j = 0
        count = 0
        for k in range(1, n1 + 1):
            for i in range(len(s1)):
                if s1[i] == s2[j]:
                    j += 1
                    if j == len(s2):
                        j = 0
                        count += 1
            repeat_count[k] = count
            next_index[k] = j
            for start in range(k):
                if next_index[start] == j:
                    prefix_count = repeat_count[start]
                    pattern_count = (repeat_count[k] - repeat_count[start]) * (n1 - start) / (k - start)
                    suffix_count = repeat_count[start + (n1 - start) % (k -start)] - repeat_count[start]
                    return (prefix_count + pattern_count + suffix_count) / n2
        return repeat_count[n1] / n2

#476.Number Complement [Easy]

Description

Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation.

Example: 

1
2
3
Input: 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.

Idea

按照定义来做就行了。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def findComplement(self, num):
        """
        :type num: int
        :rtype: int
        """
        bin_str = list(bin(num))
        for i in range(len(bin_str)-2):
            if bin_str[i+2] == '0':
                bin_str[i+2] = '1'
            else:
                bin_str[i+2] = '0'
        return int(''.join(bin_str), base=2)

#500.Keyboard Row [Easy]

Description

Given a List of words, return the words that can be typed using letters of alphabet on only one row’s of American keyboard like the image below.

Example: 

1
2
Input: ["Hello", "Alaska", "Dad", "Peace"]
Output: ["Alaska", "Dad"]

Idea

这道题我把每个字母当作键放进一个字典，排数就是键值，然后对每个单词去逐个字母判断了，如果出现不同排的就跳过这个单词。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution(object):
    def __init__(self):
        self.keyboard_map = {}
        for x in list('qwertyuiop'):
            self.keyboard_map[x] = 1
        for x in list('asdfghjkl'):
            self.keyboard_map[x] = 2
        for x in list('zxcvbnm'):
            self.keyboard_map[x] = 3
            
    def findWords(self, words):
        """
        :type words: List[str]
        :rtype: List[str]
        """
        ret = []
        for word in words:
            if len(word) == 1:
                ret.append(word)
            else:
                lower_word = word.lower()
                flag = self.keyboard_map[lower_word[0]]
                index = 1
                while index < len(word):
                    if self.keyboard_map[lower_word[index]]!=flag:
                        break
                    index += 1
                    if index == len(word):
                        ret.append(word)
        return ret

#508.Most Frequent Subtree Sum [Medium]

Description

Given the root of a tree, you are asked to find the most frequent subtree sum. The subtree sum of a node is defined as the sum of all the node values formed by the subtree rooted at that node (including the node itself). So what is the most frequent subtree sum value? If there is a tie, return all the values with the highest frequency in any order.

Example 1:
input:

1
2
3
  5
 /  \
2   -3

return [2, -3, 4], since all the values happen only once, return all of them in any order.

Example 2:
input: 

1
2
3
  5
 /  \
2   -5

return [2], since 2 happens twice, however -5 only occur once.

Idea

这道题就是通过递归去计算每个子树的和，然后再去统计频率。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def __init__(self):
        self.freq_dict= {}
    def dfs(self, node):
        if node is None:
            return 0
        else:
            sum = self.dfs(node.left) + self.dfs(node.right) + node.val
            if sum not in self.freq_dict:
                self.freq_dict[sum] = 1
            else:
                self.freq_dict[sum] += 1
            return sum
        
    def findFrequentTreeSum(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        self.dfs(root)
        ret = []
        max = 0
        for k in self.freq_dict:
            if self.freq_dict[k] > max:
                max = self.freq_dict[k]
                ret = [k]
            elif self.freq_dict[k] == max:
                ret.append(k)
        return ret

#513.Find Bottom Left Tree Value [Medium]

Description

Given a binary tree, find the leftmost value in the last row of the tree.

Example 1: 

1
2
3
4
5
6
7
8
Input:
    2
   / \
  1   3
Output:
1

Example 2: 

1
2
3
4
5
6
7
8
9
10
11
12
Input:
        1
       / \
      2   3
     /   / \
    4   5   6
       /
      7
Output:
7

Idea

这道题要关注是不是最底层，而不光是最左。所以在遍历的时候要加一个层数作为参数，如果层数增加，由于是先遍历左子树，所以第一个增加层数的节点一定是最左的节点。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def __init__(self):
        self.max_depth = 0
        self.value = 0
    
    def bfs(self, root, depth):
        if root == None:
            return None
        else:
            if depth > self.max_depth:
                self.max_depth = depth
                self.value = root.val
            if root.left != None:
                self.bfs(root.left, depth+1)
            if root.right != None:
                self.bfs(root.right, depth+1)
                
    def findBottomLeftValue(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.bfs(root, 1)
        return self.value

#526.Beautiful Arrangement [Medium]

Description

Suppose you have N integers from 1 to N. We define a beautiful arrangement as an array that is constructed by these N numbers successfully if one of the following is true for the $i_{th}$ position (1 ? i ? N) in this array:

The number at the $i{th}$ position is divisible by i.
i is divisible by the number at the $i{th}$ position.
Now given N, how many beautiful arrangements can you construct?

Example: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Input: 2
Output: 2
Explanation: 
The first beautiful arrangement is [1, 2]:
Number at the 1st position (i=1) is 1, and 1 is divisible by i (i=1).
Number at the 2nd position (i=2) is 2, and 2 is divisible by i (i=2).
The second beautiful arrangement is [2, 1]:
Number at the 1st position (i=1) is 2, and 2 is divisible by i (i=1).
Number at the 2nd position (i=2) is 1, and i (i=2) is divisible by 1.

Idea

这道题思路就是回溯法。通过visted这个数组来保存状态，记得再递归之后要恢复之前的状态。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def countArrangement(self, N):
        """
        :type N: int
        :rtype: int
        """
        self.count = 0
        self.visited =  [False] * (N+1)
        self.dfs(N)
        return self.count
        
    def dfs(self, index):
        if index == 1:
            self.count += 1
            return
        for i in range(1, len(self.visited)):
            if self.visited[i]==False and (index % i ==0 or i % index == 0):
                self.visited[i] = True
                self.dfs(index-1)
                self.visited[i] = False
        return

#529.Minesweeper [Medium]

Description

Let’s play the minesweeper game!

You are given a 2D char matrix representing the game board. ‘M’ represents an unrevealed mine, ‘E’ represents an unrevealed empty square, ‘B’ represents a revealed blank square that has no adjacent (above, below, left, right, and all 4 diagonals) mines, digit (‘1’ to ‘8’) represents how many mines are adjacent to this revealed square, and finally ‘X’ represents a revealed mine.

Now given the next click position (row and column indices) among all the unrevealed squares (‘M’ or ‘E’), return the board after revealing this position according to the following rules:

  1. If a mine (‘M’) is revealed, then the game is over - change it to ‘X’.
  2. If an empty square (‘E’) with no adjacent mines is revealed, then change it to revealed blank (‘B’) and all of its adjacent unrevealed squares should be revealed recursively.
  3. If an empty square (‘E’) with at least one adjacent mine is revealed, then change it to a digit (‘1’ to ‘8’) representing the number of adjacent mines.
  4. Return the board when no more squares will be revealed.

Example 1: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Input: 
[['E', 'E', 'E', 'E', 'E'],
 ['E', 'E', 'M', 'E', 'E'],
 ['E', 'E', 'E', 'E', 'E'],
 ['E', 'E', 'E', 'E', 'E']]
Click : [3,0]
Output: 
[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'M', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]

Explanation 1:

Explanation1

Example 2: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Input: 
[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'M', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]
Click : [1,2]
Output: 
[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'X', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]

Explanation 2:

Explanation2

Note:

  1. The range of the input matrix’s height and width is [1,50].
  2. The click position will only be an unrevealed square (‘M’ or ‘E’), which also means the input board contains at least one clickable square.
  3. The input board won’t be a stage when game is over (some mines have been revealed).
  4. For simplicity, not mentioned rules should be ignored in this problem. For example, you don’t need to reveal all the unrevealed mines when the game is over, consider any cases that you will win the game or flag any squares.

Idea

这道题其实不难，但是觉得很好玩。用递归就可以解决了。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution(object):
    def numOfMine(self, board, click):
        x_size = len(board)
        y_size = len(board[0])
        count = 0
        x = click[0]
        y = click[1]
        for i in [-1, 0, 1]:
            for j in [-1, 0, 1]:
                if x+i>=0 and x+i<x_size and y+j>=0 and y+j<y_size and not(i==0 and j ==0) and board[x+i][y+j] == 'M':
                    count += 1
        return count
        
    def updateBoard(self, board, click):
        """
        :type board: List[List[str]]
        :type click: List[int]
        :rtype: List[List[str]]
        """
        if board[click[0]][click[1]] == 'M':
            board[click[0]][click[1]] = 'X'
            return board
        else:
            num_of_mine = self.numOfMine(board, click)
            if num_of_mine == 0:
                board[click[0]][click[1]] = 'B'
                x_size = len(board)
                y_size = len(board[0])
                x = click[0]
                y = click[1]
                for i in [-1, 0, 1]:
                    for j in [-1, 0, 1]:
                        if x+i>=0 and x+i<x_size and y+j>=0 and not(i==0 and j ==0) and y+j<y_size and board[x+i][y+j] == 'E':
                            board = self.updateBoard(board, [x+i, y+j])
            else:
                board[click[0]][click[1]] = str(num_of_mine)
        return board

#535.Encode and Decode TinyURL [Medium]

Desciprtion

TinyURL is a URL shortening service where you enter a URL such as https://leetcode.com/problems/design-tinyurl and it returns a short URL such as http://tinyurl.com/4e9iAk.

Design the encode and decode methods for the TinyURL service. There is no restriction on how your encode/decode algorithm should work. You just need to ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL.

Idea

对任何一个URL都随机生成一个6个字符的字符串作为短连接，然后把随机生成的短连接和原链接存进两个字典里用来编码和解码。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
import random
class Codec:
    def __init__(self):
        self.long_short_dict = {}
        self.short_long_dict = {}
        self.prefix = "http://tinyurl.com/long_short_url"
        
    @staticmethod    
    def randomUrl(num):
        url = ""
        for i in range(num):
            url += chr(random.randint(65,122))
        return url
        
    def encode(self, longUrl):
        """Encodes a URL to a shortened URL.
        
        :type longUrl: str
        :rtype: str
        """
        if longUrl in self.long_short_dict:
            return self.prefix + self.long_short_dict[longUrl]
        else:
            url = Codec.randomUrl(6)
            while url in self.short_long_dict:
                url = Codec.randomUrl(6)
            self.long_short_dict[longUrl] = url
            self.short_long_dict[self.prefix + url] = longUrl
            return self.prefix + url
        
    def decode(self, shortUrl):
        """Decodes a shortened URL to its original URL.
        
        :type shortUrl: str
        :rtype: str
        """
        if shortUrl in self.short_long_dict:
            return self.short_long_dict[shortUrl]
        else:
            return ""
        
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.decode(codec.encode(url))

#537.Complex Number Multiplication [Medium]

Description

Given two strings representing two complex numbers.

You need to return a string representing their multiplication. Note $i^2 = -1$ according to the definition.

Idea

就是按照定义求。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def complexNumberMultiply(self, a, b):
        """
        :type a: str
        :type b: str
        :rtype: str
        """
        ca = a.split('+')
        ra = int(ca[0])
        ia = int(ca[1][0:-1])
        cb = b.split('+')
        rb = int(cb[0])
        ib = int(cb[1][0:-1])
        rr =  ra*rb - ia*ib
        ir = ra*ib + rb*ia
        return str(rr)+'+'+str(ir)+'i'

#538.Convert BST to Greater Tree [Easy]

Description

Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.

Example: 

1
2
3
4
5
6
7
8
9
Input: The root of a Binary Search Tree like this:
              5
            /   \
           2     13
Output: The root of a Greater Tree like this:
             18
            /   \
          20     13

Idea

这道题一开始想的很复杂，还是错的，忽略了二叉查找树的中序遍历（右->中->左）就是从大到小进行遍历，我们有一个全局的sum，然后不断累加节点的数值到sum中，遍历到的节点的值就是自己的值加上sum。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def __init__(self):
        self.sum = 0
    def convertBST(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if root is None:
            return None
        else:  
            self.convertBST(root.right)
            root.val += self.sum
            self.sum = root.val
            self.convertBST(root.left)
            return root

#540.Single Element in a Sorted Array [Medium]

Description

Given a sorted array consisting of only integers where every element appears twice except for one element which appears once. Find this single element that appears only once.

Example 1: 

1
2
Input: [1,1,2,3,3,4,4,8,8]
Output: 2

Example 2 

1
2
Input: [3,3,7,7,10,11,11]
Output: 10

Note: Your solution should run in O(log n) time and O(1) space.

Idea

看到O(log n)那基本上就是二分法了。Single Element一定出在个数为奇数的那一半，不停的二分直到找到它。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def singleNonDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 1:
            return nums[0]
        else:
            mid = (len(nums)-1)/2
            if nums[mid] == nums[mid-1]:
                if (mid-1) %2  == 0:
                    ret = self.singleNonDuplicate(nums[mid+1:])
                else:
                    ret = self.singleNonDuplicate(nums[:mid-1])
            elif nums[mid] == nums[mid+1]:
                if mid % 2 == 0:
                    ret = self.singleNonDuplicate(nums[mid+2:])
                else:
                    ret = self.singleNonDuplicate(nums[:mid])
            else:
                return nums[mid]
        return ret

#557.Reverse Words in a String III [Easy]

Description

Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.

Example: 

1
2
Input: "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"

Idea

这个在Python里写起来很简单。

Solution

1
2
3
4
5
6
7
8
9
class Solution(object):
    def reverseWords(self, s):
        """
        :type s: str
        :rtype: str
        """
        words = s.split(" ")
        words = [x[::-1] for x in words]
        return " ".join(words)

#561.Array Partition I [Easy]

Description

Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), …, (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.
Example:

1
2
3
4
Input: [1,4,3,2]
Output: 4
Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).

Note:

  1. n is a positive integer, which is in the range of [1, 10000].

  2. All the integers in the array will be in the range of [-10000, 10000].

    Idea

    要使题目中所说的和最大，那肯定要把所有小的两两组合求min，否则小的和大的组合会使各个项都比较小，所以先把数组排序，然后从最小开始两两组合求min，然后求和就行了。

    Solution

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    class Solution(object):
        def arrayPairSum(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            sorted_nums = sorted(nums)
            sum = 0
            for i in range(len(nums)/2):
                sum += sorted_nums[2*i]
            return sum

#565.Array Nesting [Medium]

Description

A zero-indexed array A consisting of N different integers is given. The array contains all integers in the range [0, N - 1].

Sets S[K] for 0 <= K < N are defined as follows:

S[K] = { A[K], A[A[K]], A[A[A[K]]], … }.

Sets S[K] are finite for each K and should NOT contain duplicates.

Write a function that given an array A consisting of N integers, return the size of the largest set S[K] for this array.

Example: 

1
2
3
4
5
6
7
Input: A = [5,4,0,3,1,6,2]
Output: 4
Explanation: 
A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.
One of the longest S[K]:
S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}

Note:

  1. N is an integer within the range [1, 20,000].
  2. The elements of A are all distinct.
  3. Each element of array A is an integer within the range [0, N-1].

Idea

一开始的想法是把所有的集合都算出来比大小，但是超时了。后来想其实这个集合就是几组循环数字，无论从这个循环中的哪个数字开始，集合都是一样的。所以建立一个vistied集合，当所有元素都访问过了之后，所有可能的集合就出来了，就不用再往后求更多的集合啦，因为后面的集合会和前面的一样。这个时候结束循环返回结果就可以了。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def arrayNesting(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        sets = [set() for i in range(len(nums))]
        visited = set()
        max = 0
        for i in range(len(nums)):
            index = i
            while nums[index] not in sets[i] and nums[index] not in visited:
                sets[i].add(nums[index])
                visited.add(nums[index])
                index = nums[index]
            if len(sets[i]) == len(nums):
                return len(nums)
            if len(sets[i]) > max:
                max = len(sets[i])
            if len(visited) == len(nums):
                break
        return max

#566.Reshape the Matrix [Easy]

Description

In MATLAB, there is a very useful function called ‘reshape’, which can reshape a matrix into a new one with different size but keep its original data.

You’re given a matrix represented by a two-dimensional array, and two positive integers r and c representing the row number and column number of the wanted reshaped matrix, respectively.

The reshaped matrix need to be filled with all the elements of the original matrix in the same row-traversing order as they were.

If the ‘reshape’ operation with given parameters is possible and legal, output the new reshaped matrix; Otherwise, output the original matrix.

Example: 

1
2
3
4
5
6
7
8
9
Input: 
nums = 
[[1,2],
 [3,4]]
r = 1, c = 4
Output: 
[[1,2,3,4]]
Explanation:
The row-traversing of nums is [1,2,3,4]. The new reshaped matrix is a 1 * 4 matrix, fill it row by row by using the previous list.

Idea

先判断维数是否符合，符合的话就把原矩阵先变成一维数组，然后再按给定行列往里塞。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def matrixReshape(self, nums, r, c):
        """
        :type nums: List[List[int]]
        :type r: int
        :type c: int
        :rtype: List[List[int]]
        """
        if r*c != len(nums)*len(nums[0]):
            return nums
        else:
            temp = []
            for x in nums:
                temp.extend(x)
            ret = []
            for i in range(r):
                    ret.append(temp[i*c:i*c+c])
            return ret

#575.Distribute Candies [Easy]

Description

Given an integer array with even length, where different numbers in this array represent different kinds of candies. Each number means one candy of the corresponding kind. You need to distribute these candies equally in number to brother and sister. Return the maximum number of kinds of candies the sister could gain.

Example: 

1
2
3
4
5
6
Input: candies = [1,1,2,2,3,3]
Output: 3
Explanation:
There are three different kinds of candies (1, 2 and 3), and two candies for each kind.
Optimal distribution: The sister has candies [1,2,3] and the brother has candies [1,2,3], too. 
The sister has three different kinds of candies.

Idea

这道题就是比较到底是糖的种类多还是糖总数的一半多，返回较小者。

Solution

1
2
3
4
5
6
7
class Solution(object):
    def distributeCandies(self, candies):
        """
        :type candies: List[int]
        :rtype: int
        """
        return min(len(candies)/2, len(set(candies)))

#617.Merge Two Binary Trees [Easy]

Desciprtion

Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.

You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Input: 
	Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
Output: 
Merged tree:
	     3
	    / \
	   4   5
	  / \   \ 
	 5   4   7

Note: The merging process must start from the root nodes of both trees.

Idea

二叉树就用递归的思想去做。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def mergeTrees(self, t1, t2):
        """
        :type t1: TreeNode
        :type t2: TreeNode
        :rtype: TreeNode
        """
        if t1 is None and t2 is None:
            return None
        elif t1 is None and t2 is not None:
            node = TreeNode(t2.val)
            node.left = self.mergeTrees(None, t2.left)
            node.right = self.mergeTrees(None, t2.right)
            return node
        elif t1 is not None and t2 is None:
            node = TreeNode(t1.val)
            node.left = self.mergeTrees(t1.left, None)
            node.right = self.mergeTrees(t1.right, None)
            return node
        else:
            node = TreeNode(t1.val+t2.val)
            node.left = self.mergeTrees(t1.left, t2.left)
            node.right = self.mergeTrees(t1.right, t2.right)
            return node

#637.Average of Levels in Binary Tree [Easy]

Description

Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.

Example: 

1
2
3
4
5
6
7
8
9
Input:
    3
   / \
  9  20
    /  \
   15   7
Output: [3, 14.5, 11]
Explanation:
The average value of nodes on level 0 is 3,  on level 1 is 14.5, and on level 2 is 11. Hence return [3, 14.5, 11].

Idea

先遍历二叉树，输出每一层的数字到一个字典中，然后再求均值。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def __init__(self):
        self.level_dict = {}
        
    def numsOfLevels(self, node, level):
        if level not in self.level_dict:
            self.level_dict[level] = [node.val]
        else:
            self.level_dict[level].append(node.val)
        if node.left is not None:
            self.numsOfLevels(node.left, level+1)
        if node.right is not None:
            self.numsOfLevels(node.right, level+1)
            
    def averageOfLevels(self, root):
        """
        :type root: TreeNode
        :rtype: List[float]
        """
        self.numsOfLevels(root, 0)
        ret = [0] * len(self.level_dict)
        for level in self.level_dict:
            sum = 0 
            for x in self.level_dict[level]:
                sum += x
            ret[level] = float(sum) / len(self.level_dict[level])
        return ret

#647.Palindromic Substrings [Medium]

Description

Given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

Example 1: 

1
2
3
Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2: 

1
2
3
Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Idea

这道题一开始我根本搞不懂什么叫Palindromic String，后来才知道是正反都是一样的字符串，例如“abcdcba”这样。找别人的做法才知道应该用动态规划去做。用一个数组dp去表示从第i个字符到第j个字符的子字符串是不是Palindromic的。而如果dp[i-1][j-1]是Palindromic的，如果第i个字符与第j个字符相同，那么dp[i][j]也是Palindromic的。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def countSubstrings(self, s):
        """
        :type s: str
        :rtype: int
        """
        size = len(s)
        if len == 0:
            return 0
        else:
            dp = [[0 for i in range(size)] for i in range(size)]
            ret = 0
            for i in range(size-1, -1, -1):
                for j in range(i, size):
                    if s[i] == s[j] and (j-i<3 or dp[i+1][j-1]==1):
                        dp[i][j] = 1
                        ret += 1
            return ret