求合取余即可，余数就是答案。
Time complexity: O(n)
Space complexity: O(1)
|
1 2 3 4 5 6 |
class Solution { public: int minOperations(vector<int>& nums, int k) { return accumulate(begin(nums), end(nums), 0) % k; } }; |
Posts tagged as “math”
不太喜欢这样的题目，你需要证明/猜测最优解是将所有数字转换成median/中位数。
使用nth_element找中位数，然后再循环一遍求合即可。
时间复杂度：O(n)
空间复杂度：O(1)
|
1 2 3 4 5 6 7 8 9 10 11 |
class Solution { public: int minMoves2(vector<int>& nums) { const int n = nums.size(); nth_element(begin(nums), begin(nums) + n / 2, end(nums)); const int median = nums[n / 2]; return accumulate(begin(nums), end(nums), 0, [median](int s, int x) { return s + abs(x - median); }); } }; |
You are given a 0-indexed integer array nums and an integer k. Your task is to perform the following operation exactly k times in order to maximize your score:
- Select an element
mfromnums. - Remove the selected element
mfrom the array. - Add a new element with a value of
m + 1to the array. - Increase your score by
m.
Return the maximum score you can achieve after performing the operation exactly k times.
Example 1:
Input: nums = [1,2,3,4,5], k = 3 Output: 18 Explanation: We need to choose exactly 3 elements from nums to maximize the sum. For the first iteration, we choose 5. Then sum is 5 and nums = [1,2,3,4,6] For the second iteration, we choose 6. Then sum is 5 + 6 and nums = [1,2,3,4,7] For the third iteration, we choose 7. Then sum is 5 + 6 + 7 = 18 and nums = [1,2,3,4,8] So, we will return 18. It can be proven, that 18 is the maximum answer that we can achieve.
Example 2:
Input: nums = [5,5,5], k = 2 Output: 11 Explanation: We need to choose exactly 2 elements from nums to maximize the sum. For the first iteration, we choose 5. Then sum is 5 and nums = [5,5,6] For the second iteration, we choose 6. Then sum is 5 + 6 = 11 and nums = [5,5,7] So, we will return 11. It can be proven, that 11 is the maximum answer that we can achieve.
Constraints:
1 <= nums.length <= 1001 <= nums[i] <= 1001 <= k <= 100
Solution: Greedy
Always to chose the largest element from the array.
We can find the largest element of the array m, then the total score will be
m + (m + 1) + (m + 2) + … + (m + k – 1),
We can use summation formula of arithmetic sequence to compute that in O(1)
ans = (m + (m + k – 1)) * k / 2
Time complexity: O(n)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 |
// Author: Huahua class Solution { public: int maximizeSum(vector<int>& nums, int k) { int m = *max_element(begin(nums), end(nums)); return (m + m + k - 1) * k / 2; } }; |
Given a positive integer n, find the sum of all integers in the range [1, n] inclusive that are divisible by 3, 5, or 7.
Return an integer denoting the sum of all numbers in the given range satisfying the constraint.
Example 1:
Input: n = 7 Output: 21 Explanation: Numbers in the range[1, 7]that are divisible by3,5,or7are3, 5, 6, 7. The sum of these numbers is21.
Example 2:
Input: n = 10 Output: 40 Explanation: Numbers in the range[1, 10] that aredivisible by3,5,or7are3, 5, 6, 7, 9, 10. The sum of these numbers is 40.
Example 3:
Input: n = 9 Output: 30 Explanation: Numbers in the range[1, 9]that are divisible by3,5, or7are3, 5, 6, 7, 9. The sum of these numbers is30.
Constraints:
1 <= n <= 103
Solution: Mod
Time complexity: O(n)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 |
// Author: Huahua class Solution { public: int sumOfMultiples(int n) { int ans = 0; for (int i = 1; i <= n; ++i) { if (i % 3 == 0 || i % 5 == 0 || i % 7 == 0) ans += i; } return ans; } }; |
There are n people standing in a line labeled from 1 to n. The first person in the line is holding a pillow initially. Every second, the person holding the pillow passes it to the next person standing in the line. Once the pillow reaches the end of the line, the direction changes, and people continue passing the pillow in the opposite direction.
- For example, once the pillow reaches the
nthperson they pass it to then - 1thperson, then to then - 2thperson and so on.
Given the two positive integers n and time, return the index of the person holding the pillow after time seconds.
Example 1:
Input: n = 4, time = 5 Output: 2 Explanation: People pass the pillow in the following way: 1 -> 2 -> 3 -> 4 -> 3 -> 2. Afer five seconds, the pillow is given to the 2nd person.
Example 2:
Input: n = 3, time = 2 Output: 3 Explanation: People pass the pillow in the following way: 1 -> 2 -> 3. Afer two seconds, the pillow is given to the 3rd person.
Constraints:
2 <= n <= 10001 <= time <= 1000
Solution: Math
It takes n – 1 seconds from 1 to n and takes another n – 1 seconds back from n to 1.
So one around takes 2 * (n – 1) seconds. We can mod time with 2 * (n – 1).
After that if time < n – 1 answer is time + 1, otherwise answer is n – (time – (n – 1))
Time complexity: O(1)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 |
// Author: Huahua class Solution { public: int passThePillow(int n, int time) { time %= (2 * (n - 1)); return time > n - 1 ? n - (time - (n - 1)) : time + 1; } }; |