1. 链表
给定链表{1 2 3 4 5}
头节点不变，2插在1后面，3插在1前面。往复循环
返回新链表 {5 3 1 2 4}
这个题不能用deque，会超时，需要原地修改
class Solution
{
public:
ListNode* newhead;
ListNode* tail;
ListNode *formatList(ListNode *head)
{
newhead = head;
tail = head;
int index = 1;
head = head->next;
tail->next=nullptr;
// write code here
while(head){
if (index & 1){
tail->next = head;
tail = head;
head = head->next;
tail->next=nullptr;
}
else{
auto tmp = head->next;
head->next = newhead;
newhead = head;
head = tmp;
}
index++;
}
return newhead;
}
};2. 统计满足条件的数组元素对数量
给定数组arr和int k
求时，的数量
这个题由于只让求ij对的数量，因此对ij的顺序没啥要求。所以可以先排序，再找组合。因为数组元素确定，其实数组中元素对的数目是跟排序没有关系的
暴力算法会超时，排序后二分查找就可以了
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param array int整型vector
* @param k int整型
* @return long长整型
*/
long long ans(vector<int>& array, int k) {
// write code here
long long count = 0;
int n = array.size();
sort(array.begin(), array.end());
int i = 0, j = n - 1;
while(j > 0)
{
auto tmp = lower_bound(array.begin(), array.begin() + j, k - array[j]);
if (*tmp == k - array[j]){
count += tmp - array.begin() + 1;
}
else{
count += tmp - array.begin();
}
j--;
}
return count;
}
};3. 分割环形数组
给定一个数组arr，求分割后，两边和的差的最小值
[1 2 3 4 5]分割为[3 4] 和 [1 2 5]
参考树状数组的思路，通过前缀和找到可能的最小位置
虽然ac了，但是个人感觉这段代码在index为0或1的时候可能会有一点问题
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param a int整型vector
* @return long长整型
*/
long long minimum(vector<int>& a) {
// write code here
int n = a.size();
long long minSub = INT64_MAX;
vector<long long> pre(n, a[0]); // 前缀和数组
for (int i = 1; i < n; i++)
{
pre[i] = pre[i - 1] + a[i];
}
long long sumAll = pre[n - 1];
long long halfSum = sumAll & 1 ? sumAll / 2 + 1 : sumAll / 2;
for (int i = n - 1; i > 0; i--)
{
auto tmp = lower_bound(pre.begin(), pre.begin() + i, pre[i] - halfSum);
auto halfcurrent1 = pre[i] - *tmp;
auto halfcurrent2 = pre[i] - *(tmp - 1);
auto subCurrent1 = abs(sumAll - (halfcurrent1 << 1));
auto subCurrent2 = abs(sumAll - (halfcurrent2 << 1));
minSub = min(minSub, subCurrent1);
minSub = min(minSub, subCurrent2);
}
minSub = min(minSub, abs(sumAll - a[0] - a[0]));
return minSub;
}
};评论 (15)
