Add Two Numbers
1
2
3
4
5
6
7
8
9
10
11
12
13
|
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
ListNode preHead(0), *p = &preHead;
int extra = 0;
while (l1 || l2 || extra) {
int sum = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + extra;
extra = sum / 10;
p->next = new ListNode(sum % 10);
p = p->next;
l1 = l1 ? l1->next : l1;
l2 = l2 ? l2->next : l2;
}
return preHead.next;
}
|
String to Integer (atoi)
关键点在于要设long类型的变量，字符转数字应该是字符减去‘0’
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
int myAtoi(string str) {
long result = 0;
int indicator = 1;
auto iter = str.cbegin();
while (iter != str.cend() && isspace(*iter)) ++iter;
if (iter != str.cend() && (*iter == '-' || *iter == '+'))
indicator = (*iter++ == '-') ? -1 : 1;
while (iter != str.cend() && isdigit(*iter))
{
result = result * 10 + (*iter++ - '0');
if (result * indicator >= INT_MAX) return INT_MAX;
if (result * indicator <= INT_MIN) return INT_MIN;
}
return result * indicator;
}
|
Remove Nth Node From End of List
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode preHead(0);
preHead->next = head;
ListNode *fast = &preHead, *slow = &preHead;
for (int i = 0; i != n; ++i)
fast = fast->next;
while (fast->next){
fast = fast->next;
slow = slow->next;
}
ListNode *to_del = slow->next;
slow->next = slow->next->next;
delete to_del;
return preHead.next;
}
}; // 判断fast->next使得fast停留在最后一个节点，这样就方便多了
|
Merge Two Sorted Lists
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (!l1) return l2;
if (!l2) return l1;
ListNode preHead(0), *curr = &preHead;
while (l1 && l2){
if (l1->val <= l2->val){
curr->next = l1;
curr = curr->next;
l1 = l1->next;
} else {
curr->next = l2;
curr = curr->next;
l2 = l2->next;
}
}
curr->next = l1 ? l1 : l2;
return preHead.next;
}
}; //必须注意其中有某条为空的情况，长度不同的时候只要if判断不能再while
|
Remove Duplicates from Sorted Array
1
2
3
4
5
6
7
|
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
return distance(nums.begin(), unique(nums.begin(), nums.end()));
}
};
// 若用常规解法，测试第一个元素不能用任何值，迭代器失效要考虑好。
|
Remove Element
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
auto left = nums.begin();
for (auto iter = left; iter != nums.end(); ++iter)
if (*iter != val)
*left++ = *iter;
nums.erase(left, nums.end());
return nums.size();
}
}; // 拷贝值就会简单很多
return distance(nums.begin(), remove(nums.begin(), nums.end(), target));
|
Implement strStr()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution {
public:
int strStr(string haystack, string needle) {
if (needle.empty())
return 0;
const int max_test = haystack.size() - needle.size() + 1;
for (auto k = 0;k <= max_test; ++k){
auto i = k, j = 0;
for( ;i != haystack.size() && j != needle.size(); ++i, ++j)
if (haystack[i] != needle[j])
break;
if (j == needle.size())
return k;
}
return -1;
}
}; //必须用const int 保存max_test，auto会出错。
|
Merge Sorted Array
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int ia = m - 1, ib = n - 1;
int icurr = m + n - 1;
while (ia >= 0 && ib >= 0) {
nums1[icurr--] = nums1[ia] >= nums2[ib] ? nums1[ia--] : nums2[ib--];
}
while (ib >= 0)
nums1[icurr--] = nums2[ib--];
}
};
|
Binary Tree Level Order Traversal
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
|
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> result;
if (!root) return result;
queue<TreeNode*> nodes;
nodes.push(root);
nodes.push(nullptr);
vector<int> layer;
while (!nodes.empty()){
TreeNode *curr = nodes.front();
nodes.pop();
if (curr){
if (curr->left)
nodes.push(curr->left);
if (curr->right)
nodes.push(curr->right);
layer.push_back(curr->val);
} else {
result.push_back(layer);
layer.clear();
if (!nodes.empty())
nodes.push(nullptr);
}
}
return result;
}
};
// 当一层遍历完了且队列不为空的时候才push nullptr
|
Valid Palindrome
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:
bool isPalindrome(string s) {
bool result = true;
auto left = s.cbegin();
if (left == s.cend())
return result;
auto right = prev(s.end());
while (left < right){
if (!isalnum(*left))
++left;
else if (!isalnum(*right))
--right;
else if (tolower(*left) != tolower(*right))
return false;
else {
++left;
right--;
}
}
return result;
}
};
|
Linked List Cycle
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode *fast = head, *slow = head;
while (fast && fast->next){
fast = fast->next->next;
slow = slow->next;
if (fast == slow)
return true;
}
return false;
}
};
|
Palindrome Linked List
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
|
class Solution {
public:
bool isPalindrome(ListNode* head) {
if (!head || !head->next)
return true;
ListNode *fast = head;
ListNode *slow = head;
while(fast->next &&fast->next->next){
slow = slow->next;
fast = fast->next->next;
}
slow->next = reverse(slow->next);
slow = slow->next;
while(slow!=NULL){
if(head->val!=slow->val)
return false;
head=head->next;
slow=slow->next;
}
return true;
}
ListNode *reverse(ListNode *head){
ListNode *prev = nullptr;
ListNode *next = nullptr;
while (head){
next = head->next;
head->next = prev;
prev = head;
head = next;
}
return prev;
}
};
|