文章目录
- 81. 搜索旋转排序数组 II(二分模板3)
- 82.删除排序链表中的重复元素II
- 83.删除排序链表中的重复元素
- 84.柱状图中最大的矩形
- 86.分隔链表
- 88.合并两个有序数组
- 90.子集 || (组合:去重)
- 91.解码方法
- 92.反转链表||(在指定区间内反转)
- 93.复原IP地址
- 94.二叉树的中序遍历
- 95. 不同的二叉搜索树 II
- 96.不同的二叉搜索树
81. 搜索旋转排序数组 II(二分模板3)
已知有一个按非降序排列的整数组 nums ，数组中的值不必不同。
在传递给函数之前，nums 在预先未知的下标中 k （ 0 < = k < n u m s . l e n g t h k（0 <= k < nums.length k（0<=k<nums.length上进行了 旋转 ，使数组变为 [ n u m s [ k ] , n u m s [ k 1 ] , . . . , n u m s [ n ? 1 ] , n u m s [ 0 ] , n u m s [ 1 ] , . . . , n u m s [ k ? 1 ] ] [nums[k], nums[k 1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] [nums[k],nums[k 1],...,nums[n?1],nums[0],nums[1],...,nums[k−1]]（下标 从 0 开始 计数）。例如， [ 0 , 1 , 2 , 4 , 4 , 4 , 5 , 6 , 6 , 7 ] [0,1,2,4,4,4,5,6,6,7] [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [ 4 , 5 , 6 , 6 , 7 , 0 , 1 , 2 , 4 , 4 ] [4,5,6,6,7,0,1,2,4,4] [4,5,6,6,7,0,1,2,4,4]。
给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。
示例1：
输入：nums = [2,5,6,0,0,1,2], target = 3
输出：false
自己写的~ 使用二分模板，把区间分为l,mid-1],[mid+1,r]，对应的更新操作为l=mid+1,r=mid-1
class Solution {
public:
bool search(vector<int>& nums, int target) {
int left=0,right=nums.size()-1;
while(left<=right){
int mid=left+(right-left)/2;
if(nums[mid]==target) return 1;
if(nums[mid]<nums[right]){
//mid-right是升序
if(target>nums[mid]&&target<=nums[right]) left=mid+1;
else right=mid-1;
}
else if(nums[mid]>nums[right]){
//left-mid是升序
if(target<nums[mid]&&target>=nums[left]) right=mid-1;
else left=mid+1;
}
else right--;//
}
return 0;
}
};
一开始是这样写的，但是WA，原因出现在：（标注在注释了）
class Solution {
public:
bool search(vector<int>& nums, int target) {
int left=0,right=nums.size()-1;
while(left<=right){
int mid=left+(right-left)/2;
if(nums[mid]==target) return 1;
if(nums[mid]<nums[right]){
//mid-right是升序
if(target>nums[mid]) left=mid+1;//这里不能这样写，target大于nums[mid]不能说明该值就出现在[mid+1,right]区间，因为我们知道left区间的数字是大于右边区间的，所以必须是target>nums[mid]&&target<=nums[right]才能判定其所在的区间是左还是右。
if(target<nums[mid]) right=mid-1;
}
else if(nums[mid]>nums[right]){
//left-mid是升序
if(target>nums[mid]) left=mid+1;
if(target<nums[mid]) right=mid-1;
}
else right--;
}
return 0;
}
};
82.删除排序链表中的重复元素II
存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。 返回同样按升序排列的结果链表。 示例1： 
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
先上自己写的。。。
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode*cur=head,*par=NULL;
while(cur!=NULL&&cur->next!=NULL){
if(cur->val==cur->next->val){
int DelVal=cur->val;
while(cur!=NULL&&cur->val==DelVal){
ListNode*CurNext=cur->next;delete cur;
cur=CurNext;
}
if(par==NULL) head=cur;//针对1,1,2,当cur到2的时候被外层while拦截了，根本到不了下第二个else那里，所以在这里进行跟踪新头节点
else par->next=cur;
}
else{
if(par==NULL){
par=cur;head=par;}
else{
par->next=cur;par=par->next;}
cur=cur->next;
}
}
return head;
}
};
看看人家题解写的，真的是很简洁了
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if(head==NULL) return head;
ListNode*newhead=new ListNode(0,head);
ListNode*cur=newhead;//这个cur相当于是前驱节点par
while(cur->next&&cur->next->next){
//就拿1,1,2,2，3走一遍就懂了，其实思路和我的差不多，但是我写的就是没题解的简洁
if(cur->next->val==cur->next->next->val){
int DelVal=cur->next->val;
while(cur->next&&cur->next->val==DelVal){
cur->next=cur->next->next;
}
}
else cur=cur->next;
}
return newhead->next;
}
};
83.删除排序链表中的重复元素
存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。 返回同样按升序排列的结果链表。
示例1：
输入：head = [1,1,2,3,3]
输出：[1,2,3]
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if(head==NULL) return head;
ListNode*cur=head;
while(cur->next){
if(cur->next->val==cur->val) cur->next=cur->next->next;
else cur=cur->next;
}
return head;
}
};
84.柱状图中最大的矩形
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 求在该柱状图中，能够勾勒出来的矩形的最大面积。
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10
单调栈，这里维护一个单调递增的栈，还是参考大二时期的程序算法课写出来的。
即将入栈的矩形只需要考虑向左扩展，弹出栈的矩形只考虑向右扩展。
high[i]表示sta[i]对应的矩形可以左右扩展到的宽度。
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int sz=heights.size(),top=-1,cover=0;
vector<int>high(sz+5,0);
vector<int> sta(sz+5,0);
sta[++top]=heights[0];
high[top]=1;
for(int i=1;i<heights.size();i++){
if(top>=0&&sta[top]<=heights[i]){
sta[++top]=heights[i];
high[top]=1;//是栈内最右边的一个矩形，其高最高，所以目前不可扩展
}
else{
int width=0;
while(top>=0&&sta[top]>=heights[i]){
//弹栈，即向右扩展
width+=high[top];
cover=max(cover,width*sta[top]);
top--;
}
sta[++top]=heights[i];
high[top]=1+width;//弹出的矩形都比这个栈顶矩形高，所以栈顶矩形可以向左扩展
}
}
int width=0;
while(top>=0){
//如果栈不空说明还有矩形没有计算 弹栈，即向右扩展
width+=high[top];
cover=max(cover,width*sta[top]);
top--;
}
return cover;
}
};
86.分隔链表
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。 你应当 保留 两个分区中每个节点的初始相对位置。
输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]
先上自己写的，对链表进行了一次遍历，复杂度O(n)
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode*Newhead=new ListNode(0,head);
ListNode*par=Newhead,*cur=head;
while(cur&&cur->val<x){
//先找到>=x的节点之前最后一个<x的节点
cur=cur->next;
par=par->next;
}
ListNode*front=par;
while(cur){
if(cur->val<x){
ListNode*tmp=cur->next;
cur->next=par->next;//调整该节点到par后面
par->next=cur;
front->next=tmp;//将该节点与front断链
cur=tmp;//处理下一个cur
par=par->next;
}
else {
front=front->next;cur=cur->next;}
}
return Newhead->next;
}
};
然后又改了一下，这个写法更简单，不用再申明front这个变量
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode*Newhead=new ListNode(0,head);
ListNode*par=Newhead,*cur=head;
while(cur&&cur->val<x){
//先找到>=x的节点之前最后一个<x的节点
cur=cur->next;
par=par->next;
}
while(cur&&cur->next){
if(cur->next->val<x){
ListNode*tmp=cur->next->next;
cur->next->next=par->next;
par->next=cur->next;
cur->next=tmp;
par=par->next;
}
else cur=cur->next;
}
return Newhead->next;
}
};
88.合并两个有序数组
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，，后 n 个元素为 0 ，应忽略。nums2 的长度为 n。 理解题意这里有个大坑，这个m可能是小于nums1中非0 值的数目的，m的意义是指定nums1要合并的值，nums2中所有的值都需要被合并
示例：
输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int idx=m+n-1,i=0,j=0;
for(i=m-1,j=n-1;i>=0&&j>=0;){
//逆序选大者，然后从尾到头放
if(nums1[i]>nums2[j]) nums1[idx--]=nums1[i--];
else nums1[idx--]=nums2[j--];
}
while(j>=0) {
nums1[idx--]=nums2[j--];}//如果nums2中还有未合并的要加进去
}
};
90.子集 || （组合：去重）
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。 解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
示例1：
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
这些回溯模板该记就得记！
class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<vector<int> > res;
vector<int> tmp;
sort(nums.begin(),nums.end());
combination(0,nums,tmp,res);
return res;
}
void combination(int idx,vector<int>&nums,vector<int>&tmp,vector<vector<int> >&res){
if(idx>nums.size()) return;
res.push_back(tmp);
for(int j=idx;j<nums.size();j++){
if(j>idx&&nums[j]==nums[j-1]) continue;
tmp.push_back(nums[j]);
combination(j+1,nums,tmp,res);
tmp.pop_back();
}
}
};
91.解码方法
一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
'A' -> 1
'B' -> 2
...
'Z' -> 26
要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，“11106” 可以映射为：
- “AAJF” ，将消息分组为 (1 1 10 6)
- “KJF” ，将消息分组为 (11 10 6)
注意，消息不能分组为 (1 11 06) ，因为 “06” 不能映射为 “F” ，这是由于 “6” 和 “06” 在映射中