日常刷题笔记。
- 最长公共子串
给定两个字符串A和B，长度分别为m和n，要求找出它们最长的公共子串，并返回其长度。例如：
1
2
|
A = "HelloWorld"
B = "loop"
|
第一种做法是暴力枚举， 时间复杂度是 $O(n^3)$； 第二种做法时间复杂度 $O(n^2)$，使用dp 的做法。那么状态转移方程是
$$ dp[i][j] = \begin{cases}
0 & str1[i-1] !=str2[j-1] \\
dp[i-1][j-1] +1& str1[i-1] ==str2[j-1]
\end{cases}$$
注意公共子串，要求的是需要连续的，所以当发现不连续的时候， $dp[i][j] =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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
|
#include<iostream>
#include<string>
#include<vector>
using namespace std;
// 这个是最基础的算法， 使用暴力枚举，时间复杂度是 n^3
string common_str(string &str1, string & str2)
{
string res;
int n =str1.size(), m =str2.size();
//保证n>= m
if(n< m)
{
res =common_str(str2, str1);
return res;
}
int max_l =0;
for(int i=0; i<n; i++)
{
for(int j =i+1; j<n; j++)
{
// start point , len
string substr= str1.substr(i,j-i+1);
if( str2.find(substr) != str2.npos)
{
if(j -i+1 > max_l)
{
res =substr;
max_l =j-i+1;
}
}
}
}
return res;
}
// 使用二维dp 进行优化，时间复杂度是O(n^2) 空间是O(n^2)
int common_str2(string &str1, string &str2)
{
int n =str1.size(), m =str2.size() ;
vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
if(n <m) return common_str2(str2, str1);
int max_l =0;
for(int i =1; i<=n ; i++)
{
for(int j =1; j<=m ; j++)
{
if(str1[i-1] ==str2[j-1])
{
dp[i][j] =dp[i-1][j-1] +1;
max_l =max(max_l, dp[i][j]);
}
else
dp[i][j] =0;
}
}
// 这个是dp 思想求解，但是最长的长度不是dp[n][m]
return max_l;
}
// 使用一维dp 进行优化
int findLongest(string A, int n, string B, int m) {
if(n == 0 || m == 0)
return 0;
int rs = 0;
int dp[n + 1][m + 1];
for(int i = 0 ; i <= n; i++)//初始状态
dp[i][0] = 0;
for(int i = 0; i <= m; i++)
dp[0][i] = 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j<= m; j++)
{
if(A[i - 1] == B[j - 1])
{
dp[i][j] = dp[i -1][j - 1] + 1;
rs = max(rs,dp[i][j]);//每次更新记录最大值
}
else//不相等的情况
dp[i][j] = 0;
}
return rs;//返回的结果为rs
}
int main()
{
string str1, str2;
//cin >>str1 >>str2;
str1 ="abc", str2 ="bcd";
//string res =common_str(str1, str2);
//for(auto u : res) cout << u;
int max_l =common_str2(str1, str2);
cout << max_l<< endl;
//cout << findLongest(str1, 3, str2, 3)<< endl;
cout <<endl;
return 0;
}
|
python 解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
def longest_substring(str1, str2):
n, m =len(str1), len(str2)
dp=[[0] *m]*n
max_ =0
res =""
for i in range(n):
for j in range(m):
if str1[i] ==str2[j]:
if i and j:
dp[i][j] =dp[i-1][j-1] +1
else:
dp[i][j] =1
if dp[i][j] >max_:
max_ =dp[i][j]
res += str1[i]
return res
str1 ="abc"
str2 ="bcd"
print(longest_substring(str1, str2))
|
- 求解最长公共子序列
dp[i][j] 表示string1中第 i 位置之前和string2 中第j 位置之前，最长的公共子序列。(求解的是max 操作，对于集合的划分可以重复，但是不能缺少)
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
|
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int max_sub_len(string & str1, string &str2)
{
int res =0;
int n =str1.size(), m =str2.size();
vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
// 坐标的转换
// 如果是string，这个坐标是可以从
for(int i =0; i<n; i++)
{
for(int j =0; j<m; j++)
{
dp[i+1][j+1] =max(dp[i][j+1], dp[i+1][j]);
if(str1[i] ==str2[j])
dp[i+1][j+1] =max(dp[i+1][j+1], dp[i][j] +1);
}
}
return dp[n][m];
}
int main()
{
string str1, str2;
cin >> str1 >> str2;
int res =max_sub_len(str1, str2);
cout << res<< endl;
return 0;
}
|
python 解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
# 最长公共子序列，这个可以是离散的
def longest_common_string(str1, str2):
n, m =len(str1), len(str2)
dp =[[0]* (m+1)]*(n+1)
res =""
for i in range(1, n+1):
for j in range(1, m+1):
dp[i][j] =max(dp[i-1][j], dp[i][j-1])
if str1[i-1] ==str2[j-1]:
if dp[i][j]< dp[i-1][j-1] +1:
res +=str1[i-1]
dp[i][j] = dp[i-1][j-1] +1
# dp[m][n] 是最大值
return res
str1 ="abc"
str2 ="adc"
print(longest_common_string(str1, str2))
|
- 最长上升子序列
最长公共上升子序列
暴力的解法是 $O(n^2)$，就是枚举当前位置之前的数字是否合法，如果合法，那么就需要 +1 操作。对于dp 动态规划，含义，初始化和动态转移方程。dp[i] 表示位置为i 的所有的前面的数字有多少个上升序列数字。
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 {
public:
// 最长递增子序列，动规的角度去考虑， 枚举法， 时间复杂度是O(n^2)
int lengthOfLIS(vector<int>& nums) {
int n =nums.size();
if(n ==0) return 0;
// 遍历当前位置之前的所有的位置，统计出现的小于当前数值的数字，就可以得到最后的结果
int res =1;
vector<int> dp(n, 1);
for( int i =1; i<n; i++)
{
// 这个是保证之前的所有位置的数字
for(int j =0; j<i; j++)
{
if(nums[i]> nums[j]) dp[i] =max(dp[i], dp[j]+1);
}
res =max(res, dp[i]);
}
for(auto u : dp) cout << u<<" ";
cout << endl;
return res;
}
};
|
使用二分进行优化，空间上的复杂度不变，但是时间上的复杂度由原先的 $O(n^2)$ 优化成 $O(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
|
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
// 使用二分查找进行了优化 时间复杂度从O(n^2) 优化成了 O(nlogn)
int n =nums.size();
if(n ==0) return 0;
vector<int> h(n+1, 0);
h[1] =nums[0];
int max_ =1;
for(int i =1; i< n; i++)
{
int l =1, r =max_;
while(l<=r)
{
int mid =l +r >>1;
if(h[mid] < nums[i]) l =mid +1;
else r =mid -1;
}
h[l] =nums[i];
if(l > max_) max_ =l;
}
return max_;
}
};
|
python 解法
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 lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
# 最长上升子序列，暴力解法， n^2 的时间复杂度， 然后怎么优化呢？ 因为这个是有序的，所以可以考虑使用 二分进行优化
n =len(nums)
if(n ==0): return 0;
h =[0] *(n+1);
h[1] =nums[0]
max_ =1
for i in range(1, n):
l, r = 1, max_
while(l <=r ):
mid =l +r >>1;
if(h[mid] < nums[i]): l =mid +1
else: r =mid-1
h[l] =nums[i]
if(l > max_):
max_ =l
return max_
|
- 将嵌套列表转换成一维列表
1
2
3
4
5
6
7
8
9
10
11
12
|
res =[]
def flatten(items):
for item in items:
if isinstance(item, int) or isinstance(item, str):
#flatten(item)
res.append(item)
else:
flatten(item)
#res.append(item)
return res
items =[1,2 , 'a', [3, 4, ], (5, 6)]
print(flatten(items))
|
其实还可以写成一个小的生成器的形式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
def generator(a):
for each in a:
if not isinstance(each, list):
yield each
else:
yield from generator(each)
a =[1,2, [3, 4], 5]
print(generator(a))
def generator1(a):
for each in a:
if isinstance(each, collections.Iterable) :
yield from generator1(each)
else:
yield each
print(generator1(a))
|
- remove linked list ellements
c++ 版本，主要想要个强调，如果是删除一个元素，那么需要处理f 删除头结点的问题，所以使用一个 dummy 这样的虚拟头结点，可以处理边界条件。对于有可能删除头结点的情况下，一般使用 dummy 这种虚拟头结点
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
|
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {} // 这个属于显式构造函数
* };
*/
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode * dummy = new ListNode(-1);
ListNode * p =dummy;
p ->next =head;
while(p->next)
{
auto nex =p->next;
if(nex->val == val)
{
p->next = nex->next;
}
else
p =p->next;
}
return dummy->next;
}
};
|
python 版本代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
# definition of listnode
class ListNode:
def __init__(self, x):
self.val =x
self.next =None
class Solution:
def removeElements(self, head: ListNode, val: int) -> ListNode:
dummy = ListNode(-1)
p =dummy
p.next =head
while p.next:
nex =p.next
if(val == nex.val):
p.next =nex.next
else:
p= p.next
return dummy.next
|
- 74. Search a 2D Matrix
python 解法
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
if not matrix: return False
n =len(matrix)
if n ==0: return false
m =len(matrix[0])
i, j =0, m -1
while i< n and j >=0:
if(matrix[i][j] == target): return True
elif matrix[i][j] > target: j -=1
else : i +=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
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
import string
str1 ="找出字符串中的中英文、i only regret空格、数字、标点符号 1 99 0个数"
def count_(str):
cout_num =cout_zh =cout_en =cout_space =cout_pu =0
for ch in str:
if ch.isspace():
cout_space +=1
elif ch.isdigit():
cout_num +=1
elif ch in string.ascii_letters:
cout_en +=1
elif ch.isalpha(): # 这里使用的是减法的思路
cout_zh +=1
else:
cout_pu +=1
print("英文字符数量：", cout_en)
print("中文字符数量：", cout_zh)
print("数字个数：", cout_num)
print("空格个数: ", cout_space)
print("特殊字符个数:",cout_pu)
#count_(str1)
# 方法二，使用正则表达式
import re
def cout2(str):
regex_digit = re.compile(r'[0-9]' )
regex_en =re.compile(r'[a-zA-Z]')
regex_zh =re.compile(r'[\u4E00-\u9FA5]')
digit_list =regex_digit.findall(str)
en_list =regex_en.findall(str)
zh_list =regex_zh.findall(str)
print("数字序列", digit_list)
print("英文序列", en_list)
print("中文序列", zh_list)
cout2(str1)
|
- 统计的单词的个数（注意不是字母 char类型的）, 有不同的方法
a. 在linux 环境下
文件格式：文件中每一行为一个单词
1
2
3
4
|
sort filename | uniq -c| sort -nr
-c 输出重复次数
-n 按照数值比较排序
-r 逆序输出结果
|
b. 全程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
|
import sys
word2count ={}
def word_count():
f1 =open("", 'r')
f2 =open("", 'w')
while True:
line =f1.readline()
if not line: break
# python 内置的split 只能使用单个 分割符
line =line.replace(',', ' ')
line =line.replace('.', ' ')
line =line.replace('!', ' ')
line =line.strip().split(" ")
# 可以使用 re模块中的 split() ，使用多个分割符对句子进行分割
import re
line =re.split(',.?', line)
for item in line:
if item not in word2count:
word2count[item] =1
else:
word2count[item] +=1
# 按照逆序进行排序
res =sorted(word2count.item(), key =lambda x : x[1], reverse =True)
for item in res:
f2.write(item[0])
f1.close()
f2.close()
|
python 中常见的大小写问题
1
2
3
4
|
print(str.upper()) # 把所有字符中的小写字母转换成大写字母
print(str.lower()) # 把所有字符中的大写字母转换成小写字母
print(str.capitalize()) # 把第一个字母转化为大写字母，其余小写
print(str.title()) # 把每个单词的第一个字母转化为大写，其余小写
|
- 最长01相同子串
已知一个长度为N的字符串，只由0和1组成， 求一个最长的子串，要求该子串出现0和1的次数相等。
思路：
最简单的方式是先生成字串，然后判断每个字串是否满足0的个数和1的个数相同。这种暴力求解时间复杂度O(n^3),明显是不合理的。
下面说一下简单的做法：
定义一个数组B[N]，B[i]表示从A[0…i]中 num_of_0 - num_of_1，0的个数与1的个数的差 。那么如果A[i] ~ A[j]是符合条件的子串，一定有 B[i] == B[j]，因为中间的部分0、1个数相等，相减等于0。
时间复杂度：O(n)，空间复杂度：O(n)
注意这个是求解的长度，是一个最值问题，而不是最长的01 子串本身。所以使用临时数组记录目前为止的01 的差值，然后选择最大的就行了。时间复杂度是O(N)，空间复杂度是O(N)。
算法的优化的关键在于，可以基于前一步的计算结果继续往下计算。前一步算出了 (i-1) 的01 的差值，那么下一步可以计算前 i 的01 的差值。
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
|
def lengest01SubStr(s):
'''
最长0,1 相等的子串长度
'''
count =[0, 0]
B =[0]*len(s)
dic ={} # 保存 0 1 的差值
lengest =0
for i in range(len(s)):
count[int(s[i])] +=1
B[i] =count[0] - count[1]
# start from 0th index
if B[i] ==0:
lengest +=1
continue
if B[i] in dic:
# i -dic[B[i]] , not from 0th index
lengest =max(lengest, i- dic[B[i]])
else:
dic[B[i]] =i
return lengest
a ='1011010'
b ='10110100'
print(lengest01SubStr(a)) # 6 # '011010'
print(lengest01SubStr(b)) # 8 # '10110100'
|
** 顺时针打印矩阵**
输入一个矩阵，按照从外向里以顺时针的顺序依次扫印出每一个数字。
使用四个循环，就可以解决，这个应该属于找规律的题目。
思路：
找到左上角的，一个start_point， 然后根据这个点进行上下左右的循环。
python 中的 range() 是一种左闭右开的区间，并且在逆序遍历的时候，区间的值是不变的，最后使用 -1 就OK了。还有遍历时候的 i, j 都只是一种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
30
31
32
33
34
35
36
37
38
39
40
41
42
|
def printMatrix(matrix):
if not matrix or matrix ==[[]]:
return
# 第一次见这样判断空的matrix
row =len(matrix)
column =len(matrix[0])
# 这里的left, right, up, down 都是真实能够access到数据的
left =0
right =column -1
up =0
down =row -1
res =[]
while left <right and up <down:
# from left to right
for i in range(left, right+1):
res.append(matrix[up][i])
# from up to down
for i in range(up+1, down+1):
res.append(matrix[i][right])
# from right to left
for i in range(right-1, left-1, -1):
res.append(matrix[down][i])
for i in range(down-1, up, -1):
res.append(matrix[i][left])
left +=1
right -=1
up +=1
down -=1
# 最后对于这种特殊情况的处理是容易忘记的
# left one row 这种情况很特殊，只是从左往右遍历
if up ==down and left <right:
for i in range(left, right+1):
res.append(matrix[up][i])
# left one column 只有可能是从上往下遍历
if left ==right and up <down:
for i in range(up, down+1):
res.append(matrix[i][left])
if up ==down and left ==right:
res.append(matrix[left][up])
return res
print(printMatrix(matrix))
|
** 最小调整有序**
有一个整数数组，请编写一个函数，找出索引m和n，只要将m和n之间的元素排好序，整个数组就是有序的。注意：n-m应该越小越好，也就是说，找出符合条件的最短序列。
给定一个int数组A和数组的大小n，请返回一个二元组，代表所求序列的起点和终点。(原序列位置从0开始标号,若原序列有序，返回[0,0])。保证A中元素均为正整数。
样例
1
2
|
[1,4,6,5,9,10],6
返回：[2,3]
|
第一种比较暴力，时间复杂度 $O(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
40
41
42
43
44
45
46
47
48
|
/*
最小调整有序
找出索引m 和n，只要是m 和n 之间的元素排好序，整个数组就是有序的。注意n-m 应该是越小越好，找出符合条件的最短序列
*/
#include<iostream>
#include<vector>
using namespace std;
vector<int> find_segment(vector<int>& arr)
{
vector<int> res(2, 0);
vector<int> tmp(arr.begin(), arr.end());
sort(arr.begin(), arr.end());
for(int i =0; i< arr.size(); i++)
{
if(tmp[i] != arr[i])
{
res[0] =i;
break;
}
}
for(int i =arr.size() -1; i>=0; i--)
{
if(tmp[i] != arr[i])
{
res[1] =i;
return res;
}
}
return res;
}
int main()
{
int n;
vector<int> arr;
cin >>n;
for(int i =0; i< n; i++)
{
int tmp;
cin >> tmp;
arr.push_back(tmp);
}
vector<int> res =find_segment(arr);
for(auto u: res)
cout << u << " ";
cout << endl;
return 0;
}
|
第二种是$O(n)$ 的时间复杂度。分成两个步骤
- 从左往右找，如果当前元素小于之前的最大元素则说明当前元素应处于A[first,last]无序序列中而且当前元素是当前最大下标的无序元素。
- 从右往左找，如果当前元素大于之前的最小元素则说明当前元素应处于A[first,last]无序序列中而且当前元素是当前最小下标的无序元素。
关键在于找到之后，继续遍历直到数组的最后；
增加新的一个样例
1
|
对于一个整数数组[1,3,5,8,4,10,12,9,15,17]，则最短无序数组为[5,8,4,10,12,9]。
|
好好思考一下，当时为什么想不到，这种思路是什么，我当时是想到了 $O(n)$ 遍历，但是没有相当即使第一回发现了不符合要求的数字，那么也是要遍历完，然后不断地的更新结果的。
开始的想法是正确的，左右两次遍历。但是需要不断的更新最值，从右往左是最小值，从左往右是最大值。不能只是和周围的数字进行比较。
简而言之就是找出，逆序的， 因为是有序的，所以如果发现一个比在之前数字小，那么说明找到了右端点；从右向左，如果发现比左边大，说明找到了左端点；需要转换一下思路
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class Rearrange {
public:
vector<int> findSegment(vector<int> nums, int n) {
// write code here
int maxv =nums[0], minv =nums[n-1];
vector<int> res(2, 0);
for(int i =0; i< n; i++)
{
if(nums[i] >= maxv) maxv =nums[i];
else res[1] =i;
}
for(int i =n -1; i>=0; i--)
{
if(nums[i] <= minv )minv =nums[i];
else res[0] =i;
}
return res;
}
};
|
python 实现的代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
# -*- coding:utf-8 -*-
class Rearrange:
def findSegment(self, nums, n):
# write code here
if n==1: return [0, 0]
minv, maxv =nums[-1], nums[0]
res =[0, 0]
for i in range(n):
if nums[i] >= maxv: maxv =nums[i]
else: res[1] =i
for i in range(n-1, -1, -1):
if nums[i] <=minv: minv =nums[i]
else: res[0] =i
return res
|
915. Partition Array into Disjoint Intervals
考察想法的题目真的是太难了，如果想不出来，那么真的是不会做。
分成左右两个部分，左边的全部比右边的小。那么只要保证左边最大的是小于等于右边最小的就行。这个思路是，数学题。下面就需要使用一个 $O(n)$ 空间复杂度记录从 $i$ 到$n$ 的最小值。不用使用数组保存前 $i$ 的最大值，直接在遍历的时候进行判断进行了。
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:
// tong
// 因为要求分成两部分，左边的都比右边的小，
// 使用一个数组 tmp[i] 表示从 i 到 n-1 最大值
// 然后经过一次遍历之后，如果某个arr[i] < tmp[i] 那么就得到了正确的解
int partitionDisjoint(vector<int>& nums) {
int n =nums.size();
vector<int> minv(n, INT_MAX);
minv[n-1] =nums[n-1];
for(int i =n-2; i>=0; i--)
{
minv[i] =min(minv[i+1], nums[i] );
//cout << maxv[i] << endl;
}
// 这里还需要记录到到当前位置的最大值
int maxv =0;
for(int i =0 ; i<n-1; i++)
{
maxv= max(maxv, nums[i]);
if (maxv <=minv[i+1])
return i +1;
}
return -1;
}
};
|
python 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
import sys
class Solution(object):
def partitionDisjoint(self, A):
"""
:type A: List[int]
:rtype: int
"""
n =len(A)
minv=[sys.maxsize]*n
minv[n-1] =A[n-1]
for i in range(n-2, -1, -1):
minv[i] =min(minv[i+1], A[i])
#print(minv)
maxv =0
for i in range(n-1):
maxv=max(maxv, A[i])
if(maxv <= minv[i+1]):
return i +1
return -1
|
149. Max Points on a Line
这个题目需要处理竖直直线，重复的点等特殊情况。剩下的一般情况是需要使用 顶点+ 斜率进行表示，使用dictionary 进行表示。 注意在python 中使用的是 gcb 先求解了 最大公因数，然后再进行表示。
使用c++ 实现，那么时间复杂度是$O(n^2)$
在 c++ 中使用 double long 处理精度的问题，但是可以使用gcb(最大公约数) 更加合理。
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:
// 首先这个是一个 $n^2$ 的算法，因为需要计算每一个点到其他的所有点的斜率（如果可以的话）
int maxPoints(vector<vector<int>>& points) {
int n =points.size();
int res =0;
// 以这个点为基准点 进行发射
for(int i =0; i< n; i++)
{
unordered_map<double long, int> hash;
int veticles =1, duplicates =0;
for(int j =i +1; j<n; j++)
{
if(points[i][0] ==points[j][0])
{
veticles +=1;
if(points[i][1] ==points[j][1]) duplicates +=1;
}
}
for(int j =i +1; j<n; j++)
{
if(points[i][0] != points[j][0])
{
double long slope = (double long)(points[i][1] -points[j][1])/(points[i][0] -points[j][0]);
if(hash[slope] ==0) hash[slope] =2;
else hash[slope ] ++;
res =max(res, hash[slope] + duplicates);
}
}
res =max(res, veticles);
}
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
34
35
36
37
38
|
class Solution(object):
# 在python 中 使用 gcb 处理精度问题
def maxPoints(self, points):
"""
:type points: List[List[int]]
:rtype: int
"""
res =0
n =len(points)
for i in range(n):
veticles =1
duplicates =0
dic ={}
for j in range(i+1, n):
# 对应的是不能计算 slope 斜率的情况
if(points[i][0] ==points[j][0]):
veticles +=1;
if(points[i][1] ==points[j][1]):
duplicates +=1
for j in range(i +1, n):
if points[i][0] != points[j][0]:
dx =points[i][0] -points[j][0]
dy =points[i][1] -points[j][1]
common =self.gcb(dx, dy)
if (dx//common, dy//common) in dic:
dic[(dx//common, dy //common)] +=1
else:
dic[(dx//common, dy//common)] =2
res =max(res, dic[(dx//common, dy//common)] +duplicates)
res =max(res, veticles)
return res;
def gcb(self, a, b):
if(b ==0): return a
return self.gcb(b, a%b)
|
279. Perfect Squares
时间复杂度 $O(n\sqrt(n))$，复杂度的计算是有个技巧，当 $i =n$ 时候，那么 $j$ 的遍历次数最多是 $\sqrt(n)$ 所以两者相乘就可以了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution {
public:
// 动态规划求解 f[i] 表示n 所需要的最少的数量
// f[i] =min(f[i -j*j]) 其中 1<= j<= sqrt(n)
// 最后的f[n] 表示最后的解
int numSquares(int n) {
// 按照道理求解最小值，可以初始化为 INT_MAX 这样的数字
vector<int> f(n+1, n);
f[0] =0;
for(int i =1; i<=n; i++)
{
for(int j =1; j*j <=i; j++)
f[i] =min(f[i], f[i-j*j] +1);
}
return f[n];
}
};
|
python 中使用这样的方式进行实现。关键是 sqrt(i) 是可以使用 i**0.5 进行实现的。
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution(object):
def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
nums =[n] *(n+1)
nums[0] =0
for i in range(1, n+1):
for j in range(1, int(i**0.5)+1):
nums[i] =min(nums[i], nums[i -j*j] +1)
return nums[n]
|
python 有两种写法，一种是for 小暖使用 **0.5 表示 $sqrt(x) $ 的计算，一种是使用 while 循环方式。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution(object):
# 能够想到的就是枚举， 从 1 到 sqrt(n) ，然后最后的时间复杂度是 nsqrt(n)
def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
f=[n]*(n+1)
f[0] =0
for i in range(1, n+1):
j =1
while j*j <=i:
f[i] =min(f[i], f[i -j*j] +1)
j +=1
return f[n]
|
69. Sqrt(x)
LeetCode 647. Palindromic Substrings
每次固定回文子串的中间位置，然后向左右开始扩展；每次固定后，分为奇数长度和偶数长度两种情况，然后暴力统计答案即可。
时间复杂度
共有 $O(n)$ 个中间位置，固定后，最坏情况下需要$ O(n)$ 的时间扩展回文串，故总时间复杂度为 $O(n^2)$。
使用 while 更加能够体现条件循环的精髓.
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 {
public:
int countSubstrings(string s) {
int n =s.length();
int res =0;
// 这个是遍历中间结点的，
for(int i =0; i<n; i++)
{
int j =0;
while( i-j >=0 && i +j <n && s[i-j] ==s[i+j])
{
res +=1;
j +=1;
}
j =1;
while(i-j +1 >=0 && i+j <n && s[i-j +1] == s[i+j])
{
res +=1;
j +=1;
}
}
return res;
}
};
|
使用python 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution:
def countSubstrings(self, s: str) -> int:
n =len(s)
res =0
for i in range(n):
j =0
while i-j>=0 and i+j <n and s[i-j] ==s[i+j]:
res +=1
j +=1
j =1
while i-j+1 >=0 and i +j <n and s[i-j +1] ==s[i+j]:
res +=1
j +=1
return res;
|
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
|
#include<stdio.h>
#include<iostream>
#include<string>
using namespace std;
int main()
{
// 时间复杂度是 O(n^2)
string str;
while(getline(cin, str))
{
//if(s[0] =="\n") break;
int ans =0;
int n =str.length();
for (int i = 0; i < n; i++) {
for (int j = 0; i - j >= 0 && i + j < n && str[i - j] == str[i + j]; j++)
ans++;
for (int j = 1; i - j + 1 >= 0 && i + j < n && str[i - j + 1] == str[i + j]; j++)
ans++;
}
cout << ans << endl;
// 如果不是回车，那么就一直循环，如果是回车，那么就跳出
if(getchar() =='\n') break;
}
return 0;
}
|
394. Decode String
这个题目使用 python 求解，因为python 中有比较多的字符串处理的函数 isdigit() 。整体上是 stack 的应用。貌似不太好分析时间复杂度。
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 decodeString(self, s):
"""
:type s: str
:rtype: str
"""
stk =[]
for ch in s:
if ch != ']':
stk.append(ch)
else:
t =""
while stk:
ch = stk.pop()
if ch != '[':
t = ch +t
else:
num = ''
while stk and stk[-1].isdigit():
num = stk.pop() + num
t =int(num) * t
stk.append(t)
break
return "".join(stk)
|
String Compression
和上面一道题目相反的是，压缩字符串，关键是双指针的算法，不难。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution(object):
def compress(self, chars):
"""
:type chars: List[str]
:rtype: int
"""
n =len(chars)
res =""
i =0
# 如果这里使用 range() 那么是无视下面对于i 的修改的，所以
while i<n:
#for i in range(n):
j =i
while j< n and chars[j] == chars[i] : j +=1 # 这个是常见的字符串计数的方式
if j-i >1:
res += chars[i] +str(j -i)
else:
# 如果只是有一个的话，是不需要计数的
res += chars[i]
i =j
chars[:] =list(res) # 这个是作弊的操作，因为本文要求的是 in-place 的操作，所以按照道理说是不应该申请新的内存的
return len(chars)
|
48. Rotate Image
顺时针选择数组，可以分成两个步骤。
- 按照
y =x 轴对称旋转数组
- 按照 y的中点 的轴对称 旋转数组
时间复杂度是 $O(n^2)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution {
public:
// 关键是思路的问题， rotate image ，首先是按照 y =x 进行对称； 然后是按照 竖坐标轴中间进行对称
void rotate(vector<vector<int>>& matrix) {
if(matrix.empty()) return;
int n =matrix.size();
for (int i =0; i<n; i++)
{
for(int j =i+1; j<n; j ++)
{
swap(matrix[i][j] ,matrix[j][i]);
}
// 第二个转换
int m =matrix[0].size();
for(int j=0, k =m -1; j<k ; j ++, k--)
swap(matrix[i][j], matrix[i][k]);
}
}
};
|
python 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
n, m =len(matrix), len(matrix[0])
for i in range(n):
# 这个在python中实现是比较nice的
for j in range(i+1, n):
matrix[i][j], matrix[j][i] =matrix[j][i], matrix[i][j]
j, k =0, m-1
while(j <k):
matrix[i][k], matrix[i][j] =matrix[i][j], matrix[i][k]
j +=1
k -=1
|
扩展， 如果是逆时针旋转数组，那么这个时候，可以先按照 y =-x 进行旋转，然后按照 y的中点旋转数组。
54. Spiral Matrix
这个比较简单，是四个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
|
class Solution(object):
def spiralOrder(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
if not matrix: return []
top, down =0, len(matrix)-1
left, right =0, len(matrix[0]) -1
res =[]
while left <= right and top <= down:
res += matrix[top][:]
for i in range(top+1, down):
res.append(matrix[right][i])
res += matrix[down][:][::-1]
for i in range(down -1, top, -1):
res.append(matrix[left][i])
return res
|
除了使用完整的切片 [:]操作，还可以使用一下的 [left: right] 这种切片形式。
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):
def spiralOrder(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
if not matrix : return matrix
top, down =0, len(matrix) -1
left, right =0, len(matrix[0]) -1
res =[]
while top < down and left < right:
res += matrix[top][left: right]
for i in range(top, down):
res.append( matrix[i][right])
res += matrix[down][left: right +1][::-1]
for i in range(down-1, top, -1):
res.append( matrix[i][left])
top +=1
down -=1
left +=1
right -=1
if top ==down:
res += matrix[top][left: right+1]
elif left ==right:
for i in range(top, down +1):
res.append(matrix[i][left])
return res
|
上面使用的是更新完一次，然后更新
使用类似的版本的代码， 边界问题通过多个 break语句进行处理， exactly 的方式进行处理。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
class Solution {
public:
// 边界问题如何处理
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> res;
int n = matrix.size();
if(!n) return res;
int m =matrix[0].size();
int l=0, r=m-1, u=0, d=n-1;
while (true){
if(l<=r)
for(int i =l ; i<=r; i++) res.push_back(matrix[u][i]);
else break;
u +=1;
if(u <= d)
for(int i =u ; i<=d; i++) res.push_back(matrix[i][r]);
else break;
r -=1;
if(l <=r)
for(int i=r; i>=l; i--) res.push_back(matrix[d][i]);
else break;
d -=1;
if(u<=d)
for(int i=d; i>=u; i--) res.push_back(matrix[i][l]);
else break;
l +=1;
}
return res;
}
};
|
[https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/](Remove Duplicates from Sorted List 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
|
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
// 这个是常常考察的笔试题
ListNode* deleteDuplicates(ListNode* head) {
ListNode * dummy = new ListNode(-1);
dummy ->next =head;
ListNode * p =dummy;
while(p ->next)
{
auto q =p->next;
while(q && q->val ==p->next->val) q = q->next;
// if 中表示的没有重复的元素， else中表示有重复的元素
if(p->next ->next ==q) p =p->next;
else p->next =q;
}
return dummy->next;
}
};
|
python 实现。 注意在新建对象中 python 是直接 ListNode 但是 c++ 中需要new 关键字。然后指针的使用 c++ 中 -> 然后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 singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def deleteDuplicates(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
# 有一些细节需要注意
dummy = ListNode(-1)
dummy.next =head
p = dummy
while( p.next):
q =p.next
while(q and p.next.val == q.val):
q =q.next
if(p.next.next ==q):
p=p.next;
else:
p.next =q
return dummy.next
|
Remove Duplicates from Sorted List
其中的 if 表示并没有舍弃当前的结点，每次都是前进一步。和上面那道题中，使用while 找到最后的结点不同。一个个进行操作，因为其中使用的 if 语句。上面的全部去掉使用的是 while 语句。
python 版本
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.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
# 这道题目相对上一道题目就比较简单，
class Solution(object):
def deleteDuplicates(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head: return head;
p =head
while p.next:
if(p.val == p.next.val):
p.next =p.next.next
else:
p =p.next
return head
|
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* deleteDuplicates(ListNode* head) {
if(! head) return head;
ListNode* p =head;
while(p->next)
{
// 这句话并没有舍弃当前的结点，每次都是移动一步，
if(p->next->val == p->val) p->next= p->next->next;
else p =p->next;
}
return head;
}
};
|