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

Commitf0b78e6

Browse files
committed
[Function add]
1. Add leetcode solutions using c++.
1 parentee55708 commitf0b78e6

4 files changed

+174
-0
lines changed

‎leetcode/17. Letter Combinations of a Phone Number.md

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -115,4 +115,29 @@ class Solution {
115115
}
116116
}
117117
}
118+
```
119+
120+
###C++ version
121+
* Method 1: recursion
122+
```objectivec
123+
class Solution {
124+
private:
125+
vector<string> res_;
126+
string key[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
127+
public:
128+
vector<string> letterCombinations(string digits) {
129+
if(digits.empty()) return res_;
130+
recursion(digits, "", 0);
131+
return res_;
132+
}
133+
void recursion(string s, string cur, int index){
134+
if(index == s.length()) res_.emplace_back(cur);
135+
else{
136+
string letters = key[s[index] - '0'];
137+
for(const char c: letters){
138+
recursion(s, cur + c, index + 1);
139+
}
140+
}
141+
}
142+
};
118143
```

‎leetcode/39. Combination Sum.md

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -135,4 +135,35 @@ class Solution {
135135
}
136136
}
137137
}
138+
```
139+
140+
###C++ version
141+
* Method 1: Recursion
142+
```objectivec
143+
class Solution {
144+
private:
145+
vector<vector<int>> res_;
146+
vector<int> candidates_;
147+
int target_;
148+
public:
149+
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
150+
if(candidates.empty()) return res_;
151+
candidates_ = candidates;
152+
target_ = target;
153+
vector<int> cur;
154+
recursion(0, 0, cur);
155+
return res_;
156+
}
157+
void recursion(int index, int sum, vector<int>& cur){
158+
if(sum == target_) res_.push_back(cur);
159+
else if(sum < target_){
160+
int size = candidates_.size();
161+
for(int i = index; i < size; ++i){
162+
cur.push_back(candidates_[i]);
163+
recursion(i, sum + candidates_[i], cur);
164+
cur.pop_back();
165+
}
166+
}
167+
}
168+
};
138169
```

‎leetcode/745. Prefix and Suffix Search.md

Lines changed: 98 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -160,9 +160,107 @@ Note:
160160
*Method3:TrieTree
161161
* we construct anew word before inserting to tire tree.
162162
* Example: app, we save -app, p-app, pp-app, app-app, which contains all possible suffix conditions, since the question memtioned that word range is from 0 to 10.
163+
164+
```objectivec
165+
class Trie{
166+
private:
167+
structNode{
168+
vector<Node*> childs;
169+
int index;
170+
Node(): index(-1), childs(27, nullptr){};
171+
~Node(){
172+
for(auto node: childs){
173+
delete node;
174+
}
175+
}
176+
};
177+
Node*find(conststring &s){
178+
Node* temp= root_.get();
179+
for(constchar& c: s){
180+
if(!temp->childs[c-'a'])return nullptr;
181+
temp= temp->childs[c-'a'];
182+
}
183+
return temp;
184+
}
185+
unique_ptr<Node> root_;
186+
public:
187+
Trie():root_(newNode()){};
188+
voidinsert(conststring &word,intindex){
189+
Node* temp= root_.get();
190+
for(constchar& c: word){
191+
if(!temp->childs[c-'a']){
192+
temp->childs[c-'a']=newNode();
193+
}
194+
temp= temp->childs[c-'a'];
195+
temp->index= index;
196+
}
197+
}
198+
199+
intstartWith(conststring &s){
200+
auto node= find(s);
201+
if(!node)return-1;
202+
return node->index;
203+
}
204+
};
205+
classWordFilter {
206+
private:
207+
Trie trie_;
208+
public:
209+
WordFilter(vector<string>&words) {
210+
int size= words.size();
211+
for(int i=0; i< size;++i){
212+
const string word= words[i];
213+
int len= word.length();
214+
for(int j= len; j>=0; j--)
215+
trie_.insert(word.substr(j, len)+"{"+ word, i);
216+
}
217+
}
218+
219+
intf(stringprefix,stringsuffix) {
220+
return trie_.startWith(suffix+"{"+ prefix);
221+
}
222+
};
223+
/**
224+
* Your WordFilter object will be instantiated and called as such:
225+
* WordFilter* obj = new WordFilter(words);
226+
* int param_1 = obj->f(prefix,suffix);
227+
*/
228+
```
163229

164230
*Method4:Hashmap
165231
* we create two hashmaps(key isString of prefix or suffix, value is a list to save the word) to save all possible prefix and suffix.
166232
*Example: app
167233
* prefix map: a, ap, app
168234
* suffix map: p, pp, app
235+
236+
```objectc
237+
classWordFilter {
238+
public:
239+
WordFilter(vector<string>&words) {
240+
int size= words.size();
241+
for(int k=0; k< size;++k){
242+
string word= words[k];
243+
int len= word.length();
244+
for(int i=0; i<= len;++i){
245+
string prefix= word.substr(0, i);
246+
for(int j= len; j>=0;--j){
247+
string key= prefix+"_"+ word.substr(j, len);
248+
map_[key]= k;
249+
}
250+
}
251+
}
252+
}
253+
intf(stringprefix,stringsuffix) {
254+
auto ptr= map_.find(prefix+"_"+ suffix);
255+
if(ptr== map_.end())return-1;
256+
return ptr->second;
257+
}
258+
private:
259+
unordered_map<string,int> map_;
260+
};
261+
/**
262+
* Your WordFilter object will be instantiated and called as such:
263+
* WordFilter* obj = new WordFilter(words);
264+
* int param_1 = obj->f(prefix,suffix);
265+
*/
266+
```

‎leetcode/901. Online Stock Span.md

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -64,3 +64,23 @@ Note:
6464
* int param_1 = obj.next(price);
6565
*/
6666
```
67+
68+
###C++ Version
69+
* Method 1: monostack
70+
```objectivec
71+
class StockSpanner {
72+
public:
73+
StockSpanner() {}
74+
int next(int price) {
75+
int span = 1;
76+
while(!stack_.empty() && price >= stack_.top().first){
77+
span += stack_.top().second;
78+
stack_.pop();
79+
}
80+
stack_.emplace(price, span);
81+
return span;
82+
}
83+
private:
84+
stack<pair<int, int>> stack_; // first: price, second: span
85+
};
86+
```

0 commit comments

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