// ConsoleApplication1.cpp : 定义控制台应用程序的入口点。
// #include "stdafx.h"
#include <Windows.h>
#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <numeric> using namespace std;
void show(const vector<int>& nums){
for (int i = ; i < nums.size(); i++){
cout << '\t' << nums[i];
}
cout << endl;
} int removeDuplicate(vector<int>& nums){
if (nums.empty()) return ;
int index = ;
for (int i = ; i < nums.size(); i++){
if (nums[i - ] != nums[i])
nums[index++] = nums[i];
}
return index;
} vector<int> twoSum(vector<int>& nums, int target){
unordered_map<int, int> mapping;
vector<int> res;
for (int i = ; i < nums.size(); i++)
mapping[nums[i]] = i;
for (int i = ; i < nums.size(); i++){
int gap = target - nums[i];
if (mapping.find(gap) != mapping.end()){
res.push_back(i + );
res.push_back(mapping.find(gap)->second + );
break;
}
}
return res;
} vector<vector<int>> threeSum(vector<int>& nums){
vector<vector<int>> result;
const int target = ;
if (nums.size() < ) return result;
sort(nums.begin(), nums.end());
auto last = nums.end();
for (auto i = nums.begin(); i < last - ; ++i){
while (i>nums.begin() && *i == *(i - )) continue;
auto j = i + ;
auto k = last - ;
while (j < k){
if (*i + *j + *k < target) {
++j;
while (*j == *(j - ) && j < k) ++j;
}
else if (*i + *j + *k > target){
--k;
while (*k == *(k + ) && j < k) --k;
}
else{
result.push_back({ *i, *j, *k });
++j;
--k;
while (*j == *(j - ) && *k == *(k + ) && j < k) ++j;
}
}
}
return result;
} int threeSumClose(vector<int>& nums, int target){
int result = ;
int min_gap = INT_MAX;
sort(nums.begin(), nums.end());
auto last = nums.end();
for (auto i = nums.begin(); i < last - ; ++i){
auto k = last - ;
auto j = i + ;
while (j < k){
int sum = *i + *j + *k;
int gap = abs(sum - target);
if (gap < min_gap){
min_gap = gap;
result = sum;
}
if (sum < target) ++j;
else --k;
}
}
return result;
} void next_Permutation(vector<int>& nums){
int i, j, k = nums.size();
for (i = k - ; i >= ; i--){
if (nums[i] < nums[i + ]){
for (j = k - ; j > i; j--){
if (nums[j] > nums[i])
break;
}
swap(nums[i], nums[j]);
reverse(nums.begin() + i + , nums.end());
return;
}
}
reverse(nums.begin(), nums.end());
} int trap_Water(vector<int>& hights){
int result = ;
int l = , r = hights.size() - ;
while (l < r){
int mn = min(hights[l], hights[r]);
if (mn == hights[l]){
++l;
while (mn > hights[l] && l < r)
result += mn - hights[l++];
}
else{
--r;
while (mn > hights[r] && l < r)
result += mn - hights[r--];
}
}
return result;
} int trap_WaterII(vector<int>& heights) {
vector<int> dpLeft(heights.size(), );
int maxLeft = ;
for (int i = ; i<heights.size(); ++i){
dpLeft[i] = maxLeft;
maxLeft = max(heights[i], maxLeft);
}
show(dpLeft);
int maxRight = ;
vector<int> dpRight(heights.size(), );
for (int j = heights.size() - ; j >= ; --j){
dpRight[j] = maxRight;
maxRight = max(heights[j], maxRight);
}
show(dpRight);
int result = ;
for (int k = ; k<heights.size(); ++k){
int minDiff = min(dpLeft[k], dpRight[k]);
if (minDiff > heights[k])
result += minDiff - heights[k];
}
return result;
} void rotate(vector<vector<int>>& matrix) {
const int n = matrix.size(); //matrix 的行数
for (int i = ; i < n;++i)
for (int j = ; j < n - i; ++j)
swap(matrix[i][j], matrix[n - - i][n - - j]); // 副对角线反转 for (int i = ; i < n / ;++i)
for (int j = ; j < n; ++j)
swap(matrix[i][j], matrix[n - - i][j]);//水平中线反转
} vector<int> plusOne(vector<int>& digits){
int c = ;//表示进位 carry
for (auto it = digits.rbegin(); it != digits.rend(); ++it){
*it += c;
c = *it / ;
*it = *it % ;
}
if (c > ) digits.insert(digits.begin(), );
return digits;
} int climbStairs(int n){ //迭代
int pre = ;
int cur = ;
for (int i = ; i <= n; i++){
int tmp = cur;
cur += pre;
pre = tmp;
}
return cur;
} vector<int> grayCode(int n){
int size = << n; //2^n
vector<int> result;
result.reserve(size);
for (int i = ; i < size; ++i)
result.push_back(i ^ (i >> ));
return result;
} void setZeroes(vector<vector<int>>& matrix){
const int rows = matrix.size();
const int columns = matrix[].size();
vector<bool> rowFlag(rows, false);
vector<bool> columnFlag(columns, false);
for (int i = ; i < rows; ++i){
for (int j = ; j < columns; ++j){
if (matrix[i][j] == )
rowFlag[i] = columnFlag[j] = true;
}
}
for (int i = ; i < rows; ++i){
if (rowFlag[i]){
for (int j = ; j < columns; ++j)
matrix[i][j] = ;
}
}
for (int i = ; i < columns; ++i){
if (columnFlag[i]){
for (int j = ; j < rows; ++j)
matrix[j][i] = ;
}
}
} int canCompleteCircuit(vector<int>& gas, vector<int>& cost){
int total = ,sum = ,start = ;
for (int i = ; i < gas.size(); ++i){
total += gas[i] - cost[i];
sum += gas[i] - cost[i];
if (sum < ){
start = i + ;
sum = ;
}
}
return total >= ? start : -;
} int candy(vector<int>& ratings){
const int n = ratings.size();
vector<int> nums(n, );
for (int i = ; i < n-; ++i){
if (ratings[i] < ratings[i+])
nums[i+] = nums[i] + ;
}
for (int j = n - ; j>; --j){
if (ratings[j] < ratings[j - ])
nums[j - ] = max(nums[j - ], nums[j] + );
}
return accumulate(nums.begin(), nums.end(),);
} int candyII(vector<int>& ratings) {
if (ratings.size() == ) return ;
vector<int> minLeft(ratings.size(), );
for (int i = ; i<ratings.size(); ++i){
if (ratings[i]>ratings[i - ])
minLeft[i] = minLeft[i - ] + ;
}
vector<int> minRight(ratings.size(), );
for (int j = ratings.size() - ; j >= ; --j){
if (ratings[j]>ratings[j + ]) //如果左边的等级高，而且左边的糖果又少的话
minRight[j] = max(minLeft[j], (minRight[j + ] + ));
}
int result = ;
for (int k = ; k<ratings.size(); ++k)
result += max(minLeft[k], minRight[k]); //取从左边和右边都最小的值中的最大值，这样就满足所有条件了。
return result;
} int singleNumber(vector<int>& nums){
int x = ;
for (int i = ; i < nums.size(); ++i)
x ^= nums[i];
return x;
} int singleNumberII(vector<int>& nums) {
int result = ;
for (int i = ; i < ; ++i){
int sum = ;
for (int j = ; j < nums.size(); ++j){
sum += (nums[j] >> i) & ;
}
result += (sum % ) << i;// result |= (sum % 3) << i;
}
return result;
} int main()
{
int myints[] = { ,,,,,,};
vector<int> myvec(myints, myints + sizeof(myints) / sizeof(int));
cout << "result:" << singleNumberII(myvec) << endl;
system("pause");
return ;
}
题目参考教材：https://github.com/soulmachine/leetcode（leetcode-cpp.pdf）