Leetcode

Leetcode 经验

String

遇到String 的题目，首先的想法是用指针i, j的方式做题

两种视角

Recursion：从顶端找底端

用Recursion的方式，如果会有重复的部分，新建一个Helper，存储所有见过的计算结果

EXAMPLE：62. Unique Paths

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
class Solution:
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        def helper(m,n,seen):
            if (m,n) in seen: return seen[(m,n)]

            if (m == 2 and n == 1) or (n==2 and m==1) or (m==1 and n ==1):
                return 1

            count = 0
            if m-1 >= 1:
                count += helper(m-1,n,seen)
                seen[(m-1,n)] = count
            if n-1 >=1:
                temp = helper(m, n-1, seen)
                seen[(m,n-1)] = temp
                count += temp

            return count

        return helper(m,n,{})

Store in a list：从底端到顶端

如果从0/1开始，都要遍历，可以从底端到顶端

用list，存储从小到大的结果

返回值为最后的最大值

EXAMPLE：62. Unique Paths

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def uniquePaths2(self, m, n):
    """
    :type m: int
    :type n: int
    :rtype: int
    """
    
    """
    坐标系
    Finish： A[0,0]
    Start： A[m-1,n-1]
    """

    # 预先设定其他的都是[1],那么A[i][0], A[0][j],就不需要进行遍历
    A = [[1] * n] * m

    # 直接从A[1][1]开始
    for i in range(1, m):
        for j in range(1, n):
            A[i][j] = A[i - 1][j] + A[i][j - 1]

    return A[m - 1][n - 1]

Palindromic Substring

EX: LC5: Longest Palindromic Substring

1
2
3
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
  1. Select a center, like “a”, “aa”, “aaa”
  2. Spread the center
  3. Use Middle to remeber the center, and use i, j to spread it.