You are given an integer array nums of even length n.
A cyclic rotation of nums is obtained by choosing a prefix of nums whose length is between 0 and n - 1 (inclusive), and moving it to the end of the array while preserving the order of all elements.
A cyclic rotation is good if the sum of its first n / 2 elements is strictly greater than the sum of its last n / 2 elements.
Return the number of cyclic rotations of nums that are good.
Example 1:
Input: nums = [1,2,3,4,5,6]
Output: 3
Explanation:
The cyclic rotations of nums are:
Cyclic rotation Sum of first n / 2 elements Sum of last n / 2 elements
[1, 2, 3, 4, 5, 6] 1 + 2 + 3 = 6 4 + 5 + 6 = 15
[2, 3, 4, 5, 6, 1] 2 + 3 + 4 = 9 5 + 6 + 1 = 12
[3, 4, 5, 6, 1, 2] 3 + 4 + 5 = 12 6 + 1 + 2 = 9
[4, 5, 6, 1, 2, 3] 4 + 5 + 6 = 15 1 + 2 + 3 = 6
[5, 6, 1, 2, 3, 4] 5 + 6 + 1 = 12 2 + 3 + 4 = 9
[6, 1, 2, 3, 4, 5] 6 + 1 + 2 = 9 3 + 4 + 5 = 12
The first half has a greater sum than the second half for 3 rotations. Thus, the answer is 3.
Example 2:
Input: nums = [1,2,1,2]
Output: 0
Explanation:
The cyclic rotations of nums are:
Cyclic rotation Sum of first n / 2 elements Sum of last n / 2 elements
[1, 2, 1, 2] 1 + 2 = 3 1 + 2 = 3
[2, 1, 2, 1] 2 + 1 = 3 2 + 1 = 3
[1, 2, 1, 2] 1 + 2 = 3 1 + 2 = 3
[2, 1, 2, 1] 2 + 1 = 3 2 + 1 = 3
No cyclic rotation is good because the two sums are equal for every rotation. Thus, the answer is 0.
Constraints:
2 <= n == nums.length <= 105
1 <= nums[i] <= 109
n is even.
2677. Chunk Array
Solved
Easy
conpanies icon
Companies
Given an array arr and a chunk size size, return a chunked array.
A chunked array contains the original elements in arr, but consists of subarrays each of length size. The length of the last subarray may be less than size if arr.length is not evenly divisible by size.
Please solve it without using lodash's _.chunk function.
Example 1:
Input: arr = [1,2,3,4,5], size = 1
Output: [[1],[2],[3],[4],[5]]
Explanation: The arr has been split into subarrays each with 1 element.
Example 2:
Input: arr = [1,9,6,3,2], size = 3
Output: [[1,9,6],[3,2]]
Explanation: The arr has been split into subarrays with 3 elements. However, only two elements are left for the 2nd subarray.
Example 3:
Input: arr = [8,5,3,2,6], size = 6
Output: [[8,5,3,2,6]]
Explanation: Size is greater than arr.length thus all elements are in the first subarray.
Example 4:
Input: arr = [], size = 1
Output: []
Explanation: There are no elements to be chunked so an empty array is returned.
Constraints:
arr is a string representing the array.
2 <= arr.length <= 105
1 <= size <= arr.length + 1
type JSONValue = null | boolean | number | string | JSONValue[] | { [key: string]: JSONValue };
type Obj = Record<string, JSONValue> | Array<JSONValue>;
function chunk(arr: Obj[], size: number): Obj[][] {
LC. 2670. Find the Distinct Difference Array
Solved
Easy
Topics
Hint
You are given a 0-indexed array nums of length n.
The distinct difference array of nums is an array diff of length n such that diff[i] is equal to the number of distinct elements in the suffix nums[i + 1, ..., n - 1] subtracted from the number of distinct elements in the prefix nums[0, ..., i].
Return the distinct difference array of nums.
Note that nums[i, ..., j] denotes the subarray of nums starting at index i and ending at index j inclusive. Particularly, if i > j then nums[i, ..., j] denotes an empty subarray.
Example 1:
Input: nums = [1,2,3,4,5]
Output: [-3,-1,1,3,5]
Explanation: For index i = 0, there is 1 element in the prefix and 4 distinct elements in the suffix. Thus, diff[0] = 1 - 4 = -3.
For index i = 1, there are 2 distinct elements in the prefix and 3 distinct elements in the suffix. Thus, diff[1] = 2 - 3 = -1.
For index i = 2, there are 3 distinct elements in the prefix and 2 distinct elements in the suffix. Thus, diff[2] = 3 - 2 = 1.
For index i = 3, there are 4 distinct elements in the prefix and 1 distinct element in the suffix. Thus, diff[3] = 4 - 1 = 3.
For index i = 4, there are 5 distinct elements in the prefix and no elements in the suffix. Thus, diff[4] = 5 - 0 = 5.
Example 2:
Input: nums = [3,2,3,4,2]
Output: [-2,-1,0,2,3]
Explanation: For index i = 0, there is 1 element in the prefix and 3 distinct elements in the suffix. Thus, diff[0] = 1 - 3 = -2.
For index i = 1, there are 2 distinct elements in the prefix and 3 distinct elements in the suffix. Thus, diff[1] = 2 - 3 = -1.
For index i = 2, there are 2 distinct elements in the prefix and 2 distinct elements in the suffix. Thus, diff[2] = 2 - 2 = 0.
For index i = 3, there are 3 distinct elements in the prefix and 1 distinct element in the suffix. Thus, diff[3] = 3 - 1 = 2.
For index i = 4, there are 3 distinct elements in the prefix and no elements in the suffix. Thus, diff[4] = 3 - 0 = 3.
LC. 238. Product of Array Except Self
Solved
Medium
Topics
conpanies icon
Companies
Hint
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
You must write an algorithm that runs in O(n) time and without using the division operation.
Example 1:
Input: nums = [1,2,3,4]
Output: [24,12,8,6]
Example 2:
Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]
Constraints:
2 <= nums.length <= 105
-30 <= nums[i] <= 30
The input is generated such that answer[i] is guaranteed to fit in a 32-bit integer.
Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)
+---------------+---------+
| Column Name | Type |
+---------------+---------+
| emp_id | int |
| firstname | varchar |
| lastname | varchar |
| salary | varchar |
| department_id | varchar |
+---------------+---------+
(emp_id, salary) is the primary key (combination of columns with unique values) for this table.
Each row contains employees details and their yearly salaries, however, some of the records are old and contain outdated salary information.
Write a solution to find the current salary of each employee assuming that salaries increase each year. Output their emp_id, firstname, lastname, salary, and department_id.
Return the result table ordered by emp_id in ascending order.
Explanation:
- emp_id 1 has two records with a salary of 110000, 106119 out of these 110000 is an updated salary (Assuming salary is increasing each year)
- emp_id 2 has two records with a salary of 128922, 130000 out of these 130000 is an updated salary.
- emp_id 3 has only one salary record so that is already an updated salary.
- emp_id 4 has two records with a salary of 162825, 170000 out of these 170000 is an updated salary.
- emp_id 5 has only one salary record so that is already an updated salary.
- emp_id 6 has two records with a salary of 79632, 90000 out of these 90000 is an updated salary.
# Write your MySQL query statement below
select
emp_id, firstname, lastname, max(salary) as salary, department_id
LC. 2667. Create Hello World Function
Solved
Easy
conpanies icon
Companies
Write a function createHelloWorld. It should return a new function that always returns "Hello World".
LC. 2660. Determine the Winner of a Bowling Game
You are given two 0-indexed integer arrays player1 and player2, representing the number of pins that player 1 and player 2 hit in a bowling game, respectively.
The bowling game consists of n turns, and the number of pins in each turn is exactly 10.
Assume a player hits xi pins in the ith turn. The value of the ith turn for the player is:
2xi if the player hits 10 pins in either (i - 1)th or (i - 2)th turn.
Otherwise, it is xi.
The score of the player is the sum of the values of their n turns.
Return
1 if the score of player 1 is more than the score of player 2,
2 if the score of player 2 is more than the score of player 1, and
0 in case of a draw.
Example 1:
Input: player1 = [5,10,3,2], player2 = [6,5,7,3]
Output: 1
Explanation:
The score of player 1 is 5 + 10 + 2*3 + 2*2 = 25.
The score of player 2 is 6 + 5 + 7 + 3 = 21.
Example 2:
Input: player1 = [3,5,7,6], player2 = [8,10,10,2]
Output: 2
Explanation:
The score of player 1 is 3 + 5 + 7 + 6 = 21.
The score of player 2 is 8 + 10 + 2*10 + 2*2 = 42.
LC. 2656. Maximum Sum With Exactly K Elements
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 m from nums.
Remove the selected element m from the array.
Add a new element with a value of m + 1 to 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.
Hint
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 by 3, 5, or 7 are 3, 5, 6, 7. The sum of these numbers is 21.
Example 2:
Input: n = 10
Output: 40
Explanation: Numbers in the range [1, 10] that are divisible by 3, 5, or 7 are 3, 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 by 3, 5, or 7 are 3, 5, 6, 7, 9. The sum of these numbers is 30.
Constraints:
1 <= n <= 103
class Solution:
def sumOfMultiples(self, n: int) -> int:
ans = 0
for num in range(1, n+1):
if num % 3 == 0 or num % 5 == 0 or num % 7 == 0:
ans += num
return ans
复制代码
改进的解法，数学优化 —— 容斥原理 + 等差数列求和（进阶 $O(1)$ 解法）如果面试官追问：“如果 $n$ 的范围变成 $10^9$，遍历会直接超时（TLE），该怎么优化？”这就需要用到数学方法。上一题（LC 2656）我们用到了等差数列求和，这道题可以进一步结合容斥原理（Inclusion-Exclusion Principle）。数学推导在 $[1, n]$ 范围内，能被 $k$ 整除的数构成一个公差为 $k$ 的等差数列：$$k, 2k, 3k, \dots, m \cdot k \quad (\text{其中 } m = \lfloor n / k \rfloor)$$这些数的和 $S(k)$ 为：$$S(k) = k \times \frac{m(m + 1)}{2}$$要计算能被 3、5 或 7 整除的数之和：先加上能被 3、5、7 整除的数之和：$S(3) + S(5) + S(7)$减去被重复计算的交集（即同时被两者整除的数，相当于最小公倍数）：$- S(15) - S(21) - S(35)$加上被多减了一次的三者交集：$+ S(105)$
楼主: Myron2017
狗仔卡
楼主
