网站建设成都创新互联,wordpress通栏图片插件,关于建筑建设的网站,宿迁网站建设cy0001目录
1. 数据合并
2. 回文链表
3. 完美矩形 1. 数据合并
题目描述
将两个从小到大排列的一维数组 (维长分别为 m,n , 其中 m,n≤100) 仍按从小到大的排列顺序合并到一个新的一维数组中#xff0c;输出新的数组.
输入描述
第 1 行一个正整数 m , 表示第一个要合并的一维…
目录
1. 数据合并
2. 回文链表
3. 完美矩形 1. 数据合并
题目描述
将两个从小到大排列的一维数组 (维长分别为 m,n , 其中 m,n≤100) 仍按从小到大的排列顺序合并到一个新的一维数组中输出新的数组.
输入描述
第 1 行一个正整数 m , 表示第一个要合并的一维数组中的元素个数 第 2 行一个正整数 n , 表示第二个要合并的一维数组中的元素个数 第 3 行输入 m 个整数 (每个数用空格分开) , 表示第一个数组元素的值. 第 4 行输入 n 个整数 (每个数用空格分开) , 表示第二个数组元素的值.
输出描述
一行表示合并后的数据共 m n 个数
样例输入
3
4
1 3 5
2 4 6 8
样例输出
1 2 3 4 5 6 8
代码
#include iostream
using namespace std;void merge(int * a1, int m, int * a2, int n)
{int m1 m - 1;int n1 n - 1;for (int i m n - 1; i 0; i--){if (m1 0) a1[i] a2[n1--];else if (n1 0) a1[i] a1[m1--];else if (a1[m1] a2[n1]) a1[i] a2[n1--];else a1[i] a1[m1--];}
}int main()
{int m;int n;cin m;cin n;int a1[201];int a2[101];for (int i 0; i m; i) cin a1[i];for (int i 0; i n; i) cin a2[i];merge(a1, m, a2, n);for (int i 0; i m n; i) cout a1[i] ;return 0;
}
输入输出 3 4 1 3 5 2 4 6 8 1 2 3 4 5 6 8 -------------------------------- Process exited after 5.567 seconds with return value 0 请按任意键继续. . . 2. 回文链表
给你一个单链表的头节点 head 请你判断该链表是否为回文链表。如果是返回 true 否则返回 false 。
示例 1 输入head [1,2,2,1]
输出true示例 2 输入head [1,2]
输出false提示
链表中节点数目在范围[1, 105] 内0 Node.val 9
进阶你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题
代码
#include bits/stdc.h
using namespace std;struct ListNode
{int val;ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};class Solution
{
public:bool isPalindrome(ListNode *head){vectorint v;while (head ! NULL){v.push_back(head-val);head head-next;}for (int i 0; i v.size(); i){if (v[i] ! v[v.size() - i - 1])return false;}return true;}
};int CreateList(ListNode* p, vectorint nums)
{ListNode* q (ListNode*)malloc(sizeof(ListNode));q p;for (const auto data : nums){ListNode* temp (ListNode*)malloc(sizeof(ListNode));if (q ! NULL) {q-val data;q-next temp;q temp;}}if(q ! NULL){q-next NULL;}}void PrintList(ListNode* p)
{while(p-next ! NULL){cout p-val -;p p-next;}cout null endl;
}int main()
{Solution s;ListNode* head (ListNode*)malloc(sizeof(ListNode));vector int nums {1,2,3,2,1};CreateList(head, nums); PrintList(head);cout s.isPalindrome(head) endl;return 0;} 3. 完美矩形
我们有 N 个与坐标轴对齐的矩形, 其中 N 0, 判断它们是否能精确地覆盖一个矩形区域。
每个矩形用左下角的点和右上角的点的坐标来表示。例如 一个单位正方形可以表示为 [1,1,2,2]。 ( 左下角的点的坐标为 (1, 1) 以及右上角的点的坐标为 (2, 2) )。 示例 1:
rectangles [
[1,1,3,3],
[3,1,4,2],
[3,2,4,4],
[1,3,2,4],
[2,3,3,4]
]返回 true。5个矩形一起可以精确地覆盖一个矩形区域。 示例 2:
rectangles [
[1,1,2,3],
[1,3,2,4],
[3,1,4,2],
[3,2,4,4]
]返回 false。两个矩形之间有间隔无法覆盖成一个矩形。 示例 3:
rectangles [
[1,1,3,3],
[3,1,4,2],
[1,3,2,4],
[3,2,4,4]
]返回 false。图形顶端留有间隔无法覆盖成一个矩形。 示例 4:
rectangles [
[1,1,3,3],
[3,1,4,2],
[1,3,2,4],
[2,2,4,4]
]返回 false。因为中间有相交区域虽然形成了矩形但不是精确覆盖。
代码
#include bits/stdc.h
using namespace std;class Solution
{
public:bool isRectangleCover(vectorvectorint ret){setpairint, int s;int x1 INT_MAX, y1 INT_MAX, x2 INT_MIN, y2 INT_MIN, area 0;for (int i 0; i ret.size(); i){x1 min(ret[i][0], x1);x2 max(ret[i][2], x2);y1 min(ret[i][1], y1);y2 max(ret[i][3], y2);area (ret[i][2] - ret[i][0]) * (ret[i][3] - ret[i][1]);if (s.find({ret[i][0], ret[i][1]}) s.end())s.insert({ret[i][0], ret[i][1]});elses.erase({ret[i][0], ret[i][1]});if (s.find({ret[i][2], ret[i][3]}) s.end())s.insert({ret[i][2], ret[i][3]});elses.erase({ret[i][2], ret[i][3]});if (s.find({ret[i][0], ret[i][3]}) s.end())s.insert({ret[i][0], ret[i][3]});elses.erase({ret[i][0], ret[i][3]});if (s.find({ret[i][2], ret[i][1]}) s.end())s.insert({ret[i][2], ret[i][1]});elses.erase({ret[i][2], ret[i][1]});}if (s.size() ! 4 || !s.count({x1, y1}) || !s.count({x1, y2}) || !s.count({x2, y1}) || !s.count({x2, y2}))return false;return area (x2 - x1) * (y2 - y1);}
};int main()
{Solution s;vectorvectorint rect {{1,1,3,3},{3,1,4,2},{3,2,4,4},{1,3,2,4},{2,3,3,4}};cout s.isRectangleCover(rect) endl;rect {{1,1,2,3}, {1,3,2,4}, {3,1,4,2}, {3,2,4,4}};cout s.isRectangleCover(rect) endl;return 0;
} 附 单链表的操作
基本操作
1、单链表的初始化 2、单链表的创建 3、单链表的插入 4、单链表的删除 5、单链表的取值 6、单链表的查找 7、单链表的判空 8、单链表的求长 9、单链表的清空 10、单链表的销毁 11、单链表的打印
线性表链式存储结构的优点:
1、结点空间可以动态申请和释放 2、数据元素的逻辑次序靠结点的指针来指示插入和删除时不需要移动数据元素。
线性表链式存储结构的缺点:
1、存储密度小每个结点的指针域需额外占用存储空间。当每个结点的数据域所占字节不多时指针域所占存储空间的比重显得很大 2、链式存储结构是非随机存取结构。对任一结点的操作都要从头指针依指针链查找到该结点这增加了算法的复杂度。
以下为单链表的常用操作代码来源于网络未经测试仅供参考。
#includealgorithm
#includeiostream
#includevector
using namespace std;
struct ListNode
{int data;ListNode* next;//结构体指针
};
void Listprintf(ListNode* phead)
{ListNode* curphead;while (cur ! NULL){cout cur-data -;cur cur-next;}
}
void Listpushback(ListNode** pphead, int x)
{ListNode* newnode new ListNode{ x,NULL };if (*pphead NULL){*pphead newnode;}else{ListNode* tail *pphead;while(tail-next ! NULL){tail tail-next;}tail-next newnode;}
}
void test_1()
{ListNode* phead NULL;Listpushback(phead, 1);Listpushback(phead, 2);Listpushback(phead, 3); Listprintf(phead);
}
int main()
{test_1();return 0;
} #includealgorithm
#includeiostream
#includevector
using namespace std;
struct ListNode
{int data;ListNode* next;//结构体指针
};
void Listprintf(ListNode* phead)
{ListNode* curphead;while (cur ! NULL){cout cur-data -;cur cur-next;}cout NULL endl;
}
//尾插
void Listpushback(ListNode** pphead, int x)
{ListNode* newnode new ListNode{ x,NULL };if (*pphead NULL){*pphead newnode;}else{ListNode* tail *pphead;while(tail-next ! NULL){tail tail-next;}tail-next newnode;}
}
//头插
void Listpushfront(ListNode** pphead, int x)
{ListNode* newnode new ListNode{ x,NULL };newnode-next *pphead;*pphead newnode;
}
//尾删
void Listpopback(ListNode** pphead)
{if (*pphead NULL){return;}if ((*pphead)-next NULL){delete(*pphead);*pphead NULL;}else{ListNode* tail *pphead;ListNode* prev NULL;while (tail-next){prev tail;tail tail-next;}delete(tail);tail NULL;prev-next NULL;}
}
//头删
void Listpopfront(ListNode** pphead)
{if (*pphead NULL){return;}else{ListNode* newnode (*pphead)-next;delete(*pphead);*pphead newnode;}
}
//查找元素返回值是地址
ListNode* Listfind(ListNode* phead, int x)
{ListNode* cur phead;while (cur){if (cur-data x){return cur;}else{cur cur-next;}}return NULL;
}
//插入元素在pos的前一个位置插入
//配合Listfind使用具体使用见test_insert函数
void Listinsert(ListNode** phead, ListNode* pos, int x)
{ListNode* newnode new ListNode{ x,NULL };if (*phead pos){newnode-next (*phead);*phead newnode;}else{ListNode* posprev *phead;while (posprev-next ! pos){posprev posprev-next;}posprev-next newnode;newnode-next pos;}
}
//单链表并不适合在前一个位置插入因为运算较麻烦会损失效率
//包括c中为单链表提供的库函数也只有一个insert_after而没有前一个位置插入
//在后一个位置插入相对简单
void Listinsert_after(ListNode** phead, ListNode* pos, int x)
{ListNode* newnode new ListNode{ x,NULL };newnode-next pos-next;pos-next newnode;
}
//删除指定位置的节点
void Listerase(ListNode** pphead, ListNode* pos)
{if (*pphead pos){*pphead pos-next;delete(pos);}else{ListNode* prev *pphead;while (prev-next!pos){prev prev-next;}prev-next pos-next;delete(pos);}
}
//释放链表
void Listdestory(ListNode** pphead)
{ListNode* cur *pphead;while(cur){ListNode* next cur-next;delete(cur);cur next;}*pphead NULL;
}
void test_insert()
{ListNode* phead NULL;Listpushback(phead, 1);Listpushback(phead, 2);Listpushback(phead, 3);Listprintf(phead);ListNode* pos Listfind(phead, 2);if (pos ! NULL){Listinsert(phead, pos, 20);}Listprintf(phead);pos Listfind(phead, 2);if (pos ! NULL){Listinsert_after(phead, pos, 20);}Listprintf(phead);Listdestory(phead);
}
void test_find()
{ListNode* phead NULL;Listpushback(phead, 1);Listpushback(phead, 2);Listpushback(phead, 3);Listprintf(phead);ListNode* pos Listfind(phead, 2);if (pos ! NULL){pos-data 20;//Listfind不仅能查找也能借此修改这也是函数返回地址的原因}Listprintf(phead);Listdestory(phead);
}
void test_erase()
{ListNode* phead NULL;Listpushback(phead, 1);Listpushback(phead, 2);Listpushback(phead, 3);Listprintf(phead);ListNode* pos Listfind(phead, 2);if (pos ! NULL){Listerase(phead, pos);}Listprintf(phead);Listdestory(phead);
}
void test_pop_and_push()
{ListNode* phead NULL;Listpushback(phead, 1);Listpushback(phead, 2);Listpushback(phead, 3);Listprintf(phead);Listpushfront(phead, 1);Listpushfront(phead, 2);Listpushfront(phead, 3);Listprintf(phead);Listpopback(phead);Listpopfront(phead);Listprintf(phead);Listdestory(phead);
}
int main()
{//test_pop_and_push();test_find();//test_insert();//test_erase();return 0;
} #includealgorithm
#includeiostream
#includevector
using namespace std;
struct ListNode
{int data;ListNode* next;//结构体指针
};
void Listprintf(ListNode* phead)
{ListNode* curphead;while (cur ! NULL){cout cur-data -;cur cur-next;}cout NULL endl;
}
void Listpushback(ListNode** pphead, int x)
{ListNode* newnode new ListNode{ x,NULL };if (*pphead NULL){*pphead newnode;}else{ListNode* tail *pphead;while(tail-next ! NULL){tail tail-next;}tail-next newnode;}
}
ListNode* creatlist()
{ListNode* phead NULL;Listpushback(phead, 1);Listpushback(phead, 9);Listpushback(phead, 6);Listpushback(phead, 8);Listpushback(phead, 6);Listpushback(phead, 2);Listpushback(phead, 3);return phead;
}
ListNode* removeElements(ListNode* head, int x)
{ListNode* prev NULL;ListNode* cur head;while (cur){if (cur-data x){if (cur head)//如果第一个元素就是要删除的进行头删{head cur-next;delete(cur);cur head;}else{prev-next cur-next;delete(cur);cur prev-next;}}else{prev cur;cur cur-next;}}return head;
}
int main()
{ListNode*phead creatlist();//先创建一条链表Listprintf(phead);phead removeElements(phead, 6);//删除值为6的节点Listprintf(phead);return 0;
} ListNode* reverseList(ListNode* head)
{if (head NULL){return NULL;}ListNode* prev, * cur, * next;prev NULL;cur head;next cur-next;while (cur){cur-next prev;//翻转指针//往后迭代prev cur;cur next;if (next)//这里是因为当cur指向最后一个节点的时候next就已经是NULL了这个时候如果再执行nextnext-next则会出现错误{next next-next;}}return prev;
} ListNode* reverseList(ListNode* head)
{ListNode* cur head;ListNode* newlist NULL;ListNode* next NULL;while (cur){next cur-next;//头插cur-next newlist;newlist cur;//往后迭代cur next;}return newlist;
} ListNode* middleNode(ListNode* head)
{ListNode* slow, * fast;slow fast head;while (fast fast-next){slow slow-next;fast fast-next-next;}return slow;
} ListNode* findK(ListNode* head, int k)
{ListNode* fast, * slow;fast slow head;while(k--){if (fast NULL)//如果当fast等于NULL时k仍不为0则k大于链表长度{return NULL;}fast fast-next;}while (fast){fast fast-next;slow slow-next;}return slow;
} ListNode* mergeTwoList(ListNode* l1, ListNode* l2)
{if (l1 NULL)//如果一个链表为空则返回另一个{return l2;}if (l2 NULL){return l1;}ListNode* head NULL;ListNode* tail NULL;while (l1 l2){if (l1-data l2-data){if (head NULL){head tail l1;}else{tail-next l1;tail l1;}l1 l1-next;}else{if (head NULL){head tail l2;}else{tail-next l2;tail l2;}l2 l2-next;}}if (l1){tail-next l1;}if(l2){tail-next l2;}return head;
} ListNode* mergeTwoList(ListNode* l1, ListNode* l2)
{if (l1 NULL)//如果一个链表为空则返回另一个{return l2;}if (l2 NULL){return l1;}ListNode* head NULL, * tail NULL;head tail new ListNode;//哨兵位的头结点while (l1 l2){if (l1-data l2-data){tail-next l1;tail l1;l1 l1-next;}else{tail-next l2;tail l2;l2 l2-next;}}if (l1){tail-next l1;}if (l2){tail-next l2;}ListNode* list head-next;delete(head);return list;
} ListNode* partition(ListNode* phead, int x)
{ListNode* lesshead, * lesstail, * greaterhead, * greatertail;lesshead lesstail new ListNode;//定义一个哨兵位头结点方便尾插lesstail-next NULL;greaterhead greatertail new ListNode;greatertail-next NULL;ListNode* cur phead;while (cur){if (cur-data x){lesstail-next cur;lesstail cur;}else{greatertail-next cur;greatertail cur;}cur cur-next;}lesstail-next greaterhead-next;greatertail-next NULL;//举个例子这样一条链表:1-4-15-5,现在给的x是6那么排序后15应该在最后正因如此重新排序后15的next是没变的仍然指向5不手动将next改为NULL就会成环无限排下去。ListNode* newhead lesshead-next;delete(lesshead);delete(greaterhead);return newhead;
} ListNode* middleNode(ListNode* head)
{ListNode* slow, * fast;slow fast head;while (fast fast-next){slow slow-next;fast fast-next-next;}return slow;
}
ListNode* reverseList(ListNode* head)
{ListNode* cur head;ListNode* newlist NULL;ListNode* next NULL;while (cur){next cur-next;//头插cur-next newlist;newlist cur;//往后迭代cur next;}return newlist;
}
bool check(ListNode* head)
{ListNode* mid middleNode(head);ListNode* rhead reverseList(mid);ListNode* curHead head;ListNode* curRhead rhead;while(curHeadcurRhead){if (curHead-data ! curRhead-data)return false;else{curHead curHead-next;curRhead curRhead-next;}}return true;
}
