混战极限一换一，不同的两者一旦遇见就同归于尽，最后活下来的值都是相同的，即要求的结果。
int majorityElement(int* nums, int numsSize){
int res,cnt;
res = cnt = 0;
for ( int i=0; i<numsSize; i++ ){
if ( cnt==0 ){
res = nums[i];
cnt++;
}else{
if ( res==nums[i] )
cnt++;
else
cnt--;
}
}
return res;
} 快速排序中有一步很重要的操作是 partition（划分），从数组中随机选取一个枢纽元素 v，然后原地移动数组中的元素，使得比 v 小的元素在 v 的左边，比 v 大的元素在 v 的右边。如图所示：
我们的目的是寻找最小的 k 个数。假设经过一次 partition 操作，枢纽元素位于下标 m，也就是说，左侧的数组有 m 个元素，是原数组中最小的 m 个数。那么：
- 若 k = m，我们就找到了最小的 k 个数，就是左侧的数组；
- 若 k<m ，则最小的 k 个数一定都在左侧数组中，我们只需要对左侧数组递归地 partition 即可；
- 若 k>m，则左侧数组中的 m 个数都属于最小的 k 个数，我们还需要在右侧数组中寻找最小的 k-m 个数，对右侧数组递归地 partition 即可。
void swap (int* a, int* b);
int partition (int* arr, int st, int end);
int* quickSort (int* arr, int k, int st, int end);
int* getLeastNumbers (int* arr, int arrSize, int k, int* returnSize);
int* getLeastNumbers (int* arr, int arrSize, int k, int* returnSize) {
int* ans = (int*) malloc (sizeof (int) * 10000);
*returnSize = k;
if (k == 0) {
return ans;
}
return quickSort (arr, k, 0, arrSize-1);
}
int* quickSort (int* arr, int k, int st, int end) {
if ( st>=end ){
return arr;
}
int m = partition (arr, st, end);
if ( m==k ) {
return arr;
} else if ( m>k ) {
return quickSort (arr, k, st, m-1);
} else {
return quickSort (arr, k, m+1, end);
}
}
void swap (int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
int partition (int* arr, int st, int end) {
int pivot = arr[st];
int i, j;
i = st;
j = end;
while (i < j) {
//从右开始
while (i<j && arr[j]>=pivot)
j--;
while (i<j && arr[i]<=pivot)
i++;
swap (&arr[i], &arr[j]);
}
swap (&arr[i], &arr[st]);
return i;
} 维护一个大根堆和一个小根堆，小根堆保存较大的数，大根堆保存较小的数。如此，若总数为奇数，则中位数为小根堆顶元素；若总数为偶数，则中位数为小根堆顶和大根堆顶的平均数。
加入新元素时， 用 **两个堆中元素的个数是否相等 判断 加入哪个堆。**若相等，加入小根堆；若不等，加入大根堆。**加入方式是，先入另一个堆，再把另一个堆的堆顶元素加入该堆。**目的是为了保证，小根堆保存较大的数，大根堆保存较小的数。
class MedianFinder {
public:
/** initialize your data structure here. */
priority_queue<int, vector<int>, less<int>> maxHeap;
priority_queue<int, vector<int>, greater<int>> minHeap;
MedianFinder() {
}
void addNum(int num) {
if ( maxHeap.size()==minHeap.size() ){
maxHeap.push(num);
int top = maxHeap.top();
maxHeap.pop();
minHeap.push(top);
}else{
minHeap.push(num);
int top = minHeap.top();
minHeap.pop();
maxHeap.push(top);
}
}
double findMedian() {
int m = minHeap.size();
int n = maxHeap.size();
if ( m==n ){
return (minHeap.top() + maxHeap.top())*1.0 / 2;
}else{
return minHeap.top();
}
}
}; 将待排列数组，划分为左右两部分，左边为已排列，右边为待排列。first 指向下一个要填的位置。将待填写的数与 first 交换，使 [0,first] 排列完成，继续递归填写下一个数，详细见实现代码。
class Solution {
public:
void backtrack(vector<vector<int>>& res, vector<int>& output, int first, int len){
// 所有数都填完了
if (first == len) {
res.emplace_back(output);
return;
}
for (int i = first; i < len; ++i) {
// 动态维护数组
swap(output[i], output[first]);
// 继续递归填下一个数
backtrack(res, output, first + 1, len);
// 撤销操作
swap(output[i], output[first]);
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int> > res;
backtrack(res, nums, 0, (int)nums.size());
return res;
}
}; 回溯。实现 nums 数组中 k 个数的组合排列。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void myPrint (vector<int> v, int k);
void backTrace (vector<int> nums, int k, int cur, vector<int> path);
int cnt = 0;
int main () {
int n, k;
cin >> n >> k;
vector<int> nums;
vector<int> path;
for ( int i=0; i<n; i++ ) {
int a;
cin >> a;
nums.push_back (a);
}
backTrace (nums, k, 0, path);
cout << cnt << endl;
return 0;
}
void backTrace (vector<int> nums, int k, int cur, vector<int> path) {
//cur == next num
int len = path.size ();
for ( int i=0; i<len&&len>1; i++ ) {
if ( abs(path[i]-path[len-1])>d )
return;
}
if ( len==k ) {
myPrint (path,k);
return;
}
for ( int i=cur; i<nums.size(); i++ ) {
path.push_back (nums[i]);
backTrace (nums, k, i+1, path);
path.pop_back ();
}
}
void myPrint ( vector<int> v, int k ) {
for ( int i=0; i<k; i++ )
cout << v[i] << " ";
cout << endl;
} 例题：LeetCode 322.零钱兑换
动态规划分为以下四个步骤：
-
最后一步
即，最优策略的最后一个步骤
-
转化为子问题
即规模更小的问题
根据最后一步转化的子问题，写出转移方程f[x] = ?
确认初始的 f[0] 等。
正确处理数组越界。
确定是从前往后计算，还是从后往前计算。确定的标准是，计算 f[x] 时，所用到的值是否已经计算完成。
dp[i] 为以下标 i 为结尾的连续子数组的最大和。则，dp[i] = max (dp[i-1]+nums[i], nums[i]);。最终所求的即 dp 数组中的最大值。
int maxSubArray(vector<int>& nums) {
int len = nums.size();
int dp[len];
dp[0] = nums[0];
int maxSub = dp[0];
for ( int i=1; i<len; i++ ){
dp[i] = max(dp[i-1]+nums[i], nums[i]);
if ( maxSub<dp[i] )
maxSub = dp[i];
}
return maxSub;
}priority_queue<Type, Container, Functional>;
//小根堆
priority_queue<int, vector<int>, greater<int>> q;
//大根堆
priority_queue<int, vector<int>, less<int>> q;include <queue>
- top 访问队头元素
- empty 队列是否为空
- size 返回队列内元素个数
- push 插入元素到队尾 (并排序)
- emplace 原地构造一个元素并插入队列
- pop 弹出队头元素
- swap 交换内容
sort(arr.begin(), arr.end());
vector<vector<int>> array (n); //n行
cout << array.size () << endl;
for ( int i=0; i<5; i++ ) {
array[i].resize (m); //m列
}
array[2][2] = 99; //赋值vector<vector<int>> vec(row, vector<int> (col,0));
返回大于或等于 x 的最小的整数值
头文件：#include <math>
用法：double ceil (double x)
将数值转化为字符串，并返回对应字符串
头文件：#include <string>
用法：str = to_string(3.14);
C++ 11 新标准
-
根据初始化表达式，自动判断被声明变量的类型
vector<int> vect; for ( auto it=vect.begin(); it!=vect.end(); it++ ) cout << *it << endl; //it的类型是 vector<int>::iterator
-
用 auto 声明的变量必须初始化
-
不能和其他类型组合连用
-
函数和模板参数不能被声明为 auto
-
auto 是一个占位符，而不是一个数据类型，因此不能用于类型转换和其他类似的操作，如 sizeof、typeid
-
定义在一个 auto 序列的变量，必须推导成同一类型
将小写字母转换为大写字母
头文件：#include <ctype>
用法：char c = toupper('g');
string s ("hello");
for ( auto &c: s )
c = toupper (c);
cout << s;**注意：**冒号前的部分，为用来遍历的变量，若要修改容器内的值，需要加上 &；冒号后的部分，为将被遍历的范围。
在范围 for 中需要修改容器中的值，若不通过引用遍历，则遍历的是元素的拷贝，并每次拷贝都需要调用该元素类型的copy constructor。而使用 &，是为了保证原始的元素被使用。
默认升序排序
头文件：#include <algorithm>
用法：sort( v.begin(), v.end() );
自定义排序：
sort( str.begin(), str.end(), cmp );
static bool cmp ( const string& a, const string& b ){
return a+b < b+a;
}头文件：#include <limits.h>
此头文件还包含 INT_MIN 等各类型的最值