配资网站建设是什么意思,移动端app开发需要哪些技术,如何做ppt课件,网站建设一般报价多少文章目录 题目收藏不含重复字符的最长子串最长公共子串 剑指 Offer剑指 Offer 05. 替换空格剑指 Offer 03. 数组中重复的数字剑指 Offer 04. 二维数组中的查找剑指 Offer 09. 用两个栈实现队列剑指 Offer 07. 重建二叉树剑指 Offer 06. 从尾到头打印链表剑指 Offer 11. 旋转数组… 文章目录 题目收藏不含重复字符的最长子串最长公共子串 剑指 Offer剑指 Offer 05. 替换空格剑指 Offer 03. 数组中重复的数字剑指 Offer 04. 二维数组中的查找剑指 Offer 09. 用两个栈实现队列剑指 Offer 07. 重建二叉树剑指 Offer 06. 从尾到头打印链表剑指 Offer 11. 旋转数组的最小数字剑指 Offer 12. 矩阵中的路径剑指 Offer 27. 二叉树的镜像剑指 Offer 28. 对称的二叉树剑指 Offer 29. 顺时针打印矩阵剑指 Offer 30. 包含min函数的栈剑指 Offer 31. 栈的压入、弹出序列剑指 Offer 32 - I. 从上到下打印二叉树剑指 Offer 32 - II. 从上到下打印二叉树 II剑指 Offer 33. 二叉搜索树的后序遍历序列剑指 Offer 34. 二叉树中和为某一值的路径剑指 Offer 15. 二进制中1的个数剑指 Offer 21. 调整数组顺序使奇数位于偶数前面22.链表中倒数第k个节点剑指 Offer II 022. 链表中环的入口节点剑指 Offer 24. 反转链表剑指 Offer 25. 合并两个排序的链表剑指 Offer 26. 树的子结构剑指 Offer 39. 数组中出现次数超过一半的数字剑指 Offer 42. 连续子数组的最大和 题目收藏
不含重复字符的最长子串
给定一个字符串 s 请你找出其中不含有重复字符的 最长子串 的长度。 输入: s “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”所以其长度为 3。 请注意你的答案必须是 子串 的长度“pwke” 是一个子序列不是子串。 滑动窗口左边界l, 右边界i, 右边界从0~len-1用unordered_map记录字符上一次出现的位置如果出现过就把左边界移动到max(l,字符上次出现的位置1) 每次左边界移动都是从含有一个重复的字符到不包含重复字符
class Solution {
public:int lengthOfLongestSubstring(string s) {unordered_mapchar,int last_exist;int lens.size();int l0;int ans0;for(int i0;ilen;i){if(last_exist.find(s[i])last_exist.end()){last_exist[s[i]]i;ansmax(ans,i-l1);}else{lmax(l,last_exist[s[i]]1);last_exist[s[i]]i;ansmax(ans,i-l1);}}return ans;}
};最长公共子串
给定两个字符串求这两个字符串的不包含数字的最长公共子串的长度。
#includebits/stdc.husing namespace std;const int N 10010;
char s1[N],s2[N];
int res, f[N];
int main()
{scanf(%s %s, s1 , s2);int l strlen(s1), r strlen(s2);for (int i 1; i l; i )//将s1的长度看作物品数量对应01背包{for (int j r; j1; j--)//s2的长度看作背包容量(对应01背包){if (s1[i-1] s2[j-1] s1[i-1] 9 s2[j-1] 9)//将s2的每个字符看作物品体积为1价值为x其中x只有满足条件满足相等才有价值1否则为0,既然都为0了为啥还要放进背包呢?{f[j] f[j - 1] 1;//背包的价值res max(res, f[j]);//res记录每次的最大值}else f[j] 0;//都不满足即所有物品价值为0所以背包总价值也为0}}printf(%d\n, res);return 0;
}剑指 Offer
剑指 Offer 05. 替换空格
请实现一个函数把字符串 s 中的每个空格替换成%20。
c字符串可以修改因为i一定小于j所以可能原地修改从后往前先得出修改后的长度时间复杂度 O ( n ) O(n) O(n)class Solution {
public:string replaceSpace(string s) {int ns.size();int num0;for(int i0;in;i)if(s[i] ) num;s.resize(n 2 * num);for(int in-1,jn-1num*2;ij;){ //i,j0也可if(s[i] ){s[j]0;s[j-1]2;s[j-2]%;j-3;i--;}while(i0 j0 s[i]! ) {//这一直报错因为当i--后可能变为负的s[j]s[i];i--;j--;}}return s;}
};剑指 Offer 03. 数组中重复的数字
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0n-1 的范围内。数组中某些数字是重复的但不知道有几个数字重复了也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。 输入 [2, 3, 1, 0, 2, 5, 3] 输出2 或 3 哈希表空间 O ( n ) O(n) O(n) 原地交换时间和哈希一样是 O ( n ) O(n) O(n)空间 O ( 1 ) O(1) O(1) class Solution {
public:int findRepeatNumber(vectorint nums) {int i0;while(inums.size()){if(nums[i]!i) {if(nums[nums[i]]!nums[i])//因为都在[0,n)之间不会越界swap(nums[i],nums[nums[i]]);else return nums[i];}else i;}return -1;}
};剑指 Offer 04. 二维数组中的查找
在一个 n * m 的二维数组中每一行都按照从左到右 非递减 的顺序排序每一列都按照从上到下 非递减 的顺序排序。请完成一个高效的函数输入这样的一个二维数组和一个整数判断数组中是否含有该整数。 现有矩阵 matrix 如下 [ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ] 给定 target 5返回 true。 给定 target 20返回 false。 基准是右上角或者左下角这样才可以剔除一行或一列左上角无法剔除无法缩小查找范围
class Solution {
public:bool findNumberIn2DArray(vectorvectorint matrix, int target) {int nmatrix.size();if(n0) return false; int mmatrix[0].size();int r0,cm-1;while(rn c0){if(matrix[r][c]target) return true;else if(targetmatrix[r][c]) c--;else r;}return false;}
};剑指 Offer 09. 用两个栈实现队列
用两个栈实现一个队列。队列的声明如下请实现它的两个函数 appendTail 和 deleteHead 分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素deleteHead 操作返回 -1 )
class CQueue {//两个栈一个出栈一个入栈private StackInteger stack1;private StackInteger stack2;public CQueue() {stack1 new Stack();stack2 new Stack();}public void appendTail(int value) {stack1.push(value);}public int deleteHead() {if(!stack2.isEmpty()){return stack2.pop();}else{while(!stack1.isEmpty()){stack2.push(stack1.pop());}return stack2.isEmpty() ? -1 : stack2.pop();}}
}剑指 Offer 07. 重建二叉树
输入某二叉树的前序遍历和中序遍历的结果请构建该二叉树并返回其根节点。 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 递推参数 根节点在前序遍历的索引 root 、子树在中序遍历的左边界 left 、子树在中序遍历的右边界 right
class Solution {
public:TreeNode* buildTree(vectorint preorder, vectorint inorder) {this-preorder preorder;for(int i 0; i inorder.size(); i)dic[inorder[i]] i;return recur(0, 0, inorder.size() - 1);}
private:vectorint preorder;unordered_mapint, int dic;TreeNode* recur(int root, int left, int right) { if(left right) return nullptr; // 递归终止TreeNode* node new TreeNode(preorder[root]); // 建立根节点int i dic[preorder[root]]; // 划分根节点、左子树、右子树node-left recur(root 1, left, i - 1); // 开启左子树递归node-right recur(root i - left 1, i 1, right); // 开启右子树递归return node; // 回溯返回根节点}
};剑指 Offer 06. 从尾到头打印链表
输入一个链表的头节点从尾到头反过来返回每个节点的值用数组返回。
从头遍历链表入栈再出栈。
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:vectorint reversePrint(ListNode* head) {stackListNode* sk;vectorint s;ListNode* pNodehead;while(pNode!nullptr){sk.push(pNode);pNodepNode-next;}while(!sk.empty()){pNodesk.top();s.push_back(pNode-val);sk.pop();}return s;}
};剑指 Offer 11. 旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾我们称之为数组的旋转。
给你一个可能存在 重复 元素值的数组 numbers 它原来是一个升序排列的数组并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转该数组的最小值为 1。
注意数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。 输入numbers [3,4,5,1,2] 输出1 输入numbers [2,2,2,0,1] 输出0 class Solution {
public:int minArray(vectorint numbers) {//二分int nnumbers.size();int l0,rn-1;int midl;//初始化为l当numbers直接递增时int ansnumbers[0];while(numbers[l]numbers[r]){if(l1r) {midr;break;}mid(lr)1;if(numbers[mid]numbers[l] numbers[mid]numbers[r]){for(int i0;in;i)ansmin(ans,numbers[i]);return ans;}if(numbers[mid]numbers[l]) lmid;else if(numbers[mid]numbers[r]) rmid;}return numbers[mid];}
};按照旋转规则第一个元素应该大于等于最后一个元素特例[1,2,3],此时不进while()直接return numbers[mid]numbers[0]若中间元素位于前面的递增子数组那么它应该大于等于第一个指针指向的元素—将第一个指针移到mid
剑指 Offer 12. 矩阵中的路径
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中返回 true 否则返回 false 。
单词必须按照字母顺序通过相邻的单元格内的字母构成其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
class Solution {
public:bool exist(vectorvectorchar board, string word) {rows board.size();cols board[0].size();for(int i 0; i rows; i) {for(int j 0; j cols; j) {if(dfs(board, word, i, j, 0)) return true;}}return false;}
private:int rows, cols;bool dfs(vectorvectorchar board, string word, int i, int j, int k) {if(i rows || i 0 || j cols || j 0 || board[i][j] ! word[k]) return false;if(k word.size() - 1) return true;board[i][j] \0;//已经用过这个字符了bool res dfs(board, word, i 1, j, k 1) || dfs(board, word, i - 1, j, k 1) || dfs(board, word, i, j 1, k 1) || dfs(board, word, i , j - 1, k 1);board[i][j] word[k];//回溯到上一层恢复现场return res;}
};剑指 Offer 27. 二叉树的镜像
请完成一个函数输入一个二叉树该函数输出它的镜像。 示例 1 输入root [4,2,7,1,3,6,9] 输出[4,7,2,9,6,3,1] class Solution {
public:TreeNode* mirrorTree(TreeNode* root) {if(root nullptr) return nullptr;stackTreeNode* stack;stack.push(root);while (!stack.empty()){TreeNode* node stack.top();stack.pop();if (node-left ! nullptr) stack.push(node-left);if (node-right ! nullptr) stack.push(node-right);TreeNode* tmp node-left;node-left node-right;node-right tmp;}return root;}
};class Solution {
public:TreeNode* mirrorTree(TreeNode* root) {if (root nullptr) return nullptr;TreeNode* tmp root-left;root-left mirrorTree(root-right);root-right mirrorTree(tmp);return root;}
};剑指 Offer 28. 对称的二叉树
请实现一个函数用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样那么它是对称的。 例如二叉树 [1,2,2,3,4,4,3] 是对称的。但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
bool isSymmetric(Treenode* root){if(rootNULL) return false;return check(root-left,root-right);
}
bool check(Treenode* u, Treenode* v){if(uNULL vNULL) return true;if(uNULL || vNULL || u-val!v-val) return false;return check(u.left, v.right) check(u.right, v.left);
}class Solution {
public:bool check(TreeNode *u, TreeNode *v) {queue TreeNode* q;q.push(u); q.push(v);while (!q.empty()) {u q.front(); q.pop();v q.front(); q.pop();if (!u !v) continue;if ((!u || !v) || (u-val ! v-val)) return false;q.push(u-left); q.push(v-right);q.push(u-right); q.push(v-left);}return true;}bool isSymmetric(TreeNode* root) {return check(root, root);}
};剑指 Offer 29. 顺时针打印矩阵
观察发现可以一圈一圈地输出每圈的左上角可以表示成(start,start)循环继续的条件是nstart*2 mstart*2每圈可以分为从左到右从上到下。。四步每步打印的范围是start~m-1-start。。但是有的圈并不总是由这四步组成
class Solution {
public:vectorint spiralOrder(vectorvectorint matrix) {vectorint res;int nmatrix.size();if(n0) return {};int mmatrix[0].size();int start0;while(nstart*2 mstart*2){int endXm-1-start;int endYn-1-start;for(int istart;iendX;i) res.push_back(matrix[start][i]);for(int istart1;iendY;i) res.push_back(matrix[i][endX]);if(startendY) for(int iendX-1;istart;i--) res.push_back(matrix[endY][i]);if(startendX) for(int iendY-1;istart;i--) res.push_back(matrix[i][start]);start;}return res;}
};剑指 Offer 30. 包含min函数的栈
定义栈的数据结构请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中调用 min、push 及 pop 的时间复杂度都是 O(1)。
借助一个辅助栈其包含的是一个非递增序列–如果新入栈的元素大于之前的最小值仍然往辅助栈中压入该最小值否则压入新入栈的元素
class MinStack {stackint x_stack;stackint min_stack;
public:MinStack() {min_stack.push(INT_MAX);}void push(int x) {x_stack.push(x);min_stack.push(::min(min_stack.top(), x));}void pop() {x_stack.pop();min_stack.pop();}int top() {return x_stack.top();}int min() {return min_stack.top();}
};剑指 Offer 31. 栈的压入、弹出序列
输入两个整数序列第一个序列表示栈的压入顺序请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列 {1,2,3,4,5} 是某栈的压栈序列序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
借助一个栈来模拟先按照压入顺序入栈如果弹出序列的j在栈顶就弹出否则继续压入…
class Solution {
public:bool validateStackSequences(vectorint pushed, vectorint popped) {stackint s;int npushed.size();for(int i0,j0;in;i){s.push(pushed[i]);while(jn !s.empty() popped[j]s.top()) {s.pop();j;}}if(s.empty()) return true;else return false;}
};剑指 Offer 32 - I. 从上到下打印二叉树
二叉树的层序遍历/BFS
class Solution {
public:vectorint levelOrder(TreeNode* root) {if(rootNULL) return {};vectorint res;queueTreeNode* q;q.push(root);while(!q.empty()){auto tq.front();res.push_back(t-val);q.pop();if(t-left) q.push(t-left);if(t-right) q.push(t-right);}return res;}
};剑指 Offer 32 - II. 从上到下打印二叉树 II
从上到下按层打印二叉树同一层的节点按从左到右的顺序打印每一层打印到一行 因为每次在队列中的都属于同一层。所以循环q.size()次对每个结点的处理不变。
vectorvectorint levelOrder(TreeNode* root) {if(rootNULL) return {};queueTreeNode* q;q.push(root);vectorvectorint ans;while(!q.empty()){vectorint res;int cntq.size();for(int i0;icnt;i){auto tq.front();q.pop();if(t-left) q.push(t-left);if(t-right) q.push(t-right);res.push_back(t-val); }ans.push_back(res); }return ans;}剑指 Offer 33. 二叉搜索树的后序遍历序列
输入一个整数数组判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true否则返回 false。假设输入的数组的任意两个数字都互不相同。 输入: [1,6,3,2,5] 输出: false 输入: [1,3,2,6,5] 输出: true class Solution {
public:bool verifyPostorder(vectorint postorder) {return verify(postorder,0,postorder.size()-1);}bool verify(vectorint postorder,int left,int right){if(leftright) return true;int rootpostorder[right];int ileft;while(iright postorder[i]root) i;int ji;while(jright postorder[j]root) j;//必须是递增的所哟从i之后的都要大于rootreturn jright verify(postorder,left,i-1)verify(postorder,i,right-1);}
};剑指 Offer 34. 二叉树中和为某一值的路径
给你二叉树的根节点 root 和一个整数目标和 targetSum 找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
class Solution {
public:vectorvectorint ans;vectorint path;void dfs(TreeNode* root, int target){if(rootnullptr) return;target-root-val;path.push_back(root-val);if(root-leftnullptr root-rightnullptr target0) ans.push_back(path);dfs(root-left,target);dfs(root-right,target);//回溯时的恢复path.pop_back();}vectorvectorint pathSum(TreeNode* root, int target) { dfs(root,target);return ans;}
};剑指 Offer 15. 二进制中1的个数
可能输入负数如0x80000000。负数右移10001010311110001
循环的次数等于整数二进制的位数int NumberOf1(int n){int count0;unsigned int flag1;while(flag){if(nflag) count;flagflag1;}return count;
}二进制数字n中1的个数 n(n-1)把n最右边的1变为0int NumberOf1(int n){int count0;while(n){count;nn(n-1);}return count;
}剑指 Offer 21. 调整数组顺序使奇数位于偶数前面 class Solution {
public:vectorint exchange(vectorint nums){int i 0, j nums.size() - 1;while (i j){while(i j (nums[i] 1) 1) i;while(i j (nums[j] 1) 0) j--;swap(nums[i], nums[j]);}return nums;}
};(nums[i] 1) 1)这里是一个判断数字属于数组的前半部分还是后半部分的函数。
22.链表中倒数第k个节点
只遍历链表一次 思路第一个指针从头节点开始走k-1步第二个指针保持不动从第k步开始第二个指针也开始从头结点动由于两个指针相差k-1所以当第一个指针到末尾时第二个指针刚好指向倒数第k个节点 扩展1求链表的中间结点。一个指针一次走一步另一个一次走两步当走得快的指针走到末尾时走得慢的指针刚好在链表中间。扩展2若走得快的追上了走得慢的说明链表中存在环没有追上说明一定不存在 剑指 Offer II 022. 链表中环的入口节点
给定一个链表返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环则返回 null。 第一轮相遇 fast 走的步数是 slow 步数的 2 倍即 f 2 s f2s f2s fast 比 slow 多走了 n 个环的长度即 f s n b fsnb fsnb – f 2 n b , s n b f2nb, snb f2nb,snb 目前slow 指针走过的步数为 nb 步。因此我们只要想办法让 slow 再走 a 步停下来就可以到环的入口 class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode *fast head, *slow head;while (true) {if (fast nullptr || fast-next nullptr) return nullptr;fast fast-next-next;slow slow-next;if (fast slow) break;}fast head;//fast走了a步-slow也走了a步while (slow ! fast) {slow slow-next;fast fast-next;}return fast;//不能是head}
};剑指 Offer 24. 反转链表
定义一个函数输入一个链表的头节点反转该链表并输出反转后链表的头节点。 输入: 1-2-3-4-5-NULL 输出: 5-4-3-2-1-NULL class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* tmphead;ListNode* pPrevnullptr;ListNode* pReversedHeadnullptr;while(tmp!nullptr){ListNode* pNexttmp-next;//防止链表断裂复制if(pNextnullptr) pReversedHeadtmp;//最后一个结点就是反转后的头结点tmp-nextpPrev;pPrevtmp;tmppNext;//注意这两句的顺序}return pReversedHead;}
};剑指 Offer 25. 合并两个排序的链表
输入两个递增排序的链表合并这两个链表并使新链表中的节点仍然是递增排序的。 输入1-2-4, 1-3-4 输出1-1-2-3-4-4 class Solution {
public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {ListNode* dumpnew ListNode(0);ListNode* curdump;while(l1!nullptr l2!nullptr){if(l1-val l2-val || l1-val l2-val) {cur-nextl2;l2l2-next;}else {cur-nextl1;l1l1-next;}curcur-next;}if(l1nullptr) cur-nextl2;else cur-nextl1;return dump-next;}
};递归
class Solution {
public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {if(l1nullptr) return l2;if(l2nullptr) return l1;ListNode* pMergeHeadnullptr;if(l1-val l2-val){pMergeHeadl1;pMergeHead-nextmergeTwoLists(l1-next,l2);}else{pMergeHeadl2;pMergeHead-nextmergeTwoLists(l1,l2-next);}return pMergeHead;}
};剑指 Offer 26. 树的子结构
输入两棵二叉树A和B判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构 即 A中有出现和B相同的结构和节点值。
class Solution {
public:bool isSubStructure(TreeNode* A, TreeNode* B) {bool resultfalse;if(A!nullptr B!nullptr){//找到节点值相同的点然后判断其左右子树是否相同if(A-valB-val) resultdoesTree1HasTree2(A,B);//没找到节点值相同的点继续找递归看其左右子树if(!result) resultisSubStructure(A-left,B);if(!result) resultisSubStructure(A-right,B);}return result;}bool doesTree1HasTree2(TreeNode* A,TreeNode* B){if(Bnullptr) return true;//注意这两句的顺序if(Anullptr) return false;if(A-val!B-val) return false;return doesTree1HasTree2(A-left,B-left) doesTree1HasTree2(A-right,B-right);}
};剑指 Offer 39. 数组中出现次数超过一半的数字
摩尔投票法 核心理念为 票数正负抵消。此方法时间和空间复杂度分别为 O ( N ) O(N) O(N) 和 O ( 1 ) O(1) O(1)
剑指 Offer 42. 连续子数组的最大和
class Solution {
public:int maxSubArray(vectorint nums) {int nnums.size();int resnums[0],beforenums[0],tmp;for(int i1;in;i){if(before0) tmpnums[i];else tmpbeforenums[i];beforetmp;//优化成beforemax(),resmax(before)resmax(res,tmp);}return res;}
};
