A Code

Code ( Language :C++) ( Judger :cloudjudge-cluster-4) Edit class Solution { public : /** * @param people: a random list of people * @return: the queue that be reconstructed */ vector < vector < int >> reconstructQueue( vector < vector < int >> &people) { // write your code here sort(people.begin(), people.end(), comparator); vector < vector < int >> resultVector; for ( vector < int > cur : people) { resultVector.insert(resultVector.begin() + cur[ 1 ], cur); } return resultVector; } static bool comparator ( vector < int > p1, vector < int > p2) { return (p1[ 0 ] > p2[ 0 ]) || (p1[ 0 ] == p2[ 0 ] && p1[ 1 ] < p2[ 1 ]); } }; 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Close

There are N children standing in a line. Each child is assigned a rating value. You are giving candies to these children subjected to the following requirements: Each child must have at least one candy. Children with a higher rating get more candies than their neighbors. Children with the same rating and are located next to each other get the same candies. What is the minimum candies you must give? Have you met this question in a real interview?    Yes Problem Correction Example Example 1: Input: 4 7 8 1 6 6 2 Output: 12 Explanation: 1 + 2 + 3 + 1 + 2 + 2 + 1 = 12 Example 2: Input: 10 2 3 3 7 10 Output: 14 Explanation: 2 + 1 + 2 + 2 + 3 + 4 = 14 class Solution { public : /** * @param ratings: rating value of each child * @return: Return the minimum candies you must give. */ int candyII ( vector < int > &ratings) { // write your code here const int size = ratings.size()...

Code ( Language :C++) Edit class Solution { public : /** * @param ratings: Children's ratings * @return: the minimum candies you must give */ int candy ( vector < int > &ratings) { // write your code here const int size = ratings.size(); if (size == 0 ){ return 0 ; } vector < int > candy(size, 1 ); for ( int i = 1 ; i < size; i++){ if (ratings[i] > ratings[i - 1 ]){ candy[i] = candy[i - 1 ] + 1 ; } } int res = candy[size - 1 ]; for ( int i = size - 1 ; i > 0 ; i--){ if (ratings[i - 1 ] > ratings[i] && candy[i - 1 ] <= candy[i]){ candy[i - 1 ] = candy[i] + 1 ; } res += candy[i - 1 ]; } return res; } };

Code ( Language :C++) Edit class Solution { public : /** * @param A: an array * @return: the sum of subarray minimums */ int sumSubarrayMins ( vector < int > &A) { // Write your code here. long res = 0 ; long mod = 1000000007 ; for ( int i = 0 ; i < A.size(); i++) { int l = i - 1 ; while (l >= 0 && A[l] > A[i]){ l--; } int r = i + 1 ; while (r < A.size() && A[r] >= A[i]){ r++; } res += (i - l) * (r - i) * A[i]; } return res % mod; } };

Code ( Language :C++) Edit class Solution { public : /** * @param machines: an integer array representing the number of dresses in each washing machine from left to right on the line * @return: the minimum number of moves to make all the washing machines have the same number of dresses */ int findMinMoves ( vector < int > &machines) { // Write your code here // greedy 解法 int sum = 0 ; const int size = machines.size(); for ( int i : machines){ sum += i; } if (sum % size){ return -1 ; } int avg = sum / size; int res = 0 , cnt = 0 ; for ( int i : machines){ cnt += i - avg; res = max(max(res, abs (cnt)), abs (i - avg)); } return res; } };

Code ( Language :C++) Edit class Solution { public : /** * @param nums: the array * @param target: the target * @return: the number of subsets which meet the following conditions */ long long subsetWithTarget ( vector < int > &nums, int target) { // Write you code here // two pointers const int size = nums.size(); if (size == 0 ){ return 0 ; } sort(nums.begin(), nums.end()); int left = 0 ; int right = size - 1 ; long long cnt = 0 ; while (left <= right){ if (nums[left] + nums[right] >= target){ right--; } else { cnt += pow ( 2 , right - left); left++; } } return cnt; } };

class Solution { public : /** * @param s: a string * @return: return a list of integers */ vector < int > findPermutation( string &s) { // write your code here // greedy OK? // 1 2 3 4 DDI inverse the ‘D’ overed range(1 2 3) -> 3 2 1 4 const int Ss = s.size(); vector < int > res1; if (Ss == 0 ){ return res1; } vector < int > res(Ss + 1 , 0 ); for ( int i = 0 ; i <= Ss; i++){ res[i] = i + 1 ; } int i = 0 ; while (i < Ss){ if (s[i] == 'I' ){ i++; continue ; } else { int start = i; while (i < Ss && s[i] == 'D' ){ i++; } reverse(res.begin() + start, res.begin() + i + 1 ); } ...

Given a positive  32-bit  integer  n , you need to find the smallest  32-bit  integer which has exactly the same digits existing in the integer  n  and is greater in value than n. If no such positive  32-bit  integer exists, you need to return -1. Have you met this question in a real interview?    Yes Problem Correction Example Example 1: Input: 12 Output: 21 Example 2: Input: 21 Output: -1 int nextGreaterElement ( int n) { // Write your code here //这个思路是找到前面位置上的值比后面的小就交换。是不对的。以后这个不能把握的greedy解法尽量要再斟酌。 //后面还有两部逻辑，1是交换的不一定就是挨着的两个，后面位数上有更小的，需要用来交换 //2, 交换后，后面尾巴上的数要从小到大排序一次。另外，直接在int 数上操作太不方便了，这种数上的iteration，先转换成string方便 int copy = n; int d0 = n % 10 ; int d1 = 0 ; n /= 10 ; int cnt = 1 ; int flag = 0 ; while (n > 0 ){ d1 = n % 10 ; n /= 10 ; cnt++; ...