Given an array nums of integers, return how many of them contain an even number of digits.
Example 1:
Input: nums = [12,345,2,6,7896]
Output: 2
Explanation:
12 contains 2 digits (even number of digits).
345 contains 3 digits (odd number of digits).
2 contains 1 digit (odd number of digits).
6 contains 1 digit (odd number of digits).
7896 contains 4 digits (even number of digits).
Therefore only 12 and 7896 contain an even number of digits.
Example 2:
Input: nums = [555,901,482,1771]
Output: 1
Explanation:
Only 1771 contains an even number of digits.
Constraints:
1 <= nums.length <= 500
1 <= nums[i] <= 10^5
Solution: Math
Time complexity: O(n * log(max(num))) Space complexity: O(1)
Given a m x n matrix mat and an integer threshold. Return the maximum side-length of a square with a sum less than or equal to threshold or return 0 if there is no such square.
Example 1:
Input: mat = [[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]], threshold = 4
Output: 2
Explanation: The maximum side length of square with sum less than 4 is 2 as shown.
Example 2:
Input: mat = [[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2]], threshold = 1
Output: 0
Example 3:
Input: mat = [[1,1,1,1],[1,0,0,0],[1,0,0,0],[1,0,0,0]], threshold = 6
Output: 3
Example 4:
Input: mat = [[18,70],[61,1],[25,85],[14,40],[11,96],[97,96],[63,45]], threshold = 40184
Output: 2
Constraints:
1 <= m, n <= 300
m == mat.length
n == mat[i].length
0 <= mat[i][j] <= 10000
0 <= threshold <= 10^5
Solution: DP + Brute Force
Precompute the sums of sub-matrixes whose left-top corner is at (0,0).
Try all possible left-top corner and sizes.
Time complexity: O(m*n*min(m,n)) Space complexity: O(m*n)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// Author: Huahua, 148 ms
classSolution{
public:
intmaxSideLength(vector<vector<int>>& mat, int threshold) {
iven a m * n grid, where each cell is either 0 (empty) or 1 (obstacle). In one step, you can move up, down, left or right from and to an empty cell.
Return the minimum number of steps to walk from the upper left corner (0, 0) to the lower right corner (m-1, n-1) given that you can eliminate at mostk obstacles. If it is not possible to find such walk return -1.
Example 1:
Input:
grid =
[[0,0,0],
[1,1,0],
[0,0,0],
[0,1,1],
[0,0,0]],
k = 1
Output: 6
Explanation:
The shortest path without eliminating any obstacle is 10.
The shortest path with one obstacle elimination at position (3,2) is 6. Such path is (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2).
Example 2:
Input:
grid =
[[0,1,1],
[1,1,1],
[1,0,0]],
k = 1
Output: -1
Explanation:
We need to eliminate at least two obstacles to find such a walk.
Constraints:
grid.length == m
grid[0].length == n
1 <= m, n <= 40
1 <= k <= m*n
grid[i][j] == 0 or 1
grid[0][0] == grid[m-1][n-1] == 0
Solution: BFS
State: (x, y, k) where k is the number of obstacles along the path.
Time complexity: O(m*n*k) Space complexity: O(m*n*k)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// Author: Huahua, 8 ms, 10.5 MB
classSolution{
public:
intshortestPath(vector<vector<int>>& grid, int k) {
Given a square grid of integers arr, a falling path with non-zero shifts is a choice of exactly one element from each row of arr, such that no two elements chosen in adjacent rows are in the same column.
Return the minimum sum of a falling path with non-zero shifts.
Example 1:
Input: arr = [[1,2,3],[4,5,6],[7,8,9]]
Output: 13
Explanation:
The possible falling paths are:
[1,5,9], [1,5,7], [1,6,7], [1,6,8],
[2,4,8], [2,4,9], [2,6,7], [2,6,8],
[3,4,8], [3,4,9], [3,5,7], [3,5,9]
The falling path with the smallest sum is [1,5,7], so the answer is 13.
Given an integer array sorted in non-decreasing order, there is exactly one integer in the array that occurs more than 25% of the time.
Return that integer.
Example 1:
1
2
<strong>Input:</strong>arr=[1,2,2,6,6,6,6,7,10]
<strong>Output:</strong>6
Constraints:
1 <= arr.length <= 10^4
0 <= arr[i] <= 10^5
Solution 1: Linear Scan
if arr[i] == arr[i + len/4] => arr[i] is the special integer.
Time complexity: O(n) Space complexity: O(1)
C++
1
2
3
4
5
6
7
8
9
10
// Author: Huahua
classSolution{
public:
intfindSpecialInteger(vector<int>& arr) {
int s = arr.size() / 4;
for(inti=0;i+s<arr.size();++i)
if(arr[i]==arr[i+s])returnarr[i];
return-1;
}
};
Solution 2: Binary Search
The answer must be one of (s[0], s[l/4], s[l/2], s[l*3/4]) Using binary search to find the range of each number, the one has more than 1/4 of total elements is the answer.