1.知识点总结
本次使用的OJ为牛客网（不用力扣是因为没有会员刷不了想刷的题目🤪）
不是很熟悉这种纯class的OJ，但是感觉好处就是，一些数据结构的题目必须按照要求做，不可以“数组投机”
数据结构基础题
2. 分题题解
2.1 反转链表
其实有在细节上卡住，主要是本地没有自测输入输出还是蛮容易翻车的~比如pre指针需要更新以及最后一个p的指针需要置为NULL
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* ReverseList(ListNode* pHead) {
if(pHead==NULL){
return pHead;
}
stack<ListNode*>st;
ListNode*p=pHead;
while(p){
st.push(p);
p=p->next;
}
ListNode*head=st.top();
st.pop();
ListNode*pre=head;
while(!st.empty()){
p=st.top();
p->next=NULL;
pre->next=p;
pre=p;
st.pop();
}
return head;}
};2.2 链表内区间反转
于是被迫学会了自己本地输入输出，然后卑微提交class~
还是有优化空间的，不一定要vector存储
#include<bits/stdc++.h>
using namespace std;
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
ListNode* Reverse(ListNode*pHead){
//1->2->3
if(pHead==NULL){
return pHead;
}
stack<ListNode*>st;
ListNode*p=pHead;
while(p){
st.push(p);
p=p->next;
}
ListNode*head=st.top();
st.pop();
ListNode*pre=head;
while(!st.empty()){
p=st.top();
pre->next=p;
p->next=NULL;
st.pop();
}
return head;
}
ListNode*ReverseRoom(ListNode*pHead,int m,int n){
ListNode *p,*pre;
if(pHead==NULL){
return pHead;
}
p=pHead;
vector<ListNode*>nodes;
int cnt=0;
while(p){
nodes.push_back(p);
p=p->next;
cnt++;
}
//头部讨论
if(m==1){
pHead=nodes[n-1];//没有头的情况
}else{
nodes[m-2]->next=nodes[n-1];
}
//尾部讨论
if(cnt>n){
nodes[m-1]->next=nodes[n];
}else{
nodes[m-1]->next=NULL;
}
//需要反转的位置是m-1 n-1
for(int i=n-1;i>=m-1;i--){
printf("pos=%d\n",i);
p=nodes[i];
if(i==n-1){
pre=nodes[i];
}else{
pre->next=p;
pre=p;
}
}
return pHead;
}
ListNode*create(int m){
ListNode*head=new ListNode(1);
ListNode*p,*pre;
pre=head;
for(int i=2;i<=m;i++){
p=new ListNode(i);
pre->next=p;
pre=p;
}
return head;
}
void show(ListNode*head){
ListNode*p=head;
while(p){
printf("%d ",p->val);
p=p->next;
}
printf("\n");
}
int main(){
ListNode*head=create(10);
show(head);
ReverseRoom(head,2,4);
show(head);
return 0;
} 2.3 二分查找-i
注意nums为空的特判
本地测试代码：
#include<bits/stdc++.h>
using namespace std;
int search(vector<int>&nums,int target){
int len=nums.size();
if(len==0){
return -1;
}
//0 - len-1
int low=0;
int high=len-1;
while(low<=high){
int mid=(low+high)/2;
if(nums[mid]==target){
return mid;
}else if(nums[mid]<target){
low=mid+1;
}else{
high=mid-1;
}
}
return -1;
}
vector<int>create(int m){
vector<int>nums;
for(int i=0;i<m;i++){
nums.push_back(i*2);
// 0 2 4 6 8
}
return nums;
}
int main(){
vector<int>nums=create(5);
printf("%d",search(nums,7));
return 0;
}2.4 二维数组中的查找
有一说一，虽然过了，但是总觉得……昂，不是很踏实，感觉不是最优解
- 注意[[]]特判
class Solution {
public:
bool findCol(vector<int>array,int target,int col){
int low=0,high=col-1;
while(low<=high){
int mid=(low+high)/2;
if(array[mid]==target){
return true;
}
if(array[mid]>target){
high=mid-1;
}else{
low=mid+1;
}
}
return false;
}
bool Find(int target, vector<vector<int> > array) {
//想到的方法主要是二维展开成一维，然后再处理
int row=array.size();//行数
if(row==0){
return false;
}
int col=array[0].size();//列数
if(col==0){
return false;
}
int low=0,high=row-1;
int low2=-1,high2=-1;
while(low<=high){
int mid=(low+high)/2;
//printf("%d-%d当前正在搜查第%d行\n",low,high,mid);
if(array[mid][0]>target){
high=mid-1;
}else if(array[mid][col-1]<target){
low=mid+1;
}else{
if(low2==-1){
low2=low;
high2=mid;
}
//mid是合法的，可以搜一下
if(findCol(array[mid],target,col)){
return true;
}else{
high-=1;
}
}
}
//继续搜索
if(low2!=-1){
low2=0;
high2=row-1;
}
while(low2<=high2&&low2!=-1){
int mid=(low2+high2)/2;
//
//printf("!%d-%d当前正在搜查第%d行\n",low2,high2,mid);
if(array[mid][0]>target){
high2=mid-1;
}else if(array[mid][col-1]<target){
low2=mid+1;
}else{
//mid是合法的，可以搜一下
if(findCol(array[mid],target,col)){
return true;
}else{
low2+=1;
}
}
}
return false;
}
};看了官方的精华题解
感觉应该没有严格卡我的时间，但是我的解法大多数情况下等同于遍历……
官方题解
class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
// 判断数组是否为空
int m = array.size();
if (m == 0) return false;
int n = array[0].size();
if (n == 0) return false;
int r = 0, c = n-1; // 右上角元素
while (r<m && c>=0) {
if (target == array[r][c]) {
return true;
}
else if (target > array[r][c]) {
++r;
}
else {
--c;
}
}
return false;
}
};3.参考资料
无
