LeetCode 刷题总结（一）， 使用Python 实现。该篇题目类型主要是： array 和string 的相关处理。
- Two Sum
Given an array of integers, find two numbers such that they add up to a specific target number.
Tips： 返回的是 index，所以 dict 中存储的 (num, index) 这样的组合, 是两个不相同的数字的index。题目中确保有唯一解。
使用字典，其中的(key, val) -> (数值，index)。使用字典的目的是为了记录值的index。
时间复杂度是 $O(n)$ 空间复杂度是 $O(n)$ 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> dict;
for(int i =0; i< nums.size(); i++)
{
//还可以使用dict.count(val) 判断是否存在值
if( dict.find(target -nums[i]) != dict.end())
return vector<int>{dict[target- nums[i]], i};
dict[nums[i]] =i;
}
return vector<int>{-1, -1};
}
};
|
python 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
# 时间和空间复杂度都是 O(n)
dic ={} # 存储 (num, index) 的映射关系
for (index, num) in enumerate(nums):
if target -num in dic:
return (dic[target-num], index)
dic[num] =index
return ()
|
Two Sum II - Input array is sorted
有三种解法（1）双指针，时间复杂度 $O(n)$, 空间 $O(1)$（2）使用dict 辅助，时间复杂度$O(N)$,空间$O(n)$（3）二分查找，时间复杂度$O(nlogn)$，空间$O(1)$。前两者的时间复杂度虽然都是 $O(n)$，但是第二种dict 辅助效率更高。使用二分查找不一定快。
c++ 解法
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int i =0, j =numbers.size() -1;
while (i <j)
{
if (numbers[i] +numbers[j] == target) return vector<int>{i+1, j+1};
else if(numbers[i] +numbers[j] > target) j -=1;
else i +=1;
}
return vector<int>{-1, -1};
}
};
|
同样是 $O(n)$ 时间复杂度，但是实际运行的效果要好于上面的算法。
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
unordered_map<int, int> dict;
for(int i =0; i< numbers.size() ; i++)
{
if( dict.count(target -numbers[i])) return vector<int>{dict[target-numbers[i]]+1, i+1};
dict[numbers[i]] =i;
}
return vector<int>{};
}
};
|
python解法，虽然是有序的，但是并不能达到 $O(logn)$的时间复杂度，只是是$O(n)$的时间复杂度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution(object):
def twoSum(self, numbers, target):
"""
:type numbers: List[int]
:type target: int
:rtype: List[int]
"""
l, r =0, len(numbers)-1
while l <r :
total = numbers[l] +numbers[r]
if total ==target:
return (l+1, r+1)
elif total < target:
l +=1
else:
r -=1
return (-1, -1)
|
- Two Sum IV - Input is a BST
将两数之和转移到了二叉搜索树，是否存在两个结点，使得其值相加为k。有两种解法，一种是遍历树结构，对于每一个结点，然后都需要遍历一次树，所以总的时间复杂度是$O(n^2)$，其中$n$ 是树的结点的个数。
第二种解法，保存遍历树的结果，然后使用第二题中的思路，所以是$O(n)$的时间复杂度，其中$n$是结点的个数。
二叉搜索树按照中序遍历得到的是一个增序序列。
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 traverse(self, root, res):
if not root:
return
self.traverse(root.left, res)
res.append(root.val)
self.traverse(root.right, res)
def findTarget(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: bool
"""
path =[]
self.traverse(root, path)
# 这个是从小到大的顺序
l, r =0, len(path)-1
print(path)
while(l <r):
total =path[l] +path[r]
if total==k:
return True
elif total < k:
l +=1
else:
r -=1
return False
|
3Sum
先排序，然后使用 2sum 的思路，时间复杂度是$O(n^2)$。因为三个数字相加为0，那么其中必然有一个为负数，一个为正数，所以有多个地方进行优化。
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
|
class Solution {
public:
// 3sum 可以看成是 2sum 的扩展, 可以在时间复杂度为 O(n^2) 内完成
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
if(nums.empty() || nums.front() >0 || nums.back() <0) return {}; // {} 是构造方法的简单书写形式
int n =nums.size();
vector<vector<int>> res;
for(int i =0; i< n; i++)
{
if(nums[i] >0 ) break;
if(i >0 && nums[i] ==nums[i-1]) continue;
// 下面这种是不可解释, 不对
//if(i +1< n && nums[i] == nums[i +1]) continue;
int l = i +1, r =n -1;
while (l <r)
{
if(nums[i] + nums[l] + nums[r] ==0)
{
res.push_back({nums[i], nums[l], nums[r]});
while(l<r && nums[l] ==nums[ l+1]) l ++;
while(l < r && nums[r] ==nums[r-1] ) r --;
l ++;
r --;
}
else if(nums[i] + nums[l] + nums[r] < 0)
{
l ++;
}
else
r --;
}
}
return res;
}
};
|
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
|
class Solution(object):
# 时间复杂度是 $O(n^2)$
# 首先进行排序，然后枚举每个数字，针对每个数字，然后再次枚举，看是否满足 a +b +c ==0 的条件?
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
if not nums: return nums
nums.sort()
n =len(nums)
res =[]
for i in range(n):
if nums[i] >0: break
if i >0 and nums[i] ==nums[i-1]: continue
# 开始第二次枚举
l, r =i +1, n -1
while l <r:
if nums[i] + nums[l] + nums[r] ==0:
res.append([nums[i], nums[l], nums[r]])
# 把重复的数字删去
while l +1< n and nums[l] ==nums[l +1]: l +=1
while r-1 >0 and nums[r] ==nums[r -1]: r -=1
l +=1
r -=1
elif nums[i] + nums[l] + nums[r] < 0:
l +=1
else:
r -=1
return res
|
- 在一个有序的整数数组中，给定一个目标数字target，要求返回比该target 小的第一个数字（index最大）。
这个是二分查找非常简单的变形，处理一下边界条件就行。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
int find_target(vector<int> arr, int target)
{
if (arr.size() ==0) return -1;
int l =0, r =arr.size() -1;
while(l <r)
{
int mid =l +r +1>>1;
if(arr[mid] <target) l =mid;
else r =mid -1;
}
return l;
}
|
- 请设计一个高效算法，找出数组中两数之和为指定值的所有整数对
双指针算法。首先排序，相同或者相近的数字在一块，然后使用双指针的思想求解。时间复杂度$O(nlogn)$，空间复杂度$O(1)$。寻找相同点的过程，和上面 TwoSum基本上是一样的。当发现相同的时候，可能存在两种情况，一种是全部相同，一种是有两个相同的部分组成。
样例，输入是：
返回的值是
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
|
class FindPair:
def countPairs(self, arr, n, tsum):
if n <2:
return 0
arr.sort()
count =0
i , j =0, n -1
# 双指针问题
while i<j:
total =arr[i] +arr[j]
if total >tsum:
j -=1
elif total < tsum:
i +=1
else:
if arr[i] ==arr[j]:
x = j -i+1
count += x*(x-1)/2
break
else:
ni, nj =1, 1
while i< j and arr[i] ==arr[i+ni]:
ni +=1
i =i +ni-1
while i <j and arr[j] ==arr[j-nj]:
nj +=1
j =j -nj+1
count += ni*nj
i +=1
j -=1
return count
|
** ZigZag Conversion**
The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
P A H N
A P L S I I G
Y I R
And then read line by line: “PAHNAPLSIIGYIR”
Tips: 字符串处理
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 convert(self, s, numRows):
"""
:type s: str
:type numRows: int
:rtype: str
"""
if numRows == 1 or numRows >= len(s): # string of list
return s
L = [''] * numRows # string of list
row, step = 0, 1
for x in s:
L[row] += x
if row == 0:
step = 1
elif row == numRows -1:
step = -1
row += step
return ''.join(L) # array (list) 转成string 常用的方法
|
11. Container With Most Water
Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
Tips: 左储水量取决于小的板，所以直接双指针进行遍历就行。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution:
"""
储水量取决于小的板，所以直接双指针进行遍历就行。
"""
def maxArea(self, height: List[int]) -> int:
if len(height) ==2: return min(height)
l, r = 0, len(height) -1
res = 0
while l < r:
if height[l] < height[r]:
t = height[l] * (r -l)
l +=1
else:
t = height[r] * (r -l)
r -=1
res =max(res, t)
return res
|
c++ 实现
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 {
public:
int maxArea(vector<int>& height) {
int n =height.size();
int l =0, r =n -1;
int res =0;
while (l <r)
{
int t =0;
if(height[l] < height[r])
{
t = (r -l) * height[l];
l ++;
}
else{
t =(r -l) * height[r];
r --;
}
res =max(res, t);
}
return res;
}
};
|
Remove Duplicates from Sorted Array
Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
Tips: 前后两个指针覆盖的思想，最后返回的是index，如果发现了后者覆盖前者
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution(object):
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
# 这个题目是能够想到 n^2 的思路，但是对于 n 的思路，是没有什么想法的， 所以重点在于思路
# 使用双指针进行求解
k =0
for index in range(1, len(nums)):
if nums[k] != nums[index]:
k +=1 # k+=1 是先为新的元素增加一个位置
nums[k] =nums[index]
return k +1
|
** Remove Element**
Given an array nums and a value val, remove all instances of that value in-place and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
Tips: in-place 表示不能创建数组，可以使用（临时）变量。通过双指针进行处理，想想为什么可以使用这么简洁的代码进行处理呢。m n 分别从左到右、从右到左进行遍历，将和 val 相同的元素都放到右边，不相同的放到左边
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
|
class Solution(object):
def removeElement(self, nums, val):
"""
:type nums: List[int]
:type val: int
:rtype: int
"""
if not nums:
return 0
len_n =len(nums)
m,n =0, len_n-1
# 注意跳出条件，遍历的方向和跳出条件是相关的, 这个 等号取于不取 一是比较难把握，可以具体带个值
while m <=n:
if val ==nums[m]:
if val !=nums[n]: # 这个是不能使用 while 找，因为有比较多的case 需要考虑，所以使用 if 进行单步操作
nums[m], nums[n] =nums[n], nums[m]
m +=1
n -=1
else:
n -=1
else:
m +=1
return m # 因为 m 是从0开始的
|
Search in Rotated Sorted Array
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
You are given a target value to search. If found in the array return its index, otherwise return -1.
Tips：一定是 二分思想，关键是判断 增序列 和 target 的关系，所以有两层 if 判断条件，一层是增序列， 一层是 target 是否在增序列下面这个观点是要有的： 整个数组由两个有序的子序列构成，且左子序列中的每个元素都>,右子序列中的每个元素。
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
|
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
# 这个就是 二分的做法
if not nums: return -1
l, r =0, len(nums) -1
while l <r:
mid =l +r >>1
if nums[mid] >= nums[0]:
if target >= nums[0] and target <= nums[mid] :
r =mid
else:
l =mid +1
else:
if target > nums[mid] and target < nums[0]:
l =mid +1
else:
r =mid
return l if nums[l] ==target else -1
|
** Search Insert Position**
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Tips： 二分查找，之前是found or not found，现在如果没有找见返回的是 index，没有什么本质区别。
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 searchInsert(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
if not nums:
return None
len_n =len(nums)
if nums[0] > target:
return 0
if nums[-1] < target:
return len_n
left, right =0, len_n-1
while left<=right:
mid =(left +right)/2
if nums[mid] ==target:
return mid
elif nums[mid] <target:
left =mid +1
else:
right =mid -1
return left
|
** Rotate Image**
You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Given input matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
rotate the input matrix in-place such that it becomes:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
Tips: 好好观察四个等式，就是行变列，然后其他的一个坐标是对称的，这个就是旋转 90度；然后有五个变量（有重复的）
1
2
3
4
5
6
7
8
9
10
11
|
class Solution(object):
def rotate(self, matrix):
n = len(matrix)
if 1 == n:
return
round = int(n / 2)
for x in range(0, round):
for y in range(x, n - x - 1):
matrix[n - y - 1][x], matrix[n - x - 1][n - y - 1], matrix[y][n - x - 1], matrix[x][y] = matrix[n - x - 1][n - y - 1], matrix[y][n - x - 1], matrix[x][y], matrix[n - y - 1][x]
|
Spiral Matrix
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
螺旋形
Input:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]
Tips: 在处理”行“ 信息的时候，是可以数组切割的。在处理列信息的时候，需要一个个append()
下面的代码思路上没有问题，边界等细节问题上是需要debug的。代码形式上没有那么 pythonic，因为 python 是可以使用切片，而c++ 使用for 循环单个处理。
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
|
class Solution(object):
def spiralOrder(self, matrix):
if not matrix: return matrix
top, bottom =0, len(matrix) -1
left, right = 0, len(matrix[0]) -1
res =[]
while left < right and top < bottom:
# 一行
res += matrix[top][left : right]
for i in range(top, bottom):
res.append(matrix[i][right])
res += matrix[bottom][left: right+1 ][::-1]
for i in range(bottom-1, top, -1):
res.append(matrix[i][left])
top +=1
bottom -= 1
left += 1
right -=1
if top ==bottom:
res += matrix[top][left: right+1]
elif left ==right:
for i in range(top, bottom+1):
res.append(matrix[i][right])
return res
|
c++ 实现有一种 exact 的那种感觉，每一行都是严格控制。
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
|
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> res;
if(!matrix.size()) return res;
int l =0, r =matrix[0].size() -1, u =0, d =matrix.size() -1;
while(true)
{
if (l <= r)
for(int i =l; i <=r ; i++) res.push_back(matrix[u][i]);
else break;
u ++;
if(u <= d)
for(int i =u; i<= d; i++) res.push_back(matrix[i][r]);
else
break;
r --;
if(r >= l)
for(int i =r ; i>=l; i --) res.push_back(matrix[d][i]);
else
break;
d --;
if(d >= u)
for(int i =d; i>=u ; i--) res.push_back(matrix[i][l]);
else break;
l ++;
}
return res;
}
};
|
** Spiral Matrix II**
Given a positive integer n, generate a square matrix filled with elements from 1 to $n^2$ in spiral order.
Tips : 注意边角的细节。初始化赋值的应该是常见的操作，这里的cur 是比较核心的东西。
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
|
class Solution(object):
# version 1 是遍历获取， version 2 是填充。这个真是有趣的东西
# 还是设置上下左右四个坐标进行遍历的处理
def generateMatrix(self, n):
ans =[ [0] *n for _ in range(n)]
top, bottom, left, right =0, n-1, 0, n-1
cur =1
while left <= right and top <= bottom:
for i in range(left, right+1):
ans[top][i] =cur
cur +=1
top +=1
# 根据问题需求，是可以在题目中 设置这种break，不需要等到 while 的判断
if top > bottom:
break
for i in range(top, bottom+1):
ans[i][right] =cur
cur +=1
right -=1
if left > right: break
# 好好体会这个连接点的处理，左边是能够访问到的，右边为了能够访问到
# 进行了 -1 的操作
for i in range(right, left-1, -1):
ans[bottom][i] =cur
cur +=1
bottom -=1
if bottom <top: break
for i in range(bottom, top-1, -1):
ans[i][left] =cur
cur +=1
left +=1
return ans
|
** Length of Last Word**
Given a string s consists of upper/lower-case alphabets and empty space characters ' ‘, return the length of last word in the string.
If the last word does not exist, return 0.
Tips: 不能使用 split() 因为太多的case需要单独的处理，所以应该使用字母为基本，一个个处理。等不等于 ' ‘进行的切分。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution(object):
# 这个是需要从 字母角度考虑，而不是从单词角度考虑
def lengthOfLastWord(self, s):
len_s =len(s)
if 0==len_s:
return 0
index =len_s -1
# 找到第一个不是 ' '的字母
while index>=0 and ' ' ==s[index]:
index -=1
len_last_word =0
while index >=0 and ' ' != s[index]:
index -=1
len_last_word +=1
return len_last_word
|
** Valid Number **
Validate if a given string can be interpreted as a decimal number.
Tips :对于小数(decimal ) 各种 case 的熟知程度
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
|
class Solution(object):
def isNumber(self, s):
"""
:type s: str
:rtype: bool
"""
s = s.strip()
digits = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
met_dot = met_e = met_digit = False
for i, char in enumerate(s):
if char in ['+', '-']:
if i > 0 and s[i-1] != 'e':
return False
elif char == '.':
if met_dot or met_e: return False
met_dot = True
elif char == 'e':
if met_e or not met_digit:
return False
met_e, met_digit = True, False
#elif char.isdigit():
elif char in digits:
met_digit = True
else:
return False
return met_digit
|
** Plus One**
Given a non-empty array of digits representing a non-negative integer, plus one to the integer.
The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.
You may assume the integer does not contain any leading zero, except the number 0 itself.
Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Tips: 重点在于加法的处理，一般使用 求余得到digit，然后使用carry 得到进位。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution(object):
def plusOne(self, digits):
"""
:type digits: List[int]
:rtype: List[int]
"""
len_s =len(digits)
carry =1
for i in range(len_s-1, -1, -1):
total =digits[i] +carry
digit =int(total %10)
carry =int(total //10)
digits[i] =digit
# 这个是最后一个进位
if carry ==1:
digits.insert(0, 1)
return digits
|
** Simplify Path**
Given an absolute path for a file (Unix-style), simplify it. Or in other words, convert it to the canonical path.
Tips：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution(object):
# 这个从考点上是 stack，但是使用python字符串处理更好
# 按照 '/' 进行split()
def simplifyPath(self, path):
"""
:type path: str
:rtype: str
"""
stack = []
for token in path.split('/'):
if token in ('', '.'):
pass
# continue 这两个是一样的效果， pass 就类似一种占位符，在测试的时候常见
elif token == '..':
if stack: stack.pop()
else:
stack.append(token)
return '/' + '/'.join(stack)
|
** Edit Distance**
Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.
Tips: 动态规划就通过存储子问题结果来加快运算，但一个好的动态规划算法会尽量减少空间复杂度。 然后是可以继续优化的，使用 O(n) 的空间的复杂度. 真正的写出来之后，发现代码是比想法更加简单的。
提供了两种解法，第一种比较常规 dp，比较容易理解。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
class Solution(object):
def minDistance(self, word1, word2):
"""
:type word1: str
:type word2: str
:rtype: int
"""
m = len(word1)
n = len(word2)
table = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
table[i][0] = i
for j in range(n + 1):
table[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i - 1] == word2[j - 1]:
table[i][j] = table[i - 1][j - 1]
else:
table[i][j] = 1 + min(table[i - 1][j], table[i][j - 1], table[i - 1][j - 1])
return table[-1][-1]
|
第二种就是参考一下吧。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution(object):
# 从实现的角度讲，这个是需要把握住有一个 word的index 是不变的
def minDistance(self, word1, word2):
l1, l2 = len(word1)+1, len(word2)+1
pre = [0 for _ in range(l2)]
for j in range(l2):
pre[j] = j
for i in range(1, l1):
cur = [i]*l2
for j in range(1, l2):
cur[j] = min(cur[j-1]+1, pre[j]+1, pre[j-1]+(word1[i-1]!=word2[j-1]))
#pre = cur[:]
pre =cur
return pre[-1]
|
** Set Matrix Zeroes**
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.
Tips: 使用第一行和第一列作为标记，使用 0作为标记。
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 setZeroes(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: None Do not return anything, modify matrix in-place instead.
"""
firstRowHasZero = not all(matrix[0]) # all() 只有所有的不为0 返回的才不为0，否则返回0
for i in range(1,len(matrix)):
for j in range(len(matrix[0])):
if matrix[i][j] == 0: # 这种遍历并标记的方法还是比较优秀的
matrix[0][j] = 0
matrix[i][0] = 0
for i in range(1,len(matrix)):
for j in range(len(matrix[0])-1,-1,-1): # 注意是从后往前标记的
if matrix[0][j] == 0 or matrix[i][0] == 0:
matrix[i][j] = 0
if firstRowHasZero:
matrix[0] = [0]*len(matrix[0]) #最后处理第一行
|
** Remove Duplicates from Sorted List **
Given a sorted linked list, delete all duplicates such that each element appear only once.
Tips: 注意这道题和上面有道题是有差别的，这个是 delete all duplicates
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 singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
"""
使用两个 while 是因为，逻辑上简单
"""
def deleteDuplicates(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
cur =head
while cur:
while cur.next and cur.val == cur.next.val:
cur.next =cur.next.next
# skip duplicates
cur =cur.next
return head
|
Merge Sorted Array
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
The number of elements initialized in nums1 and nums2 are m and n respectively.
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.
Tips: 题目中说了 nums1 是不会出现 index 访问报错的。从后往前遍历，因为这个是要求 merge 2 into 1的。
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
|
class Solution(object):
def merge(self, nums1, m, nums2, n):
"""
:type nums1: List[int]
:type m: int
:type nums2: List[int]
:type n: int
:rtype: None Do not return anything, modify nums1 in-place instead.
"""
i, j, k =m-1, n-1, m+n-1
while i >=0 and j>=0:
if nums1[i] > nums2[j]:
nums1[k] =nums1[i]
i -=1
else:
nums1[k] =nums2[j]
j -=1
k -=1
#import ipdb
#ipdb.set_trace()
# 如果这是 if 那么使用的就是字符串的切割，如果是while 那么就是一个个操作
if j>=0:
nums1[:k+1] =nums2[:j+1]
|
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 {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
// 这个是比较典型的题目，使用指针就可以搞定
// 使用三个index: i, j ,k
int i =m-1, j =n-1, k =m +n -1;
while (i >= 0 && j >=0 )
{
if(nums1[i] > nums2[j])
{
nums1[k] =nums1[i];
i -=1;
}
else
{
nums1[k] =nums2[j];
j -=1;
}
k -=1;
}
if(j >= 0)
while (j>=0)
{
nums1[k] =nums2[j];
j -=1;
k -=1;
}
}
};
|
93. Restore IP Addresses
Given a string containing only digits, restore it by returning all possible valid IP address combinations.
Tips： 细节比较多，在进行 dfs 的时候
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
|
class Solution {
public:
// 对于字符串问题，如果是匹配，使用dp；如果是求全解，那么可以考虑 dfs （回溯）
vector<string> res;
vector<int> path;
// 常见的套路
vector<string> restoreIpAddresses(string s) {
dfs(0, 0, s);
return res;
}
// u 表示string s 的位置， k 表示ip的个数
void dfs(int u, int k, string &s)
{
if( u ==s.size())
{
if(k ==4)
{
// 数字转换成字符串
string ip = to_string(path[0]);
for(int i =1; i< 4; i++)
ip += '.'+ to_string(path[i]);
res.push_back(ip);
}
return ;
}
if(k >4) return ;
unsigned t =0;
for(int i =u; i< s.size() ; i++)
{
//是通过一个数字进行枚举的
t = t* 10 + s[i] -'0';
if( t >= 0 && t < 256)
{
path.push_back(t);
dfs(i +1, k +1, s);
path.pop_back();
}
}
}
};
|
python没有找到可读性比较强的方式，所以暂时只有c++ 的解法。
** Interleaving String **
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
Tips： interleaving 插入；s3 是否能够用s1 和s2 组成, len(s1) +len(s2) == len(s3) 这个样子的。行列分别表示s1 和s2 中的字母，然后 (x, y) 值表示当前的能够”走“ 通的路径。
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
|
class Solution(object):
"""
interleaving, 判断s3是否由s1和s2交叉构成，
"""
def isInterleave(self, s1, s2, s3):
"""
:type s1: str
:type s2: str
:type s3: str
:rtype: bool
"""
r, c, l =len(s1), len(s2), len(s3)
if r+c !=l:
return False
# 0 行和 0列的初始化，使用 true or false 来进行表示结果
dp =[ [True] * (c+1) for _ in range(r+1)]
for i in range(1, r+1):
dp[i][0] =dp[i-1][0] and s1[i-1] == s3[i-1]
for j in range(1, c+1):
dp[0][j] =dp[0][j-1] and s2[j-1] ==s3[j-1]
# 看到代码之后觉得很简单，
for i in range(1, r+1):
for j in range(1, c+1):
dp[i][j] = dp[i-1][j] and s1[i-1] ==s3[i+j-1] or dp[i][j-1] and s2[j-1] ==s3[i+j-1]
return dp[-1][-1]
|
方法二：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
# 从运行的结果来说，内存下降了0.1M， 但是这个时间却商城了
def isInterleave(self, s1, s2, s3):
r, c, l= len(s1), len(s2), len(s3)
if r+c != l:
return False
dp = [True for _ in range(c+1)]
for j in range(1, c+1):
dp[j] = dp[j-1] and s2[j-1] == s3[j-1]
for i in range(1, r+1):
dp[0] = (dp[0] and s1[i-1] == s3[i-1])
for j in range(1, c+1):
dp[j] = (dp[j] and s1[i-1] == s3[i-1+j]) or (dp[j-1] and s2[j-1] == s3[i-1+j])
return dp[-1]
|
** Pascal’s Triangle **
Given a non-negative integer numRows, generate the first numRows of Pascal’s triangle.
Tips: 这个是小学数学题，变成了编程题、对应好index 进行了。最后 res 可能不是正三角形（直角三角形）但一定是可以这样做的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution(object):
def generate(self, numRows):
"""
:type numRows: int
:rtype: List[List[int]]
"""
res = [[1 for _ in range(i+1)] for i in range(numRows)]
for i in range(2, numRows):
for j in range(1, i):
# 这个就是一个数学问题
# 就是上一行(i-1) 的 j-1 和j 元素的相加
res[i][j] =res[i-1][j-1] + res[i-1][j]
return res
|
Given a non-negative index k where k ≤ 33, return the kth index row of the Pascal’s triangle.
Note that the row index starts from 0.
Tips： 相比于上一个，这个只是返回了最后一行。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution(object):
# 相对比上一个，只是输出最后一行的信息， rowIndex
def getRow(self, rowIndex):
"""
:type rowIndex: int
:rtype: List[int]
"""
res =[ [1 for _ in range(i+1) ] for i in range(rowIndex+1)]
for i in range(2, rowIndex+1):
for j in range(1, i):
res[i][j ] = res[i-1][j] + res[i-1][j-1]
return res[-1]
|
** Valid Palindrome**
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
Note: For the purpose of this problem, we define empty string as valid palindrome.
Input: "A man, a plan, a canal: Panama"
Output: true
Tips： 建议使用 is.alnum() 这个python 中自带的函数，因为这种判断还是挺常见的。回文数。先是预处理，然后才是 lower() 判断。
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
|
class Solution(object):
# palindrome 回文数， alphanumeric ， 字母与数字并用的;
# 预处理之后，然后比较前后两个字符的异同
# Python isalnum() 方法检测字符串是否由字母和数字组成，这种函数只有在 歪果仁的代码中常见
# s[i] >= 'a' and s[i] <= 'z' or s[i] >= '0' and s[i] <= '9' or s[i] >= 'A' and s[i] <= 'Z':, 这个是国人的写法
# a=''.join([x for x in s if x.isalpha() or x.isdigit()]).lower() 或者这样
# 喜欢写源码
def isPalindrome(self, s):
"""
:type s: str
:rtype: bool
"""
left, right =0, len(s)-1
while left < right:
while left < right and not s[left].isalnum():
left +=1
while left < right and not s[right].isalnum():
right -=1
if s[left].lower() != s[right].lower():
return False
left +=1
right -=1
return True
|
** 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 clockwise direction, otherwise return -1.
Input:
gas = [1,2,3,4,5]
cost = [3,4,5,1,2]
Output: 3
Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.
Tips: 看着挺吓人的，但是落实到代码上，就是一个循环，当不能出发时， r (rest) 是为0，然后寻求下一个可以出发的点。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution(object):
def canCompleteCircuit(self, gas, cost):
if sum(gas) < sum(cost): return -1
index, rest = 0, 0
for i in range(len(gas)):
if gas[i] + rest < cost[i]: #这个是需要遍历整个 gas的，因为有可能开始行但是后来不行，所以开始的index 还是无法完成整个遍历
index = i +1
rest = 0
else:
rest += gas[i] - cost[i]
return index
|
** Evaluate Reverse Polish Notation **
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Division between two integers should truncate toward zero.
The given RPN expression is always valid. That means the expression would always evaluate to a result and there won't be any divide by zero operation.
Tips： 术语，逆波兰表达式（操作数在前，操作符在后）的一种形式。栈是存储操作数 和运算结果的。对于负数不能整除的，向着 0 靠拢
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 evalRPN(self, tokens):
"""
:type tokens: List[str]
:rtype: int
"""
stack =[]
for t in tokens:
if t not in "+-*/":
stack.append(int(t))
else:
right, left =stack.pop(), stack.pop()
if t =="+":
stack.append(left +right)
elif t =="-":
stack.append(left-right)
elif t =="*":
stack.append(left*right)
else:
# case like 1/(-2) 负数且不能整除
if left*right <0 and left % right!=0:
stack.append(left/right +1)
else:
stack.append(left/right)
return stack.pop()
|
** Reverse Words in a String**
Given an input string, reverse the string word by word.
Tips： 正常的思路是第一次全翻转，第二次按照 word 进行翻转。但是python 十分擅长 字符串的处理。
1
2
3
4
5
6
7
8
9
|
class Solution(object):
# 两次翻转。第一次是全翻转，然后第二次是word 翻转
# 字符串类型的算法题目，使用python 是无法get 到算法层面的 hahaha
def reverseWords(self, s):
"""
:type s: str
:rtype: str
"""
return " ".join(s.split()[::-1])
|
** Search a 2D Matrix**
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
- Integers in each row are sorted from left to right.
- The first integer of each row is greater than the last integer of the previous row.
Tips: 注意第二个条件，下一行的开头是大于上一行的末尾，所以如果 dense 一下，是可以看成大的有序，所以思路就是二叉排序。
https://leetcode.com/problems/search-a-2d-matrix/
Input:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
Output: true
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
|
class Solution(object):
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
# 如果写成 not target 是有问题，当 target ==0 的时候，这个是不成立的，所以需要看一下数据的范围
# 注意区分
if not matrix or target ==None:
return False
rows, cols=len(matrix), len(matrix[0])
low, high =0, rows*cols-1 # 总的二叉
while low <=high:
mid =(low +high) /2
num =matrix[mid/cols][mid%cols]
if num ==target:
return True
elif num< target:
low =mid +1
else:
high =mid -1
return False
|
** Search a 2D Matrix II**
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
- Integers in each row are sorted in ascending from left to right.
- Integers in each column are sorted in ascending from top to bottom.
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
Tips: 注意区分和上一道题目的第二点的区别。这个只能是一步步走，下面的程序是从右上方开始走，如果 target 大则向下直走，否则左走。可以有两种初始化方式，一种是右上角，一种是左下角。
https://leetcode.com/problems/search-a-2d-matrix-ii/
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
|
class Solution(object):
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
# 一开始的时候不知道使用什么遍历方式，因为 for 好像不太行，应该使用 while 基于条件遍历
if matrix ==[]:
return False
rows, cols =len(matrix)-1, len(matrix[0])-1
"""
row, col = 0, cols # start points
while row <= rows and col >= 0:
if matrix[row][col] == target:
return True
elif matrix[row][col] < target:
row +=1
else:
col -=1
"""
# 还有一种初始化方式
row, col =rows, 0
while row >=0 and col <= cols:
if matrix[row][col] ==target:
return True
elif matrix[row][col] < target:
col +=1
else:
row -=1
return False
|
** Kth Smallest Element in a Sorted Matrix **
Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.
Tips: 主要是看到 example 中的数据，有两种类型，一种是可以把matrix dense 之后依然是有序，另一种不是。这个是属于前者。下面这种解法比较新颖，使用heapq 进行操作，遍历k th 就得到了kth 最小。
···python
class Solution(object):
# 有一种方法是初始化为右上角，然后小往左走，大往下走
# 这个默认求解的k smallest，所以python 中heapq 默认也是小根堆，所以
def kthSmallest(self, matrix, k):
"""
:type matrix: List[List[int]]
:type k: int
:rtype: int
"""
heap, res, n =[(matrix[0][0], 0, 0)], 0, len(matrix)
for k in range(1, k+1): # 这个是次数
res, row, col =heapq.heappop(heap)
# 问题在于这里并没有体现了 row col相应的变化 +1 这类东西
# 这个是通过 heapq 不断地push 和pop 来得到相应的 row col 然后进行res 的获取的
if not row and col< n-1:
heapq.heappush(heap, (matrix[row][col+1], row, col+1))
if row< n-1:
heapq.heappush(heap, (matrix[row+1][col], row+1, col))
return res
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
|
** Evaluate Reverse Polish Notation**
> Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Tips: 逆波兰又称之为后缀表达式，操作符置于操作数后面，这个前后是以“操作符” 进行定义的。解题思路，如果是操作数，那么就压栈，如果是操作符，那么弹出进行运算。
```python
class Solution(object):
def evalRPN(self, tokens):
stack =[]
operators =['+', '-', '*', '/']
for token in tokens:
if token not in operators: #这种比较nice exact
stack.append(int(token)) # 细节 string to int
else:
if len(stack) <2:
return False
second =stack.pop()
first =stack.pop()
if token =="+":
result =first +second
elif token =="-":
result =first -second
elif token =="*":
result =first *second
else:
# 除法向来处理就比较麻烦
if second ==0:
return False
# 这个是操作中的abs 没有改变原来的值，所以比较nice
result =abs(first)/abs(second)
if first *second <0:
result =-result
stack.append(result)
# 最后只有一个result 值，所以十分简洁
if len(stack) !=1:
return False
return stack[0]
|
** Excel Sheet Column Number**
Given a column title as appear in an Excel sheet, return its corresponding column number.
Tips: 在于 char 和num 的对应关系。ord() 用于 char 转成int 这种库函数还是要有的。 可以看成 26 进制。
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution(object):
def titleToNumber(self, s):
"""
:type s: str
:rtype: int
"""
res =0
for char in s:
res =res*26 +(ord(char)- ord('A') +1)
return res
|
** Largest Number **
Given a list of non negative integers, arrange them such that they form the largest number.
Tips: string 类型组合成的数字是最大的。 在string 里面 ‘9’ > ‘88888’ 这个是成立，所以这个特性可以处理这个题目，很巧妙。
1
2
3
4
5
6
7
8
9
10
11
|
class Solution(object):
def largestNumber(self, nums):
"""
:type nums: List[int]
:rtype: str
"""
nums =map(str, nums)
nums.sort(cmp =lambda a, b :cmp(a+b, b+a), reverse =True) # 降序
# 可能出现 00 这样的字符串，所以是先 int 然后再string，感觉这个不是算法的味道
return str(int(''.join(nums)))
|
Longest Substring with At Least K Repeating Characters
Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.
Tips: 这个codes 中的else 还是相当的牛逼，第一次见这种写法的。如果 for 循环中的条件不成立，else。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution:
def longestSubstring(self, s, k):
"""
:type s: str
:type k: int
:rtype: int
"""
stack = []
stack.append(s)
ans = 0
while stack:
s = stack.pop()
for c in set(s):
if s.count(c) < k:
stack.extend([z for z in s.split(c)])
break
else:
ans = max(ans, len(s))
return ans
|
** Longest Increasing Path in a Matrix**
Given an integer matrix, find the length of the longest increasing path.
From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).
Tips: dfs, 判断条件是 val > matrix[i][j]
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 longestIncreasingPath(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: int
"""
# 表示以这点为终点的 路径是有多长
# 这个逻辑上是比较简单的， 就是dfs()，然哦吼如果从任意一点出发 range() range()，
# 使用 dfs() ，如果是value > matrix[][]，就直接返回了 dp[i][j]
def dfs(i, j):
if not dp[i][j]:
val = matrix[i][j]
# i-1 的时候要大于0 i+1的时候要i < M 这样的操作
dp[i][j] = 1 + max(
dfs(i - 1, j) if i and val > matrix[i - 1][j] else 0,
dfs(i + 1, j) if i < M - 1 and val > matrix[i + 1][j] else 0,
dfs(i, j - 1) if j and val > matrix[i][j - 1] else 0,
dfs(i, j + 1) if j < N - 1 and val > matrix[i][j + 1] else 0)
return dp[i][j]
if not matrix or not matrix[0]: return 0
M, N = len(matrix), len(matrix[0])
dp = [[0] * N for i in range(M)] # 以该点为终点的 increasing path 有多少个
return max(dfs(x, y) for x in range(M) for y in range(N))
|
Word Ladder
Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:
Only one letter can be changed at a time.
Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
可以把每个单词当做图中的一个点，如果存在从一个单词到另一个单词的转化方式，那么就表示为两点之间有路径。可以归结为单源最短路，求解单源最短路通常有 BFS 和Dijkstra 算法那，区别在于在有权重的图中不能使用BFS， 在本题中字符串之间是没有权重的，所以可以使用BFS。在时间复杂度上 BFS 是 $O(n)$， Dijkstra最多可以优化到 $mlogn$。
使用python 实现。BFS 的过程中每个点都需要遍历，每次遍历都是需要枚举所有节点，所以需要 $n^2$， 假设单词的长度是 $L$，那么总的时间复杂度是 $O(n^2L)$，注意其中 $26 * L^2$ 是 $L^2$
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(object):
def ladderLength(self, beginWord, endWord, wordList):
"""
:type beginWord: str
:type endWord: str
:type wordList: List[str]
:rtype: int
"""
wordList =set(wordList)
queue =collections.deque([(beginWord, 1)])
visited =set()
alpha =string.ascii_lowercase # 'abcd..z'
while queue:
word, length =queue.popleft()
if word == endWord:
return length
for i in range(len(word)):
for ch in alpha:
new_word =word[:i] +ch+word[i+1:]
if new_word in wordList and new_word not in visited:
queue.append((new_word, length+1))
visited.add(new_word)
return 0
|
** Fraction to Recurring Decimal**
Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.
If the fractional part is repeating, enclose the repeating part in parentheses.
Tips: 分数变成小数
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
|
class Solution(object):
# 主要是考察分情况讨论，这样是比较多的
# 就是在拼接呀
def fractionToDecimal(self, numerator, denominator):
"""
:type numerator: int
:type denominator: int
:rtype: str
"""
res =''
if numerator % denominator ==0:
return str(numerator/denominator)
if numerator* denominator <0:
res += '-'
numerator, denominator =abs(numerator), abs(denominator)
res += str(numerator/denominator)
res +='.'
numerator %= denominator
i =len(res)
table ={}
# 下面描述的就是辗转相除的过程， 使用 {} 进行存储
while numerator !=0:
if numerator not in table:
table[numerator] =i
else:
i =table[numerator]
res =res[:i] +'('+res[i:]+')'
return res
numerator =numerator*10
res += str(numerator/denominator)
numerator %= denominator
i +=1
return res
|
** Reverse Bits**
Reverse bits of a given 32 bits unsigned integer.
Tips: 与操作和左移操作 ( & and «) 是常见的 bit operation中用到的
···python
class Solution:
# @param n, an integer
# @return an integer
# 没有什么说的， 二级制操作，注意输入和输出都是 integer
# One small thing is the plus operator can be replaced by "bitwise or", aka "|".
# Just generate the answer bit by bit, do not use things like "% 2" or "2 ** k" or "bin". Bit manipulation is a lot faster.
def reverseBits(self, n):
ans =0
# 从后往前处理，所以这就reverse 了
for i in range(32):
# n&1 是取最后一位
# ans <<1 左移一位，类似乘2
ans += n &1
if i ==31:
return ans
n >>= 1
ans <<= 1
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
[139. Word Break](https://leetcode.com/problems/word-break/)
> Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
对于字符串匹配的问题，一般是可以先考虑 dp, dp[i] 表示前i 个字符串是否可以使用 wordDict 分开
```python
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
words =set(wordDict)
dp =[False for _ in range(len(s)+1 )]
dp[0] =True
for i in range(1, len(s) +1):
for j in range(i):
if dp[j] and s[j: i] in words:
dp[i] =True
break
return dp[-1]
|
c++ 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
int n =s.size();
vector<bool> dp(n +1, false);
unordered_set <string> hash(wordDict.begin(), wordDict.end());
dp[0] =true;
for(int i =1; i <=n ; i++)
for(int j =0; j< i; j++)
{
if (dp[j] ==true&&hash.find(s.substr(j, i -j)) != hash.end() )
{
dp[i] =true;
break;
}
}
return dp[n];
}
};
|
Word Break II
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.
Tips : dfs
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
|
class Solution(object):
# 上一题是返回 true or false，这个是要求是路径，那么最直接的就是dfs(), 不能使用dp了
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: List[str]
:rtype: List[str]
"""
return self.dfs(s, wordDict, {})
def dfs(self, s, wordDict, memo):
# 这个memo 就是某长度的字符串，在之前的dfs 中是否存在过
# 'penapple': ['pen apple'], 'applepenapple': ['apple pen apple'
if s in memo:
return memo[s]
if not s:
return []
res =[]
for word in wordDict:
# 这种直接从 dictionary 中寻找要比 从string 中拼凑快一些
if not s.startswith(word): # 这个就是最贪婪的找开头的python 句子
continue
if len(word) ==len(s): # 包含且长度相同，那么 res.append() 就是这个操作了
res.append(word)
else:
rest =self.dfs(s[len(word):], wordDict, memo) # 如果原来的 s 比较长 那么就切分了
# 这种不收 递归影响的思维还是挺牛逼的 哈哈
for item in rest:
item =word +' '+item
res.append(item)
memo[s] =res
return res
|
太难了，没有看懂，下回使用这个吧。
LeetCode 140. Word Break II Solution 题解
** Palindrome Partitioning**
Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
Tips: dfs, 其中 ispa 写的是比较简洁的
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
|
class Solution(object):
# 感觉这个有点难度呀
# 所有值的一般是 dfs() 这个还是得不断的加强认识的，
def partition(self, s):
"""
:type s: str
:rtype: List[List[str]]
"""
res =[]
self.dfs(s, [], res)
return res
def dfs(self, s, path, res):
if not s:
res.append(path)
return
# 关键是这里的理解， path 是不断的增加的，并且 s[I:] 这个是不断的介绍的，
# 先是要求 s[:i] 是 palindrome 然后递归 s[i:] 是palindrome ，整体上是比较nice的
for i in range(1, len(s)+1):
if self.isPal(s[:i]):
self.dfs(s[i:], path+[s[:i]], res)
def isPal(self, s):
return s ==s[::-1]
|
** Word Search II**
Given a 2D board and a list of words from the dictionary, find all words in the board.
Each word must be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.
Tips: 使用字典树
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
49
50
51
52
53
54
|
class TrieNode():
def __init__(self):
self.children = collections.defaultdict(TrieNode)
self.isWord = False
class Trie():
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for w in word:
node = node.children[w]
node.isWord = True
def search(self, word):
node = self.root
for w in word:
node = node.children.get(w)
if not node:
return False
return node.isWord
# 上面在上一道题目中就应该记住，这个是一道经典的题目
class Solution(object):
def findWords(self, board, words):
res = []
trie = Trie()
node = trie.root
for w in words:
trie.insert(w)
# 先是insert，然后在每一个点进行查找，最后看res
for i in range(len(board)):
for j in range(len(board[0])):
self.dfs(board, node, i, j, "", res)
return res
def dfs(self, board, node, i, j, path, res):
if node.isWord:
res.append(path)
node.isWord = False
if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]):
return
tmp = board[i][j]
node = node.children.get(tmp)
if not node:
return
board[i][j] = "#"
self.dfs(board, node, i + 1, j, path + tmp, res)
self.dfs(board, node, i - 1, j, path + tmp, res)
self.dfs(board, node, i, j - 1, path + tmp, res)
self.dfs(board, node, i, j + 1, path + tmp, res)
board[i][j] = tmp
|
** Valid Anagram**
Given two strings s and t , write a function to determine if t is an anagram of s.
Tips: dictionary 的应用
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):
# 这个和旋转数组 感觉上是差不多的呀
# 解答的时候，应该从 dictionary 的角度考虑
def isAnagram(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
dic ={}
# dic =collections.defaultdic(int) 和上面的唯一差别就是，直接使用 dic[char] +=1 这样的操作
# 不用判断是否存在 这样的操作
for n in s:
if n not in dic:
dic[n] =1
else:
dic[n] +=1
for n in t:
if n not in dic:
return False
else:
dic[n] -=1
"""
for n in dic:
if dic[n]!=0:
return False
return True
"""
for value in dic.values():
if value !=0:
return False
return True
|
** First Unique Character in a String**
Given a string, find the first non-repeating character in it and return it’s index. If it doesn’t exist, return -1.
Tips: 注意是第一个 non-repeating的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution(object):
# 这个不重复 是整体之后的不重复，而不是左右的不重复，是全局的
# 我的想法使用dict
def firstUniqChar(self, s):
"""
:type s: str
:rtype: int
"""
dic ={}
seen =set()
for index, ch in enumerate(s):
if ch not in seen:
dic[ch] =index
seen.add(ch)
elif ch in dic:
del dic[ch] # 这个是通过更新index 达到的
# 因为题目中提到的是 第一个 non-repeating
|
Reverse String
Write a function that reverses a string. The input string is given as an array of characters char[].
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
Tips : in-place 操作 pointer
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution(object):
# 我反手一个reverse() 过去，有问题吗
# sting is immutable, cannot reverse in-place
def reverseString(self, s):
"""
:type s: List[str]
:rtype: None Do not return anything, modify s in-place instead.
"""
left, right =0, len(s)-1
while left < right:
s[left], s[right] =s[right], s[left]
left +=1
right -=1
|
除了上面那种判别条件，还可以根据交换的次数进行判别，下面这种写法更加直观。
1
2
3
4
5
6
7
8
9
10
|
class Solution(object):
def reverseString(self, s):
if not s: return s
l, r = 0, len(s) -1
counts =l +r+1 >>1;
while counts:
s[l], s[r] =s[r], s[l]
l += 1;
r -= 1;
counts -=1;
|
使用c++ 实现，该版本代码比python 都要简洁。
1
2
3
4
5
6
7
8
|
class Solution {
public:
void reverseString(vector<char>& s) {
int l =0, r =s.size() -1;
while (l <r)
swap(s[l++], s[r--]);
}
};
|
2. Add Two Numbers
时间复杂度是$O(n)$。模拟加法运算，从位数小的开始，注意处理进位的情况。使用 dummy 头指针是linked list 中常见的技巧，直接返回头指针的下一个就是答案。
注意三点
- dummy
- 加法的计算过程 （carry 最后的处理）
- linked list 的遍历
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
|
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode * dummy =new ListNode(-1);
ListNode * head = dummy;
int carry =0;
while(l1 || l2 || carry ==1)
{
int val1 = l1 ? l1 ->val :0;
int val2 = l2 ? l2 ->val : 0;
int total = val1 + val2 + carry;
carry = (total)/10;
head ->next = new ListNode(total %10);
head =head ->next;
if (l1) l1 =l1 ->next;
if(l2 ) l2 =l2 ->next; //这个if 判断是细节
}
return dummy->next;
}
};
|
python 解法
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
|
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
dummy =ListNode(-1)
head =dummy
carry =0
while l1 or l2:
v1 =l1.val if l1 else 0
v2 =l2.val if l2 else 0
total =v1 +v2 +carry
carry = total // 10
head.next =ListNode(total %10)
head =head.next
if(l1): l1 =l1.next
if(l2): l2 =l2.next
if(carry): head.next =ListNode(1)
return dummy.next
|
4. Median of Two Sorted Arrays
hard 级别的题目，题目中要求时间复杂度是$O( \log (m +n))$，并且是有序的数组，那么需要使用二分的思想。当单个有序数组中查找中位数时候比较简单，当n 为偶数时候为中间两个数字的平均数；当n 为奇数时候为中间的数字。为了简化代码，这里使用 $m+n +1 /2$ 和$m +n +2/2$ 来统一表示。
定义一个函数求解两个有序数组中第 k 个元素。需要处理一些边界情况，如开始的index 大于数组的长度；当k 为1 的时候。如果当前数组的中位数存在（因为两个数组的第k个元素和一个数组的第k 个元素是不一样的），那么取出各自的中位数，如果一个数组中的中位数小，那么该数组的前 $k/2$个元素都不需要考虑，递归进行。
详细讲解 。属于hard 级别的题目，好好理解。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(), n = nums2.size(), left = (m + n + 1) / 2, right = (m + n + 2) / 2;
return (findKth(nums1, 0, nums2, 0, left) + findKth(nums1, 0, nums2, 0, right)) / 2.0;
}
int findKth(vector<int>& nums1, int i, vector<int>& nums2, int j, int k) {
if (i >= nums1.size()) return nums2[j + k - 1];
if (j >= nums2.size()) return nums1[i + k - 1];
if (k == 1) return min(nums1[i], nums2[j]); # 这个是最后return 的语句
int midVal1 = (i + k / 2 - 1 < nums1.size()) ? nums1[i + k / 2 - 1] : INT_MAX; // index 的范围是需要注意的
int midVal2 = (j + k / 2 - 1 < nums2.size()) ? nums2[j + k / 2 - 1] : INT_MAX;
if (midVal1 < midVal2) {
return findKth(nums1, i + k / 2, nums2, j, k - k / 2);
} else {
return findKth(nums1, i, nums2, j + k / 2, k - k / 2);
}
}
};
|