707 Design Linked List
错因：思考不完善，对于双链表，如何判断达到尾节点、插入索引的范围是多少（0到size都行）、删除索引的范围是多少（0到size-1）
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
61
62
63
64
65
66
67
68
69
70
| struct _node{
int val;
_node *prev;
_node *next;
_node(int val):val(val){};
};
class MyLinkedList {
private:
_node *node;
unsigned int size;
_node* find_index(int index){
_node *temp = node;
for(int i = 0; i <= index; i++){
temp = temp->next;
if(temp == node && i != index) // 注意这里很关键
return nullptr;
}
return temp;
}
public:
MyLinkedList(int val = -1) {
node = new _node(val);
node->prev = node;
node->next = node;
size = 0;
}
int get(int index) {
_node *temp = node;
for(int i = 0; i <= index; i++){
temp = temp->next;
if(temp == node)
return -1;
}
return temp->val;
}
void addAtHead(int val) {
addAtIndex(0, val);
}
void addAtTail(int val) {
addAtIndex(size, val);
}
void addAtIndex(int index, int val) {
auto temp = find_index(index);
if(!temp)
return;
_node *data = new _node(val);
temp->prev->next = data;
data->prev = temp->prev;
temp->prev = data;
data->next = temp;
size++;
}
void deleteAtIndex(int index) {
if(index >= size)
return;
auto temp = find_index(index);
if(!temp)
return;
auto prev = temp->prev;
auto next = temp->next;
prev->next = next;
next->prev = prev;
delete temp;
size--;
}
};
|
24 反转节点
错误原因：没有考虑尾端链表置空
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* phead = new ListNode();
ListNode* phead_cycle = phead;
phead->next = head;
ListNode* next;
ListNode* thead = head;
while(thead != nullptr && thead->next != nullptr){
next = thead->next->next;
phead_cycle->next = thead->next;
phead_cycle->next->next = thead;
phead_cycle = thead;
thead = next;
}
phead_cycle->next = thead; // 没有这行就错了
head = phead->next;
//delete phead;[1,2,3,4]
return head;
}
};
|
19 移除元素
错误原因：思维不够缜密，比如mid == nullptr没判断
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
| class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
vector<ListNode*> vec;
ListNode* hhead = new ListNode();
ListNode* temp = hhead;
hhead->next = head;
if(!head)
return head;
while(temp->next != nullptr){
vec.push_back(temp);
temp = temp->next;
}
if(n > vec.size()){
delete hhead;
return head;
}
else{//主要是这里出错
temp = vec[vec.size() - n];
ListNode *mid = temp->next;
if(mid == nullptr){
temp->next = mid;
}
else{
temp->next = mid->next;
delete mid;
}
mid = hhead->next;
delete hhead;
return mid;
}
}
};
|
142 环形链表
主要思路是对的，但是为什么最后的while变成do while就不对了
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
| class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if(!head)
return head;
ListNode *fast = head, *low = head;
do{
if(fast->next != nullptr && fast->next->next != nullptr)
fast = fast->next->next;
else
return nullptr;
low = low->next;
}
while(low != fast);
low = head;
while(low != fast){ // 变成do while 就会错两个
fast = fast->next;
low = low->next;
}
;
return low;
}
};
|
454
这题分为四个数，可以选择两两凑对，但错误点在于，两两之和没找全（第一个建立map的循环只写了一个）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
map<int, int> first, last;
for(int i = 0; i < nums1.size(); i++){
for(int j = 0; j < nums1.size(); j++){
first[nums1[i] + nums2[j]]++;
last[nums3[i] + nums4[j]]++;
}
}
int counts = 0;
map<int, int>::iterator temp;
for(auto it : first){
if(last.count(-it.first)){
counts += it.second * last.find(-it.first)->second;
}
}
return counts;
}
};
|
三数之和
一个很大的问题在于超时，
滑动窗口最大值239
要记录滑动窗口的最大值，只需要维护一个单调队列就行了，要动脑子想一下。
有点像kmp需要一个结构，来维护之前的信息，而更近的、更小的数据肯定是不需要的。
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
| class mycon{
public:
deque<int> _data;
void push(int item){
while(!_data.empty() && item > _data.back()) _data.pop_back();
_data.push_back(item);
}
void pop(int item){
if(_data.front() == item){//如果item < front,那么该节点肯定没有被加入到deque中，不用管
_data.pop_front();
}
}
const int front(){return _data.front();};
};
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
/*vector<int> out;
int max;
for(int i = 0; i <= nums.size()-k; i++){
max = nums[i];
for(int j = i ; j < i+k; j++){
max = max > nums[j] ? max:nums[j];
}
out.push_back(max);
}
return out;*/
mycon con;
vector<int> out;
for(int i = 0; i < k; i++){
con.push(nums[i]);
}
out.push_back(con.front());
for(int i = k; i < nums.size(); i++){
con.push(nums[i]);
con.pop(nums[i-k]);
out.push_back(con.front());
}
return out;
}
};
|
前k个高频元素
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。首先可以通过一个map来统计，关键是如何根据值来排序，如果需要全排序，使用vector是可以的，但这里只需要找出k个最大的，用堆是最好的。优先级队列其实就是个堆。假设是n个数中找k个最大的数，
- 如果用大顶堆，则需要构建容量为n的堆，然后pop出k个数
- 如果用小顶堆，则需要构建容量为k的堆，堆中的数就是答案
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 compare{
public:
bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs){
return lhs.second > rhs.second;
}
};
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
vector<int> out;
map<int, int> mmm;
for(int i = 0; i < nums.size(); i++){
mmm[nums[i]]++;
}
priority_queue<pair<int, int>, vector<pair<int, int>>, compare> com;
for(const auto &item : mmm){
com.push(item);
if(com.size() > k)
com.pop();
}
while(com.size()){
auto temp = com.top();
com.pop();
out.push_back(temp.first);
}
return out;
}
};
|
二叉树的迭代法遍历方式
二叉树使用栈很好遍历，使用迭代法时，前序很好处理，但后序和中序需要做点额外的处理。
用cur来访问左子节点，用栈来存储父节点.如果是后序，还需要一个变量来标识上一次访问的是左子节点还是右子节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
TreeNode* cur = root;
vector<int> out;
stack<TreeNode*> st;
//用cur来访问左子节点，用栈来存储父节点
while(nullptr != cur || !st.empty()){
if(nullptr != cur){
st.push(cur);
cur = cur->left;
}
else{
cur = st.top();
st.pop();
out.push_back(cur->val);
cur = cur->right;
}
}
return out;
}
};
|
后序
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
| vector<int> postorderTraversal(TreeNode* root) {
vector<int> out;
TreeNode* cur = root, *last_visit = nullptr;
stack<TreeNode*> st;
while(nullptr != cur || !st.empty()){
if(nullptr != cur){
st.push(cur);
cur = cur->left;
}
else{
cur = st.top();
if(cur->right && cur->right != last_visit){
st.push(cur->right);
cur = cur->right->left;
}
else{
last_visit = cur;
out.push_back(cur->val);
st.pop();
cur = nullptr; //这行很关键
}
}
}
return out;
}
|
迭代的统一版本：中序
可以使用加节点后加nullptr代表该节点的左子节点被访问了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| TreeNode* cur = root;
vector<int> out;
stack<TreeNode*> st;
if(root) st.push(root);
while(!st.empty()){
cur = st.top();
if(cur == nullptr){ //注意这里不能使用st.top() == nullptr, 而省略上面那行，会导致if内的cur没有被更新。
st.pop();
cur = st.top();
st.pop();
out.push_back(cur->val);
if(cur->right) st.push(cur->right); //千万不能将空接点加进去了
}
else{
st.push(nullptr);
if(cur->left) st.push(cur->left);
}
}
return out;
}
|
迭代，后序（迭代法的巧妙点就在于用nullptr区分了已访问节点和未访问节点）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> out;
TreeNode* cur = root;
stack<TreeNode*> st;
if(root) st.push(root);//避免将空接点加入
while(!st.empty()){
cur = st.top();
if(nullptr != cur){
st.push(nullptr);
if(cur->right) st.push(cur->right);
if(cur->left) st.push(cur->left);
}
else{
st.pop();
cur = st.top();
st.pop();
out.push_back(cur->val);
}
}
return out;
}
};
|
404左叶子节点
关键在于判断什么是左叶子节点：节点A的左孩子不为空，且左孩子的左右孩子都为空（说明是叶子节点），那么A节点的左孩子为左叶子节点（在父节点才能判断它的左子节点是不是左叶子节点，不能到子节点中判断，因为他可能没有父节点了）
1
2
3
4
5
6
7
| int sumOfLeftLeaves(TreeNode* root) {
int ret = 0;
if(!root) return 0;//先序遍历，父节点，左子节点，右子节点
if(root->left!=nullptr && root->left->left==nullptr && root->left->right==nullptr)
return root->left->val + sumOfLeftLeaves(root->right);
return sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
}
|
验证二叉搜索树
不能只判断左子节点小于父节点小于右子节点，要避免这种情况
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public:
long long prev = LONG_MIN;
bool isValidBST(TreeNode* root) {
if(!root) return true;
bool left = isValidBST(root->left);
if(prev >= root->val) return false;
else prev = root->val;
bool right = isValidBST(root->right);
return left && right;
}
};
|
450.
需要判断很多种情况，
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
| class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
TreeNode* preroot = new TreeNode(INT_MIN);
preroot->right = root;
TreeNode* cur = preroot, *pre = nullptr;
while(cur){
if(cur->val == key){
bool left;
if(!pre->left) //错因1，没有判断pre->left 是否为空，而直接使用left = (pre->left->val == key)
left = false;
else
left = (pre->left->val == key);
std::cout << "dddd";
if(!cur->left){
if(left) pre->left = cur->right;
else pre->right = cur->right;
std::cout << "jjjj";
}
else{
std::cout << "hhhh";
TreeNode* temp = cur->left;
if(temp->right == nullptr){
temp->right = cur->right;
if(left) pre->left = temp;
else pre->right = temp;
}
else{
while(temp->right && temp->right->right != nullptr ) temp = temp->right;
if(left){
pre->left = temp->right;
temp->right = temp->right->left;
pre->left->left = cur->left;
pre->left->right = cur->right;
}
else{
pre->right = temp->right;
temp->right = temp->right->left;
pre->right->left = cur->left;
pre->right->right = cur->right;
}
}
}
delete cur;
break;
}
else if(cur->val > key){
pre = cur, cur = cur->left;
std::cout << "left";
}
else{
pre = cur, cur = cur->right;
std::cout << "right";
}
}
return preroot->right;
}
};
|
