?重新排列数组
?
给出一个数组 nums，数组中一共有 2n 个元素，分为两段，第一段是 x1 ~ xn，第二段是 y1 ~ yn
需要把它重新排列为[x1,y1,x2,y2,...,xn,yn]
示例1：
2、5、1、3、4、7??????? n = 3
开一个新的数组用来记录最终答案，从 0 ~ n - 1 去遍历一遍，每次把当前循环变量指向的这个数放到数组的最后一个位置，再把它后面的和它配对的一个数(当前指针 + n 的位置上的数) 放在后面，最后把指针往后移动一位. . .
时间复杂度 O( n )，n 的范围为 500
?
class Solution {
public:
vector<int> shuffle(vector<int>& nums, int n) {
//定义答案数组
vector<int> res;
//从 0 ~ n 循环一遍
for(int i = 0;i < n;i++ ) {
//每次把当前第 i 个数放进来
res.push_back(nums[i]);
//把 i + n 位置上的数放进来
res.push_back(nums[i + n]);
}
return res;
}
};数组中的 k 个最强值
给出一个数组和一个整数 k，定义了数组中两个元素比较大小的方式：先求数组里面的中位数，假设中位数是 m，按照如下方式来比较两个变量的大小，如果|arr[i] - m| != |arr[j]?- m|，绝对值大的那个更好，如果|arr[i] - m| == |arr[j]?- m|，数值大的那个更好，返回由数组中最强的 k 个值组成的列表
任何两个元素之间都可以作比较
需要排序
数据范围为 10^5，时间复杂度要控制在 nlogN
中位数的定义：
如果是奇数个数，中位数一定是最中间这个数，如果是偶数个数，中位数是中间偏左的那个数
在 sort 函数中传入自定义的比较方式
输入的数组不一定是有序的，想求中位数的话需要先给它排序
注意 Lambda 表达式中间不能写变量，可以加引用 &
int m;
bool cmp(int a,int b) {
if(abs(a - m) != abs(b - m)) return abs(a - m) > abs(b - m);
return a > b;
}
class Solution {
public:
vector<int> getStrongest(vector<int>& arr, int k) {
sort(arr.begin(),arr.end());
m = arr[(arr.size() - 1) / 2];
sort(arr.begin(),arr.end(),cmp);
return vector<int>({arr.begin(),arr.begin() + k});
}
};class Solution {
public:
vector<int> getStrongest(vector<int>& arr, int k) {
sort(arr.begin(),arr.end());
//中位数用 m 表示
int m = arr[(arr.size() - 1) / 2];
//自定义比较函数
sort(arr.begin(),arr.end(),[&](int a,int b) {
//绝对值的大小关系 绝对值大的靠前
if(abs(a - m) != abs(b - m)) return abs(a - m) > abs(b - m);
//否则数字大的那个数更大
return a > b;
});
//返回前 k 个元素
return vector<int>({arr.begin(),arr.begin() + k});
}
};设计浏览器历史记录
实现一个类，需要维护游览器的历史记录，一共有三种操作：进到某个新页面，退回到某个页面，前进到某个页面，要求实现这三个操作，最开始在根目录 homepage
注意：从当前页跳转访问 url 对应的页面，执行此操作会把浏览历史前进的记录全部删除，一开始前进 n 步，然后回退 n 步，如果在后退中的某一步( m < n ) 跳到了某一个新的页面：会先把之前 前进跳进去的所有页面 (当前后退步骤后面的所有页面) 全部删除，再跳到新的页面，再回退 1 步，前进 1 步，就会发现前进到的页面是新的页面
示例1：
根目录是 LeetCode，先访问 Google，再访问 Facebook，再访问 YouTube，回退一步输出 Facebook，再回退一步输出 Google，再前进一步输出 Facebook，从 Facebook 访问新的页面 LinkedIn：会把 Facebook→ YouTube 的分支删除，重新连接到 LinkedIn，再前进一步，由于后面没有页面就把前进当作没有发生过，所以从 LinkedIn 再前进的话 前进不了，还是 LinkedIn，输出 LinkedIn，再回退两格，退到 Google，输出 Google，再回退两格，没有得退了，还是 LeetCode，输出 LeetCode. . .
维护一个 vector，每个元素最多只会被插入一次，删除一次，时间复杂度 O( 1 )，整个算法时间复杂度 O( n )
class BrowserHistory {
public:
vector<string> records;
//记录当前位置
int cur;
BrowserHistory(string homepage) {
//一开始是一个空的 vector 将homepage 插到vector 中
records.push_back(homepage);
cur = 0;
}
void visit(string url) {
//如果访问一个新页面 需要把当前位置后面的元素都删除
records.erase(records.begin() + cur + 1,records.end());
//在最后插入一个新的页面
records.push_back(url);
//将当前位置移到下一个位置
cur ++;
}
string back(int steps) {
//如果要退回一个页面 从当前位置移到前一个位置 最多退到 0
cur = max(0,cur - steps);
return records[cur];
}
string forward(int steps) {
//如果要往后跳一个页面 从当前位置往后跳到下个页面 最多前进到 (int)records.size() - 1
cur = min((int)records.size() - 1,cur + steps);
return records[cur];
}
};
/**
* Your BrowserHistory object will be instantiated and called as such:
* BrowserHistory* obj = new BrowserHistory(homepage);
* obj->visit(url);
* string param_2 = obj->back(steps);
* string param_3 = obj->forward(steps);
*/粉刷房子 III
