前言
正文
- 技巧
- 算法题
- - 1. [最长有效括号](https://leetcode-cn.com/problems/longest-valid-parentheses/)——动态规划的内容
  - 2. [大数相加](https://blog.csdn.net/fesdgasdgasdg/article/details/80953829)
  - 3. [10亿int型数，统计只出现一次的数](https://blog.csdn.net/u010983881/article/details/75097358)
  - 4. 层序遍历二叉树
  - 5. 两个栈实现一个队列
  - 6. [判断链表中是否有环 —– 有关单链表中环的问题](https://www.cnblogs.com/yorkyang/p/10876604.html)
  - - 6.1 判断单链表中是否有环
    - 6.2 判断单链表的入口点的地址
    - 6.3 如果存在环，求出环上各点的个数。
  - 7. 两个有序的数组，求中位数
  - 8. 给定一个无序数组，建一个最大堆。
  - 10. [调整数组顺序使奇数位于偶数前面](https://www.nowcoder.com/practice/beb5aa231adc45b2a5dcc5b62c93f593?tpId=117)
  - 11.旋转链表
  - 12. 求一个数组最大递减子数组，要求返回数组
  - 13. 完全二叉树怎么判断？
  - 15. [链表中将所有的偶数移到奇数后面不改变原来的相对位置？](https://blog.csdn.net/u013309870/article/details/62897748)
  - 16. LCS最大子序列问题
  - 17. 字母的全排列
  - 18. 判断回文链表？
  - 19. 反转链表
  - 20、二叉树的序列化和反序列化
  - 21. [返回峰值](https://leetcode-cn.com/problems/find-peak-element/)
  - 22. 写生成堆的代码
  - 23. 二叉树叶节点中的最小深度
  - 24. 求两个数组的交集，返回交集数组
  - 25.给定正整数n，找到若干个完全平方数使得他们的和等于n，求最少的个数
  - 26.判断是否是二叉搜索树
  - 27. [求平方根](https://zihengcat.github.io/2018/03/07/LeetCode-069-sqrt/)
  - 28. [最长递增子序列](https://leetcode-cn.com/problems/longest-increasing-subsequence/submissions/)
  - 29. 两两交换链表中的节点
  - 30. 生成堆的代码
  - 31. [二叉树的最小深度](https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/)
  - 32.滑动窗口的最大值
  - 33.最小体力合并土堆：https://blog.csdn.net/weixin_44781107/article/details/103085001
  - 34.奇偶链表重排：https://leetcode-cn.com/problems/odd-even-linked-list/comments/
  - 35. [无重复最长子串](https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/wu-zhong-fu-zi-fu-de-zui-chang-zi-chuan-by-leetc-2/)
  - 36. [合并两个有序数组](https://leetcode-cn.com/problems/merge-two-sorted-lists/)
  - 37. 用队列实现栈
  - 38.剑指 Offer 03. 数组中重复的数字
参考

前言

这里就专门放一些编程题。

正文

技巧

leetcode 上判定指针是否为空，统一用:if(head!=NULL) 而不用if(!head)。再强调一遍.
计算链表的长度使用这样的方式:
code

int len2 = 1;
while(node1->next!=NULL)//这里错第二次了，老是写成node!=NULL,要协程Node->next
{++len1;node1 = node1->next;
}

这样的错误:

段错误:您的程序发生段错误，可能是数组越界，堆栈溢出（比如，递归调用层数太多）等情况引起.

原因一：由于有一些地方出现了空指针的情况。比如head==nullptr，但我却还使用了head->next;

时间超时：
原因一：有可能是你while循环没出来。
若遇到要对链表进行切割以及重连的，建议弄一个虚拟节点。

算法题

1. 最长有效括号——动态规划的内容

class Solution {
public:int longestValidParentheses(string s) {stack<int> st;//申请一个栈空间vector<int> mark(s.length());//弄一个标记数组，若该括号是有效的，标记还是0，若不是，则更改为1for(int i = 0;i<mark.size();i++){mark[i]=0;}for(int j=0;j<s.length();j++){if(s[j]=='(')//当左括号是，进栈{st.push(j);}else//这肯定是右括号了{if(st.empty())//这就是无用的右括号了,这个时候只是把右括号的那个位置标记成0{mark[j]=1;}else{st.pop();//若是真的可以匹配的右括号就栈元素出来}}}while(!st.empty())//，这个点很重要，容易忽视，有可能剩下一些左括号，也要标记成0{mark[st.top()]=1;st.pop();}int len = 0;int ans = 0;int max1 = 0;for(int k =0;k<s.length();k++)//从头到尾遍历一遍，看连续的0有多少个{if(mark[k]){len=0;continue;}len++;max1 = len;ans=max(ans,max1);}return ans;}
};

题解
先将所有元素都标成0，将不能匹配的右括号全部置为1.遍历一遍，结束后，将不能匹配的左括号也都置为1.最好判断一下连续最长的0是多少个就可以了。

2. 大数相加

code

string add(string str_1,string_2)
{string result;string temp;bool carryFlag = false;string maxString=(str_1.size()>=str_2.size())?str_1:str_2;//先得到较长，较短字符串的长度string minString=(str_1.size()<str_2.size())?str_1:str_2;//将短字符串补齐到和长字符串一样长，在短字符串前边补上字符0int maxLength = maxString.size();int minLength = minString.size();temp.append((maxLength-minLength),'0').append(minString);minString.clear();minString.append(temp);//字符串进行倒序遍历，按位相机for(int i=(maxString.size()-1);i>=0;i--){int res;if(carryFlag)//看一下上一位是否有进位，若有进位要进行加一 res=(maxString[i]-48)+(minString[i]-48)+1;elseres=(maxString[i]-48)+(minString[i]-48);if(res<10)//res是否小于10 carryFlag = false;esecarryFlag = true;result.push_back((res%10)+48);//然后将当前的这个值存入result之中 }	if(carryFlag)//若最后一位还有进位，那么就直接在该结果上加一result.push_back(49);reverse(result.begin(),result.end());//接下来，翻转整个数组return result;
}

3. 10亿int型数，统计只出现一次的数

思路：
位图法：用bit来标识一个int整数。
分治法：分批处理这10亿的数值。

4. 层序遍历二叉树

反正就是用队列。
code

void layerTrace(BTreeNode *T)
{if(T== nullptr)//先判断这棵树是否为空return;BTreeNode *p=T;queue<BTreeNode*>q;q.push(p);//然后让头结点先入队列while(!q.empty())//这里可以去判断队列是否非空{p=q.front();//队列中的元素出来，q.pop();cout<<<<p->data;if(p->left!= nullptr)q.push(p->left);//找左子树，让其入队列if(p->right!= nullptr)q.push(p->right);//找，让其入队列右子树}
}

5. 两个栈实现一个队列

code

class Solution
{public:void push(int node) {stack1.push(node);}int pop() {if(stack2.size()!=0){int tmp = stack2.front();stack2.pop();return tmp;}else{//若栈二为空了，我们就要把栈一的值全都放在栈二中去while(stack1.size()!=0){int tmp = stack1.top();stack1.pop();stack2.push(tmp);}return pop();}}private:stack<int> stack1;stack<int> stack2;}；

6. 判断链表中是否有环 —– 有关单链表中环的问题

其实最重要的就是要明白的一个关系：
就是头节点到入口点的距离 = 相遇点到入口点的距离。
求相遇点就用双指针就可以了。

6.1 判断单链表中是否有环

快慢指针，若两个指针相遇，则证明有环。
code

//如何判断是否有环
typedef struct node{char data;node *next;
}; bool exitLoop(Node *head)
{Node *fast,*slow;slow = fast = head;while(slow!=NULL&&fast->next!=NUL)//这样就可以判断有没有环了，如果没环，第二个节点肯定很早就到达末尾了，不会有slow = fast的这种情况。{slow = slow->next;fast = fast->next->next;if(slow==fast)return true;		}return false;
}

6.2 判断单链表的入口点的地址

相遇点到入口点的距离=头节点到入口点的距离
code

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};
*/
class Solution {
public:ListNode* EntryNodeOfLoop(ListNode* head) {
//这题第一眼看到也是没有多少想法,https://www.cnblogs.com/yorkyang/p/10876604.htmlListNode *fast,*slow;slow = fast = head;while(slow!=NULL&&fast->next!=NULL){    slow = slow->next;fast = fast->next->next;if(slow==fast)//这时找到入口点就停下来break;}if(slow==NULL||fast->next==NULL)//你这里肯定判断有没有环了，若有环才继续下一步return NULL;ListNode *ptr1 = head;ListNode *ptr2 = slow;while(ptr1!=ptr2)//有一个相等关系：头->入口点 = 两个指针的相遇点->入口点/。这两段距离是相等的{ptr1 = ptr1->next;ptr2 = ptr2->next;}return ptr1;}
};

6.3 如果存在环，求出环上各点的个数。

思路1：记录下相遇节点存入临时变量tempPtr，然后让slow(或者fast，都一样)继续向前走slow = slow -> next；一直到slow == tempPtr; 此时经过的步数就是环上节点的个数；

思路2：从相遇点开始slow和fast继续按照原来的方式向前走slow = slow -> next; fast = fast -> next -> next；直到二者再次项目，此时经过的步数就是环上节点的个数。

7. 两个有序的数组，求中位数

方法一：
code

class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int size1 = nums1.size();int size2 = nums2.size();int totalSize = size1+size2;int middle1 = INT_MIN;int middle2 = INT_MAX;int index1 = 0;int index2 = 0;for(int i = 0;i<=totalSize/2;i++){middle1 = middle2;if(index2>=size2||(index1<size1&&nums1[index1]<nums2[index2]))middle2 = nums1[index1++];elsemiddle2 = nums2[index2++];}if((totalSize%2)==0)return (middle1+middle2)/2.0;elsereturn middle2;}
};

8. 给定一个无序数组，建一个最大堆。

priority_queue<int，vector>这个是堆的表达式
code

class Solution {
public:vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {//采用最小堆的方式vector<int> arr;if(input.size()==0||k==0||k>input.size())return arr;priority_queue<int,vector<int>> que;//实现优先队列的数据结构，底层实现堆实现 priority_queue<Type,Container,Functional> Type为数据类型，Container为保存数据的容器，Functional为元素比较方式，若不写后两个元素，则容器默认是vector，比较方式默认用operator<,也就是优先队列是大顶堆，队头元素最大。for(auto x:input){if(que.size()<k){que.push(x);}else{if(x>que.top()){que.pop();que.push(x);}}}while(!que.empty()){arr.push_back(que.top());que.pop();}return arr;}
};

10. 调整数组顺序使奇数位于偶数前面

题目

方法一：多开辟一个数组的方法
code

class Solution {
public:    /**     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可     *     ** @param array int整型vector      * @return int整型vector     */vector<int> reOrderArray(vector<int>& array){if (array.size() == 0)return array;vector<int> num(array.size());int head = 0;int tail = array.size() - 1;int index_head = head;int index_tail = tail;while (head < array.size() && tail >= 0){if (array[head] % 2 == 1){num[index_head] = array[head];index_head++;}head++;if (array[tail] % 2 == 0){num[index_tail] = array[tail];index_tail--;}tail--;}return num;}
};

方法二：用一个i来放奇数，不断移动该值。
思路：进行一次遍历，若得到当前数为奇数的话，则将该数到真正存放奇数部分的那一位的后面一位的前部数，都往后移。这样，就相当于把所有的技术都放在前面了。
code

class Solution {
public:void reOrderArray(vector<int>& array){int i = 0;for (int j = 0; j < array.size(); j++){if (array[j] & 1)//表示是奇数的话         {int temp = array[j];//先将该奇数进行赋值  for (int k = j - 1; k >= i; --k)//从该奇数的位置，到要存放奇数的i位置  {array[k + 1] = array[k];//不断的向后移动 }array[i++] = temp;//然后，将该temp值赋值给放奇数的这个位置    }}}
};

11.旋转链表

题目

思路：先收尾相连，然后在最后面的那个指针向前移动k个位置，移到那个位置后，断开当前链表。**注意一点点是若k的大小大于这个链表的长度的话，则哟啊进行取余的操作。
code

/*** 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* rotateRight(ListNode* head, int k) {if(k==0||head==nullptr||head->next==nullptr)return head;int n = 1;ListNode* node = head;while(node->next!=nullptr)//通过这个可以计算出当前有多少元素{node = node->next;n++;}int add = n-k%n;if(add==n)//若需要左移的元素刚好是n的整数倍return head;node->next = head;//收尾相连while(add--)//根据这个，移到要断开的那个位置{node = node->next;}ListNode *ret = node->next;node->next  = nullptr;return ret;}
};

题解
这题有几个点：

首先，将链表首尾相连

得出链表有多少个元素。

注意移动的元素的数量有可能大于n.所以要取余。

注意，这里的这个add，移动的个数是n-k。

12. 求一个数组最大递减子数组，要求返回数组

思路：在这个的基础上修改一下就可以了。首先，dp[0]为数组的第一个元素，接下来，dp[i] = max(arr[i-1],dp[i-1]+arr[i-1])哪个更大。然后，还要比较一下之前的最大值，和现在形成的最大值。
code

class Solution {
public:int FindGreatestSumOfSubArray(vector<int> array){int size = array.size();vector<int> dp(size + 1, 1);dp[0] = 0;int ret = array[0];//ret作为返回值    for (int i = 1; i <= size; i++)//由第一个元素到最后一个元素 {dp[i] = max(array[i - 1], dp[i - 1] + array[i - 1]);//判断加上这个元素更大，还是不加更大 ret = max(ret, dp[i]);}return ret;}
};

13. 完全二叉树怎么判断？

思路:转变思路，如何判断该树不是完全二叉树，就是层序遍历已经输出null节点了，后面却还有节点。
code

class Solution
{
public:bool isCompleteTree(TreeNode* root){queue<TreeNode*> q;bool reachNull = false;q.push(root);while (!q.empty()){TreeNode* cur = q.front();q.pop();if (cur == nullptr){reachNull = true;continue;}else{if (reachNull){return false;}q.push(cur->left);q.push(cur->right);}}return true;}
};

15. 链表中将所有的偶数移到奇数后面不改变原来的相对位置？

code

ListNode* oddEvenList(ListNode* head)
{if (head == nullptr || head->next == nullptr)return head;ListNode* q = NULL;ListNode* p = head;while (p){if (p->val & 1){if (q == NULL){swap(head->val, p->val);q = head;}else{q = q->next;//相当于q所指的位置，就是所有奇数的最后一位 swap(q->val, p->val);}}p = p->next;}return head;
}

16. LCS最大子序列问题

17. 字母的全排列

code

class Solution {
public:set<string> tempRes;//为了剔除掉重复的，所以用set vector<string> Permutation(string str){vector<string> strOut;if (str.size() == 0)return strOut;Recursion(str, 0);for (auto x : tempRes){strOut.push_back(x);}return strOut;}/*    void swap(string str,int r,int k){char temp = str[k];str[k] = str[r];str[r] = temp;}*/void Recursion(string str, int index){if (index == str.size() - 1)//这个只是为了把最后一个也放进去，然后回溯的时候就会把该放的放进去 tempRes.insert(str);for (int i = index; i < str.size(); i++){swap(str[index], str[i]);Recursion(str, index + 1);}}
};

18. 判断回文链表？

题目

code

class Solution {
public:bool isPalindrome(ListNode* head){if (head == nullptr){return true;}// 找到前半部分链表的尾节点并反转后半部分链表  ListNode* firstHalfEnd = endOfFirstHalf(head);//先使用快慢指针找到中间节点 ListNode* secondHalfStart = reverseList(firstHalfEnd->next);//将该节点后面的所有节点进行翻转  // 判断是否回文   ListNode* p1 = head;ListNode* p2 = secondHalfStart;bool result = true;while (result && p2 != nullptr){if (p1->val != p2->val){result = false;}p1 = p1->next;p2 = p2->next;}// 还原链表并返回结果    firstHalfEnd->next = reverseList(secondHalfStart);return result;}ListNode* reverseList(ListNode* head){ListNode* prev = nullptr;ListNode* curr = head;while (curr != nullptr){ListNode* nextTemp = curr->next;//先储存下这个next节点 curr->next = prev;//将指针进行反转 prev = curr;//把cur变成pre,把next变成cur curr = nextTemp;}return prev;}ListNode* endOfFirstHalf(ListNode* head){//返回的是链表中间节点的指针   ListNode* fast = head;ListNode* slow = head;while (fast->next != nullptr && fast->next->next != nullptr){fast = fast->next->next;slow = slow->next;}return slow;}
};

19. 反转链表

code

/*struct ListNode {	int val;	struct ListNode *next;	ListNode(int x) :			val(x), next(NULL) {	}};*/class Solution {
public:ListNode* ReverseList(ListNode* pHead){ListNode* pReversedHead = NULL;ListNode* pNode = pHead;ListNode* pPrev = NULL;while (pNode != NULL){ListNode* pNext = pNode->next;if (pNext == NULL)//这时只有一个节点的情况 pReversedHead = pNode;pNode->next = pPrev;pPrev = pNode;pNode = pNext;}return pReversedHead;}
};

20、二叉树的序列化和反序列化

21. 返回峰值

22. 写生成堆的代码

code

#include <iostream>
#include <vector>
#include <stdio.h> 
using namespace std;void adjustHeap(std::vector<int>& in, int i, int size);
void heapBuild(std::vector<int>& vec);
void heapSort(std::vector<int>& in);
void swap(std::vector<int>& in, int index1, int index2);void swap(vector<int>& in, int index1, int index2)
{int tmp = in[index1];in[index1] = in[index2];in[index2] = tmp;
}void adjustHeap(vector<int>& in, int i, int size)
{int root = i;int left = i * 2;int right = i * 2 + 1;int max = root;if (left<=size && in[left - 1]>in[max-1]){max = left;}if (right<=size && in[right - 1]>in[max - 1]){max = right;}//上面两个if做出的结果是max中的值得索引，是最大值的索引if (left <= size && max == left){swap(in, root - 1, left - 1);//然后进行交换adjustHeap(in, left, size);//调整这一边的树就可以了，另一边不用调整}if (right<=size&&max == right){swap(in, root - 1, right - 1);adjustHeap(in, right, size);}}
void heapBuild(vector<int>& vec)
{for (int i = vec.size() / 2; i > 0; --i)//从1/2处开始到第一个元素，逐渐调整吗{adjustHeap(vec, i, vec.size());}
}
void heapSort(vector<int>& in)
{heapBuild(in);//第一遍，建堆for (int size = in.size(); size > 1; --size){swap(in, 0, size-1);adjustHeap(in, 1, size-1);}
}int main() {vector<int> input = { 1,25,24,34,65,1,214,-89,74 };heapSort(input);//堆排序for (auto it : input) {cout << it << " ";}cout << endl;return 0;
}

23. 二叉树叶节点中的最小深度

24. 求两个数组的交集，返回交集数组

题目
给定两个数组，编写一个函数来计算它们的交集。

code

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {vector<int> arr;if(nums1.size()==0||nums2.size()==0)return arr;map<int,int> map;for(int i = 0;i<nums1.size();i++){//map还是得要一个一个进行初始化的，逃不掉的map[nums1[i]] = 0;}sort(nums1.begin(),nums1.end());sort(nums2.begin(),nums2.end());int i = 0;int j = 0;while(i<nums1.size()&&j<nums2.size()){if(nums1[i]==nums2[j]){if(map[nums1[i]]==0){arr.push_back(nums1[i]);map[nums1[i]]++;}i++;j++;}else if(nums1[i]>nums2[j])j++;else if(nums1[i]<nums2[j])i++;}return arr;}
};

思路：思路还是比较简单的，先把两个数组进行排序，然后用一个map做剔除重复元素的。然后用双指针，一个指向第一个数组的第一个元素，一个指向第二个数组的第一个元素。

25.给定正整数n，找到若干个完全平方数使得他们的和等于n，求最少的个数

26.判断是否是二叉搜索树

//这二叉搜索树的特性是左子树小于根节点，根节点小于其所有的右子树

27. 求平方根

28. 最长递增子序列

code

class Solution {
public:int lengthOfLIS(vector<int>& nums) {int n = (int)nums.size();if(n==0)return 0;vector<int> dp(n,0);//申请一个n的空间for(int i = 0 ;i<n;i++){dp[i] = 1;for(int j = 0;j<i;j++){if(nums[j]<nums[i])dp[i] = max(dp[i],dp[j]+1);//每个dp[i]代表的就是在当前这个数之前的最长递增子序列有多少个}}return *max_element(dp.begin(),dp.end());}
};

29. 两两交换链表中的节点

题目

code

/*** 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* swapPairs(ListNode* head) {if(head==nullptr||head->next==nullptr)return head;ListNode* newNode = head->next;head->next= swapPairs(newNode->next);newNode->next = head;return newNode;}
};

30. 生成堆的代码

31. 二叉树的最小深度

题目

递归的方法一：深度优先遍历
code

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int minDepth(TreeNode* root) {if(root==nullptr)return 0;if(root->left==nullptr&&root->right==nullptr)return 1;int left = 0;int right = 0;int minDepthInt =INT_MAX;if(root->left)minDepthInt = min(minDepthInt,minDepth(root->left));if(root->right)minDepthInt = min(minDepthInt,minDepth(root->right));return minDepthInt+1;}
};

32.滑动窗口的最大值

题目

暴力破解法
code

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {vector<int> arrOut;if(nums.size()==0||k==0)return arrOut;int r = 1-k;for(int i = 0;i<=nums.size()-k;i++){int res = nums[i];for(int j = i;j<i+k;j++){res = max(res,nums[j]);}arrOut.push_back(res);}return arrOut;}
};

方法二：动态规划用笔绘制一下比较容易出来。
code

class Solution {
public:vector<int> maxInWindows(const vector<int>& num, unsigned int size) {vector<int> res;int n = num.size();if(num.size()<size||num.size()<1||size<1)return res;int low = 1-size;//因为要保证当high走到size的时候，才会有第一个元素入数组int high = 0;deque<int> dp;//双端队列while(high<n){if(low>=1&&num[low-1]==dp[0])//当目前的最大元素是low-1.已经出了滑窗的话，就要出队列了{dp.pop_front();}while(!dp.empty()&&num[high]>dp[0])//判断是否大于dp[0]{dp.pop_front();}while(!dp.empty()&&num[high]>dp[dp.size()-1])//判断是否大于dp的最后一个元素{dp.pop_back();}dp.push_back(num[high]);//直接加入high元素if(low>=0)//dp[0]每次都是最大值，所以，直接加入，但注意，要low端滑到0的时候，才可以加入该数组res.push_back(dp[0]);low++;high++;}return res;}
};

33.最小体力合并土堆：https://blog.csdn.net/weixin_44781107/article/details/103085001

34.奇偶链表重排：https://leetcode-cn.com/problems/odd-even-linked-list/comments/

35. 无重复最长子串

code

class Solution {
public:int lengthOfLongestSubstring(string s) {if(s.size()==0)return 0;unordered_set<char> set;int rk = -1;//右边界int res = 0;//每次求的最长子串for(int i = 0;i<s.size();i++)//这个i就是左边界{if(i!=0){set.erase(s[i-1]);//只有在i>0的时候才会进行erase}while(rk+1<s.size()&&(set.count(s[rk+1])<1)){set.insert(s[rk+1]);rk++;}res = max(res,rk-i+1);}return res;}
};

讲解视频

36. 合并两个有序数组

题目

方法一
code

class Solution {
public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {if (l1 == nullptr) {return l2;} else if (l2 == nullptr) {return l1;} else if (l1->val < l2->val) {l1->next = mergeTwoLists(l1->next, l2);return l1;} else {l2->next = mergeTwoLists(l1, l2->next);return l2;}}
};

方法二：
code

class Solution {
public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {ListNode* preHead = new ListNode(-1);ListNode* prev = preHead;while (l1 != nullptr && l2 != nullptr) {if (l1->val < l2->val) {prev->next = l1;l1 = l1->next;} else {prev->next = l2;l2 = l2->next;}prev = prev->next;}// 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可prev->next = l1 == nullptr ? l2 : l1;return preHead->next;}
};

37. 用队列实现栈

用队列实现栈

方法一：单个队列解决
code

class MyStack {
public:queue<int> q;MyStack() {}void push(int x) {q.push(x);}int pop() {int size = q.size();size--;while(size--){q.push(q.front());//把头部的元素移到尾巴，除了最后一个元素q.pop();}int result= q.front();q.pop();return result;}int top() {return q.back();}bool empty() {return q.empty();}
};/*** Your MyStack object will be instantiated and called as such:* MyStack* obj = new MyStack();* obj->push(x);* int param_2 = obj->pop();* int param_3 = obj->top();* bool param_4 = obj->empty();*/

方法二：双队列实现栈
code

class MyStack {
public:queue<int> que1;queue<int> que2;MyStack() {}void push(int x) {que2.push(x);//这个就是作为一个辅助队列而已，while(!que1.empty())//这个是作为一个主队列{que2.push(que1.front());que1.pop();}swap(que1,que2);}int pop() {int r = que1.front();que1.pop();return r;}int top() {int r = que1.front();return r;}bool empty() {return que1.empty();}
};/*** Your MyStack object will be instantiated and called as such:* MyStack* obj = new MyStack();* obj->push(x);* int param_2 = obj->pop();* int param_3 = obj->top();* bool param_4 = obj->empty();*/

38.剑指 Offer 03. 数组中重复的数字

题目

答案
方法一：使用set<int> ，时间复杂度O(N),空间复杂度O(N)
code

class Solution {
public:int findRepeatNumber(vector<int>& nums) {if(nums.size()==0){return 0;}set<int> set;for(int i = 0;i<nums.size();i++){if(set.count(nums[i])){return nums[i];}else{set.insert(nums[i]);}}return 0;}
};

方法二：时间复杂度：O(nlogn)，空间复杂度O(1)
code

class Solution {public int findRepeatNumber(int[] nums) {Arrays.sort(nums);for(int i = 0;i < nums.length;i++){if(nums[i] == nums[i+1]){return nums[i];}}return -1;}
}

方法三：利用好所有元素都在1-n的这个区间的这个条件，时间复杂度O(n),空间复杂度O(1)

参考

牛客网

编程题集锦

目录

前言

正文

技巧

算法题

1. 最长有效括号——动态规划的内容

2. 大数相加

3. 10亿int型数，统计只出现一次的数

4. 层序遍历二叉树

5. 两个栈实现一个队列

6. 判断链表中是否有环 —– 有关单链表中环的问题

6.1 判断单链表中是否有环

6.2 判断单链表的入口点的地址

6.3 如果存在环，求出环上各点的个数。

7. 两个有序的数组，求中位数

8. 给定一个无序数组，建一个最大堆。

10. 调整数组顺序使奇数位于偶数前面

11.旋转链表

12. 求一个数组最大递减子数组，要求返回数组

13. 完全二叉树怎么判断？

15. 链表中将所有的偶数移到奇数后面不改变原来的相对位置？

16. LCS最大子序列问题

17. 字母的全排列

18. 判断回文链表？

19. 反转链表

20、 二叉树的序列化和反序列化

21. 返回峰值

22. 写生成堆的代码

23. 二叉树叶节点中的最小深度

24. 求两个数组的交集，返回交集数组

25.给定正整数n，找到若干个完全平方数使得他们的和等于n，求最少的个数

26.判断是否是二叉搜索树

27. 求平方根

28. 最长递增子序列

29. 两两交换链表中的节点

30. 生成堆的代码

31. 二叉树的最小深度

32.滑动窗口的最大值

33.最小体力合并土堆：https://blog.csdn.net/weixin_44781107/article/details/103085001

34.奇偶链表重排：https://leetcode-cn.com/problems/odd-even-linked-list/comments/

35. 无重复最长子串

36. 合并两个有序数组

37. 用队列实现栈

38.剑指 Offer 03. 数组中重复的数字

参考

宏碁推出 Predator Bifrost Radeon RX 7900 GRE OC 显卡

Python 正则表达式基本语法

赞助商推荐

最新文章

大众 ID.与众电动 SUV 限时成交价直降 4 万元，16.99 万元起

标签

点击排行

oppo问答系统技术路线

怎么打印网页内容(如何打印网页选中的内容图片)

pikachu通关教程~~~~

加大虚拟内存会怎么样(虚拟内存设置太大有什么坏处吗苹果)

Windows 无法访问指定设备、路径或文件的提示解决方法

关注我们的公众号

20、二叉树的序列化和反序列化