2021 年剑指offer 刷题总结。
03. 数组中重复的数字
c++ 实现
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution {
public:
int findRepeatNumber(vector<int>& nums) {
unordered_map<int, int> dic;
for(auto num: nums)
{
if (dic[num]) return num;
dic[num] +=1;
}
return -1;
}
};
|
练习c++ 中的set 的使用。使用 set 更加符合逻辑上的定义，因为是判断有没有，而非统计数量。set 的函数 count() 和 insert()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution {
public:
int findRepeatNumber(vector<int>& nums) {
//unordered_map<int, int> dic;
unordered_set<int> dic;
for(auto num: nums)
{
if (dic.count(num)) return num;
//if (dic[num]) return num;
dic.insert(num);
}
return -1;
}
};
|
使用空间优化成 $O(1)$，利用nums 的所有数字都是 在 {0, n-1} 区间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution {
public:
int findRepeatNumber(vector<int>& nums) {
// for while 循环可曾记得
int n =nums.size();
for(int i =0; i< n; i++)
{
// 当 index 和nums[i] 不一样的时候
while(i != nums[i])
{
if(nums[i] == nums[nums[i]]) return nums[i];
swap(nums[i], nums[nums[i]]);
}
}
return -1;
}
};
|
使用python 实现
（下面注释共有 三种方法，其中2和 3是可以的，但是 1是不行的）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution(object):
def findRepeatNumber(self, nums):
n =len(nums)
for i in range(n):
while i != nums[i]:
if nums[i] == nums[nums[i]]:
return nums[i]
#(1)nums[i], nums[nums[i]] =nums[nums[i]], nums[i]
t =nums[i]
nums[i] =nums[t]
nums[t] =t
#(3) nums[nums[i]], nums[i] = nums[i], nums[nums[i]]
return -1
|
Python 为什么只需一条语句“a,b=b,a”，就能直接交换两个变量？
总结如下：
- Python 能在一条语句中实现多重赋值，这是利用了序列解包的特性
- Python 能在一条语句中实现变量交换，不需引入中间变量，在变量数少于 4 个时（3.8 版本起是少于 5 个），CPython 是利用了 ROT_* 指令来交换栈中的元素，当变量数超出时，则是利用了序列解包的特性。
- 序列解包是 Python 的一大特性，但是在本文的例子中，CPython 解释器在小小的操作中还提供了几个优化的指令，这绝对会超出大多数人的认知
剑指 Offer 04. 二维数组中的查找
python 解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution(object):
def findNumberIn2DArray(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
# 时间复杂度可以优化到 $O(m +n)$
if matrix ==[]: return False
rows, cols = len(matrix) , len(matrix[0])
i , j =0, cols -1
while i < rows and j >=0:
if matrix[i][j] == target:
return True
elif matrix[i][j] < target:
i += 1
else:
j -= 1
return False
|
c++ 解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution {
public:
bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
//if (matrix == None) return false;
//if (matrix == null ) return false;
int rows = matrix.size();
if (rows ==0) return false;
int cols = matrix[0].size();
int i =0, j =cols -1;
while (i < rows && j >= 0)
{
if(matrix[i][j] == target)
return true;
else if (matrix[i][j] > target)
j -= 1;
else
i +=1;
}
return false;
}
};
|
剑指 Offer 07. 重建二叉树
使用 map 预处理 inorder 数组，以便于快速访问。整个事件复杂度是 $O(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
|
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
// 递归求解 树结构的问题；
unordered_map<int, int> pos;
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int n =preorder.size();
for(int i =0; i< n; i++)
pos[inorder[i]] =i;
return dfs(preorder, inorder, 0, n-1, 0, n -1);
}
TreeNode* dfs(vector<int>& pre, vector<int>& in, int pl, int pr, int il, int ir )
{
if(pl > pr) return NULL;
int len = pos[pre[pl]] -il;
TreeNode* root =new TreeNode(pre[pl]);// c++ 中使用 new 关键词
root -> left = dfs(pre, in, pl +1, pl +len,il, il+len-1 ); // [p1+1, p1+len+1] 本质上就是 index
root -> right =dfs(pre, in, pl +len+1, pr, il +len +1, ir);
return root;
}
};
|
python 解法
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:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# python 中对数组可以使用切片，编程更加简便
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
n =len(preorder)
return self.dfs(preorder, inorder)
def dfs(self, pre, ino):
if len(pre) ==0: return None
root = TreeNode(pre[0])
index =ino.index(pre[0])
root.left = self.dfs( pre[1:index +1], ino[:index])
root.right =self.dfs( pre[index +1:], ino[index+1:])
return root
|
剑指 Offer 05. 替换空格
简单题目。c++ 解法
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution {
public:
string replaceSpace(string s) {
string res;
for(auto ch: s)
{
if (ch ==' ') res += "%20";
else res += ch;
}
return res;
}
};
|
python 解法
1
2
3
4
5
6
7
8
9
|
class Solution:
def replaceSpace(self, s: str) -> str:
res =""
for ch in s:
if ch ==' ':
res += "%20"
else:
res += ch
return res
|
剑指 Offer 06. 从尾到头打印链表
python 解法，从排名效率上看，应该不是最高的。所以，查找一下。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class ListNode:
def __init__(self, val):
self.val =val
self.next = None
class Solution:
def reversePrint(self, head: ListNode) -> List[int]:
res =[]
while head:
res.append(head.val)
head =head.next
return res[::-1]
|
c++ 解法。注意反向迭代器的使用。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
vector<int> reversePrint(ListNode* head) {
vector<int> res;
while(head)
{
res.push_back(head -> val);
head =head -> next;
}
return vector<int>(res.rbegin(), res.rend());
}
};
|
c++ 中的结构体
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
|
#include<iostream>
using namespace std;
struct Employee{
string name;
int vacationDays;
Employee(string name_ ="", int day =0)// 构造函数
{
name =name_;
vacationDays =day;
}
};
// 声明结构体
struct Date{
int month;
int day;
int year;
// 有默认的构造函数
};
struct Student{
int num; // 声明不同类型的变量
char name[20];
char sex;
int age;
Date birthday; // 结构体可以嵌套
float score;
char addr[30];
};
int main(){
Student two = {1, "dianzi", 'm', 19, 10, 01, 1993, 100, "Beijing"};
Student one =two;
cout << one.num << endl;
cout << one.name << endl;
cout << one.sex << endl;
cout<<one.birthday.month<<"/"<<one.birthday.day<<"/"<<one.birthday.year<<endl;
return 0;
}
|
剑指 Offer 09. 用两个栈实现队列
队列对应的操作是先进先出，栈对应的操作是后进先出。 stk1 接受数据列表， stk2 用来弹出列表，当弹出的时候，需要再次从 stk1 中弹出数据，这样两次 后进先出 就转换成了先进先出。
python 解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class CQueue:
def __init__(self):
self.stk1 =[]
self.stk2 =[]
def appendTail(self, value: int) -> None:
self.stk1.append(value)
def deleteHead(self) -> int:
if self.stk2:
return self.stk2.pop()
elif self.stk1:
while self.stk1:
self.stk2.append(self.stk1.pop())
return self.stk2.pop()
return -1
# Your CQueue object will be instantiated and called as such:
# obj = CQueue()
# obj.appendTail(value)
# param_2 = obj.deleteHead()
|
c++
需要注意的是 c++ 使用全局变量；然后 stack 的访问是先用 top() 获取元素， 然后再用 pop() 去除元素。
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
|
class CQueue {
public:
// c++ 中不用 self 关键词，但需要使用全局变量
stack<int> stk1, stk2;
CQueue() {
}
void appendTail(int value) {
stk1.push(value);
}
int deleteHead() {
if(stk2.size())
{
int res =stk2.top();
stk2.pop();
return res;
}
else if ( stk1.size())
{
while (stk1.size())
{
int val =stk1.top();
stk1.pop();
stk2.push(val);
}
int res = stk2.top();
stk2.pop();
return res;
}
return -1;
}
};
/**
* Your CQueue object will be instantiated and called as such:
* CQueue* obj = new CQueue();
* obj->appendTail(value);
* int param_2 = obj->deleteHead();
*/
|
剑指 Offer 10- I. 斐波那契数列
c++ 解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution {
public:
// 简单题目， 时间复杂度是 O(n) 空间可以优化成 O(1)
int fib(int n) {
const int MOD = 1000000000 +7;
if(n <=1) return n;
int a, b;
a =0;
b=1;
int t ;
for(int i =1; i< n; i++)
{
t =(a +b) % MOD;
a =b;
b =t;
}
return t %MOD ;
}
};
|
python 解法。 python 中可以使用简化的形式书写。注意 python 中是以元组的形式进行赋值。
1
2
3
4
5
6
7
8
9
10
11
|
class Solution:
def fib(self, n: int) -> int:
MODE = 1000000000 +7;
if n <=1: return n
a, b =0, 1
for i in range(1,n):
#t = (a+b ) %MODE
#a =b
#b =t
b, a =(a+b) %MODE, b
return b % MODE
|
剑指 Offer 10- II. 青蛙跳台阶问题
开始使用 dfs 的思路，超时了；后来写成的循环的模式。
python 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution:
# 这个是递归做法
def __init__(self):
self.MODE = 1e9+7
def numWays(self, n: int) -> int:
if n ==0: return 1
elif n <=2: return n
a, b = 1, 2
for i in range(3, n+1):
c = a+b % self.MODE
a =b
b =c
return int(b % self.MODE)
|
c ++ 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution {
public:
const int MODE = 1e9 +7;
int numWays(int n) {
if(n ==0 ) return 1;
else if (n <= 2) return n;
int a = 1, b =2;
int c;
for(int i =3; i<= n; i++)
{
c = (a +b) % MODE;
a =b ;
b = c;
}
return c % MODE;
}
};
|
剑指 Offer 11. 旋转数组的最小数字
时间复杂度需要满足： $O(logn)$， 这个数组是部分有序，所以可以采用二分的思路。
c++ 求解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution {
public:
int minArray(vector<int>& numbers) {
int n =numbers.size() -1;
// 先去重
while (n && numbers[0] == numbers[n]) n -=1;
// 特别的case：如果是正序，那么直接输出 numbers[0]
if(numbers[0] < numbers[n]) return numbers[0];
int l =0, r =n;
while(l <r)
{
int mid = l +r >>1;
if( numbers[0] > numbers[mid]) r =mid;
else
l = mid +1;
}
return numbers[l];
}
};
|
python 求解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution:
def minArray(self, numbers: List[int]) -> int:
n =len(numbers) -1
#注意两种特殊的case: 去重和正序
while(n and numbers[0] == numbers[n]):
n -=1
if(numbers[0] < numbers[n]): return numbers[0]
l, r =0, n
while l <r:
mid =l +r >>1;
if numbers[0] <= numbers[mid]:
l =mid +1
else:
r =mid
return numbers[l]
|
剑指 Offer 12. 矩阵中的路径
dfs 解法最重要的是搜索顺序。这里首先枚举起点，然后按照上下左右的顺序进行遍历，因为是不能重复，所以每个点有三种可能性。时间复杂度是 $O(n^2 3^k)$，其中 n 表示 board 的长宽， k 表示字符串的长度。
c++ 解法
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 {
public:
// dfs 中最重要的是搜索顺序。首先枚举起点，然后按照顺序上下左右进行枚举
bool exist(vector<vector<char>>& board, string word) {
int rows = board.size(), cols = board[0].size();
for( int i =0 ; i< rows; i++)
{
for(int j =0 ; j< cols; j++)
{
if( dfs(board, word, 0 ,i, j)) return true;
}
}
return false;
}
bool dfs(vector<vector<char>>& board, string word, int n , int row, int col)
{
// 跳出条件
if(board[row][col] != word[n]) return false;
if(n ==word.size() -1) return true; //遍历完成
char t = board[row][col];
board[row][col] ='*';
int a[4] ={-1, 0, 1, 0}, b[4] ={0, 1, 0, -1};
for(int k =0 ; k <4; k ++)
{
int r = row + b[k], c = col + a[k];
if(r >=0 && r < board.size() && c >= 0 && c < board[0].size() )
{
if (dfs(board, word, n +1, r, c)) return true;
}
}
board[row][col] =t;
return false;
}
};
|
python 解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution:
def dfs(self, board: List[List[str]], word : str, n : int, x: int , y : int) -> bool:
if(board[x][y] != word[n]): return False
if(n ==len(word) -1): return True;
ch = board[x][y]
board[x][y] ='#'
dx =[0, 1, 0, -1]
dy =[-1, 0, 1, 0]
for k in range(4):
a, b = dx[k] + x, dy[k] + y
if (a >=0 and a< len(board) and b >=0 and b <len(board[0])):
if (self.dfs(board, word, n +1, a, b)): return True
board[x][y] =ch
return False
def exist(self, board: List[List[str]], word: str) -> bool:
for i in range(len(board)):
for j in range(len(board[0])):
if self.dfs(board, word, 0, i, j ):
return True
return False
|
剑指 Offer 13. 机器人的运动范围
枚举的方法是不行的。
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:
# 从数据范围上看，n^2 的时间复杂度就可以满足要求
# python3 中使用 // 表示整除
# 这个不能按照行列进行枚举，因为是从 (0, 0) 开始移动的，不是选点，还得是 dfs
def is_valid(self, m: int , n :int , k :int) -> bool:
s =0
while m:
s += m%10
m =m // 10
while n:
s += n %10
n =n //10
if s <=k:
return True
return False
def movingCount(self, m: int, n: int, k: int) -> int:
count =0
for i in range(m):
for j in range(n):
if self.is_valid(i,j, k):
count += 1
return count
|
需要按照 dfs 的思路去求解。 时间复杂度是 $O(mn)$ ，因为这里设置了 visited 数组，所以每个点都只能被访问一次。
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
27
|
class Solution:
def __init__(self):
self.cnt =0
def get_sum(self, x, y):
s =0
while x :
s += x %10
x = x//10
while y:
s += y %10
y = y//10
return s
def dfs(self, x,y, m, n, k, is_visited):
if x == m or y == n or is_visited[x][y] : return
is_visited[x][y] =True
if self.get_sum(x, y) >k: return
self.cnt += 1
self.dfs(x +1, y, m, n, k, is_visited)
self.dfs(x, y +1, m, n, k,is_visited)
def movingCount(self, m: int, n: int, k: int) -> int:
is_visited =[[False] * n for _ in range(m)]
self.dfs(0, 0, m, n, k, is_visited)
return self.cnt
|
如果没有写成一个类
cnt 在子函数中是可以直接访问。如果修改访问 cnt 的变量名，那么首先需要使用 global 定义，然后才能修改。
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
|
cnt =0 # 首先在这里申明
def get_sum(x, y):
s =0
while x :
s+= x %10
x = x//10
while y :
s += y %10
y = y //10
return s
def dfs(x, y, m, n, k, is_visited):
if x ==m or y ==n or is_visited[x][y] : return
is_visited[x][y] =True
if get_sum(x, y) >k: return
global cnt # 然后在这里申明
cnt += 1
dfs(x +1, y, m, n, k, is_visited)
dfs(x, y +1, m, n, k, is_visited)
def moving_count(m, n, k):
is_visited =[[False] *n for _ in range(m)]
dfs(0, 0, m, n, k, is_visited)
return cnt
#print(moving_count(2, 3, 1))
print(moving_count(3, 1, 0))
|
c++ 解法
（重点学习一下c++ 中多重数组的定义和初始化）
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
|
class Solution {
public:
int count =0;
int dfs(int m, int n, int i, int j, int k, vector<vector<bool>>& visited)
{
if(i >= m || j >=n || visited[i][j]) return 0;
visited[i][j] = true;
int ii =i, jj =j;
int s =0;
while(i)
{
s += i %10;
i =i /10;
}
while(j )
{
s += j %10;
j =j /10;
}
if (s <=k)
{
count +=1;
dfs(m, n, ii +1, jj, k, visited);
dfs(m, n, ii, jj +1, k, visited);
}
return 0;
}
int movingCount(int m, int n, int k) {
// 二维数组的声明
vector<vector<bool>> visited(m, vector<bool>(n));
// 二维数组的初始化
for(int i =0 ; i< m ; i++)
for(int j =0; j< n; j++)
visited[i][j] =false;
dfs(m, n, 0, 0, k, visited);
return count;
}
};
|
剑指 Offer 14- I. 剪绳子
这个是一个经典的数学题。思路：这些数越接近平均数，乘积越大。可以证明尽可能选择3，然后选择 2 和4。相关证明可以查看：https://www.acwing.com/solution/content/731/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution {
public:
// 这个有一个算法：尽可能选择3，剩下的去选择2 和4
int cuttingRope(int n) {
if(n <=3) return 1 * (n-1);
int res =1;
if(n %3 ==1) res *=4, n -=4;
else if(n %3 ==2) res *=2, n -=2;
while(n)
{
res *= 3;
n -=3;
}
return res;
}
};
|
python 解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution:
# 这里并没有限制分成的段数，所以可以
def cuttingRope(self, n: int) -> int:
if n<=3: return 1 *(n-1)
res =1
if(n %3 ==1):
res *=4
n -= 4
elif n %3 ==2:
res *= 2
n -= 2
while n:
res *= 3
n -= 3
return res
|
剑指 Offer 14- II. 剪绳子 II
剑指 Offer 14- I. 剪绳子 和 剑指 Offer 14- II. 剪绳子 II 的区别：后者的数据范围更大。因为最优的时间复杂度是 $log(n)$，所以可以复用上述的算法。
c++ 解法
c++ 中注意数据类型的范围。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution {
public:
const int MOD = 1e9 +7;
int cuttingRope(int n) {
if(n <=3) return 1 *(n -1);
long long res =1;
if(n %3 ==1) res *=4, n -=4;
else if(n %3 ==2) res *=2, n -=2;
while(n)
{
//res = (res*3 )% MOD;
res =res *3 % MOD;
n -=3;
}
return (int)res % MOD;
}
};
|
python 解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution:
def cuttingRope(self, n: int) -> int:
MOD = 1e9 +7
if n <=3: return 1*(n-1)
res =1
if n %3 ==1:
res *= 4
n -= 4
elif n %3 ==2:
res *= 2
n -= 2
while n:
res = res *3 % MOD
n -= 3
return int(res %MOD)
|
剑指 Offer 15. 二进制中1的个数
时间复杂度是$O(n)$
c++ 解法，遍历二进制和遍历十进制是一样的规则。当从后往前遍历的时候，十进制是 /10，二进制是 /2。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution {
public:
// 二进制在 c++ 中不知道如何遍历
int hammingWeight(uint32_t n) {
int res =0;
while(n)
{
res += n &1;
n =n /2;
}
return res;
}
};
|
python 解法，注意 python 中的整除。
1
2
3
4
5
6
7
|
class Solution:
def hammingWeight(self, n: int) -> int:
res =0
while n:
res += n&1
n =n // 2
return res
|
剑指 Offer 16. 数值的整数次方
求解 $m^k %p$ ，时间复杂度是$O(log k)$
c++ 解法
这个是一个模板题：快速幂。可以在 $logn $ 时间内完成。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution {
public:
double myPow(double x, int n) {
typedef long long LL;
double res =1, t =x;
bool is_minus = n <0;
for( LL k =abs(n) ; k ; k >>= 1)
{
if(k & 1) res *= t;
t =t *t;
}
if(is_minus) res =1.0 /res;
return res;
}
};
|
python 解法
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution:
def myPow(self, x: float, n: int) -> float:
is_minus = n < 0
res =1.0
t =x
k =abs(n)
while k:
if(k &1 ): res *= t
t =t *t
k >>= 1
if is_minus:
res = 1.0/ res
return res
|
剑指 Offer 17. 打印从1到最大的n位数
简单题目面试时候不会问的，一笔带过就行。
python 解法
1
2
3
4
5
6
7
8
|
class Solution:
def printNumbers(self, n: int) -> List[int]:
b =1
while n:
b *= 10
n -=1
lst = [ num for num in range(1, b)]
return lst
|
c++ 解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution {
public:
vector<int> printNumbers(int n) {
vector<int> res ;
int b =1;
while(n)
{
b *= 10;
n -=1;
}
for(int i =1; i < b; i++)
{
res.push_back(i);
}
return res;
}
};
|
剑指 Offer 18. 删除链表的节点
c++ 实现
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
|
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* deleteNode(ListNode* head, int val) {
// 链表的题目：通过添加一个元素来 处理删除头指针的特殊情况
// c++ 中类 是使用 new 进行声明
ListNode* dummpy =new ListNode(-1);
dummpy -> next =head;
ListNode* pre =dummpy;
while(pre -> next)
{
head = pre ->next;
int value = head ->val;
if (value ==val)
{
pre ->next =head ->next;
}
pre =head;
}
return dummpy ->next;
}
};
|
python 中使用 类。 c++ 中使用结构体。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteNode(self, head: ListNode, val: int) -> ListNode:
dummy = ListNode(-1)
dummy.next =head
pre =dummy
while pre.next:
head =pre.next
if head.val ==val:
pre.next =head.next
pre =head
return dummy.next
|
剑指 Offer 19. 正则表达式匹配
详解看这里：https://www.acwing.com/solution/content/557/
c++ 解法。时间复杂度 $O(mn)$
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 {
public:
bool isMatch(string s, string p) {
int n =s.size(), m =p.size();
vector<vector<bool>> f(n +1, vector<bool>(m +1, false));
f[0][0] =true;
s = " " +s;
p = " " +p;
for(int i =0; i<= n; i++)
{
for(int j =1; j <=m ; j++)
{
if (i >0 && (s[i] ==p[j] || p[j] =='.' ))
f[i][j] = f[i][j] | f[i-1][j-1];
if( p[j] =='*')
{
if (j >= 2)
f[i][j] = f[i][j] | f[i][j -2];
if(i >0 && (s[i] == p[j-1] || p[j-1] =='.'))
f[i][j] = f[i][j] | f[i-1][j];
}
}
}
return f[n][m];
}
};
|
python 解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution:
# 这个是一个很经典的题目，使用 dp 进行处理。只是转换方程 dp 比较难写
#
def isMatch(self, s: str, p: str) -> bool:
m, n =len(s), len(p)
dp =[ [ False ] *(n +1) for _ in range(m +1)]
s =" "+s
p = " " +p
dp[0][0] = True
for i in range(m+1):
for j in range(1, n +1):
if i > 0 and (s[i] ==p[j] or p[j] =='.'):
dp[i][j] = dp[i][j] | dp[i-1][j -1]
if p[j] =="*":
if j >=2:
dp[i][j] = dp[i][j] | dp[i][j -2]
if i >0 and (s[i] == p[j-1] or p[j-1] =='.'):
dp[i][j] = dp[i][j] | dp[i-1][j]
#print(dp)
return dp[m][n]
|
python 解法。使用归并的思路，当二路归并的shihou
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:
def merge_sort(self, nums, l, r):
# 递归的跳出条件
if l >= r: return 0
mid = l +r >> 1
res = self.merge_sort(nums, l , mid ) + self.merge_sort(nums, mid +1, r)
#print(l , r, res)
# 这里可以用来 debug 每一层递归的输出
i, j = l, mid +1
tmp =[]
while i <= mid and j <= r:
if nums[i] <= nums[j]:
tmp.append(nums[i])
i +=1
else:
res += (mid -i +1)
tmp.append(nums[j])
j +=1
while i <= mid:
tmp.append(nums[i])
i +=1
while j <= r:
tmp.append(nums[j])
j +=1
i =l
for t in tmp:
nums[i] =t
i +=1
return res
def reversePairs(self, nums: List[int]) -> int:
return self.merge_sort(nums, 0, len(nums) -1)
|
c++ 解法
在快排，二分中 > 比较多；归并排序中使用 >= 。
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 {
public:
int merge_sort(vector<int> & nums, int l, int r)
{
if(l >= r) return 0;
int mid = l+r >> 1;
int res = merge_sort(nums, l, mid ) + merge_sort(nums, mid +1, r);
vector<int> tmp;
int i =l, j =mid +1;
while(i <= mid && j <= r)
if(nums[i] <= nums[j])
tmp.push_back(nums[i++]);
else
{
// 如果是第一个split 小的话，那么就不是逆序；只要当第二个数小的时候，才是逆序
res += (mid -i +1);
tmp.push_back(nums[j ++]);
}
while(i <=mid)
tmp.push_back(nums[i++]);
while(j <=r)
tmp.push_back(nums[j++]);
i =l;
for(auto item : tmp)
nums[i++] = item;
return res;
}
int reversePairs(vector<int>& nums) {
return merge_sort(nums, 0, nums.size() -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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
#include<iostream>
#include<vector>
using namespace std;
void merge_sort(vector<int>& arr, int l, int r)
{
if (l >= r) return ;
int mid = (l+r) >> 1;
merge_sort(arr, l, mid);
merge_sort(arr, mid +1, r);
int i =l, j = mid+1;
vector<int> tmp;
while(i <=mid && j <= r)
if(arr[i] <= arr[j])
tmp.push_back(arr[i ++]);
else
tmp.push_back(arr[j ++]);
while (i <= mid)
tmp.push_back(arr[i++]);
while(j <= r)
tmp.push_back(arr[j ++]);
// 把当前递归层中的tmp数值重新赋值给原数组
i =l;
for(auto t:tmp)
arr[i ++] =t;
}
int main()
{
int n ;
cin >>n;
vector<int> arr(n);
for(int i =0; i<n; i++)
cin >> arr[i];
merge_sort(arr, 0, n -1);
//for(int i =0; i<n; i++)
// cout << arr[i] << " ";
return 0;
}
|
简单题目，使用 c++ 写就行了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution {
public:
// 使用快排的思路，从左往右找偶数，从右往左找奇数。算法复杂度是O(n)
vector<int> exchange(vector<int>& nums) {
int l =0, r =nums.size() -1;
while(l <=r)
{
while(l <=r && nums[r] %2 ==0 ) r -=1;
while(l <=r && nums[l] %2 ==1) l +=1;
if (l <r)
{
//int t = nums[l];
swap(nums[l], nums[r]);
}
//t = nums[l]
}
return nums;
}
};
|
c++ 解法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* getKthFromEnd(ListNode* head, int k) {
vector<ListNode*> lst;
while(head)
{
lst.push_back(head);
head =head -> next;
}
return lst[lst.size() -k];
}
};
|
python 代码
联系一下手动实现 ListNode
1
2
3
4
5
6
7
8
9
10
11
12
|
class ListNode:
def __init__(self, val):
self.val =val
self.next =None
class Solution:
def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
lst =[]
while head:
lst.append(head)
head = head.next
return lst[len(lst) -k]
|
这里的 nex 是没必要非要判断的，因为下回的 while 自然是会进行判断。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
# 反转之后的头结点
pre =None
cur =head
while cur:
nex = cur.next
cur.next =pre
pre =cur
cur =nex
return pre
|
c++ 的解法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* pre = nullptr; // c++ 中空指针的定义
ListNode* cur = head;
while(cur)
{
ListNode* nex = cur -> next;
cur ->next =pre;
pre =cur, cur =nex;
}
return pre;
}
};
|
归并排序的思路
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
|
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
head =ListNode()
dummy =head
while l1 and l2:
if l1.val <= l2.val:
t =ListNode(l1.val)
head.next =t
head =head.next
l1 =l1.next
else:
head.next =ListNode(l2.val)
head =head.next
l2 =l2.next
while l1:
head.next = ListNode(l1.val)
l1 =l1.next
head =head.next
while l2:
head.next =ListNode(l2.val)
l2 =l2.next
head =head.next
return dummy.next
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 思路：首先遍历 a 中的每个节点，找出根节点相同的点，然后在根节点相同的时候，继续判断之后是否相同
def is_sub(self, p1, p2):
if not p2: return True
if not p1 or p1.val != p2.val: return False
return self.is_sub(p1.left, p2.left) and self.is_sub(p1.right, p2.right)
def isSubStructure(self, p1: TreeNode, p2: TreeNode) -> bool:
if not p1 or not p2: return False
# 这里只是遍历，没有判断根节点是否值相同，判断是下一个函数
if self.is_sub(p1, p2) : return True
return self.isSubStructure(p1.left, p2) or self.isSubStructure(p1.right, p2)
|
python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 树方面的算法，一般使用递归解法
def mirrorTree(self, root: TreeNode) -> TreeNode:
if not root: return root
root.left, root.right =root.right, root.left
self.mirrorTree(root.left)
self.mirrorTree(root.right)
return root
|
c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool dfs(TreeNode* p1, TreeNode* p2)
{
if(!p1 || !p2) return !p1 && !p2;
return p1 -> val == p2 ->val && dfs(p1 -> left, p2 ->right) && dfs(p1 ->right,p2 ->left );
}
bool isSymmetric(TreeNode* root) {
// 判断是否为镜像，只是需要看根节点的左子树和右子树是否为镜像
return !root || dfs(root -> left, root -> right);
}
};
|
python 代码
1
2
3
4
5
6
7
8
9
10
11
12
|
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def dfs(self, p1, p2):
if not p1 or not p2: return (not p1) and (not p2)
return p1.val == p2.val and self.dfs(p1.left, p2.right) and self.dfs(p1.right, p2.left)
def isSymmetric(self, root: TreeNode) -> bool:
return not root or self.dfs(root.left, root.right)
|
c++ 代码，
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 {
public:
// 按照传统循环方式去写，那么比较复杂。可以参考 yxc 的写法
vector<int> spiralOrder(vector<vector<int>>& matrix) {
int rows = matrix.size();
vector<int> res;
if(!rows) return res;
int cols = matrix[0].size();
vector<vector<bool>> st(rows, vector<bool>(cols, false));
int dx[4]={-1, 0, 1, 0}, dy[4] ={0, 1, 0, -1};
int x =0, y =0, d =1; // d 表示从第 几个开始遍历，这里因为横着先进行遍历，所以从 1开始。
for(int i =0;i < rows *cols; i++)
{
res.push_back(matrix[x][y]);
st[x][y] =true;
int a = x +dx[d], b = y+ dy[d];
if (a <0 || a >= rows || b <0 || b >= cols || st[a][b])
{
d = (d +1) %4;
a = x +dx[d], b = y+ dy[d];
}
x =a, y =b;
}
return res;
}
};
|
python 代码
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:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
res =[]
rows =len(matrix)
if not rows: return res
cols =len(matrix[0])
st =[[False] * cols for _ in range(rows)]
# 这两组坐标组合好了，可以表示上下左右的坐标移动。真的很神奇
dx =[-1, 0, 1, 0]
dy =[0, 1, 0, -1]
x, y, d =0, 0, 1
for i in range(rows *cols):
res.append(matrix[x][y])
st[x][y] = True
a, b = x + dx[d] , y + dy[d]
if a<0 or a >= rows or b <0 or b >= cols or st[a][b]:
d = (d +1) %4
a, b = x + dx[d] , y + dy[d]
x, y =a, b
return res
|
模拟题。关键在于使用 程序语言表达出来思路。当可以 pop 的时候，优先进行pop 操作，否则push 操作。当pop 完了之后没有报错，那么就完成了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution:
# 模拟题。 stack
def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
# 边界条件
if not pushed and not popped: return True
if not popped: return False
stk =[]
while popped:
# 如果可以 pop，那么尽可能pop 出来
if stk and stk[-1] == popped[0]:
popped.pop(0)
stk.pop()
elif pushed:
stk.append(pushed[0])
pushed.pop(0)
else:
# 只有 push 和 pop 两种操作，如果出现了第三种，那么就是错误的
return False
return True
|
c++ 代码
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 {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
if (pushed.empty() && popped.empty() ) return true;
if (popped.empty()) return false;
int i =0, n =popped.size(), j =0;
stack<int> stk;
//cout << i << endl;
while(i <n)
{
if(stk.size() && stk.top() == popped[i])
{
i +=1;
stk.pop();
}
else if (j < pushed.size())
stk.push(pushed[j++]);
else
return false;
//cout << i << stk.top() << endl;
}
if(i ==n)
return true;
else return false;
}
};
|
主要是从 c++ 语法层面的。queue 队列
1
2
3
4
5
6
|
size() # 大小长度
empty() # 判断是否为空
push() # 向队尾插入一个元素
front() # 访问队头的元素
back() # 访问队尾元素
pop() # 弹出队头元素
|
stack 访问函数
1
2
3
4
5
|
size() # 长度
empty() # 判断是否为空
push() # 栈顶插入一个元素
top() # 返回栈顶元素
pop() # 弹出栈顶元素
|
队列适合宽度优先搜索。
cpp 脚本
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
|
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> levelOrder(TreeNode* root) {
// 这个是考察队列的应用，而不是栈
queue<TreeNode*> q;
vector<int> res;
if(root == nullptr) return res;
q.push(root);
while (q.size())
{
auto item =q.front();
q.pop();
res.push_back(item -> val);
if(item -> left) q.push(item -> left);
if(item -> right) q.push(item ->right);
}
return res;
}
};
|
python 脚本
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:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# python 中队列默认是可以两段进行编辑的
def levelOrder(self, root: TreeNode) -> List[int]:
from collections import deque
res =[]
if not root: return res
q =deque()
q.appendleft(root)
while q:
item =q.pop()
res.append(item.val)
if item.left:
q.appendleft(item.left)
if item.right:
q.appendleft(item.right)
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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
// 需要一个终止点来标识每行的结束
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if(!root) return res;
vector<int> level; // 临时保存结果信息
queue<TreeNode* > qu;
qu.push(root);
qu.push(nullptr);
while(!qu.empty())
{
auto item =qu.front();// 这个是队列
qu.pop();
if(!item)
{
if(level.empty()) break;
res.push_back(level);
qu.push(nullptr);
level.clear();
continue;
}
level.push_back(item -> val);
if(item -> left) qu.push(item ->left);
if(item ->right) qu.push(item -> right);
}
return res;
}
};
|
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
27
28
29
30
31
32
33
|
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
res =[]
if not root: return res
level =[]
from collections import deque
qu =deque()
qu.appendleft(root);
qu.appendleft("level")
while qu:
item = qu.pop()
#print(item.val)
if item =="level":
if level ==[]:
break
qu.appendleft("level")
res.append(level)
level =[]
continue
level.append(item.val)
if item.left:
qu.appendleft(item.left)
if item.right:
qu.appendleft(item.right)
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
|
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 在第 3 个版本的基础上，设置 flag，如果是单数，那么是从左到右打印；如果是双数，那么从右往左打印
def levelOrder(self, root: TreeNode) -> List[List[int]]:
res =[]
if root ==None: return res
from collections import deque
qu =deque()
qu.appendleft(root)
qu.appendleft("level")
level =[]
revered =False # 只需要设置一个参数，说明当前是否需要 reverse 就行
while qu:
item = qu.pop()
#print(item)
if item =='level':
if level==[]:
break
if revered:
level =level[::-1]
revered = not revered
res.append(level)
qu.appendleft("level")
level =[]
continue
level.append(item.val)
if item.left:
qu.appendleft(item.left)
if item.right:
qu.appendleft(item.right)
return res
|
python 解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution:
# 可以得到的已知条件：二叉搜索树按照中序遍历是一个增序列
# 候选遍历的话，是最后遍历根节点
# 递归判断
# root 的大小关系去判断是否符合搜索二叉树
def verifyPostorder(self, postorder: List[int]) -> bool:
if not postorder: return True
# python 中闭包的概念
def dfs(postorder):
if not postorder: return True
root =postorder[-1]
i =0
while postorder[i] < root:
i +=1
for j in postorder[i:-1]:
if j < root:
return False
return dfs(postorder[:i]) and dfs(postorder[i:-1]) # 数据范围变小，但是方法还是没有变的
# 可以把 python 中的函数写成 嵌套函数，
return dfs(postorder)
|
c++ 解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution {
public:
bool dfs(vector<int>& postorder, int l, int r)
{
if (l>=r) return true;
int root = postorder[r];
int i =l;
while( i <r&& postorder[i] < root )
i ++;
for(int j =i ;j <r; j ++)
if(postorder[j] <root)
return false;
//cout << postorder[l] << " "<< postorder[i] << " "<< postorder[r]<< endl;
return dfs(postorder, l, i-1) && dfs(postorder, i, r -1); // 这个阈值不是很好去调节
}
bool verifyPostorder(vector<int>& postorder) {
if(postorder.size() ==0) return true;
return dfs(postorder, 0, postorder.size() -1);
}
};
|
c++ 求解
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 Node.
class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};
*/
class Solution {
public:
Node* copyRandomList(Node* head) {
// 可以参考使用 dictionary 进行赋值保存
if(!head) return head;
unordered_map<Node*, Node*> hash;
// 先复制结点
hash[nullptr] =nullptr;
for(auto p= head; p; p = p ->next)
{
hash[p] =new Node(p -> val);
}
// 然后复制指针关系
for(auto p= head; p ; p = p->next)
{
hash[p] ->next = hash[p->next];
hash[p] -> random = hash[p->random];
}
return hash[head];
}
};
|
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
|
"""
# Definition for a Node.
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
"""
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
dic ={}
# 先复制结点
p =head
dic[None] =None
while p:
dic[p] =Node(p.val)
p = p.next
# 复制指针关系
p =head
while p:
dic[p].next = dic[p.next]
dic[p].random = dic[p.random]
p = p.next
return dic[head]
|
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
|
"""
# Definition for a Node.
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
"""
class Solution:
def treeToDoublyList(self, root: 'Node') -> 'Node':
# 中序遍历
def dfs(root):
if not root: return
dfs(root.left)
if self.pre:
self.pre.right, root.left =root, self.pre
else:
self.head =root
self.pre = root
dfs(root.right)
if not root: return root
self.pre =None
dfs(root)
self.head.left, self.pre.right =self.pre, self.head
return self.head
|
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
55
56
57
58
59
|
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Codec:
# 先序遍历，队列的数据结构
from collections import deque
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
if root =='[]': return
deq = deque()
deq.append(root)
res =[]
while deq:
node = deq.popleft()
if node:
res.append(str(node.val))
deq.append(node.left)
deq.append(node.right)
else:
res.append(str(None))
return ",".join(res)
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
if data =="[]": return
vals, i = data.split(","), 1
root = TreeNode(int(vals[0]))
deq =deque()
deq.append(root)
while deq:
node = deq.popleft()
if vals[i] != 'None':
node.left = TreeNode(int(node.val))
deq.append(node.left)
i += 1
if vals[i] != 'None':
node.right = TreeNode(int(node.val))
deq.append(node.right)
i +=1
return root
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))
|
时间复杂度是 $n!$， 其中 $n$ 是字符串的长度，因为数据最大长度是 8，所以直接 dfs 就可以解决。
python 脚本。
主要是 python 中的切片比较好用。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution:
# 从数据范围上看，直接使用 dfs 就可以解决问题
# 问题在于 dfs 不知道如何进行书写
# dfs 中一般是先按照某个点 进行枚举（将范围缩小），然后进行相同的操作
def permutation(self, s: str) -> List[str]:
if len(s) <= 1:
return list(s)
res =[]
for i in range(len(s)):
# 枚举 i
for j in self.permutation(s[:i] + s[i+1:]):
#res.append(s[i] +j)
t = s[i] +j
if t not in res:
res.append(t)
return res
|
c++ 脚本
python 解法，使用的内置的库函数 collections.defaultdict 。这种解法没有考虑到一个数字超过半数的条件。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution:
# O(n) 的时间复杂度
def majorityElement(self, nums: List[int]) -> int:
if not nums: return nums
from collections import defaultdict
dic =defaultdict(int)
dic[nums[0]] =1
val,cnt = nums[0], 1
for i in range(1, len(nums)):
dic[nums[i]] +=1
if dic[nums[i]] > cnt:
cnt = dic[nums[i]]
val = nums[i]
return val
|
python 版本，不使用内置的库函数。 和上一版本的区别是： dic[val] += 1 操作只能在 val 已经保存在 dic 中才能进行。如果使用 defaultdic 是可以直接进行操作的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution:
# O(n) 的时间复杂度
def majorityElement(self, nums: List[int]) -> int:
if not nums: return nums
dic ={}
dic[nums[0]] =1
val,cnt = nums[0], 1
for i in range(1, len(nums)):
if nums[i] in dic:
dic[nums[i]] +=1
if cnt < dic[nums[i]]:
cnt = dic[nums[i]]
val = nums[i]
else:
dic[nums[i]] =1
return val
|
最优的解法：
时间： $o(n)$ 空间 :$O(1)$
充分利用了 多数的值 在统计上是多个的。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution:
def majorityElement(self, nums: List[int]) -> int:
if not nums: return nums
cnt, val= 1, nums[0]
for i in range(1,len(nums)):
if nums[i] ==val:
cnt +=1
elif cnt ==0:
val = nums[i]
cnt =1
else:
cnt -=1
return val
|
c++ 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution {
public:
int majorityElement(vector<int>& nums) {
if (nums.size() ==0) return -1;
int val = nums[0], cnt =1;
for (int i =1; i< nums.size() ; i++)
{
if (val == nums[i])
cnt +=1;
else if (cnt ==0)
{
val =nums[i];
cnt =1;
}
else
cnt -=1;
}
return val;
}
};
|
c++ 解法
时间复杂度是$nlogn$，使用了两个栈。
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 MedianFinder {
public:
/** initialize your data structure here. */
// 大根堆存储小的元素，小根堆存储大的元素
MedianFinder() {
}
priority_queue<int> smaller;
priority_queue<int, vector<int>, greater<int>> larger;
void addNum(int num) {
if(smaller.empty() || num < smaller.top())
smaller.push(num);
else
larger.push(num);
// 核心逻辑在于，size(smaller) == size(larger) || size(smaller) = size(larger) +1
if (smaller.size() == larger.size() +2)
{
int top = smaller.top();
smaller.pop();
larger.push(top);
}
else if (larger.size()== smaller.size() +1)
{
int top =larger.top();
larger.pop();
smaller.push(top);
}
}
double findMedian() {
if (smaller.size() == larger.size() )return (smaller.top() + larger.top()) /2.0;
return smaller.top();
}
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();
* obj->addNum(num);
* double param_2 = obj->findMedian();
*/
|
python 解法
使用 heapqpushpop 在于 相比于 heappush 更加高效。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class MedianFinder:
import heapq
def __init__(self):
"""
initialize your data structure here.
"""
self.smaller =[] # 小根堆， 放大数值， 默认是小根堆
self.larger =[] # 大根堆， 放小数值， 通过负值来实现
def addNum(self, num: int) -> None:
if (len(self.smaller) == len(self.larger)):
heapq.heappush(self.smaller, -heapq.heappushpop(self.larger, -num))
else:
heapq.heappush(self.larger, -heapq.heappushpop(self.smaller, num))
def findMedian(self) -> float:
if len(self.smaller) == len(self.larger):
return (self.smaller[0] - self.larger[0]) /2
return self.smaller[0]
# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()
|
dp 一般可以使用在求解最值 和求解符合要求的个数 类型的题目上。
$f[i]$ 表示以第 $i$ 个数字结尾的最大连续子序列的 总和是多少
转移方程 $f[i] =max(f[i-1] +nums[i], nums[i])$
最后的答案是 $ans = max(f[k]), k \in (0,n)$
python 求解
1
2
3
4
5
6
7
8
|
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
max_s = nums[0]
t = nums[0]
for i in range(1, len(nums)):
t =max(nums[i], t +nums[i])
max_s= max(max_s, t)
return max_s
|
c++ 求解
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int res =nums[0];
int t = nums[0];
for(int i =1; i< nums.size() ; i++)
{
t = max(t + nums[i], nums[i]);
res =max(res,t);
}
return res;
}
};
|
这个是一个统计学的问题，比较费解
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution {
public:
int countDigitOne(int n) {
int count =0;
for(long long i =1; i<=n ; i *=10)
{
long long a = n /i,b = n %i;
count += (a + 8) / 10 * i + ((a % 10 == 1) ? b + 1 : 0);
}
return count;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution:
# 这个属于找规律题目
# 1.求n所落在的数值的位数,如 13 落在【10-99】区间
# 2.求所在数值x是多少和对应数值x的第几位，如第13位对应数值11的第二位
def findNthDigit(self, n: int) -> int:
digit , start, count = 1, 1, 9
while n > count:
n -= count
start *= 10
digit += 1
count = 9 * start * digit
num = start + (n-1) /digit
return int(str(num)[(n-1) %digit] )
|
python 实现，时间复杂度是 $O(nlogn)$
1
2
3
4
5
6
7
8
|
class Solution:
def minNumber(self, nums: List[int]) -> str:
if not nums:
return ''
nums = [str(x) for x in nums]
from functools import cmp_to_key
nums = sorted(nums, key = cmp_to_key(lambda x, y: int(x +y) - int(y +x)))
return ''.join(nums) or '0'
|
python 实现
思路很重要，按照斐波那契数列的做法，每次可以选择一个数字或者两个数字，这样对应的是两步操作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution:
# 可以仿照经典的 斐波那契 数列，每次可以走一步或者两步
def translateNum(self, num: int) -> int:
s =str(num)
n = len(s)
if not n: return 0
if n ==1: return 1
dp =[0] *(n +1)
dp[n], dp[n-1] =1, 1
for i in range(n-2, -1, -1):
dp[i] =dp[i-1]
if s[i] =='1' or (s[i] =='2' and s[i+1] <'6'):
dp[i] = dp[i+2] +1
return dp[0]
|
最后求解的是最值，所以考虑使用 动态规划。因为当前点只能从上一个和左边一个点转换过来，所以取其最大值。
1
2
|
dp[i][j] 表示走到 (i,j) 的礼物最大价值
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j] # 左边或者上面的最大值 + 当前值
|
1
2
3
4
5
6
7
8
9
10
11
|
class Solution:
# 考察的是一个动态规划的问题：求解最值和求解解法的数量
def maxValue(self, grid: List[List[int]]) -> int:
rows, cols = len(grid),len(grid[0])
dp =[[0] *(cols+1) for _ in range(rows+1)]
dp[0][0] = grid[0][0]
for i in range(1, rows+1):
for j in range(1, cols+1):
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1]
return dp[rows ][cols]
|
python 解法
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution:
def nthUglyNumber(self, n: int) -> int:
j, k,l =0,0, 0
dp =[1]
for i in range(1,n):
t = min(dp[j] *2, dp[k] *3, dp[l] *5)
if t == dp[j]*2: j +=1
if t == dp[k]*3: k +=1
if t ==dp[l]*5: l +=1
dp.append(t)
return dp[-1]
|
下面是错误的解法： 丑数的取决并不是依靠前 k 个状态，其中 k 是不确定的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
# 2 3 5 丑数， 给定 n
def get_number(n):
if n <1: return -1
if n <=3: return n
dp = [0] * (n+1)
#dp[1] , dp[2], dp[3] = 2, 3, 4
dp[1], dp[2], dp[3],dp[4] =2, 3, 4, 5
for i in range(5, n+1):
dp[i] = min( dp[i-1] *5, dp[i-1] * 3 , dp[i-1] *2)
dp[i] = min(dp[i-3] *2, dp[i-3] *3, dp[i-3] *5, dp[i])
dp[i] = min(dp[i-2] *2, dp[i-2] *3, dp[i-2] *5, dp[i])
#dp[i] = min(dp[i-4] *2, dp[i-4] *3, dp[i-4] *5, dp[i])
print(dp)
return dp[n]
print(get_number(10))
|
python 解法， $j-i$ 表示当前不重复字符的长度，使用 dic 最后一次出现的 index。
1
2
3
4
5
6
7
8
9
10
11
|
class Solution:
# 双指针 + 哈希表
def lengthOfLongestSubstring(self, s: str) -> int:
dic, res, i ={}, 0, -1
# 双指针 + 哈希表
for j in range(len(s)):
if s[j] in dic:
i = max(dic[s[j]], i) # 更新左指针
dic[s[j]] =j
res =max(res, j -i)
return res
|
c++ 解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution {
public:
// 最值问题，可以考虑 dp
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> dic;
int res =0, i = -1;
for(int j =0; j< s.size(); j++)
{
if(dic.count(s[j]))
i =max(i, dic[s[j]]);
dic[s[j]] =j;
res =max(res, j -i);
}
return res;
}
};
|