LeetCode14701473

 重新排列数组

给出一个数组 nums&＃xff0c;数组中一共有 2n 个元素&＃xff0c;分为两段&＃xff0c;第一段是 x1 ~ xn&＃xff0c;第二段是 y1 ~ yn

需要把它重新排列为[x1,y1,x2,y2,...,xn,yn]

示例1&＃xff1a;

2、5、1、3、4、7        n &＃61; 3

开一个新的数组用来记录最终答案&＃xff0c;从 0 ~ n - 1 去遍历一遍&＃xff0c;每次把当前循环变量指向的这个数放到数组的最后一个位置&＃xff0c;再把它后面的和它配对的一个数(当前指针 &＃43; n 的位置上的数) 放在后面&＃xff0c;最后把指针往后移动一位. . .

时间复杂度 O( n )&＃xff0c;n 的范围为 500

class Solution {
public:vector shuffle(vector& nums, int n) {//定义答案数组vector res;//从 0 ~ n 循环一遍for(int i &＃61; 0;i };

数组中的 k 个最强值

给出一个数组和一个整数 k&＃xff0c;定义了数组中两个元素比较大小的方式&＃xff1a;先求数组里面的中位数&＃xff0c;假设中位数是 m&＃xff0c;按照如下方式来比较两个变量的大小&＃xff0c;如果|arr[i] - m| !&＃61; |arr[j] - m|&＃xff0c;绝对值大的那个更好&＃xff0c;如果|arr[i] - m| &＃61;&＃61; |arr[j] - m|&＃xff0c;数值大的那个更好&＃xff0c;返回由数组中最强的 k 个值组成的列表

任何两个元素之间都可以作比较

需要排序

数据范围为 10^5&＃xff0c;时间复杂度要控制在 nlogN

中位数的定义&＃xff1a;

如果是奇数个数&＃xff0c;中位数一定是最中间这个数&＃xff0c;如果是偶数个数&＃xff0c;中位数是中间偏左的那个数

在 sort 函数中传入自定义的比较方式

输入的数组不一定是有序的&＃xff0c;想求中位数的话需要先给它排序

注意 Lambda 表达式中间不能写变量&＃xff0c;可以加引用 &

int m;
bool cmp(int a,int b) {if(abs(a - m) !&＃61; abs(b - m)) return abs(a - m) > abs(b - m);return a > b;
}
class Solution {
public:vector getStrongest(vector& arr, int k) {sort(arr.begin(),arr.end());m &＃61; arr[(arr.size() - 1) / 2];sort(arr.begin(),arr.end(),cmp);return vector({arr.begin(),arr.begin() &＃43; k});}
};

class Solution {
public:vector getStrongest(vector& arr, int k) {sort(arr.begin(),arr.end());//中位数用 m 表示int m &＃61; arr[(arr.size() - 1) / 2];//自定义比较函数sort(arr.begin(),arr.end(),[&](int a,int b) {//绝对值的大小关系 绝对值大的靠前if(abs(a - m) !&＃61; abs(b - m)) return abs(a - m) > abs(b - m);//否则数字大的那个数更大return a > b;});//返回前 k 个元素return vector({arr.begin(),arr.begin() &＃43; k});}
};

设计浏览器历史记录

实现一个类&＃xff0c;需要维护游览器的历史记录&＃xff0c;一共有三种操作&＃xff1a;进到某个新页面&＃xff0c;退回到某个页面&＃xff0c;前进到某个页面&＃xff0c;要求实现这三个操作&＃xff0c;最开始在根目录 homepage

注意&＃xff1a;从当前页跳转访问 url 对应的页面&＃xff0c;执行此操作会把浏览历史前进的记录全部删除&＃xff0c;一开始前进 n 步&＃xff0c;然后回退 n 步&＃xff0c;如果在后退中的某一步( m 前进跳进去的所有页面 (当前后退步骤后面的所有页面) 全部删除&＃xff0c;再跳到新的页面&＃xff0c;再回退 1 步&＃xff0c;前进 1 步&＃xff0c;就会发现前进到的页面是新的页面

示例1&＃xff1a;

根目录是 LeetCode&＃xff0c;先访问 Google&＃xff0c;再访问 Facebook&＃xff0c;再访问 YouTube&＃xff0c;回退一步输出 Facebook&＃xff0c;再回退一步输出 Google&＃xff0c;再前进一步输出 Facebook&＃xff0c;从 Facebook 访问新的页面 LinkedIn&＃xff1a;会把 Facebook→ YouTube 的分支删除&＃xff0c;重新连接到 LinkedIn&＃xff0c;再前进一步&＃xff0c;由于后面没有页面就把前进当作没有发生过&＃xff0c;所以从 LinkedIn 再前进的话 前进不了&＃xff0c;还是 LinkedIn&＃xff0c;输出 LinkedIn&＃xff0c;再回退两格&＃xff0c;退到 Google&＃xff0c;输出 Google&＃xff0c;再回退两格&＃xff0c;没有得退了&＃xff0c;还是 LeetCode&＃xff0c;输出 LeetCode. . .

维护一个 vector&＃xff0c;每个元素最多只会被插入一次&＃xff0c;删除一次&＃xff0c;时间复杂度 O( 1 )&＃xff0c;整个算法时间复杂度 O( n )

class BrowserHistory {
public:vector records;//记录当前位置int cur;BrowserHistory(string homepage) {//一开始是一个空的 vector 将homepage 插到vector 中records.push_back(homepage);cur &＃61; 0;}void visit(string url) {//如果访问一个新页面 需要把当前位置后面的元素都删除records.erase(records.begin() &＃43; cur &＃43; 1,records.end());//在最后插入一个新的页面records.push_back(url);//将当前位置移到下一个位置cur &＃43;&＃43;;}string back(int steps) {//如果要退回一个页面 从当前位置移到前一个位置 最多退到 0 cur &＃61; max(0,cur - steps);return records[cur];}string forward(int steps) {//如果要往后跳一个页面 从当前位置往后跳到下个页面 最多前进到 (int)records.size() - 1cur &＃61; min((int)records.size() - 1,cur &＃43; steps);return records[cur];}
};/*** Your BrowserHistory object will be instantiated and called as such:* BrowserHistory* obj &＃61; new BrowserHistory(homepage);* obj->visit(url);* string param_2 &＃61; obj->back(steps);* string param_3 &＃61; obj->forward(steps);*/

粉刷房子 III