做卖车网站需要什么手续,企业数据哪里找,wordpress 获取标签,中文网站建设合同剑指offer 文章目录 剑指offer数组[数组中重复的数据 ](https://leetcode.cn/problems/find-all-duplicates-in-an-array/description/)将元素交换到对应的位置 二维数组中的查找二叉搜索树 旋转数组的最小数字二分查找 数组中出现次数超过一半的数字相互抵消 连续子数组的最大…剑指offer 文章目录 剑指offer数组[数组中重复的数据 ](https://leetcode.cn/problems/find-all-duplicates-in-an-array/description/)将元素交换到对应的位置 二维数组中的查找二叉搜索树 旋转数组的最小数字二分查找 数组中出现次数超过一半的数字相互抵消 连续子数组的最大和(二)动态规划 链表从尾到头打印链表栈反转链表双指针、递归拓展反转链表中间一部分 删除链表的节点链表合并链表中倒数最后k个结点双指针思想 复杂链表的复制哈希表在每个旧节点后加上新节点 删除有序链表中重复的元素-I双指针思想 删除链表中重复的结点 二叉树二叉树的深度递归 二叉树的最小深度二叉树的镜像 队列、栈用两个栈实现队列 动态规划跳台阶DP(ACM模式)递归(ACM模式) 数组
数组中重复的数据
将元素交换到对应的位置
class Solution {
public:vectorint findDuplicates(vectorint nums) {vectorint result;for (int i 0; inums.size();i){while (nums[i] ! nums[nums[i]-1]){swap(nums[i],nums[nums[i]-1]);}}for (int i 0; inums.size();i){if (nums[i]-1 ! i){result.push_back(nums[i]);}}return result;}
};时间复杂度O(n)
空间复杂度O(1)
二维数组中的查找
二叉搜索树
class Solution{
public:bool Find(int target, vectorvectorint arr){if (arr.empty() || arr[0].empty()) return false;int i 0;//行int j arr.size()-1;//列while (iarr.size()-1 j0){if (target arr[i][j])return true;else if (tartget arr[i][j])--j;elsei;}return false;}
}类似于二叉搜索树 旋转数组的最小数字
二分查找
最小值一定在右区域
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param nums int整型vector * return int整型*/int minNumberInRotateArray(vectorint nums) {int left 0, right nums.size()-1;int mid;while (leftright){mid (left right)/2;if (nums[left]nums[right])//left一定在左区域或最低点right一定在右区域左区域的数一定大于等于右区域的数return nums[left];if (nums[mid] nums[right])//mid在左区域,最小的数字在mid右边{left mid 1;}else if (nums[mid] nums[right])//mid在重复元素{--right;}else //mid在右区域, 最小数字要么是mid要么在mid左边{right mid;}}return nums[left];}
};数组中出现次数超过一半的数字
相互抵消
用不同数字相互抵消的方法最后留下来的一定是超过一半的数字 int MoreThanHalfNum_Solution(vectorint numbers) {// write code hereint num numbers[0];int count 1;for (int i 1; inumbers.size(); i){if (count 0){if (numbers[i]num){count;}else {--count;}}else //count 0{num numbers[i];count 1;}}return num;}
};1287. 有序数组中出现次数超过25%的元素
由于这题是升序可以直接用步长判断也可以用上题的步骤判断
连续子数组的最大和(二)
根据剑指offer自己想的待优化 int最大值INT_MAX最小值INT_MIN int的最小值可以写成0x8000000最大值可以写成0x7FFFFFFF class Solution {
public:vectorint FindGreatestSumOfSubArray(vectorint arr) {// write code hereint result 0x80000000;vectorint vresult;vectorint temp;int sum 0;for (int i 0;iarr.size();i){if (sum0)//如果和为负数那么前一个和一定是从那个元素开始算的最大和了{temp.clear();temp.push_back(arr[i]);sumarr[i];}else {sumarr[i];temp.push_back(arr[i]);}if (sumresult){result sum;vresult temp;}}return vresult;}
};动态规划
//只需要保存最大值时
int res nums[0];
for (int i 1; i nums.size(); i) {if (nums[i - 1] 0) nums[i] nums[i - 1];if (nums[i] res) res nums[i];
}
return res;
//需要保存对应的子数组时
求连续子数组的最大和ACM模式
#include iostream
#include string
#include vector
using namespace std;int main() {string str;cinstr;//输入是个字符串int k 0;vectorint numbers;while((k str.find(,)) ! str.npos){//注意输出的方法string temp str.substr(0, k);numbers.push_back(stoi(temp));str str.substr(k 1);}numbers.push_back(stoi(str));int tempmax 0;int result 0x80000000;int sum 0;for (int i 0; inumbers.size();i){if (sum0){sumnumbers[i];}else {sumnumbers[i];}result max(sum,result);}if (result0){result 0;}printf(%d,result);
}
// 64 位输出请用 printf(%lld)链表
从尾到头打印链表
栈
利用栈先入后出的特点很好解决
class Solution {
public:vectorint printListFromTailToHead(ListNode* head) {stackint stk;vectorint result;int value 0;while (head!nullptr){stk.push(head-val);head head-next;}while (!stk.empty()){value stk.top();result.push_back(value);stk.pop();}return result;}
};时间复杂度O(n)
空间复杂度O(n)
反转链表双指针、递归
双指针
class Solution {
public:vectorint printListFromTailToHead(ListNode* head) {ListNode* preNode nullptr;ListNode* curNode head;while(curNode!nullptr){ListNode* temp curNode-next;curNode-next preNode;preNode curNode;curNode temp;}vectorint result;while(preNode!nullptr){result.push_back(preNode-val);preNode preNode-next;}return result;}
};时间复杂度O(n)
空间复杂度O(1)
递归
class Solution {
public:vectorint printListFromTailToHead(ListNode* head) {ListNode* newhead ReverseList(head);vectorint result;while (newhead!nullptr){result.push_back(newhead-val);newhead newhead-next;}return result;}ListNode* ReverseList(ListNode* head){if (headnullptr || head-nextnullptr){return head;}ListNode* newhead ReverseList(head-next);head-next-next head;head-next nullptr;return newhead;}
};时间复杂度O(n)
空间复杂度O(n)
拓展反转链表中间一部分
92. 反转链表 II - 力扣LeetCode
class Solution {
public:ListNode* reverseBetween(ListNode* head, int left, int right) {if (head-nextnullptr || leftright){return head;}ListNode* dummyhead new ListNode(0);dummyhead-next head;ListNode* preleftEdge dummyhead;ListNode* leftEdge head;ListNode* rightEdge head;for(int i 1; ileft;i){preleftEdge preleftEdge-next;leftEdge preleftEdge-next;}for(int i 1; iright;i){rightEdge rightEdge-next;}ListNode* nextrightEdge rightEdge-next;ListNode* leftNode leftEdge;ListNode* firstNode leftNode;ListNode* rightNode leftNode-next;while (rightNode!nextrightEdge){ListNode* temp rightNode-next;rightNode-next leftNode;leftNode rightNode;rightNode temp;}preleftEdge-next leftNode;firstNode-next nextrightEdge;return dummyhead-next;}
};删除链表的节点
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param head ListNode类 * param val int整型 * return ListNode类*/ListNode* deleteNode(ListNode* head, int val) {// write code hereListNode* dummyhead new ListNode(0);dummyhead-next head;ListNode* pre dummyhead;ListNode* cur head;while (cur!nullptr){if (cur-valval){pre-next cur-next;break;}else {cur cur-next;pre pre-next;}}return dummyhead-next;}
};还有一种不需要知道前驱结点就可以“删除”链表结点的方法,前提是不能删除最后一个结点
class Solution {
public:void deleteNode(ListNode* node) {node-val node-next-val;node-next node-next-next;}
};链表合并
ACM模式的话要注意输入输出然后要注意cur指针的更新
#include iostream
using namespace std;
struct ListNode
{int val;ListNode* next;ListNode(int val): val(val), next(nullptr){}
};int main() {int a;ListNode* dummyhead new ListNode(0);ListNode* cur dummyhead;ListNode* dummyhead1 new ListNode(0);ListNode* cur1 dummyhead1;ListNode* dummyhead2 new ListNode(0);ListNode* cur2 dummyhead2;while(cina){ListNode* node new ListNode(a);cur1-next node;cur1 cur1-next;if(cin.get()\n){break;}}while(cina){ListNode* node new ListNode(a);cur2-next node;cur2 cur2-next;}cur1 dummyhead1-next;cur2 dummyhead2-next;while (cur1!nullptr cur2!nullptr){if (cur1-valcur2-val){cur-next cur1;cur1 cur1-next;}else {cur-next cur2;cur2 cur2-next;}cur cur-next;}if (cur1nullptr){cur-next cur2;}if (cur2nullptr){cur-next cur1;}cur dummyhead-next;while (cur!nullptr){printf(%d ,cur-val);cur cur-next;}return 0;
}
// 64 位输出请用 printf(%lld)链表中倒数最后k个结点
双指针思想
右指针指向左指针后k个元素这样当右指针为最后一个节点后的元素时左指针指向的就是所求元素
/*** struct ListNode {* int val;* struct ListNode *next;* ListNode(int x) : val(x), next(nullptr) {}* };*/
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param pHead ListNode类 * param k int整型 * return ListNode类*/ListNode* FindKthToTail(ListNode* pHead, int k) {// write code hereif (pHeadnullptr){return nullptr;}ListNode* left pHead;ListNode* right left;for (int i 0; ik;i){if(rightnullptr){return nullptr;}right right-next; }while (right!nullptr){right right-next;left left-next;}return left;}
};复杂链表的复制
LCR 154. 复杂链表的复制 - 力扣LeetCode
哈希表
键为旧指针值为新指针。第一次遍历时初始化键和值的label第二次赋上next和random指针
class Solution {
public:Node* copyRandomList(Node* head) {if (headnullptr){return nullptr;}unordered_mapNode*,Node* mp;Node* cur head;while (cur!nullptr){Node* newNode new Node(cur-val);mp[cur] newNode;cur cur-next;}cur head;while (cur!nullptr){mp[cur]-next mp[cur-next];mp[cur]-random mp[cur-random];cur cur-next;}return mp[head];}
};在每个旧节点后加上新节点
最后要记得把旧链表头结点断开连接
class Solution {
public:RandomListNode* Clone(RandomListNode* pHead) {if (pHeadnullptr){return nullptr;}//初始化nextRandomListNode* cur1 pHead;while (cur1!nullptr){RandomListNode* newNode new RandomListNode(cur1-label);newNode-next cur1-next;cur1-next newNode;cur1 cur1-next-next;}//赋值randomcur1 pHead;RandomListNode* cur2 pHead-next;while (cur1!nullptr){if (cur1-random ! nullptr){cur2-random cur1-random-next;}cur1 cur1-next-next;cur2 cur2-next-next;}//拆分链表RandomListNode* newCloneHead pHead-next;cur2 newCloneHead;pHead-next nullptr;while (cur2-next!nullptr){cur2-next cur2-next-next;cur2 cur2-next;}cur2-nextnullptr;cur1 pHead;cur2 pHead-next;return newCloneHead;}
};删除有序链表中重复的元素-I
双指针思想 ListNode* deleteDuplicates(ListNode* head) {// write code hereif (headnullptr){return nullptr;}ListNode* dummyhead new ListNode(0);ListNode* left dummyhead;ListNode* right head;while(right!nullptr){while (right-next!nullptr right-valright-next-val){right right-next;}left-next right;left left-next;right right-next;}return dummyhead-next;}删除链表中重复的结点
比前面多了再将right右移一步的动作以及最后要把left指向nullptr
class Solution {
public:ListNode* deleteDuplication(ListNode* pHead) {if (pHeadnullptr){return nullptr;}ListNode* dummyhead new ListNode(0);ListNode* left dummyhead;ListNode* right pHead;while(right!nullptr){if(right-next!nullptr right-valright-next-val){while (right-next!nullptr right-valright-next-val){right right-next;}right right-next;continue;}left-next right;left left-next;right right-next;}left-next nullptr;return dummyhead-next;}
};二叉树
二叉树的深度
递归
返回左子树和右子树深度的最大值加上一后序遍历
class Solution {
public:int TreeDepth(TreeNode* pRoot) {if (pRootnullptr){return 0;}return max(TreeDepth(pRoot-left),TreeDepth(pRoot-right))1;}
};二叉树的最小深度
111. 二叉树的最小深度 - 力扣LeetCode
和二叉树的最大深度的区别是计算的是到叶子节点左右孩子都为空的最小深度也用后序遍历实现
class Solution {
public:int minDepth(TreeNode* root) {if (rootnullptr){return 0;}if (root-leftnullptr root-right!nullptr){return minDepth(root-right)1;}else if (root-rightnullptr root-left!nullptr){return minDepth(root-left)1;}else{return min(minDepth(root-left),minDepth(root-right))1;}}
};二叉树的镜像
LCR 144. 翻转二叉树 - 力扣LeetCode
前序遍历
TreeNode* Mirror(TreeNode* pRoot) {// write code hereif (pRootnullptr) return pRoot;swap(pRoot-left,pRoot-right);Mirror(pRoot-left);Mirror(pRoot-right);return pRoot;}后序遍历
TreeNode* Mirror(TreeNode* pRoot) {// write code hereif (pRootnullptr) return pRoot;Mirror(pRoot-left);Mirror(pRoot-right);swap(pRoot-left,pRoot-right);return pRoot;}队列、栈
用两个栈实现队列
每当要pop的时候就获取stack2的最上面的元素如果stack2为空则将stack1依次出栈到stack2。这样stack2上面的就是最先push进去的元素最底下是最新push进去的元素。
class Solution
{
public:void push(int node) {stack1.push(node);}int pop() {while (!stack2.empty()){int result stack2.top();stack2.pop();return result;}while (!stack1.empty()){int temp stack1.top();stack2.push(temp);stack1.pop();}int result stack2.top();stack2.pop();return result;}private:stackint stack1;stackint stack2;
};动态规划
跳台阶
DP(ACM模式)
#include iostream
#include unordered_mapusing namespace std;int main() {int a;cina;unordered_mapint,int dp;dp[0] 1;dp[1] 1;dp[2] 2;if (a2){printf(%d,dp[a]);}else {for (int i3;ia;i){int temp dp[2];dp[2] dp[1];dp[1] temp;}printf(%d,dp[2]);}return 0;
}
// 64 位输出请用 printf(%lld)
递归(ACM模式)
#include iostream
using namespace std;int Jump(int num)
{if (num0) return 1;if (num1) return 1;if (num2) return 2;return Jump(num-1) Jump(num-2);
}int main() {int a;cina;int result Jump(a);printf(%d,result);return 0;
}
// 64 位输出请用 printf(%lld)
