长尾关键词爱站网,宁波seo推广怎么做,百度刷搜索词,wordpress营销型大气目录1、反转链表2、排序3、先序中序后序遍历4、最小的k个数5、子数组的最大累加和6、 用两个栈实现队列7、142. 环形链表 II8、20. 有效的括号9、最长公共子串(动态规划),磕磕绊绊10、二叉树之字形层序遍历11、重建二叉树12、LRU缓存13、合并两个有序链表15、大数加法16、一个二… 目录1、反转链表2、排序3、先序中序后序遍历4、最小的k个数5、子数组的最大累加和6、 用两个栈实现队列7、142. 环形链表 II8、20. 有效的括号9、最长公共子串(动态规划),磕磕绊绊10、二叉树之字形层序遍历11、重建二叉树12、LRU缓存13、合并两个有序链表15、大数加法16、一个二叉树和一个值sum请找出所有的根节点到叶子节点的节点值之和等于sum 的路径17、寻找第K大18、买卖股票的最佳时机19、二数之和20、合并两个有序数组21、二叉树的最近公共祖先 感觉所有算法里面掌握最好的还是回溯其他的都是半吊子。 1、反转链表
反转链表 双指针法
class Solution {
public:ListNode* ReverseList(ListNode* pHead) {ListNode* cur pHead;ListNode* prev nullptr;while(cur ! nullptr){ListNode* tmp cur-next;cur-next prev;prev cur;cur tmp;}return prev;}
};2、排序
排序 这里我们选择使用快速排序来求解
class Solution {
public:void Quicksort(vectorint a, int s, int t){int i, j;if (s t){//【1】设置两个变量i、j.分别指向首元素和尾元素设定i指向的首元素为基准元素i s;j t 1;while (1){do i;while (!(a[s] a[i] || i t)); //【2】重复i操作直到i指向的元素基准元素或者i指向尾部do j--;while (!(a[s] a[j] || j s)); //【3】反复执行j--直到指向的元素基准元素或者j指向头部if (i j) //【5】若此时ij将i和j指向的元素进行交换。大的元素在后面{swap(a[j], a[i]);}else break; //【5】完成第一次交换后重复执行步骤1、2直到ij位置}//【6】此时ij然后将基准元素与j指向的元素交换位置至此完成了原序列的第一次划分swap(a[s], a[j]);//【7】接下来分别对基准元素前后的子序列中长度大于1的子序列重复执行上述操作。Quicksort(a, s, j - 1); //前半序列Quicksort(a, j 1, t); //后半序列}}vectorint MySort(vectorint arr) {// write code hereQuicksort(arr,0,arr.size()-1);return arr;}
};3、先序中序后序遍历
递归法
class Solution {
public:/*** * param root TreeNode类 the root of binary tree* return int整型vectorvector*/vectorint pre;vectorint mid;vectorint post;void preorder(TreeNode* root){if(root nullptr) return;pre.push_back(root-val);preorder(root-left);preorder(root-right);}void midorder(TreeNode* root){if(root nullptr) return;midorder(root-left);mid.push_back(root-val);midorder(root-right);}void postorder(TreeNode* root){if(root nullptr) return;postorder(root-left);postorder(root-right);post.push_back(root-val);}vectorvectorint threeOrders(TreeNode* root) {// write code herepre.clear();mid.clear();post.clear();preorder(root);midorder(root);postorder(root);return {pre,mid,post};}
};4、最小的k个数
sort 取值
class Solution {
public:vectorint GetLeastNumbers_Solution(vectorint input, int k) {if(k input.size()) return {};vectorint result(k,0);sort(input.begin(),input.end());for(int i 0; i k; i)result[i] input[i];return result;}
};方法二堆 我们用一个大根堆实时维护数组的前 k 小值。首先将前 k个数插入大根堆中随后从第 k1 个数开始遍历如果当前遍历到的数比大根堆的堆顶的数要小就把堆顶的数弹出再插入当前遍历到的数。最后将大根堆里的数存入数组返回即可。在下面的代码中由于 C 语言中的堆即优先队列为大根堆我们可以这么做。
class Solution {
public:vectorint GetLeastNumbers_Solution(vectorint input, int k) {if(k input.size()) return {};if(k 0) return {};priority_queueint que;for(int i 0; i k; i){que.push(input[i]);}int size (int)input.size();for(int i k; i size; i){if(input[i] que.top()){que.pop();que.push(input[i]);}}vectorint res(k,0);for(int i 0; i k; i){res[i] que.top();que.pop();}return res;}
};如果是要求最大的k个数就用小根堆
5、子数组的最大累加和
https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/
class Solution {
public:int maxSubArray(vectorint nums) {if(nums.empty()) return 0;int res INT_MIN;int sum 0;for(int i 0; i nums.size(); i){sum nums[i];if(sum res) res sum;if(sum 0) sum 0;}return res;}
};6、 用两个栈实现队列
用两个栈实现队列 一个输入栈一个输出栈。 push数据的时候只要把数据放进输入栈即可。 pop的时候 1、输出栈如果为空就将进栈的数据全部导入再出栈弹出数据。 2、如果栈不为空直接从出栈弹出数据
class Solution
{
public:void push(int x) {stIn.push(x);}int pop() {if(stOut.empty()){while(!stIn.empty()){stOut.push(stIn.top());stIn.pop();}}//out有元素了那么就popint result stOut.top();stOut.pop();return result;}private:stackint stIn;stackint stOut;
};7、142. 环形链表 II
环形链表 II 使用快慢指针 通过数学证明x z 即从头节点出发一个index从相遇地点出发一个index每次移动一点直到两者相遇相遇地点就是入口 这里给出牛客网同样题目的代码 https://www.nowcoder.com/practice/6e630519bf86480296d0f1c868d425ad?tpId117tqId37713companyId134rp1ru%2Fcompany%2Fhome%2Fcode%2F134qru%2Fta%2Fjob-code-high%2Fquestion-rankingtabanswerKey
class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode* fast head;ListNode* slow head;while(fast ! nullptr fast-next ! nullptr){slow slow-next;fast fast-next-next;//当两者相遇的时候开始计算入口地点while(slow fast){ListNode* index1 slow;ListNode* index2 head;while(index1 ! index2){index1 index1-next;index2 index2-next;}return index1;}}//如果遇到nullptr说明没有环return nullptr;}
};8、20. 有效的括号
https://leetcode-cn.com/problems/valid-parentheses/ 使用栈的时候三者对应到的栈的情况; 1、已经遍历完字符串但是栈不为空 2、遍历字符串匹配的过程中栈已经为空了 3、再遍历字符串匹配的过程中发现栈中没有要匹配的字符。
class Solution {
public:bool isValid(string s) {stackchar st;for(int i 0; i s.size(); i){if(s[i] () st.push());else if(s[i] [) st.push(]);else if(s[i] {) st.push(});//接下来就是判断,这个是1、3情况else if(st.empty() || st.top() ! s[i]){return false;}//如果匹配那么出栈else{st.pop();}}//第2种情况遍历完字符串栈不为空return st.empty();}
};9、最长公共子串(动态规划),磕磕绊绊
给定两个字符串str1和str2,输出两个字符串的最长公共子串 题目保证str1和str2的最长公共子串存在且唯一。 1≤∣str1∣,∣str2∣≤5000 “1AB2345CD”,“12345EF” “2345” 1、把两个字符串分别以行和列组成一个二维矩阵。
2、比较二维矩阵中每个点对应行列字符中否相等相等的话值设置为1否则设置为0。
3、通过查找出值为1的最长对角线就能找到最长公共子串。 string LCS(string str1, string str2) {// write code hereint len1 str1.size();int len2 str2.size();int start_index 0;int res_length 0;if(len1 0 || len2 0) return ;vectorvectorint f(len11,vectorint(len21,0));for(int i0;i len1;i) //防止数组越界{for(int j0;j len2;j){//i-1:text中的第i个字符 if(str1[i] str2[j]){if( i 0 || j 0){f[i][j] 1;}else{f[i][j] f[i-1][j-1] 1;}}else f[i][j] 0;//更新坐标if(f[i][j] res_length){start_index i - res_length;res_length f[i][j];}}}
// cout start_index endl;
// cout res_length endl;return str1.substr(start_index,res_length);}10、二叉树之字形层序遍历
层序遍历flag标志即可 vectorvectorint zigzagLevelOrder(TreeNode* root) {// write code herequeueTreeNode* que;if(root ! nullptr) que.push(root);vectorvectorint result;int flag 0;while(!que.empty()){int size que.size();vectorint vec;for(int i 0; i size; i){TreeNode* node que.front();que.pop();vec.push_back(node-val);if(node-left) que.push(node-left);if(node-right) que.push(node-right);}if(flag 0){result.push_back(vec);flag 1;}else{reverse(vec.begin(),vec.end());result.push_back(vec);flag 0;}}return result;}11、重建二叉树
https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/
/*** 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* traversal(vectorint preorder,int prestart,int preend,vectorint inorder,int instart,int inend){//首先检查先序数组大小,根据下标if(prestart preend){return nullptr;}//先序数组中第一个节点就是当前中间节点,new一个节点int rootval preorder[prestart];TreeNode* root new TreeNode(rootval);//如果是叶子节点就不需要分割了直接返回该节点if(preend - prestart 1){return root;}//中序数组找切割点int splitIndex instart; //注意区间是左闭右开的for(splitIndex instart; splitIndex inend; splitIndex){if(inorder[splitIndex] rootval) break;}//切割中序数组int leftInbegin instart;int leftInend splitIndex;int rightInbegin splitIndex 1;int rightInend inend;//切割先序数组int leftPrebegin prestart 1;int leftPreend prestart leftInend - leftInbegin;int rightPrebegin leftPreend;int rightPreend preend;//递归处理左区间和右区间root-left traversal(preorder,leftPrebegin,leftPreend,inorder,leftInbegin,leftInend);root-right traversal(preorder,rightPrebegin,rightPreend,inorder,rightInbegin,rightInend);return root;}TreeNode* buildTree(vectorint preorder, vectorint inorder) {if(preorder.empty() || inorder.empty()) return nullptr;return traversal(preorder,0,preorder.size(),inorder,0,inorder.size());}
};12、LRU缓存
struct DLinkedNode {
public:int key;int value;DLinkedNode* prev;DLinkedNode* next;DLinkedNode() : key(0), value(0), prev(nullptr), next(nullptr) {};DLinkedNode(int _key, int _value) : key(_key), value(_value), prev(nullptr), next(nullptr) {};
};
class LRUCache {
private:unordered_mapint,DLinkedNode* cache;//dummyhead and dummytailDLinkedNode* dummyhead;DLinkedNode* dummytail;// now size of cacheint _size;// capacity of cacheint _capacity;
public:LRUCache(int capacity) {_capacity capacity;_size 0;dummyhead new DLinkedNode();dummytail new DLinkedNode();dummyhead-next dummytail;dummytail-prev dummyhead;}~LRUCache() {delete dummyhead;delete dummytail;}int get(int key) {// if not findif(cache.find(key) cache.end()){return -1;}//if find//haxi DLinkedNode* node cache[key];//move this Node to headmoveHead(node);return node-value;}void put(int key, int value) {// if key not exist ,create itif(cache.find(key) cache.end()){// if size capacity delete tail nodeif(_size 1 _capacity){DLinkedNode* deleted_node deleteTail();cache.erase(deleted_node-key);delete deleted_node;_size--;}DLinkedNode* newnode new DLinkedNode(key,value);cache[key] newnode;addHead(newnode);_size;}else //chage value{DLinkedNode* node cache[key];node-value value;moveHead(node);}}void addHead(DLinkedNode* node){//双向指针操作 虚拟头节点node-prev dummyhead;node-next dummyhead-next;dummyhead-next-prev node;dummyhead-next node;}DLinkedNode* deleteTail(){//尾节点是虚拟tail前面一个。DLinkedNode* node dummytail-prev;deleteNode(node);return node;}void deleteNode(DLinkedNode* node){node-prev-next node-next;node-next-prev node-prev;}void moveHead(DLinkedNode* node){//先删除当前节点deleteNode(node);//然后将它加入头部addHead(node);}
};13、合并两个有序链表
https://leetcode-cn.com/problems/merge-two-sorted-lists/
/*** 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* mergeTwoLists(ListNode* l1, ListNode* l2) {ListNode* dummyHead new ListNode(-1);ListNode* cur dummyHead;while(l1 ! nullptr l2 ! nullptr){if(l1-val l2-val){cur-next l2;cur cur-next;l2 l2-next;}else{cur-next l1;cur cur-next;l1 l1-next;}} while(l1 ! nullptr) {cur-next l1;cur cur-next;l1 l1-next;}while(l2 ! nullptr){cur-next l2;cur cur-next;l2 l2-next;}ListNode* ret dummyHead-next;delete dummyHead;return ret;}
};15、大数加法
大数加法
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可* 计算两个数之和* param s string字符串 表示第一个整数* param t string字符串 表示第二个整数* return string字符串*/string solve(string s, string t) {// write code hereif(s.empty()) return t;if(t.empty()) return s;if(s.size()t.size()) swap(t,s);int tail s.size() - t.size();int tmp 0;//补零操作 t是短的那个while(tail--) t 0t;//每次只处理1位从低到高for(int is.size()-1;i0;i--){tmp s[i]-0 t[i] -0 tmp;s[i] tmp%10 0;tmp/10;}//最高位是否有进位位if(tmp) s 1s;return s;}
};16、一个二叉树和一个值sum请找出所有的根节点到叶子节点的节点值之和等于sum 的路径
一个二叉树和一个值sum… 普通的回溯即可。
class Solution {
public:/*** * param root TreeNode类 * param sum int整型 * return int整型vectorvector*/vectorvectorint result;vectorint path;void traversal(TreeNode* root,int count){if(root-left nullptr root-right nullptr){if(count 0) {result.push_back(path);}return ;}if(root-left){count - root-left-val;path.push_back(root-left-val);traversal(root-left,count);path.pop_back();count root-left-val;}if(root-right){count - root-right-val;path.push_back(root-right-val);traversal(root-right,count);path.pop_back();count root-right-val;}return ;}vectorvectorint pathSum(TreeNode* root, int sum) {// write code herepath.clear();result.clear();if(root nullptr) return result;path.push_back(root-val);traversal(root,sum - root-val);return result;}
};17、寻找第K大
18、买卖股票的最佳时机
int maxProfit(vectorint prices) {// write code hereint n prices.size();vectorint dp(n1,0);int minnum prices[0];for(int i 1; i n; i){minnum min(minnum,prices[i]);dp[i] max(prices[i] - minnum,dp[i-1]);}return dp[n-1];}可以使用滚动数组优化
int maxProfit(vectorint prices) {int nprices.size();if(n0) return 0;int ans0;int minnum prices[0];for(int i1;in;i){minnummin(minnum,prices[i]);ansmax(ans,prices[i]-minnum);}if(ans0)ans0;return ans;}19、二数之和
https://leetcode-cn.com/problems/two-sum/
class Solution {
public:vectorint twoSum(vectorint nums, int target) {unordered_mapint,int umap;for(int i 0; i nums.size(); i){auto iter umap.find(target - nums[i]);//如果找到了if(iter ! umap.end()){return {i,iter-second};}//否则进行插入操作umap.insert(pairint,int(nums[i],i));}return {};}
};20、合并两个有序数组
void merge(int A[], int m, int B[], int n) {int l1 0;int l2 0;vectorint res;while(l1 m l2 n){if(A[l1] B[l2]){res.push_back(A[l1]);l1;}else{res.push_back(B[l2]);l2;}}while(l1 m) {res.push_back(A[l1]);l1;}while(l2 n) {res.push_back(B[l2]);l2;}for(int i 0; i res.size(); i)A[i] res[i];}21、二叉树的最近公共祖先
NC二叉树的最近公共祖先 int lowestCommonAncestor(TreeNode* root, int o1, int o2) {// write code hereif(root nullptr) return -1;if(o1 root-val || o2 root-val) return root-val;int left lowestCommonAncestor(root-left,o1,o2);int right lowestCommonAncestor(root-right,o1,o2);if(left -1) return right;if(right -1) return left;return root-val;}
