一、算法思想

1.动态规划

动态规划的基本思想：将复杂问题进行分解，通过求解小规模子问题反推出原问题的结果。
动态规划适合求解多阶段决策问题的最优解（可以简单理解为有状态转换的阶段性问题）。
这些问题必须满足最优化原理和子问题的无后向性。

1. 最优化原理：不管之前的决策是否最优，但是一定要保证从现在开始的决策是在之前决策基础上的最优决策。
2. 无后向性原理：当各个子阶段的子问题确定以后，对于某个特定阶段的子问题来说，它之前的各个阶段的子问题的决策只影响当前阶段的决策，而对该阶段之后的决策不产生影响。即每个阶段的决策只受之前决策的影响，不影响之后各阶段的决策。

动态规划与贪婪算法以及分治法的比较：

三者都需要对原问题进行分解，分解为需要求解的子问题。
分治法求解的子问题是独立的，每个问题的求解模式一样，分别求解再合并就是原问题的解。
而贪婪算法只考虑当前状态，并依据贪婪法则取得局部最优解，直到扩展到原来的问题。

2.分治法

设计思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。

3.贪心

所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择 。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的 局部最优解 。

4.回溯

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。

二、排序

1. 冒泡排序(O(N^2)，稳定，n小）

时间复杂度最好O(n)，最坏O(N^2），空间O(1)
是一种简单的排序算法，它重复的访问要排序的数列，一次比较两个元素，安装想要的顺序将其排序。
一趟排序：

1. 比较相邻元素，比如想要升序，那么如果第一个比第二个大，则交换两个元素
2. 对每一对元素进行比较，直到最后一对
3. 固定最后一个元素，重新对0~n-i个数进行冒泡比较

优化：加入flage判断

void bubbleSort(vector<int> &nums) //冒泡{int n = nums.size();bool flage = false;for (int i = 0; i < n; i++){flage = false;for (int j = 0; j < n - 1 - i; j++){if (nums[j] > nums[j + 1]){swap(nums[j], nums[j + 1]);flage = true;}}if (flage == false)break;}}

2.选择排序（O(N^2),不稳定，n小）

时间复杂度O(N^2），空间O(1)
找到最小的元素，记录它的下标，然后和第i个元素进行交换，每进行一个循环就找到一个最小值。

void selectSort(vector<int> &a) //选择{int n = a.size();for (int i = 0; i < n; i++){int swap_pos = i;for (int j = i+1; j < n; j++){if (a[j] < a[swap_pos]){swap_pos = j;}}if(swap_pos != i){swap(a[i],a[swap_pos]);}}}

3. 插入排序（O(N^2),稳定，n小）

时间复杂度最好O(n)，最坏O(N^2），空间O(1)
和玩斗地主一样，对于未排序的数据，在已排序的序列中从后向前扫描，找到相应位置插入。

1. 从第一个元素开始，该元素被认为以及排序；
2. 取下一个元素，在以及排序的序列中从后向前扫描；
3. 如果扫描到的元素大于待排序的元素，将扫描到的元素移到下一个位置；
4. 重复3，直到找到已排序的元素小于或者等于新元素的位置；

void insertSort(vector<int> &nums) // 插入{int n = nums.size();for (int i = 1; i < n; i++){int insert_num = nums[i];int j;for (j = i - 1; j >= 0; j--){if (nums[j] > insert_num){nums[j + 1] = nums[j];}elsebreak;}nums[j + 1] = insert_num;}}

4.快排（O(NlogN），不稳定，n大）

时间复杂度O(nlogn)，最坏（O(N^2），空间O(nlogn)
通过一趟排序将待排记录分个成独立的两个部分，其中一部分均比另外一部分小，再对剩下的两部分分别进行排序，使得整个序列有序。

1. 从数列中挑选一个元素作为基准，一般选取第一个元素或者选取随机数
2. 对数组进行重新排列（即分区），将元素比基准小的放在基准前，将元素比基准大的放在基准后；
3. 使用递归的方法重复1-2，分别对分区后的序列再进行快排

加入随机数
（针对特殊测试用例：顺序数组或者逆序数组）一定要随机化选择切分元素（pivot），否则在输入数组是有序数组或者是逆序数组的时候，快速排序会变得非常慢（等同于冒泡排序或者「选择排序」）

class Solution {
public:vector<int> sortArray(vector<int>& nums) {srand((unsigned)time(NULL));//初始化quicksort(nums, 0, nums.size() - 1);return nums;}
private:void quicksort(vector<int>& nums, int left, int right){if(left < right){int pos = position(nums, left, right);quicksort(nums, left, pos - 1);quicksort(nums, pos + 1, right);} }int position(vector<int>& nums, int left, int right){int t = rand() % (right - left + 1) + left;//从范围right到left里选择一个随机数swap(nums[t], nums[left]);int i = left, j = right;while(i < j){while(nums[j] >= nums[left] && i <j) j--;while(nums[i] <= nums[left] && i <j) i++;swap(nums[i], nums[j]);}swap(nums[i], nums[left]);return i;}
};

5.归并排序（O(nlogn),稳定，n大）

时间复杂度O(nlogn)，空间O(n)
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并

1. 将列表从正中间分为两个子列表
2. 递归拆分每个子列表，知道子列表最大长度为1；
3. 按照拆分层级，依次按照大小合并各子列表，直到全部合并完成

// 归并排序
// 合并两有序序列，两序列分别为array的0到mid部分和mid+1到末尾部分。
void merge(vector<int>& array, vector<int>& copyArray, int left, int right) {int mid = (left + right) / 2;int i = left, j = mid + 1, k = 0;while (i <= mid || j <= right) {if (i > mid) {copyArray[k] = array[j];j++;}else if (j > right) {copyArray[k] = array[i];i++;}else if (array[i] > array[j]) {copyArray[k] = array[j];j++;}else {copyArray[k] = array[i];i++;}k++;}for (size_t i = left; i <= right; i++) {array[i] = copyArray[i - left];}}
void mergeSortHelp(vector<int>& array, vector<int>& copyArray, int left, int right) {if (left < right) {int mid = (left + right) / 2;mergeSortHelp(array, copyArray, left, mid);mergeSortHelp(array, copyArray, mid + 1, right);merge(array, copyArray, left, right);}
}
// 归并排序 递归实现
void mergeSort(vector<int>& array) {vector<int> copyArray(array);mergeSortHelp(array, copyArray, 0, array.size() - 1);
}

6.堆排序（O(nlogn),不稳定，n小）

时间复杂度O(nlogn)，空间O(1)
参考：
C++中两种实现堆的方式:make_heap和priority_queue

1. 将数组转化为一个堆：
   堆是具有以下两属性的二叉树：
   （1）每个节点的值大于等于其子节点的值；
   （2）树完全平衡，即最底层叶子节点都位于左侧（完全），且左右子树高度相差不超过1（平衡）；
2. 取出堆顶元素（最大元素），作为有序数数组末尾元素，并对二叉树进行调整使其满足堆的特性；
3. 重复上一步骤，依次取出堆顶元素，并插入到有序数组中，上一插入元素之前的位置，直到堆空为止；

class solution
{
public:void show(vector<int> &nums, int size){for (int i = 0; i < size; i++){cout << nums[i] << " ";}cout << endl;}void down(vector<int> &nums, int first, int last){int parent = first;int child = first * 2 + 1;while (child < last){if (child + 1 < last && nums[child] < nums[child + 1]){child++;}if (nums[parent] < nums[child]){swap(nums[parent], nums[child]);parent = child;}child = parent * 2 + 1;}}void buildheap(vector<int> &nums){for (int i = nums.size() / 2 - 1; i >= 0; i--){down(nums, i, nums.size()-1);}}void heapSort(vector<int> &nums){buildheap(nums);for (int i = nums.size() - 1; i > 0; i--){swap(nums[0], nums[i]);down(nums, 0, i);}}
};

使用优先队列

    void priorisort(vector<int> &nums){priority_queue<int> a; //默认大顶堆;//等于 priority_queue<int, vector<int>, less<int> > apriority_queue<int, vector<int>, greater<int>> c;for (int i = 0; i < nums.size(); i++){a.push(nums[i]);c.push(nums[i]);}while (!a.empty()){cout << a.top() << " ";a.pop();}cout << endl;while (!c.empty()){cout << c.top() << " ";c.pop();}cout << endl;}

7.最小k个数

时间复杂度O(Nlogk)，空间复杂度为O(1)

class Solution {
public:priority_queue<int> q;vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {// 将数组里面的数字都放入一个优先队列里面for(auto x:input){q.push(x);if(q.size()>k){q.pop();}}// 对input数组input.clear();// 如果达不到k个数字if(q.size()<k){  return input;}while(!q.empty()){input.push_back(q.top());q.pop();}return input;}
};

8.二分查找

给定一个 元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的第一个出现的target，如果目标值存在返回下标，否则返回 -1

时间复杂度：O(logn), 标准的二分查找，空间复杂度：O(1), 未定义数组

class Solution {
public:int search(vector<int>& nums, int target) {int l = 0, r = nums.size()-1;while (l<r) {// 这里不可以写上取整，否则在l+1==r的情况下会陷入死循环int mid = (l+r)>>1;// 如果大于目标值，说明mid及其右侧都不可能是答案if (nums[mid] > target) r = mid-1;// 如果小于目标值，说明mid及其左侧都不可能是答案else if (nums[mid] < target) l = mid+1;// 如果等于目标值，说明mid右侧不是答案，但mid有可能是！！！！！！else r = mid;}// 请注意这里wa了一次，需要特判断下数组是否为空，如果为空会越界if (nums.size() && nums[l] == target) return l;// 如果没找到目标值，是-1return -1;}
};

二、链表

1.合并两个有序链表

迭代

class Solution {
public:ListNode* Merge(ListNode* pHead1, ListNode* pHead2){ListNode *vhead = new ListNode(-1);ListNode *cur = vhead;while (pHead1 && pHead2) {if (pHead1->val <= pHead2->val) {cur->next = pHead1;pHead1 = pHead1->next;}else {cur->next = pHead2;pHead2 = pHead2->next;}cur = cur->next;}cur->next = pHead1 ? pHead1 : pHead2;return vhead->next;}
};

递归

class Solution {
public:ListNode* Merge(ListNode* pHead1, ListNode* pHead2){if (!pHead1) return pHead2;if (!pHead2) return pHead1;if (pHead1->val <= pHead2->val) {pHead1->next = Merge(pHead1->next, pHead2);return pHead1;}else {pHead2->next = Merge(pHead1, pHead2->next);return pHead2;}}
};

2.环的入口节点

时间O（n），空间O（1）

class Solution {
public:ListNode* EntryNodeOfLoop(ListNode* pHead){ListNode *fast = pHead;ListNode *slow = pHead;while (fast && fast->next) {fast = fast->next->next;slow = slow->next;//第一次相遇在C处，停止if (fast == slow) break;}if (!fast || !fast->next) return nullptr;//让fast指向头结点，Slow原地不动，fast = pHead;while (fast != slow) {//快慢指针每次走一步fast = fast->next;slow = slow->next;}return fast;}
};

3.删除链表倒数第n个节点

时间复杂度: O(n) 遍历整个链表
空间复杂度: O(1) 使用了若干个变量

class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* Head =new ListNode(0);Head->next =head;ListNode* p=Head;//开始的双指针都指向头节点ListNode* q=Head;for( int i=0;i<n+1;i ++ ){q=q->next;//q指针指向第n-1个节点}while(q){p=p->next;q=q->next;}ListNode* delNode=p->next;p->next=delNode->next;delete delNode;//删除多于结点ListNode* retNode=Head->next;delete Head;//删除多余节点return retNode;}
};

4.链表中节点每k个一组翻转

将给出的链表中的节点每k 个一组翻转，返回翻转后的链表
如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样
你不能更改节点中的值，只能更改节点本身。
要求空间复杂度O(1)
例如：
给定的链表是1→2→3→4→5
对于 k=2, 你应该返回 2→1→4→3→5
对于 k=3, 你应该返回3→2→1→4→5
时间复杂度:O(n)，空间复杂度:O(1)

class Solution {
public:ListNode* reverseKGroup(ListNode* head, int k) {auto node=head;for (int i=0;i<k;i++) { if (!node) return head;node = node->next;}auto res = reverse(head, node); // 翻转长度是k的链表head->next = reverseKGroup(node, k); // 递归处理下一个长度是k的链表return res; //返回头指针}
private://reverse函数实现反转a到b之间的结点ListNode* reverse(ListNode* left, ListNode* right) {auto pre=right;while (left!=right) {auto node=left->next;left->next=pre;pre = left;left = node;}return pre;}
};

5.合并k个升序链表

使用分治
渐进时间复杂度为 O(kn*log k)，空间复杂度 O(logk)

class Solution {
public:ListNode* mergeTwoLists(ListNode *a, ListNode *b) {if ((!a) || (!b)) return a ? a : b;ListNode head, *tail = &head, *aPtr = a, *bPtr = b;while (aPtr && bPtr) {if (aPtr->val < bPtr->val) {tail->next = aPtr; aPtr = aPtr->next;} else {tail->next = bPtr; bPtr = bPtr->next;}tail = tail->next;}tail->next = (aPtr ? aPtr : bPtr);return head.next;}ListNode* merge(vector <ListNode*> &lists, int l, int r) {if (l == r) return lists[l];if (l > r) return nullptr;int mid = (l + r) >> 1;return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));}ListNode* mergeKLists(vector<ListNode*>& lists) {return merge(lists, 0, lists.size() - 1);}
};

三、二叉树

1.层序遍历

时间复杂度 O(N)：
空间复杂度 O(N)：用到了队列和集合

class Solution {
public:/*** * @param root TreeNode类 * @return int整型vector<vector<>>*/vector<vector<int> > levelOrder(TreeNode* root) {// write code herevector<vector<int>>res;queue<TreeNode*> que;if(root)que.push(root);elsereturn{};while(!que.empty()){int size = que.size();vector<int>path;for(int i = 0; i< size;i++){TreeNode*cur = que.front();que.pop();path.push_back(cur->val);if(cur->left) que.push(cur->left);if(cur->right) que.push(cur->right); }res.push_back(path);}return res;}
};

2.先序后序中序遍历

时间复杂度为O(N)，空间复杂度为O(N)。

/*** struct TreeNode {*	int val;*	struct TreeNode *left;*	struct TreeNode *right;* };*/
class Solution {
public:vector<int> pre;vector<int> mid;vector<int> post;vector<vector<int> > threeOrders(TreeNode* root) {if(root != nullptr){//nullptr任意指针类型preorder(root);midorder(root);postorder(root);}vector<vector<int>>res = {pre,mid,post};return res;}//先序void preorder(TreeNode* root){//中左右if(root == NULL)return ;pre.push_back(root->val);//在Vector最后添加一个元素（参数为要插入的值）preorder(root->left);preorder(root->right);}//中序void midorder(TreeNode* root){//左中右if(root == NULL)return;midorder(root->left);mid.push_back(root->val);midorder(root->right);}//后序void postorder(TreeNode* root){//左右中if(root == NULL)return;postorder(root->left);postorder(root->right);post.push_back(root->val);}
};

3.判断是否平衡二叉树

class Solution {
public:bool IsBalanced_Solution(TreeNode* pRoot) {return dfs(pRoot) != -1;}int dfs(TreeNode* root){if(!root) return 0;int left = dfs(root->left);if(left == -1) return -1;int right = dfs(root->right);if(right == -1) return -1;return abs(left - right) > 1 ? -1 : max(left, right) + 1;}
};

4.二叉树最大深度

class Solution {
public:int maxDepth(TreeNode* root) {if(root == nullptr)//特殊情况return 0;int sub_left = maxDepth(root->left);//递归判断int sub_right = maxDepth(root->right);return (sub_left > sub_right ? sub_left : sub_right) + 1;//返回最大值}
};

5.重建二叉树

给定某二叉树的前序遍历和中序遍历，请重建出该二叉树并返回它的头结点。
时间复杂度为O(n)，空间复杂度为O(n)

/*** Definition for binary tree* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:TreeNode* root;// 定义一个全局变量，减少参数的传递vector<int> p,i;TreeNode* build(int lp,int rp,int lv,int rv){// 不满足区间的情况if(lp>rp) return NULL;TreeNode* now=new TreeNode(p[lp]);int index=lv;  // 这个变量用来查找在中序遍历里面根节点的下标while(index<=rv&&p[lp]!=i[index]){index++;}int len=index-lv;// 递归查找左节点now->left=build(lp+1,lp+len,lv,index-1);// 递归查找右节点now->right=build(lp+len+1,rp,index+1,rv);return now;}TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {p=pre,i=vin;TreeNode* root=build(0,pre.size()-1,0,vin.size()-1);return root;}
};

四、字符串

2.最长回文子串

时间复杂度：O(n^2)，双重循环，对二维数组dp每个访问一次。
空间复杂度：O(n^2)，二维数组dp。
思路：使用二维数组dp，对于dp[i][j]（其中i<=j，i表示子串起始位置，j表示子串结束位置），如果dp[i][j]为1，则表明当前子串为回文串；如果为0，则表示不是回文串。其中
(1)if（ j>i+1） dp[i][j]=dp[i+1][j-1]&&(A[i] == A[j])
(2) if（ j == i+1） dp[i][j]=(A[i] == A[j])
(3) if （j==i） dp[i][j]=1

对于上述递推式，式(3)以及式(2)分别是针对字符串长度为1和2的情况，易得。式(1)是判断字符串首尾两字符相等，且去掉首尾两字符后的字符串为回文串，便可得当前字符串为回文串。

class Solution {
public:int getLongestPalindrome(string A, int n) {// write code herevector<vector<int>> dp(n,vector<int>(n));int ans=1;//l表示子串长度，i为子串起始位置for(int l=0;l<n;l++){for(int i=0;i+l<n;i++){int j=i+l;if(l==0){dp[i][j]=1;}else if(l==1){dp[i][j]=(A[i]==A[j]);}else{dp[i][j]=(A[i]==A[j]&&dp[i+1][j-1]);}if(dp[i][j]&&l+1>ans){ans=l+1;}}}return ans;}
};

3.最长公共子串

时间复杂度：O（mn），m和n分别表示两个字符串的长度
空间复杂度：O（mn）

class Solution {
public:string LCS(string str1, string str2) {int l1 = str1.size();int l2 = str2.size();int maxlen = 0;int maxend = 0;vector<vector<int>> dp(l1+1,vector<int>(l2+1,0));for(int i = 1; i <= l1; i++){for(int j = 1; j <= l2; j++){if(str1[i-1] == str2[j-1]){dp[i][j] = dp[i-1][j-1] + 1;if(dp[i][j] > maxlen){maxlen = dp[i][j];maxend = i-1;}}}}return str1.substr(maxend - maxlen + 1, maxlen);}
};

五、其他

1.整数的除法

class Solution {
public:int divide(int a, int b) {     if (a == INT_MIN && b == -1) {return INT_MAX;}//2负数，2整数，1正1负int negative = 2;        if(a>0){ a = -a; negative--;    }        if(b>0){b = -b;  negative--;}unsigned int result = DivideCore(a,b); return negative == 1 ? -result : result;}unsigned int DivideCore(int a,int b){int ret = 0;// 注意a, b都是负数，所以a <= b就是还可以继续除while (a <= b) {int value = b;unsigned int quo = 1;while (value >= 0xc0000000 && a <= value + value) {quo += quo;value += value;}ret += quo;a -= value;}return ret;}
};

2.岛屿数量

class Solution {
public:int numIslands(vector<vector<char>>& grid) {int len_row = grid.size();int len_col = grid[0].size();int count = 0;for (int i = 0; i < len_row; ++i) {for (int j = 0; j < len_col; ++j) {if (grid[i][j] == '1') {++count;grid[i][j] = '0';//入栈queue<pair<int, int>> que;que.push({i, j});while (!que.empty()) {auto temp = que.front();que.pop();int row = temp.first, col = temp.second;if (row - 1 >= 0 && grid[row-1][col] == '1') {que.push({row-1, col});grid[row-1][col] = '0';}if (row + 1 < len_row && grid[row+1][col] == '1') {que.push({row+1, col});grid[row+1][col] = '0';}if (col - 1 >= 0 && grid[row][col-1] == '1') {que.push({row, col-1});grid[row][col-1] = '0';}if (col + 1 < len_col && grid[row][col+1] == '1') {que.push({row, col+1});grid[row][col+1] = '0';}}}}}return count;}
};

3.用两个栈实现队列

时间复杂度：push操作为O(1),pop操作为O(1)
空间复杂度：需要stack来存，O(n)

class Solution
{
public:void push(int node) {stack1.push(node);}int pop() {if (stack2.empty()) {while (!stack1.empty()) {stack2.push(stack1.top());stack1.pop();}}int ret = stack2.top();stack2.pop();return ret;}
private:stack<int> stack1;stack<int> stack2;
};

4.螺旋矩阵输出

时间复杂度:O(n * m) n,m分别表示矩阵的行数和列数
空间复杂度:O(n * m) 需要用二维数组来储存结果

class Solution {
public:vector<int> spiralOrder(vector<vector<int> > &matrix) {vector<int> res;int m = matrix.size();if(!m) return res;int n = matrix[0].size();int center = min((m-1)/2, (n-1)/2);int r = m, c = n;int z;for(z = 0; z <= center ; z++){for(int i = 0; i < c - 1; i++) res.push_back(matrix[z][z+i]);for(int i = 0; i < r - 1; i++) res.push_back(matrix[z+i][z+c-1]);// 当r=1或c=1时，只需要左上到右上和右上到右下的两步遍历，// 但会漏掉matrix[z+r-1][z+c-1]，因此补上if(r == 1 || c == 1) res.push_back(matrix[z+r-1][z+c-1]);else {for(int i = c - 1; i > 0; i--) res.push_back(matrix[z+r-1][z+i]);for(int i = r - 1; i > 0; i--) res.push_back(matrix[z+i][z]);}r -= 2;c -= 2;}return res;}
};

5.字符串大数相乘

时间复杂度O(n∗m)

class Solution {
public:string multiply(string num1, string num2) {vector<int> A, B;int n = num1.size(), m = num2.size();for (int i = n - 1; i >= 0; i -- ) A.push_back(num1[i] - '0'); //反向存贮for (int i = m - 1; i >= 0; i -- ) B.push_back(num2[i] - '0');vector<int> C(n + m);for (int i = 0; i < n; i ++ )for (int j = 0; j < m; j ++ )C[i + j] += A[i] * B[j];int t = 0;  //存贮进位for (int i = 0; i < C.size(); i ++ ) {t += C[i];C[i] = t % 10;t /= 10;}int k = C.size() - 1;while (k > 0 && !C[k]) k -- ;  //去除前导0string res;while (k >= 0) res += C[k -- ] + '0';  //反转return res;}
};

6.实现LRU缓存

双链表+哈希) O(1)

class LRUCache {
public://定义双链表struct Node{int key,value;Node* left ,*right;Node(int _key,int _value): key(_key),value(_value),left(NULL),right(NULL){}}*L,*R;//双链表的最左和最右节点，不存贮值。int n;unordered_map<int,Node*>hash;void remove(Node* p){p->right->left = p->left;p->left->right = p->right;}void insert(Node *p){p->right = L->right;p->left = L;L->right->left = p;L->right = p;}LRUCache(int capacity) {n = capacity;L = new Node(-1,-1),R = new Node(-1,-1);L->right = R;R->left = L;    }int get(int key) {if(hash.count(key) == 0) return -1; //不存在关键字 key auto p = hash[key];remove(p);insert(p);//将当前节点放在双链表的第一位return p->value;}void put(int key, int value) {if(hash.count(key)) //如果key存在，则修改对应的value{auto p = hash[key];p->value = value;remove(p);insert(p);}else {if(hash.size() == n) //如果缓存已满，则删除双链表最右侧的节点{auto  p = R->left;remove(p);hash.erase(p->key); //更新哈希表delete p; //释放内存}//否则，插入(key, value)auto p = new Node(key,value);hash[key] = p;insert(p);}}
};

7.复原IP地址（回溯）

class Solution {
private:vector<string> result;// 记录结果// startIndex: 搜索的起始位置，pointNum:添加逗点的数量void backtracking(string& s, int startIndex, int pointNum) {if (pointNum == 3) { // 逗点数量为3时，分隔结束// 判断第四段子字符串是否合法，如果合法就放进result中if (isValid(s, startIndex, s.size() - 1)) {result.push_back(s);}return;}for (int i = startIndex; i < s.size(); i++) {if (isValid(s, startIndex, i)) { // 判断 [startIndex,i] 这个区间的子串是否合法s.insert(s.begin() + i + 1 , '.');  // 在i的后面插入一个逗点pointNum++;backtracking(s, i + 2, pointNum);   // 插入逗点之后下一个子串的起始位置为i+2pointNum--;                         // 回溯s.erase(s.begin() + i + 1);         // 回溯删掉逗点} else break; // 不合法，直接结束本层循环}}// 判断字符串s在左闭又闭区间[start, end]所组成的数字是否合法bool isValid(const string& s, int start, int end) {if (start > end) {return false;}if (s[start] == '0' && start != end) { // 0开头的数字不合法return false;}int num = 0;for (int i = start; i <= end; i++) {if (s[i] > '9' || s[i] < '0') { // 遇到非数字字符不合法return false;}num = num * 10 + (s[i] - '0');if (num > 255) { // 如果大于255了不合法return false;}}return true;}
public:vector<string> restoreIpAddresses(string s) {result.clear();if (s.size() > 12) return result; // 算是剪枝了backtracking(s, 0, 0);return result;}
};

8.验证IP地址是否属于IPV4/IPV6

class Solution {
public:string validIPAddress(string IP) {regex IPv4("(([0-9]|[1-9][0-9]|1[0-9][0-9]|2[0-4][0-9]|25[0-5])\.){3}([0-9]|[1-9][0-9]|1[0-9][0-9]|2[0-4][0-9]|25[0-5])");regex IPv6("([0-9a-fA-F]{1,4}\:){7}[0-9a-fA-F]{1,4}");if(regex_match(IP,IPv4)) return "IPv4";else if(regex_match(IP,IPv6)) return "IPv6";else return"Neither";}
};

9.跳台阶

时间复杂度：O(n)
空间复杂度：O(n)

1. 递归，利用一个哈希表，把计算过的fib(n)的值存在哈希表中，这样就可以减少大量运算

class Solution {
public:unordered_map<int,int> mp;int dfs(int n){//边界条件if(n==0)return 1;else if(n==1)return 1;//先检查下，这个n是不是之前就算过，如果算过直接返回else if(mp.count(n))return mp[n];//哈希表中没有，先算出来，再存在哈希表中，下次用到就不用重复计算int a=dfs(n-1)%1000000007;mp[n-1]=a;int b=dfs(n-2)%1000000007;mp[n-2]=b;mp[n]=(a+b)%1000000007;return mp[n];}int numWays(int n) {return dfs(n);}
};

10.矩阵中的最大矩形

class Solution {
public:int maximalRectangle(vector<string>& matrix) {if (matrix.size() == 0) {return 0;}vector<int> heights(matrix[0].size(), 0);int maxArea = 0;for (int i = 0; i < matrix.size(); ++i) {for (int j = 0; j < matrix[0].size(); ++j) {if (matrix[i][j] == '0') {heights[j] = 0;}else {heights[j] += matrix[i][j] - '0';}}maxArea = max(maxArea, largestRectangleArea(heights));}return maxArea;}int largestRectangleArea(vector<int>& heights) {stack<int> sta;sta.push(-1);int maxArea = 0;for (int i = 0; i < heights.size(); ++i) {while (sta.top() != -1 && heights[sta.top()] >= heights[i]) {int height = heights[sta.top()];sta.pop();int width = i - sta.top() - 1;maxArea = max(maxArea, height * width);}sta.push(i);}while (sta.top() != -1) {int height = heights[sta.top()];sta.pop();int width = heights.size() - sta.top() - 1;maxArea = max(maxArea, height * width);}return maxArea;}
};

六、华为

华为2题梅花桩

#include <bits/stdc++.h>
using namespace std;
struct node
{int x, y;
};
int m, n;
int nums[110][110], res[110][110];
//借助队列+动态规划，从右下角到左上角进行bfs搜索
void MHty(int x, int y)
{//首先把终点入栈queue<node> que;que.push({x, y});//初始化res里面全为最大值//res表示这个点对终点的最小距离memset(res, 0x3f, sizeof res);res[x][y] = 0;while (!que.empty()){//从栈顶开始，并弹出该点，表示已经遍历过了node u = que.front();que.pop();//从（x-1,y）点开始由后往前遍历，更新该点的这一列for (int i = u.x - 1; i >= 1; i--){//如果该点允许跳跃的距离大于或等于该点到终点的距离//且该点储存的最小跳跃次数大于上一个点+跳跃一次的值，表示可以跳跃if (nums[i][u.y] >= u.x - i && res[i][u.y] > res[u.x][u.y] + 1){//更新resres[i][u.y] = res[u.x][u.y] + 1;//把点入队列，稍后遍历该点que.push({i, u.y});}}//同理，从（x，y-1）点开始右往左遍历，更新这一行for (int i = u.y - 1; i >= 1; i--){if (nums[u.x][i] >= u.y - i && res[u.x][i] > res[u.x][u.y] + 1){res[u.x][i] = res[u.x][u.y] + 1;que.push({u.x, i});}}}
}
int main()
{char d;cin >> m >> d >> n;for (int i = 1; i <= m; i++){for (int j = 1; j <= n; j++){int k;cin >> k;nums[i][j] = k;}}MHty(m, n);if (res[1][1] != INT_MAX)cout << res[1][1] << endl;elsecout << -1 << endl;return 0;
}

华为3题

#include<bits/stdc++.h>
using namespace std;
const int N = 50100;
unordered_map<string,int> mymp;
int in[N],nums[N],arr[N];
int akk;
string ss;
vector<int> G[N];
int main()
{cin >> ss;if(mymp.find(tmp) == mymp.end()) mymp[ss] = ++akk;string now;int cnt = 0;while(cin >> now){++cnt;//以","来分割字符now += ",";string tmp;int p = now.find(',');tmp = now.substr(0,p);//如果没找到tmpif(mymp.find(tmp) == mymp.end()) mymp[tmp] = ++akk;now.erase(now.begin(),now.begin()+p+1);string t;p = now.find(',');//从0开始复制P个数t = now.substr(0,p);int v = 0;//从string转换到intfor(int i = 0;i < t.size();i++){v = v*10 + t[i] - '0';}nums[mymp[tmp]] = v;now.erase(now.begin(),now.begin()+p+1);while (now.size() > 0){p = now.find(',');t = now.substr(0,p);if(mymp.find(t) == mymp.end()) mymp[t] = ++akk;in[mymp[tmp]] ++;now.erase(now.begin(),now.begin()+p+1);G[mymp[t]].push_back(mymp[tmp]);}}if(cnt != mymp.size()){cout << -1 << endl;return 0;}for(int i = 1;i <= akk;i++){arr[i] = -1;}queue<int> que;for(int i = 1; i <= akk;i++){if(in[i] != 0){arr[i] = nums[i];que.push(i);}}while(!que.empty()){int u = que.front();que.pop();for(int i = 0; i < G[u].size();i++){int v = G[u][i];in[v]--;arr[v] = max(arr[u] + nums[v],arr[v]);if(in[v] == 0) que.push(v);}}cout << arr[mymp[ss]] << endl;return 0;
}