设计理念简短范文,腾讯云wordpress优化,体育php网站源码,美食网站开发前期准备文章目录 1. JZ66 构建乘积数组暴力解法双向遍历 2. JZ19 正则表达式匹配3. JZ20 表示数值的字符串有限状态机遍历 4. JZ75 字符流中第一个不重复的字符5. JZ23 链表中环的入口结点快慢指针哈希表 6. JZ76 删除链表中重复的结点快慢指针三指针如果只保留一个重复结点 7. JZ8 二… 文章目录 1. JZ66 构建乘积数组暴力解法双向遍历 2. JZ19 正则表达式匹配3. JZ20 表示数值的字符串有限状态机遍历 4. JZ75 字符流中第一个不重复的字符5. JZ23 链表中环的入口结点快慢指针哈希表 6. JZ76 删除链表中重复的结点快慢指针三指针如果只保留一个重复结点 7. JZ8 二叉树的下一个结点数组保存结点直接查找 分类讨论 8. JZ28 对称的二叉树9. JZ77 按之字形顺序打印二叉树栈实现队列实现 10. JZ78 把二叉树打印成多行 1. JZ66 构建乘积数组 暴力解法
class Solution {
public:vectorint multiply(vectorint A) {// write code herevectorint result(A.size(), 0);int flag, res, index 0;while(index result.size()){flag A[index];res 1;//cout flag flag endl;for(int i0; iA.size(); i){if(A[i] flag iindex) continue;res * A[i];}result[index] res;index;}return result;}
};双向遍历 class Solution {
public:vectorint multiply(vectorint A) {//双向遍历int len A.size();vectorint result(len, 1);int cur 1;//先乘左边从左到右for(int i1; iA.size(); i){//每多一位由数组B左边的元素多乘一个前面A的元素result[i] result[i-1] * A[i - 1];//cur * A[i];result[i] cur;}//再乘右边从右到左for(int ilen-1; i0; i--){result[i] * cur;//左右两边都乘起来cur * A[i];//cur为右边的累乘}return result;}
};2. JZ19 正则表达式匹配 好难啊我真的服了搬运K神题解
解题思路 初始化 初始化首行 dp数组更新
class Solution {
public:bool isMatch(string s, string p) {//1.dp定义 s前i个字符和p前j个字符都匹配 不包括i、jint m s.size()1, n p.size()1;vectorvectorbool dp(m, vectorbool(n, false));//2.初始化dp[0][0] true;//两个字符串都为空for(int j2; jn; j2)//s空 p不空dp[0][j] dp[0][j-2] p[j-1]*;//如果j-1是* 看j-2的匹配状态//3.更新dp/*for(int i1; im; i){for(int j1; jn; j){dp[i][j] p[j-1] * ?dp[i][j-2] || dp[i-1][j] (s[i-1] p[j-2] || p[j-2] .) :dp[i-1][j-1] (p[j-1]. || s[i-1]p[j-1]);}}*/for(int i1; im; i){for(int j1; jn; j){if(p[j-1] *){if(dp[i][j-2]) dp[i][j] true;// *可以为0所以aa和aab*中 *前前一个字符匹配就可以匹配// 此时看不加s串最后一个字母能不能匹配到这个位置如果能的话// 再看 * 前面的字母和s串新加的这个字母一样不如果一样就能匹配如果不一样因为此时s串多了一个字母// 就无法跟现在的 p 进行匹配了例如从 aa 可以匹配 aab* ,但是 aaa 匹配到 aab* 的时候dp[i - 1][j]为true// 但是s[i - 1] 与 p[j - 2]不一样就无法匹配else if(dp[i-1][j] s[i-1]p[j-2]) dp[i][j] true;// 但是如果 * 的前一个字符是万能的 . 即可匹配else if(dp[i-1][j] p[j-2].) dp[i][j] true;}else{// 不是 * 的情况下新加的两个字符相同则可以继续匹配if(dp[i-1][j-1] s[i-1]p[j-1]) dp[i][j] true;// 新加的字符不同但是 p 中新加的是万能的 . 就能随便匹配else if(dp[i-1][j-1] p[j-1].) dp[i][j] true;}}}return dp[m-1][n-1]; }
};3. JZ20 表示数值的字符串 无语了又很难的样子搬运力扣K神的题解了。
有限状态机 解题思路 本题使用有限状态自动机。根据字符类型和合法数值的特点先定义状态再画出状态转移图最后编写代码即可。 字符类型 空格「 」、数字「 0—90—90—9 」、正负号「 −±− 」、小数点「 … 」、幂符号「 eEeEeE 」。 状态定义 按照字符串从左到右的顺序定义以下 9 种状态。 0 开始的空格1 幂符号前的正负号2 小数点前的数字3 小数点、小数点后的数字4 当小数点前为空格时小数点、小数点后的数字5 幂符号6 幂符号后的正负号7 幂符号后的数字8 结尾的空格 结束状态合法的结束状态有 2, 3, 7, 8 。
class Solution {
public:bool isNumber(string s) {//2.有限状态机unordered_mapState, unordered_mapCharType, State transfer{{ STATE_INTITIAL, //初始状态{{CHAR_SPACE, STATE_INTITIAL},{CHAR_NUMBER, STATE_INTEGER}, {CHAR_POINT, STATE_DOT_WITHOUT_INT}, {CHAR_SIGN, STATE_INT_SIGN}} },{ STATE_INT_SIGN,{{CHAR_NUMBER, STATE_INTEGER}, {CHAR_POINT, STATE_DOT_WITHOUT_INT}} },{ STATE_INTEGER,{{CHAR_NUMBER, STATE_INTEGER},{CHAR_EXP, STATE_EXP},{CHAR_POINT, STATE_DOT},{CHAR_SPACE, STATE_END}}},{ STATE_DOT,{{CHAR_NUMBER, STATE_FRACTION},{CHAR_EXP, STATE_EXP}, {CHAR_SPACE, STATE_END}}},{STATE_DOT_WITHOUT_INT, {{CHAR_NUMBER, STATE_FRACTION}}}, {STATE_FRACTION,{{CHAR_NUMBER, STATE_FRACTION},{CHAR_EXP, STATE_EXP},{CHAR_SPACE, STATE_END}}}, {STATE_EXP,{{CHAR_NUMBER, STATE_EXP_NUMBER},{CHAR_SIGN, STATE_EXP_SIGN}}}, {STATE_EXP_SIGN, {{CHAR_NUMBER, STATE_EXP_NUMBER}}}, {STATE_EXP_NUMBER, {{CHAR_NUMBER, STATE_EXP_NUMBER},{CHAR_SPACE, STATE_END}}}, {STATE_END, {{CHAR_SPACE, STATE_END}}}};int len s.size();State st STATE_INTITIAL;for(int i0; ilen; i){CharType typ toCharType(s[i]);if(transfer[st].find(typ) transfer[st].end()) return false;else st transfer[st][typ];}return st STATE_INTEGER || stSTATE_DOT || stSTATE_FRACTION || stSTATE_EXP_NUMBER || stSTATE_END;}enum State{STATE_INTITIAL,STATE_INT_SIGN,STATE_INTEGER,STATE_DOT,STATE_DOT_WITHOUT_INT,STATE_FRACTION,STATE_EXP,STATE_EXP_SIGN,STATE_EXP_NUMBER,STATE_END};enum CharType {CHAR_NUMBER,CHAR_EXP,CHAR_POINT,CHAR_SIGN,CHAR_SPACE,CHAR_ILLEGAL};CharType toCharType(char ch) {if (ch 0 ch 9) {return CHAR_NUMBER;} else if (ch e || ch E) {return CHAR_EXP;} else if (ch .) {return CHAR_POINT;} else if (ch || ch -) {return CHAR_SIGN;} else if (ch ) {return CHAR_SPACE;} else {return CHAR_ILLEGAL;}}
};遍历
小天才才的题解
class Solution {
public:bool isNumber(string s) {//1. 遍历 找到所有合法情况int i 0, j s.size() - 1;//找到字符串中第一个不为空的位置for(; is.size(); i){if(s[i] ! ) break;}//从末尾找到字符串最后一个不为空的位置for(; j0; j--){if(s[j] ! ) break;}//判断是否为数值以及是否有小数点和e/Ebool numFlag false;bool dotFlag false;bool eFlag false;for(int ki; kj; k){//判断是否为数字//if(isdigit(s[k])) numFlagtrue;if(s[k] 0 s[k] 9) numFlag true;//判断是否为小数点并且之前是否出现过小数点和e/Eelse if(s[k]. !dotFlag !eFlag) dotFlag true;//是小数点 且之前没有出现过小数点和e/E//判断是否为e/E并且之前是否出现过e/E和数字else if((s[k]e || s[k]E) !eFlag numFlag)//是e/E 之前没有出现过e/E 且e/E 前后是数字{eFlag true;//因为e/E的前后必须都是数字所以如果找到了e/E就把num_flag设为false//遇到下一个数字再设为true避免出现12e的情况numFlag false;}//判断是否为-并且符号是否在数值的首位或者前一位是e/Eelse if((s[k] || s[k]-) (ki || s[k-1]e || s[k-1]E)) continue;//在数值的首位或者前一位是e/Eelse return false;//其他均为非法情况输出false}return numFlag;//肯定有数字}
};4. JZ75 字符流中第一个不重复的字符 class Solution
{
public://Insert one char from stringstreamvoid Insert(char ch) {v.push_back(ch);result[ch];//统计次数}//return the first appearence once char in current stringstreamchar FirstAppearingOnce() {for(int i0; iv.size(); i){if(result[v[i]] 1) return v[i];}return #;}vectorchar v;unordered_mapchar, int result;
};5. JZ23 链表中环的入口结点 快慢指针
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};
*/
class Solution {
public:ListNode* EntryNodeOfLoop(ListNode* pHead) {if(pHead nullptr || pHead-next nullptr) return nullptr;ListNode* fast pHead, *slow pHead;//写法1while(fast fast-next){slow slow-next;fast fast-next-next;if(fast slow)//第一次相遇{slow pHead;while(slow ! fast){slow slow-next;fast fast-next;}return fast;}}return nullptr;}
};写法2
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};
*/
class Solution {
public:ListNode* EntryNodeOfLoop(ListNode* pHead) {if(pHead nullptr || pHead-next nullptr) return nullptr;ListNode* fast pHead, *slow pHead;//写法2while(fast!nullptr fast-next!nullptr){slow slow-next;fast fast-next-next;if(slow fast) break;//不应该直接返回 要做判断 return fast-next;//cout slow-val fast-valendl;}// 若是快指针指向null则不存在环if(fastnullptr || fast-nextnullptr) return nullptr;//此时fast在环入口 让slow从头出发 同时走slow pHead;//再次相遇就是环入口while (fast ! slow) {fast fast-next;slow slow-next;}return fast;}
};哈希表
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};
*/
class Solution {
public:ListNode* EntryNodeOfLoop(ListNode* pHead) {if(pHead nullptr || pHead-next nullptr) return nullptr;//哈希表unordered_setListNode* hashset;while (pHead) {if(hashset.count(pHead)) return pHead;hashset.insert(pHead);pHead pHead-next;}return nullptr;}
};6. JZ76 删除链表中重复的结点 快慢指针
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};
*/
class Solution {
public:ListNode* deleteDuplication(ListNode* pHead) {if (!pHead) return NULL;ListNode* slow new ListNode(-1), *fast new ListNode(-1), *dummy new ListNode(-1);dummy-next pHead;// 初始化两个指针slow dummy;fast dummy-next;while(fast){while(fast-next fast-val fast-next-val)// 遇到重复fast fast-next;cout fast fast-val endl;cout slow slow-val endl;if(slow-next ! fast)// 此时slow连接的还是fast的重复结点 需要删除结点{slow-next fast-next;fast fast-next;}else// 没有重复{fast fast-next;slow slow-next;}}return dummy-next;}
};三指针
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};
*/
class Solution {
public:ListNode* deleteDuplication(ListNode* pHead) {if (!pHead) return NULL;//三指针ListNode* pre new ListNode(-1), *cur new ListNode(-1), *dummyhead new ListNode(-1);dummyhead-next pHead;cur pHead;//遍历链表 判断是否有重复pre dummyhead;//虚拟链表尾while(cur){if(cur-next!nullptr cur-val cur-next-val){while(cur-next!nullptr cur-val cur-next-val)cur cur-next;//此时没有重复了pre-next cur-next;cur cur-next;}else{cur cur-next;pre pre-next;}}return dummyhead-next;}
};如果只保留一个重复结点
在一个排序的链表中存在重复的结点请删除该链表中重复的结点重复的结点保留返回链表头指针。 例如链表1-2-3-3-4-4-5 处理后为 1-2-3-4-5
ListNode* deleteDuplication(ListNode* pHead)
{if (pHead nullptr) return nullptr;ListNode* node (ListNode*)malloc(sizeof(struct ListNode));node pHead;while (node ! nullptr) {if (node-next!nullptr node-val node-next-val) {//这里千万要判断node-next也不为空才可以while (node-next ! nullptr node-val node-next-val) {node-next node-next-next;}}node node-next;}return pHead;
}写法2
ListNode* deleteDuplication(ListNode* pHead)
{if (pHead nullptr || pHead-next nullptr) return pHead;ListNode dummpyHead(0);dummpyHead.next pHead;ListNode* pre dummpyHead;ListNode* cur dummpyHead.next;while (cur ! nullptr) {if (cur-next ! nullptr cur-val cur-next-val) {while (cur-next ! nullptr cur-val cur-next-val){cur cur-next;}pre-next cur;//删除重复结点pre pre-next;cur cur-next;}else {pre pre-next;cur cur-next;}}return dummpyHead-next;
}
7. JZ8 二叉树的下一个结点 数组保存结点
中序遍历保存节点在数组中再匹配目标节点
/*
struct TreeLinkNode {int val;struct TreeLinkNode *left;struct TreeLinkNode *right;struct TreeLinkNode *next;TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {}
};
*/
class Solution {
public:TreeLinkNode* GetNext(TreeLinkNode* pNode) {if(pNode nullptr) return nullptr;vectorTreeLinkNode* v;//1.获取根节点TreeLinkNode* root pNode;while(root-next ! nullptr) root root-next;//2.保存节点inOrder(root, v);//3.匹配目标节点for(int i0; iv.size(); i){if(pNode v[i]) return v[i1];}return nullptr;}void inOrder(TreeLinkNode* root, vectorTreeLinkNode* v){if(root nullptr) return;if(root-left) inOrder(root-left, v);v.push_back(root);if(root-right) inOrder(root-right, v);}
};直接查找 分类讨论
默认当前节点作为根节点那么中序遍历的下一个节点应该是其右子节点如果 有右子树 有左子树中序遍历的下一个节点 写法1
/*
struct TreeLinkNode {int val;struct TreeLinkNode *left;struct TreeLinkNode *right;struct TreeLinkNode *next;TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {}
};
*/
class Solution {
public:TreeLinkNode* GetNext(TreeLinkNode* pNode) {if(pNode nullptr) return nullptr;//分类// 如果有右子树TreeLinkNode* cur nullptr;if(pNode-right ! nullptr){pNode pNode-right;// 一直找到右子树的最左下的结点为返回值while(pNode-left ! nullptr) pNode pNode-left;return pNode;}//如果有父节点 先看有没左子节点 有就返回没有说明当前节点是右叶子节点 只有右子节点 一直往上找父节点while(pNode-next ! nullptr){cur pNode-next;//当前结点的父节点if(cur-left pNode) return cur;//无右子树 直到当前结点是其父节点的左子结点 返回pNode pNode-next;}return nullptr;}
};写法2
/*
struct TreeLinkNode {int val;struct TreeLinkNode *left;struct TreeLinkNode *right;struct TreeLinkNode *next;TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) { }
};
*/
#include unistd.h
class Solution {
public:TreeLinkNode* GetNext(TreeLinkNode* pNode) {if(pNode nullptr) return nullptr;//分类 写法2TreeLinkNode* node nullptr;if(pNode-right ! nullptr)//如果当前节点有右子树,则右子树最左边的那个节点就是{node pNode-right;while(node-left ! nullptr) node node-left;return node;}node pNode;while(node-next ! nullptr node node-next-right)//当前节点有右子树{node node-next;//找到当前节点是其父亲节点的左孩子的那个节点然后返回其父亲节点 相当于一直往上找父节点}return node-next;//如果当前节点没有右子树 有左子树 返回当前节点的父节点}
};写法3
/*
struct TreeLinkNode {int val;struct TreeLinkNode *left;struct TreeLinkNode *right;struct TreeLinkNode *next;TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {}
};
*/
#include unistd.h
class Solution {
public:TreeLinkNode* GetNext(TreeLinkNode* pNode) {if(pNode nullptr) return nullptr;//分类 写法3TreeLinkNode* cur nullptr;if(pNode-right)// 如果有右子树 一直找到右子树的最左下的结点为返回值{cur pNode-right;while(cur-left ! nullptr) cur cur-left;return cur;}// 如果无右子树 且当前结点是其父节点的左子结点if(pNode-next ! nullptr pNode pNode-next-left)return pNode-next;// 返回当前结点的父节点// 如果无右子树 且当前结点是其父节点的右子节点if(pNode-next ! nullptr){cur pNode-next;// 沿着左上一直爬树爬到当前结点是其父节点的左自己结点为止while(cur-next ! nullptr cur cur-next-right) cur cur-next;return cur-next;// 返回当前结点的父节点}return nullptr;}
};
8. JZ28 对称的二叉树 /*** struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* };*/
class Solution {
public:bool isSymmetrical(TreeNode* pRoot) {if(pRoot nullptr) return true;return dfs(pRoot-left, pRoot-right);}bool dfs(TreeNode* node1, TreeNode* node2){if(node1 nullptr node2 nullptr) return true;if(node1 nullptr || node2 nullptr) return false;if(node1-val ! node2-val) return false;return dfs(node1-left, node2-right) dfs(node1-right, node2-left);}
};9. JZ77 按之字形顺序打印二叉树 栈实现 /*** struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* };*/
class Solution {
public:vectorvectorint Print(TreeNode* pRoot) {vectorvectorint result;if(pRoot nullptr) return result;stackTreeNode* st1;//保存从右向左节点stackTreeNode* st2;//保存从左向右节点st1.push(pRoot);while(!st1.empty() || !st2.empty()){vectorint temp;TreeNode* cur;if(!st1.empty()){while(!st1.empty()){cur st1.top();//访问st1节点后 从左向右存入st2temp.push_back(cur-val);//当前层的节点if(cur-left) st2.push(cur-left);if(cur-right) st2.push(cur-right);st1.pop();}result.push_back(temp);}temp.clear();if(!st2.empty()) {while (!st2.empty()) {cur st2.top();temp.push_back(cur-val);if(cur-right) st1.push(cur-right);if(cur-left) st1.push(cur-left);st2.pop();}result.push_back(temp);}}return result;}
};队列实现 /*** struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* };*/
#include vector
class Solution {
public:vectorvectorint Print(TreeNode* pRoot) {vectorvectorint result;if(pRoot nullptr) return result;//队列实现queueTreeNode* que;que.push(pRoot);int level 0, size 0;//TreeNode* cur nullptr;while(!que.empty()){vectorint temp;//存储每一行结果size que.size();// 当前队列长度 否则后面会更新for(int i0; isize; i){TreeNode* cur que.front();que.pop();if(cur nullptr) continue; // 空元素跳过que.push(cur-left); // 左孩子入队列que.push(cur-right); // 右孩子入队列//第一层从左向右 level从0开始 level为偶数 左到右;下一层从右向左 level为奇数 右到左if(level % 2 0) temp.push_back(cur-val);// 从左至右打印else temp.insert(temp.begin(), cur-val);// 从右至左打印}level;if(!temp.empty()) result.push_back(temp);}return result;}
};10. JZ78 把二叉树打印成多行 队列迭代和上面那道题有点像简单一点
/*** struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* };*/
class Solution {
public:vectorvectorint Print(TreeNode* pRoot) {vectorvectorint result;if(pRoot nullptr) return result;//队列queueTreeNode* que;que.push(pRoot);vectorint v;TreeNode* cur;int size 0;while(!que.empty()){v.clear();size que.size();for(int i0; isize; i){cur que.front();que.pop();v.push_back(cur-val);if(cur-left) que.push(cur-left);if(cur-right) que.push(cur-right);}result.push_back(v);}return result;}
};
