Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitfe106a0

Browse files
Improvement
Signed-off-by: begeekmyfriend <begeekmyfriend@gmail.com>
1 parent999ff02 commitfe106a0

File tree

4 files changed

+127
-12
lines changed

4 files changed

+127
-12
lines changed

‎0043_multiply_strings/multiply_strings.cc‎

Lines changed: 14 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -5,23 +5,29 @@ using namespace std;
55
classSolution {
66
public:
77
stringmultiply(string num1, string num2) {
8-
stringres(num1.length() + num2.length(),'0');
8+
vector<int>v(num1.length() + num2.length());
99
for (int i = num2.length() -1; i >=0; i--) {
10-
int j, carry =0;
11-
for (j = num1.length() -1; j >=0; j--) {
12-
carry += (num1[j] -'0') * (num2[i] -'0') + (res[i + j +1] -'0');
13-
res[i + j +1] = carry %10 +'0';
14-
carry /=10;
10+
for (int j = num1.length() -1; j >=0; j--) {
11+
int a = num2[j] -'0';
12+
int b = num1[i] -'0';
13+
v[i + j +1] = a * b;
1514
}
16-
res[i + j +1] = carry +'0';
1715
}
1816

19-
int i;
17+
int i, carry =0;
18+
stringres(v.size(),'0');
19+
for (i = v.size() -1; i >=0; i--) {
20+
carry += v[i];
21+
res[i] += carry %10;
22+
carry /=10;
23+
}
24+
2025
for (i =0; i < res.length() -1; i++) {
2126
if (res[i] !='0') {
2227
break;
2328
}
2429
}
30+
2531
return res.substr(i);
2632
}
2733
};
Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
#include<bits/stdc++.h>
2+
3+
usingnamespacestd;
4+
5+
classSolution {
6+
public:
7+
vector<vector<string>>partition(string s) {
8+
vector<vector<string>> res;
9+
vector<vector<bool>>isPalindrome(s.size(), vector<bool>(s.size(),true));
10+
11+
// From bottom to up
12+
for (int i = s.length() -1; i >=0; i--) {
13+
// From left to right
14+
for (int j = i +1; j < s.length(); j++) {
15+
// notebook for palindrome substring judgement
16+
isPalindrome[i][j] = s[i] == s[j] && isPalindrome[i +1][j -1];
17+
}
18+
}
19+
20+
dfs(s,0, isPalindrome, res);
21+
return res;
22+
}
23+
24+
private:
25+
vector<string> ans;
26+
voiddfs(const string& s,int start, vector<vector<bool>>& isPalindrome, vector<vector<string>>& res) {
27+
// DFS for combination. When the start index reaches to the end, all
28+
// the substrings are collected.
29+
if (start == s.length()) {
30+
res.push_back(ans);
31+
return;
32+
}
33+
34+
for (int i = start; i < s.length(); i++) {
35+
if (isPalindrome[start][i]) {
36+
ans.push_back(s.substr(start, i - start +1));
37+
dfs(s, i +1, isPalindrome, res);
38+
ans.pop_back();
39+
}
40+
}
41+
}
42+
};

‎0133_clone_graph/clone_graph.cc‎

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
#include<bits/stdc++.h>
2+
3+
usingnamespacestd;
4+
5+
// Definition for a Node.
6+
classNode {
7+
public:
8+
int val;
9+
vector<Node*> neighbors;
10+
Node() {
11+
val =0;
12+
neighbors = vector<Node*>();
13+
}
14+
Node(int _val) {
15+
val = _val;
16+
neighbors = vector<Node*>();
17+
}
18+
Node(int _val, vector<Node*> _neighbors) {
19+
val = _val;
20+
neighbors = _neighbors;
21+
}
22+
};
23+
24+
classSolution {
25+
public:
26+
Node*cloneGraph(Node* node) {
27+
if (node ==nullptr) {
28+
return node;
29+
}
30+
#if1// DFS
31+
if (cloned.find(node) != cloned.end()) {
32+
return cloned[node];
33+
}
34+
35+
cloned[node] =newNode(node->val);
36+
37+
for (auto& neighbor : node->neighbors) {
38+
cloned[node]->neighbors.emplace_back(cloneGraph(neighbor));
39+
}
40+
#else // BFS
41+
queue<Node *> q;
42+
q.push(node);
43+
cloned[node] = new Node(node->val);
44+
45+
while (!q.empty()) {
46+
int size = q.size();
47+
for (int i = 0; i < size; i++) {
48+
auto n = q.front();
49+
q.pop();
50+
51+
for (auto& neighbor : n->neighbors) {
52+
if (cloned.find(neighbor) == cloned.end()) {
53+
cloned[neighbor] = new Node(neighbor->val);
54+
q.push(neighbor);
55+
}
56+
cloned[n]->neighbors.emplace_back(cloned[neighbor]);
57+
}
58+
}
59+
}
60+
#endif
61+
return cloned[node];
62+
}
63+
private:
64+
unordered_map<Node *, Node *> cloned;
65+
};

‎0567_permutation_in_string/permutation_in_string.cc‎

Lines changed: 6 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -10,18 +10,20 @@ class Solution {
1010
count[c]++;
1111
}
1212

13-
int l =0, r =0,len =0;
13+
int l =0, r =0,hits =0;
1414
while (r < s2.length()) {
1515
if (--count[s2[r++]] >=0) {
16-
len++;
16+
hits++;
1717
}
1818

19+
// When the window length equals to the hit length,
20+
// the permutation is contained.
1921
if (r - l >= s1.length()) {
20-
if (len == s1.length()) {
22+
if (hits == s1.length()) {
2123
returntrue;
2224
}
2325
if (++count[s2[l++]] >0) {
24-
len--;
26+
hits--;
2527
}
2628
}
2729
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp