// 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 ;

 }