刷题整理笔记。
最小编辑距离
链接地址
leetcode 版本
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
|
#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
int minDistance(string word1, string word2) {
int rows = word1.length();
int cols = word2.length();
vector<vector<int> > dp(rows+1, vector<int>(cols+1, 0));
for(int i=1; i<=rows; ++i)
dp[i][0] = i;
for(int j=1; j<=cols; ++j)
dp[0][j] = j;
for(int i=1; i<=rows; ++i){
for(int j=1; j<=cols; ++j){
if(word1[i-1] == word2[j-1])
dp[i][j] = dp[i-1][j-1];
else
dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1;
}
}
return dp[rows][cols];
}
};
int main()
{
Solution solution;
string str1 ="hello";
string str2 ="hello1";
cout << solution.minDistance(str1, str2) << endl;
return 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
|
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
/**
使用dp 的思想，
f[i][j] 表示string1中第i 个位置和 string2 中第j 位置之间的最小编辑距离
转移: f[i][j] =f[i-1][j-1] if string1[i] ==string2[j]
= min(f[i-1][j], f[i][j-1] ) 对应的是修改
初始化: f[0][0] =1, 然后f[i][0] 和 f[0][j] 都是0， 最后的f[m][n] 就是最后的结果
**/
int main()
{
string str1, str2;
cin >> str1>> str2;
int n,m;
n =str1.size(), m =str2.size();
vector<vector<int>> f(n+1, vector<int>(m+1));
// 初始化需要根据实际意义进行
f[0][0] =0;
for(int i =1; i<=n; i++) f[i][0] =i;
for(int j =1; j<=m ;j++) f[0][j] =j;
for(int i =1; i<=n; i++)
{
for(int j =1; j<=m; j++)
{
//if(!i ||!j) f[i][j] =0;
if(str1[i] ==str2[j]) f[i][j] =f[i-1][j-1];
else
{
f[i][j] =min(f[i-1][j-1], min(f[i-1][j], f[i][j-1]))+1;
}
}
}
cout<<f[n][m]<<endl;
return 0;
}
|
python 语言实现
注意两种初始化的区别：
1
2
|
dp =[(cols+1)*[0]]*(rows+1) # 这种是不 work 的
dp =[ [0] *(cols+1) for _ in range(rows+1)] # 这种是 work 的
|
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
|
def minDistance(string1, string2):
if not string1 or not string2 : return
rows, cols =len(string1), len(string2)
if rows ==0: return cols;
elif cols ==0: return rows;
#dp =[(cols+1)*[0]]*(rows+1)
dp =[ [0] *(cols+1) for _ in range(rows+1)]
for i in range(1, rows+1): dp[i][0] =i
for j in range(1, cols+1): dp[0][j] =j
#ipdb.set_trace()
for i in range(1, rows+1):
for j in range(1, cols+1):
if string1[i-1] ==string2[j-1]:
dp[i][j] =dp[i-1][j-1]
else:
dp[i][j] =1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])
return dp[-1][-1]
print(minDistance("string1", "string"))
|
** 从无头单链表中删除节点**
删除节点的通常做法是找到该结点的前一个结点（头结点），然后 head.next =head.next.next
这个题目说没有头结点，直接给出的就是应该删除的结点
假设这个是头结点，那么下一个是待删除的结点，所以 current.next =current.next.next ，但是需要把current.next.value 赋值给 current.value
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
|
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef struct node{
int data;
node *next;
}Node;
void delete_node(Node *current)
{
assert(current !=NULL);
Node *next =current->next;
if (next !=NULL)
{
current->next =next->next
current-> data =next-> data;
}
}
int main()
{
return 0;
}
|
38. Count and Say
https://leetcode.com/problems/count-and-say/
leetcode 版本
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:
string countAndSay(int n) {
string s ="1";
for(int i =0; i<n -1; i++)
{
string ns;
for(int j =0; j< s.size();j++ )
{
int k =j;
while(s[k] ==s[j]) k++;
ns += to_string(k-j)+ s[j];
j =k -1;
}
s =ns;
}
return s;
}
};
|
单机版本
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
|
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
string count_say(int n)
{
string s ="1";
for(int i =0; i<n-1; i++)
{
string ns;
for(int j =0; j<s.size(); j++)
{
int k =j;
while( s[k] ==s[j]) k++;
ns += to_string(k-j)+s[j];
j = k-1;
}
s =ns;
}
return s;
}
int main()
{
int n;
cin >>n;
cout<< count_say(n)<<endl;
return 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
|
class Solution {
public:
// 单词不同组合的本质，然后使用dictionary 进行存储
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> hash;
for(auto str: strs)
{
string tmp =str;
sort(tmp.begin(), tmp.end());
hash[tmp].push_back(str);
}
// 本质 -> 现象
//for(auto item: hash) cout<<item<<endl;
vector<vector<string>> res;
for(auto item: hash) res.push_back(item.second);
return res;
}
};
|
https://leetcode.com/problems/group-anagrams/submissions/
vector中push_back 类似 python 中list 的append 操作
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
|
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<unordered_map>
using namespace std;
// 单词打错了，也是不通过的
vector<vector<string>> group(vector<string>& input)
{
// 还原本质,
unordered_map<string, vector<string>> dict; // map 的底层实现是平衡树，操作的时间复杂度是logn， 所以慢，而unordered_map(hash表) 是常数
for(auto str : input)
{
string tmp =str;
sort(tmp.begin(), tmp.end());
dict[tmp].push_back(str);
}
// 结果
vector<vector<string>> res;
for(auto key: dict) res.push_back(key.second);
return res;
}
int main()
{
int n ;
cin>>n;
vector<string> input;
for(int i =0; i<n;i++)
{
string tmp ;
cin >>tmp;
input.push_back(tmp);
}
vector<vector<string>> res =group(input);
for(auto u: res)
{
for(auto v: u)
cout<< v<<" ";
cout<<endl;
}
return 0;
}
|
Two sum 系列套题
有多对解，输出一对解就可以。最简单的一种情况。
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>
#include<unordered_set>
#include "vector"
using namespace std;
#define LEN 100
vector<int> nums(LEN);
vector<int> find_sum(vector<int> & nums, int target)
{
unordered_set<int> hash;
for(int i =0; i<nums.size(); i++)
{
if(hash.count(target -nums[i] )) return vector<int>{target-nums[i], nums[i]};
hash.insert(nums[i]);
}
return vector<int>();
}
int main()
{
int n , target;
cin >>n >> target;
for(int i =0; i<n; i++)
cin>> nums[i];
vector<int> res =find_sum(nums, target);
for(int i =0; i<res.size(); i++)
cout<< res[i]<<" ";
cout<<endl;
return 0;
}
|
逆序对
暴力求解，时间复杂度是$O(N^2)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution {
public:
int InversePairs(vector<int> data) {
int n =data.size();
// 先是暴力求解 理解一下题意
int res =0;
for(int i =0; i<n; i++)
{
for(int j =i+1; j<n; j++)
if(data[i] >data[j]) res +=1;
}
return res;
}
};
|
这个在牛客网上，使用归并的方式，也是没有办法完全通过，只能保证是 50% 的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
28
29
30
31
32
33
34
|
class Solution {
public:
// 归并排序 时间复杂度 O(nlogn), 对于当前的区间分成左区间的结果，右区间的结果和两个区间之间的结果
// 递归的思想就是要递归跳出的条件
int merge(vector<int>& data, int l, int r)
{
if(l >=r) return 0;
int mid =l +r >>1;
int res= merge(data, l, mid) +merge(data, mid+1, r);
int i =l, j =mid+1;
vector<int> temp;
while( i<=mid && j<=r)
{
if(data[i]< data[j]) temp.push_back(data[i++]);
else
{
res += mid -i+1;
temp.push_back(data[j++]);
}
}
while(i<=mid) temp.push_back(data[i++]);
while(j <=r) temp.push_back(data[j++]);
// 这个是当前区间的起点
i =l;
for(auto u: temp) data[i++] =u;
return res % 1000000007;
}
int InversePairs(vector<int> data) {
return merge(data, 0, data.size()-1);
}
};
|