A Code

Code ( Language :C++) ( Judger :cloudjudge-cluster-7) Edit class Solution { public : /** * @param nums: a list of integers * @param m: an integer * @return: return a integer */ int splitArray ( vector < int > &nums, int m) { // write your code here // binary search const int size = nums.size(); if (size < m){ return -1 ; } long long sum = 0 ; int maxVal = INT_MIN; for ( auto i : nums){ sum += i; maxVal = max(maxVal, i); } int start = maxVal; long long end = sum; while (start < end){ //注意这里和模板不同 long long mid = start + (end - start) / 2 ; if (!splitNum(nums, mid, m)){ start = mid + 1 ; //注意这里的操作。 } else { end = mid; } } // if(!splitNum(nums, (long long)end, m)){ ...

隐形的二分法： Code ( Language :C++) ( Judger :cloudjudge-cluster-5) Edit class Solution { public : /* * @param A: An integer array * @param B: An integer array * @return: a double whose format is *.5 or *.0 */ double findMedianSortedArrays ( vector < int > &A, vector < int > &B) { // write your code here //核心点1是转化为找k-th smallest number; 2是能发现 比较A[k/2 - 1]和B[k/2 - 1], k th number在较小值所在的vector和 the other one中。 //坑点: 注意index的选取，以一个简单例子看，会避免出错。 const int m = A.size(); const int n = B.size(); int size = m + n; if (size == 0 ){ return -1 ; } if (size % 2 ){ return findkth(A, B, 0 , 0 , (size + 1 ) / 2 ); } else { return (findkth(A, B, 0 , 0 , size / 2 ) + findkth(A, B, 0 , 0 , size / 2 + 1 )) / 2.0 ; } } int findkth ( vector < int > &A, vector < int ...

Description 中文 English For  n  people, each of them needs to do  m  jobs independently. The  i  job takes  cost[i]  time. Since each person's free time is different, the  i  person has  val[i]  time, which means that the total time for his jobs will not exceed  val[i] . Everyone starts with the first job, then the 2nd, the 3rd... Now, you need to figure out how much time they spend. 1<=n<=100000 1<=m<=100000 1<=val[i]<=100000 1<=cost[i]<=100000 Have you met this question in a real interview?    Yes Problem Correction Example Example 1: Given `cost=[1,2,3,5]`,`val=[6,10,4]`, return `15`. Input: [1,2,3,5] [6,10,4] Output: 15 Explanation: The first person can complete the 1st job, the 2nd job, the 3rd job, 1+2+3<=6. The second person cancomplete the 1st job, the 2nd job, the 3rd job, and cannot complete the 4th job, 1+2+3<=10, 1+2+3+5>10. T...

There are  n  stones between the starting point and the end point. The distance between the starting point and the  ith  (i starts from 0) stone is  d[i] . And the distance between the starting point and end point is  target . From the starting point, we can only jump to the  adjacent  stone until the end point. Now you can remove at most  m  stones. Return the maximum value of the shortest jump distance in your jumping from start point to end point. 0 \leq m \leq n \leq 50,000 0 ≤ m ≤ n ≤ 5 0 , 0 0 0 1 \leq target \leq 1,000,000,000 1 ≤ t a r g e t ≤ 1 , 0 0 0 , 0 0 0 , 0 0 0 These stones are given in order from small to large distances from the starting point, and no two stones will appear in the same place. Have you met this question in a real interview?    Yes Problem Correction Example Example 1: Input: n = 5, m = 2, target = 25, d = [2,11,14,17,21] Output: 4 Explanation: Remove th...

Code ( Language :C++) Edit class Solution { public : /** * @param A: An integers array. * @return: return any of peek positions. */ int findPeak ( vector < int > &A) { // write your code here const int size = A.size(); int start = 0 ; int end = size - 1 ; while (start + 1 < end){ int mid = start + (end - start) / 2 ; if (A[mid] > A[mid - 1 ]){ start = mid; } else { end = mid; } } if (A[start] > A[end]){ return start; } else { return end; } } };

Code ( Language :C++) Edit class Solution { public : /** * @param A: an integer sorted array * @param target: an integer to be inserted * @return: a list of length 2, [index1, index2] */ vector < int > searchRange( vector < int > &A, int target) { // write your code here const int size = A.size(); vector < int > res( 2 , -1 ); if (size == 0 ){ return res; } int start = 0 ; int end = size - 1 ; while (start + 1 < end){ int mid = start + (end - start) / 2 ; if (A[mid] >= target){ end = mid; } else { start = mid; } } if (A[start] == target){ res[ 0 ] = start; } else if (A[end] == target){ res[ 0 ] = end; } else { return res; } star...

Given a list of salaries, find the smallest  cap  which makes the sum of adjusted salary be equal to or larger than the given  target .  cap  is defined as: if the current salary is smaller than  cap , then  cap  is used as the new salary, otherwise keep the original salary The length of the list does not exceed  100000 1 0 0 0 0 0 The salaries do not exceed  10000 1 0 0 0 0 Have you met this question in a real interview?    Yes Problem Correction Example Example 1： Give `a=[1,2,3,4],target=13`, return `3`. Input: 1 2 3 4 13 Output:3 Explanation: If cap=3, the list will change into [3,3,3,4]. Example 2: Give `a=[1,2,3,4],target=16`, return `4`. Input: 1 2 3 4 16 Output:4 Explanation: If cap=4, the list will change into [4,4,4,4]. Code ( Language :C++) Edit class Solution { public : /** * @param a: the list of salary * @param target: the target of the...