Leet Code 刷题笔记 - - 不求最快最省，但求最简最优雅 ✒，Simpler is better here.
- 如有更简解法，欢迎 fork 或 issue。
- 为了快速找到题目可以按 [Ctrl键 + F键] 输入题目序号或名字定位。
- 欢迎加入QQ交流群：902025048 ∷二维码 群内提供更多相关资料~
此专栏追求代码的精简和技巧性，默认已看过题目，🤖 没看过的话点标题可以跳转链接，一起体验炫酷的 C++
class Solution {
public:
int romanToInt(string s) {
unordered_map<string, int> m = {{"I", 1}, {"IV", 3}, {"IX", 8}, {"V", 5}, {"X", 10}, {"XL", 30}, {"XC", 80}, {"L", 50}, {"C", 100}, {"CD", 300}, {"CM", 800}, {"D", 500}, {"M", 1000}};
int r = m[s.substr(0, 1)];
for(int i=1; i<s.size(); ++i){
string two = s.substr(i-1, 2);
string one = s.substr(i, 1);
r += m[two] ? m[two] : m[one];
}
return r;
}
};- 构建一个哈希表记录所有罗马数字子串，注意长度为2的子串记录的值是（实际值-子串内左边罗马数字代表的数值）
- 遍历整个s的时候判断当前位置和前一个位置的两个字符组成的字符串是否在字典内，如果在就记录值，不在就说明当前位置不存在小数字在前面的情况，直接记录当前位置字符对应值。整个过程时间复杂度为O(N)
- 举个例子，遍历经过IV的时候先记录I的对应值1再往前移动一步记录IV的值3，加起来正好是IV的真实值4
/*
// Definition for a Node.
class Node {
public:
int val;
Node* left;
Node* right;
Node* next;
Node() {}
Node(int _val, Node* _left, Node* _right, Node* _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
};
*/
class Solution {
public:
Node* connect(Node* root) {
if(root and root->left){
root->left->next = root->right;
if(root->next) root->right->next = root->next->left;
connect(root->left);
connect(root->right);
}
return root;
}
};- 对于任意一次递归，只需要考虑如何设置子节点的 next 属性：
- 将左子节点连接到右子节点
- 将右子节点连接到
root.next的左子节点 - 递归左右节点
/*
// Definition for a Node.
class Node {
public:
int val;
Node* left;
Node* right;
Node* next;
Node() {}
Node(int _val, Node* _left, Node* _right, Node* _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
};
*/
class Solution {
public:
Node* connect(Node* root) {
if(root and (root->left or root->right)){
if(root->left and root->right) root->left->next = root->right;
Node *node = root->right ? root->right : root->left;
Node *head = root->next;
while (head and not (head->left or head->right)){
head = head->next;
}
node->next = head ? (head->left ? head->left : head->right) : nullptr;
connect(root->right);
connect(root->left);
}
return root;
}
};- 对于任意一次递归，只考虑如何设置子节点的 next 属性,分为三种情况：
- 没有子节点：直接返回
- 有一个子节点：将这个子节点的
next属性设置为同层的下一个节点，即为root.next的最左边的一个节点，如果root.next没有子节点，则考虑root.next.next，依次类推 - 有两个节点：左子节点指向右子节点，然后右子节点同第二种情况的做法
- 注意递归的顺序需要从右到左
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode *pre = NULL;
while(head){
ListNode *next = head -> next;
head -> next = pre;
pre = head;
head = next;
}
return pre;
}
};/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
TreeNode *l = root->left ? lowestCommonAncestor(root->left, p, q) : nullptr;
TreeNode *r = root->right ? lowestCommonAncestor(root->right, p, q) : nullptr;
return (root == p or root == q or (l and r)) ? root : l ? l : r;
}
};- 递归全部节点，p 的祖先节点全部返回 p，q 的祖先节点全部返回 q，如果它同时是俩个节点的最近祖先，那么返回自身，否则返回 nullptr
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> res(n, 1);
int l = 1;
for(int i=0; i<n; ++i){
res[i] *= l;
l *= nums[i];
}
int r = 1;
for(int j=n-1; j>=0; --j){
res[j] *= r;
r *= nums[j];
}
return res;
}
};- 本题利用双指针，新数组每个位置上的值应该等于数组左边所有数字的乘积 × 数组右边所有数字的乘积
- 1.初始化一个新的数组res（result），包含n个1
2.初始化变量l（left）代表左边的乘积，从左到右遍历数组，每次都让新数组的值乘以它左边数字的乘积l，然后更新l。此时新数组里的所有数字就代表了nums数组中对应位置左边所有数字的乘积
3.再从右往左做一遍同样的操作，最终
res[i] = 1 * nums中i左边所有数字的乘积 * nums中i右边所有数字的乘积
class Solution {
public:
int missingNumber(vector<int>& nums) {
int n = nums.size();
int sum = 0;
for(int i=0; i<n; ++i){
sum += nums[i];
}
n++;
return n * (n - 1) / 2 - sum;
}
};- 缺失数字 = 0 加到 n+1 的总和 - 数组中所有数字的总和
- 计算 0 加到 n+1 的总和，可利用等差数列求和公式，此题可理解为
总和 = (元素个数 / 2) * (首尾两数字之和)
class Solution {
public:
void reverseString(vector<char>& s) {
int i = -1, j = s.size();
while(++i < --j){
swap(s[i], s[j]);
}
}
};class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
for(int i=0; i<nums.size(); ++i){
nums[abs(nums[i])-1] = -abs(nums[abs(nums[i])-1]);
}
vector<int> r;
for(int i=0; i<nums.size(); ++i){
if(nums[i] > 0){
r.push_back(i+1);
}
}
return r;
}
};- 应题目进阶要求，O(N)时间，无额外空间，此解实际上是利用索引把数组自身当作哈希表处理
- 将 nums 中所有正数作为索引i，置 nums[i] 为负值。那么，仍为正数的位置即为（未出现过）消失的数字
- 原始数组：[4,3,2,7,8,2,3,1]
- 重置后为：[-4,-3,-2,-7,
8,2,-3,-1] - 结论：[8,2] 分别对应的index为[5,6]（消失的数字）
class Solution {
public:
int hammingDistance(int x, int y) {
return bitset<32>(x ^ y).count();
}
};class Solution {
public:
vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
int p = pow(points[0][0], 2) + pow(points[0][1], 2);
vector<vector<int>> l, m, r;
for(int i=0; i<points.size(); ++i){
int v = pow(points[i][0], 2) + pow(points[i][1], 2);
if(v < p){
l.push_back(points[i]);
}else if(v == p){
m.push_back(points[i]);
}else{
r.push_back(points[i]);
}
}
if(K <= l.size()){
return kClosest(l, K);
}else if(K <= l.size() + m.size()){
l.insert(l.end(), m.begin(), m.begin() + K - l.size());
return l;
}else{
r = kClosest(r, K - l.size() - m.size());
l.insert(l.end(), m.begin(), m.end());
l.insert(l.end(), r.begin(), r.end());
return l;
}
}
};- 快速选择的一般流程，计算lmr，组合
class Solution {
public:
string defangIPaddr(string address) {
for(int i = address.size(); i >= 0; i--){
if(address[i] == '.'){
address.replace(i, 1, "[.]");
}
}
return address;
}
};- 逆遍历字符串并替换
.为[.] - 本题若正遍历，每次替换完，下一个字符会变成
.，进入死循环