环形链表
给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。 否则，返回 false 。
进阶：
你能用 O(1)（即，常量）内存解决此问题吗？
提示：
链表中节点的数目范围是 [0, 10^4]
-10^5 <= Node.val <= 10^5
pos 为 -1 或者链表中的一个 有效索引 。
解题思路，立马想到利用 set 存储节点是否被访问过，如果在遍历的过程中，再次被访问说明存在环。
但是看到题目要求用常量内存解决问题，那么就修改节点的值，把访问过的节点的 val 修改为 INT_MAX。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
while(head!=NULL) {
if(head->val == INT_MAX) return true;
head->val = INT_MAX;
head = head->next;
}
return false;
}
};
环形链表 II
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
说明：不允许修改给定的链表。
进阶：
你是否可以使用 O(1) 空间解决此题？
提示：
链表中节点的数目范围在范围 [0, 10^4] 内
-10^5 <= Node.val <= 10^5
pos 的值为 -1 或者链表中的一个有效索引
解题思路：已经把上一题简单粗暴型的修改值方法给禁用了，又是使用常量空间，所以看样子就是指明只能使用快慢指针解决问题了。
快指针每次走两步，慢指针每次走一步，那么如果存在环，快慢指针终将会相遇。
假设 x 代表从 head 到入环点的距离，a 表示入环点到快慢指针相遇的距离，b 表示环剩余的距离。
可以得到 low 指针走的距离：x + a, fast 指针走的距离：x + (a + b)*n + a;
因为 fast 指针走的距离是 low 的两倍，可以得到 2(x + a) = x + (a + b)n + a，最终得到 x = b + (a + b) * (n - 1);
又因为 a+b 表示一环的长度，所以可以知道当快慢指针相遇时，此时派出一个节点从 head 出发，同时慢节点也开始转圈，这两个节点相遇时的节点就是入环点。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* fast = head;
ListNode* low = head;
while(fast && fast->next && fast->next->next) {
low = low->next;
fast = fast->next->next;
if(fast == low) {
ListNode* res = head;
while(res != low) {
res = res->next;
low = low->next;
}
return res;
}
}
return NULL;
}
};
重排链表
给定一个单链表 L：L0→L1→…→Ln-1→Ln ， 将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
解题思路：利用 vector 遍历链表存储节点，再次遍历 vector 进行重新排列。
也可以用先把链表的后半段反转，然后合并前后半段得到答案。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
//利用vector链表
class Solution {
public:
void reorderList(ListNode* head) {
vector<ListNode*> vl;
for(int i = 0; head != NULL; i++) {
vl.push_back(head);
head = head->next;
}
int i = 0, n = mil.size() - 1;
while(i < mil.size()/2 ) {
vl[i]->next = vl[n-i];
vl[n-i]->next = vl[i+1];
i++;
}
vl[mil.size()/2]->next = NULL;
}
};
//反转合并链表
class Solution {
public:
ListNode* findMid(ListNode* head) {
ListNode* low = head;
ListNode* fast = head;
while(fast && fast->next && fast->next->next) {
low = low->next;
fast = fast->next->next;
}
//cout << low->val << endl;
return low;
}
ListNode* revertNode(ListNode* root) {
ListNode* prev = nullptr;
ListNode* curr = head;
while (curr != nullptr) {
ListNode* nextTemp = curr->next;
curr->next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
void mergeTwo(ListNode* fir, ListNode* sec) {
while(sec) {
ListNode* tmp = fir->next;
fir->next = sec;
sec = sec->next;
fir->next->next = tmp;
fir = tmp;
}
fir->next = NULL;
}
void reorderList(ListNode* head) {
if(head && head->next) {
ListNode* Pre = head;
ListNode* RePre = revertNode(findMid(head)->next);
mergeTwo(Pre, RePre);
}
}
};
二叉树的前序遍历
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
解题思路：递归解决二叉树的遍历问题
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> res;
void visit(TreeNode* root) {
if(root) {
res.push_back(root->val);
visit(root->left);
visit(root->right);
}
}
vector<int> preorderTraversal(TreeNode* root) {
visit(root);
return res;
}
};
二叉树的后序遍历
给定一个二叉树，返回它的 后序 遍历。
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
解题思路：刚看到这道题和上一道题其实是推荐用迭代解决，其实迭代就是用 stack 解决问题。
需要注意的是在后序遍历的时候，从左节点访问到根节点时需要判断是否有访问过其右节点，如果没有访问过需要重新把根节点入栈，利用 prev 节点存储上一个访问的节点。
ps：Morris 遍历，有兴趣的可以去看一下，利用线索二叉树来降低空间复杂度。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> stn;
TreeNode* scan = root;
TreeNode *prev = nullptr;
while(scan || !stn.empty()) {
while(scan) {
stn.emplace(scan);
scan = scan->left;
}
scan = stn.top();
stn.pop();
if (scan->right == nullptr || scan->right == prev) {
res.emplace_back(scan->val);
prev = scan;
scan = nullptr;
} else {
stk.emplace(scan);
scan = scan->right;
}
}
return res;
}
};
LRU 缓存机制
运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制 。
实现 LRUCache 类：
- LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
- int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
- void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？
示例：
输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]
解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4
提示：
1 <= capacity <= 3000
0 <= key <= 3000
0 <= value <= 10^4
最多调用 3 * 10^4 次 get 和 put
解题思路：利用 vector 数组来管理最近最少使用的数组，从 0 到数组末表示很少使用->最常使用，实现方法为每次 get 或者 put 都更新数组来保持使用频率。
利用 map 保存 key-value。
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache* obj = new LRUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/
class LRUCache {
public:
vector<int> mKey;
int mCapacity = 0;
unordered_map<int, int> mKeyValue;
LRUCache(int capacity) {
mCapacity = capacity;
}
int get(int key) {
int res = -1;
auto it = find(mKey.begin(), mKey.end(), key);
if(it != mKey.end()) {
mKey.erase(it);
mKey.emplace_back(key);
res = mKeyValue[key];
}
return res;
}
void put(int key, int value) {
if(get(key) != -1) {
mKeyValue[key] = value;
}else {
if(mKey.size() >= mCapacity) {
int key = mKey[0];
mKey.erase(mKey.begin());
mKeyValue.erase(key);
}
mKey.emplace_back(key);
mKeyValue[key] = value;
}
}
};
对链表进行插入排序
对链表进行插入排序。
插入排序算法：
- 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
- 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
- 重复直到所有输入数据插入完为止。
解题思路：管理一个有序节点，这个节点是有序的，然后遍历未排序的节点，每次操作一个未排序的节点，把这个节点插入到有序的链表中。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* insertionSortList(ListNode* head) {
ListNode* sort = head;
ListNode* ope = head->next;
sort->next = nullptr;
while(ope) {
ListNode* unSort = ope->next;
ListNode* sortScan = sort;
ListNode* preScan = nullptr;
while(sortScan && ope->val > sortScan->val) {
preScan = sortScan;
sortScan = sortScan->next;
}
if(!sortScan) {
//sortScan 为 nullptr 插入有序链表尾部
preScan->next = ope;
ope->next = nullptr;
}else if (!preScan) {
//preScan 为 nullptr 插入有序链表头部
ope->next = sort;
sort = ope;
}else {
//插入到 preScan 和 sortScan 之间
preScan->next = ope;
ope->next = sortScan;
}
ope = unSort;
}
return sort;
}
};
排序链表
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
进阶：
- 你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
示例 1：
输入：head = [4,2,1,3]
输出：[1,2,3,4]
示例 2：
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
示例 3：
输入：head = []
输出：[]
提示：
链表中节点的数目在范围 [0, 5 * 10^4] 内
-10^5 <= Node.val <= 10^5
解题思路：看到这个时间复杂度，想到应该是二分来排序链表。至于怎么二分，关于链表有一个非常好用的方法来找到链表的中点，那就是快慢指针。
利用快慢指针来找到中点，那么就可以实现二分，然后递归排序前后两段，最后合并两个有序链表。但是利用递归的话空间复杂度是达不到常数级别的，陷入沉思。。。
怎样才能即利用二分来解决问题，有使得空间复杂度在常数空间呢，其实转换一个思路，递归版的二分是从 n -> n/2 -> … -> 1; 那么可以反过来，从 1 开始排序，
这样就会变成 1 -> 2 -> … -> n；这样也是实现了二分的思想，而且可以保证空间复杂度在常数级别。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* sortList(ListNode* head) {
int length = 0;
ListNode* tmp = head;
while(tmp) {
length++;
tmp = tmp->next;
}
ListNode* res = new ListNode(-1, head);
for(int i = 1; i < length; i *= 2) {
ListNode *scan = res->next, *prev = res;
while(scan) {
ListNode* fir = scan;
for(int j = 1; j < i && scan->next; j++) scan = scan->next;
ListNode* sec = scan->next;
scan->next = nullptr;
scan = sec;
for(int j = 1; j < i && scan && scan->next; j++) scan = scan->next;
ListNode* next = nullptr;
if(scan) {
next = scan->next;
scan->next = nullptr;
}
prev->next = merge(fir, sec);
while(prev->next) prev = prev->next;
scan = next;
}
}
return res->next;
}
ListNode* merge(ListNode* fir, ListNode* sec) {
ListNode* root = new ListNode(-1);
ListNode* scan = root;
while(fir && sec) {
if(fir->val < sec->val) {
scan->next = fir;
fir = fir->next;
}else {
scan->next = sec;
sec = sec->next;
}
scan = scan->next;
}
if(fir) scan->next = fir;
if(sec) scan->next = sec;
return root->next;
}
};
直线上最多的点数
给定一个二维平面，平面上有 n 个点，求最多有多少个点在同一条直线上。
示例 1:
输入: [[1,1],[2,2],[3,3]]
输出: 3
解释:
^
|
| o
| o
| o
+------------->
0 1 2 3 4
示例 2:
输入: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出: 4
解释:
^
|
| o
| o o
| o
| o o
+------------------->
0 1 2 3 4 5 6
解题思路：直线方程是 y = kx+b，遍历数组构造直线并且记录 k 和 b，寻找最多个数。后面发现这道题的难点是精度问题，而不是思路。
由于求斜率需要用到除法，所以会导致精度出问题，那么最好的办法就是避免用除法，那么这样的话就无法保存斜率，直接遍历即可。
遍历的方法就是利用三个点是否共线，(x1 - x2) * (y3 - y1) == (y1 - y2) * (x3 - x1), 为了避免 int 相乘溢出，使用 long long 保存相乘结果。
class Solution {
public:
int maxPoints(vector<vector<int>>& points) {
if(points.size() < 3) return points.size();
int res = 0;
for(int i = 0;i<points.size();++i) {
int same = 1;
for(int j = i+1;j < points.size(); ++j) {
int count = 0;
if(points[i][0] == points[j][0] && points[i][1] == points[j][1]) same++;
else{
count++;
long long xDiff = (long long)(points[i][0] - points[j][0]);
long long yDiff = (long long)(points[i][1] - points[j][1]);
for (int k = j + 1; k < points.size(); k ++)
if (xDiff * (points[i][1] - points[k][1]) == yDiff * (points[i][0] - points[k][0]))
count++;
}
res = max(res, same + count);
}
if(res > points.size()/2 || res > points.size() - i) {
break;
}
}
return res;
}
};
逆波兰表达式求值
根据 逆波兰表示法，求表达式的值。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明：
整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1：
输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
示例 2：
输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
示例 3：
输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
解释：
该算式转化为常见的中缀算术表达式为：
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
提示：
1 <= tokens.length <= 10^4
tokens[i] 要么是一个算符（"+"、"-"、"*" 或 "/"），要么是一个在范围 [-200, 200] 内的整数
逆波兰表达式：
逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。
- 平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
- 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。
逆波兰表达式主要有以下两个优点：
- 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
- 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。
解题思路：解题思路已经给出了，适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。
而且相信如果有写过计算器的程序的经验会很熟悉这个，先是把计算器中的表达式中缀转后缀，然后利用栈计算结果。
class Solution {
public:
int cacul(string ope, int fir, int sec) {
int res = 0;
if(ope == "+") {
res = fir + sec;
}else if(ope == "-") {
res = sec - fir;
}else if(ope == "*") {
res = fir * sec;
}else {
res = sec / fir;
}
return res;
}
int evalRPN(vector<string>& tokens) {
stack<int> res;
for(int i = 0; i < tokens.size(); ++i) {
if(tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {
int fir = res.top();
res.pop();
int sec = res.top();
res.pop();
int tmp = cacul(tokens[i], fir, sec);
res.push(tmp);
}else {
res.push(atoi(tokens[i].c_str()));
}
}
return res.top();
}
};
