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

Commitee55708

Browse files
committed
[Function add]
1. Add two leetcode solutions using C++.
1 parent88ee419 commitee55708

File tree

2 files changed

+89
-0
lines changed

2 files changed

+89
-0
lines changed

‎leetcode/307. Range Sum Query - Mutable.md

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -300,4 +300,41 @@ class NumArray {
300300
* obj.update(i,val);
301301
* int param_2 = obj.sumRange(i,j);
302302
*/
303+
```
304+
305+
###C++ Version
306+
```objectc
307+
class NumArray {
308+
private:
309+
vector<int> sum_;
310+
vector<int> nums_;
311+
public:
312+
NumArray(vector<int>& nums): nums_(std::move(nums)) {
313+
int size = nums_.size();
314+
if(size == 0) return;
315+
sum_.resize(size, 0);
316+
sum_[0] = nums_[0];
317+
for(int i = 1; i < size; i++){
318+
sum_[i] = sum_[i - 1] + nums_[i];
319+
}
320+
}
321+
void update(int i, int val) {
322+
int pre = nums_[i];
323+
nums_[i] = val;
324+
int diff = val - pre;
325+
for(int j = i; j < sum_.size(); j++){
326+
sum_[j] += diff;
327+
}
328+
}
329+
int sumRange(int i, int j) {
330+
return sum_[j] - sum_[i] + nums_[i];
331+
}
332+
};
333+
334+
/**
335+
* Your NumArray object will be instantiated and called as such:
336+
* NumArray* obj = new NumArray(nums);
337+
* obj->update(i,val);
338+
* int param_2 = obj->sumRange(i,j);
339+
*/
303340
```

‎leetcode/720. Longest Word in Dictionary.md

Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -84,3 +84,55 @@ The length of words[i] will be in the range [1, 30].
8484
}
8585
}
8686
```
87+
88+
###C++ version
89+
```objectc
90+
class Solution {
91+
public:
92+
string longestWord(vector<string>& words) {
93+
root_.reset(new Node());
94+
sort(words.begin(), words.end());
95+
for(const string & word: words){
96+
int len = word.length();
97+
if(len == 1 && !root_->childs[word[0] - 'a']){
98+
root_->childs[word[0] - 'a'] = new Node();
99+
root_->childs[word[0] - 'a']->isLeaf = true;
100+
}else{
101+
Node* pre = find(word.substr(0, len - 1));
102+
if(!pre) continue;
103+
else if(!pre->childs[word[len - 1] - 'a']){
104+
pre->childs[word[len - 1] - 'a'] = new Node();
105+
}
106+
pre->childs[word[len - 1] - 'a']->isLeaf = true;
107+
}
108+
if(len > max_){
109+
max_ = len;
110+
res_ = word;
111+
}
112+
}
113+
return res_;
114+
}
115+
private:
116+
struct Node{
117+
vector<Node*> childs;
118+
bool isLeaf;
119+
Node(): isLeaf(false), childs(26, nullptr){}
120+
~Node(){
121+
for(auto node: childs){
122+
delete node;
123+
}
124+
}
125+
};
126+
unique_ptr<Node> root_;
127+
Node* find(string word){
128+
Node* temp = root_.get();
129+
for(const char &c: word){
130+
if(!temp->childs[c - 'a']) return nullptr;
131+
temp = temp->childs[c - 'a'];
132+
}
133+
return temp->isLeaf ? temp: nullptr;
134+
}
135+
int max_ = 0;
136+
string res_ = "";
137+
};
138+
```

0 commit comments

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