引言
707. 设计链表 – 力扣（LeetCode）
206. 反转链表 – 力扣（LeetCode）
209. 长度最小的子数组 – 力扣（LeetCode）
59. 螺旋矩阵 II – 力扣（LeetCode）
在一个城市区域内，被划分成了n * m个连续的区块，每个区块都拥有不同的权值，代表着其土地价值。目前，有两家开发公司，A 公司和 B 公司，希望购买这个城市区域的土地。
现在，需要将这个城市区域的所有区块分配给 A 公司和 B 公司。
然而，由于城市规划的限制，只允许将区域按横向或纵向划分成两个子区域，而且每个子区域都必须包含一个或多个区块。
为了确保公平竞争，你需要找到一种分配方式，使得 A 公司和 B 公司各自的子区域内的土地总价值之差最小。
第一题
这一题就是设计链表，但是里面有很多细节是我们平时手搓链表的时候根本不会考虑的，这个一定要好好思考。
首先第一个就是我们在使用双链表的时候，我们从哪里开始找元素，如果这个元素离头更近，就从头开始找，反之就是尾
第二个就是我们应该遍历到哪里停止。对于增加元素，比如index = 4，那么我们需要遍历到index=3和index=4，然后对3和4之间进行插入操作。而删除元素，我们就应该遍历到index=3和index=5，所以一定要注意遍历的范围
最后，题目中还有一个坑就是index也是从0开始计数的，和数组是一样的。
struct Node{
int val;
Node* pre;
Node* next;
Node(int val) : val(val), pre(nullptr), next(nullptr) {}
};
class MyLinkedList {
public:
MyLinkedList() {
size = 0;
dummyHead = new Node(0);
dummyTail = new Node(0);
dummyHead->next = dummyTail;
dummyTail->pre = dummyHead;
}
int get(int index) {
if(index < 0 || index >= size) {
return -1;
}
Node* cur = nullptr;
if(index + 1 < size – index) { // 离头更近一些
cur = dummyHead;
for(int i = 0; i <= index; i++) {
cur = cur->next;
}
} else {
cur = dummyTail;
for(int i = 0; i < size – index; i++) {
cur = cur->pre;
}
}
return cur->val;
}
void addAtHead(int val) {
addAtIndex(0, val);
}
void addAtTail(int val) {
addAtIndex(size, val);
}
void addAtIndex(int index, int val) {
if(index > size) {
return;
}
index = max(0, index);
Node* p; // 前面一个指针
Node* t; // 后面一个指针
if(index < size – index) {
p = dummyHead;
for(int i = 0; i < index; i++) { // 要找到我们插入结点的前面一个结点
p = p->next;
}
t = p->next;
} else {
t = dummyTail;
for(int i = 0; i < size – index; i++) {
t = t->pre;
}
p = t->pre;
}
size++;
Node* newNode = new Node(val);
p->next = newNode;
newNode->pre = p;
newNode->next = t;
t->pre = newNode;
}
void deleteAtIndex(int index) {
if(index < 0 || index >= size) {
return;
}
Node* p;
Node* t;
if(index < size – index) {
p = dummyHead;
for(int i = 0; i < index; i++) {
p = p->next;
}
t = p->next->next;
} else {
t = dummyTail;
for(int i = 0; i < size – index – 1; i++) {
t = t->pre;
}
p = t->pre->pre;
}
size–;
Node* oldNode = p->next;
t->pre = p;
p->next = t;
delete oldNode;
}
private:
int size;
Node* dummyHead;
Node* dummyTail;
};
/**
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList* obj = new MyLinkedList();
* int param_1 = obj->get(index);
* obj->addAtHead(val);
* obj->addAtTail(val);
* obj->addAtIndex(index,val);
* obj->deleteAtIndex(index);
*/
第二题
这一题是非常经典的反转链表，我们一般思路是开辟一个新的链表，但是这样太耗费空间，我们可以直接在链表上操作。反转链表实际上就是改变头节点，然后把指针反过来的过程，这个过程完全可以用双指针来实现。p指向pre，不过要记得用temp稍微保存一下p的下一个结点，不然到时候找不到了
/**
* 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* reverseList(ListNode* head) {
ListNode* p = head;
ListNode* pre = nullptr;
while(p != nullptr) {
ListNode* temp = p->next;
p->next = pre;
pre = p;
p = temp;
}
return pre;
}
};
第三题
这一题的本质是滑动窗口。顾名思义，滑动窗口的本质就是求一段长度，所以我们就拿着头指针和尾指针把这一段数组包围起来。我们首先写一个for（int j）循环，但是这个for循环里的变量是什么呢？表示的是尾指针。因为如果移动的是头指针，那么就应该是两段for循环了，那就变成暴力搜索了，而尾指针的话只有一个for循环，至于头指针怎么移动，我们可以在for循环里面写一个while（）循环。
可能大家会有疑问，为什么不是if，而是while，因为while的目的就是找到刚刚不满则sum >= target的那个数，因为我们不知道有一个数，所以我们需要用while循环。然后更新res的数据地方是在while（）的外面，因为我们走出了while循环，得到的那个下表是sum < target的，不满足题目的要求。
所以滑动窗口就是用for循环移动尾指针，在for（）循环里面去根据题目移动头指针
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int res = INT_MAX;
int sum = 0;
int i = 0;
for(int j = 0; j < nums.size(); j++) {
int subL = 0;
sum += nums[j];
while(sum >= target) {
subL = j – i + 1;
res = min(res, subL);
sum -= nums[i];
i++;
}
}
if(res == INT_MAX) {
return 0;
} else {
return res;
}
}
};
第四题
这一题的主要麻烦就是边界条件限制的实在是太多，导致很有可能在细节上出现问题。首先，我们模拟顺时针遍历的特点，然后一定要遵循一定的规律去遍历这个数组，我们这里采取的是左闭右开的规则，所以每一次for（）循环里面接没有等于号。然后loop是循环的圈数，最后注意一下，因为如果n是奇数的话，最里面那个数是不会被计算到的，因为毕竟我们选择的是左闭右开，左边的区间和右边的区间如果重合的话，那个数我们是取不到的。
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
int left = 0;
int right = n – 1;
int top = 0;
int botton = n – 1;
int count = 1;
int mid = n / 2;
int size = n;
int loop = n / 2;
vector<vector<int>> nums(n, vector<int> (n, 0));
while(loop–) {
for(int i = left; i < right; i++) {
nums[top][i] = count++;
}
for(int i = top; i < botton; i++) {
nums[i][right] = count++;
}
for(int i = right; i > left; i–) {
nums[botton][i] = count++;
}
for(int i = botton; i > top; i–) {
nums[i][left] = count++;
}
left++;
top++;
right–;
botton–;
}
if(size % 2 == 0) {
return nums;
} else {
nums[mid][mid] = count;
return nums;
}
}
};
第五题
这一题用的是前缀和，然后题目的要求是只能画一条线，所以我们需要收集水平和竖直两个方向的前缀和，然后进行一一的比较。这一题大家可能有的会去使用二维的前缀和，但是其实没有这个方法方便，所以还是要多多审题
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
int sum = 0;
vector<vector<int>> nums(n, vector<int>(m, 0));
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
cin >> nums[i][j];
sum += nums[i][j];
}
}
vector<int> horizonal(n, 0);
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
horizonal[i] += nums[i][j];
}
}
vector<int> vertical(m, 0);
for(int j = 0; j < m; j++) {
for(int i = 0; i < n; i++) {
vertical[j] += nums[i][j];
}
}
int horizonalSum = 0;
int verticalSum = 0;
int res = INT_MAX;
for(int i = 0; i < n; i++) {
horizonalSum += horizonal[i];
res = min(res, abs(sum – horizonalSum – horizonalSum));
}
for(int i = 0; i < m; i++) {
verticalSum += vertical[i];
res = min(res, abs(sum – verticalSum – verticalSum));
}
cout << res << endl;
return 0;
}
总结
数组的故事到这里就基本结束了，不过双指针这个方法在以后我们还会依然的遇到。数组的主要困难不是在实现，而是在于怎么样压缩时间和空间的复杂度。
感谢大家的阅读！！！希望可以帮助大家更好的理解~~~
