Huahua’s Tech Road

花花酱 LeetCode 977. Squares of a Sorted Array

By zxi on January 20, 2019

Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order.

Example 1:

Input: [-4,-1,0,3,10]
Output: [0,1,9,16,100]

Example 2:

Input: [-7,-3,2,3,11]
Output: [4,9,9,49,121]

Note:

1 <= A.length <= 10000
-10000 <= A[i] <= 10000
A is sorted in non-decreasing order.

Solution: Two pointers + Merge two sorted arrays

Time complexity: O(n)
Space complexity: O(1)

c++

// Author: Huahua, running time: 120 ms

class Solution {

public:

vector<int> sortedSquares(vector<int>& A) {

vector<int> ans(A.size());

auto e = prev(end(A));

auto s = begin(A);

auto it = end(ans);

while (--it >= begin(ans)) {

if (e > s && abs(*e) > abs(*s))

*it = pow(*e--, 2);

else

*it = pow(*s++, 2);

}

return ans;

}

};

花花酱 LeetCode 974. Subarray Sums Divisible by K

By zxi on January 17, 2019

Given an array A of integers, return the number of (contiguous, non-empty) subarrays that have a sum divisible by K.

Example 1:

Input: A = [4,5,0,-2,-3,1], K = 5 
Output: 7 
Explanation: There are 7 subarrays with a sum divisible by K = 5: [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

Note:

1 <= A.length <= 30000
-10000 <= A[i] <= 10000
2 <= K <= 10000

Solution: Count prefix sums

let c[i] denotes the counts of prefix_sum % K init: c[0] = 1
Whenever we end up with the same prefix sum (after modulo), which means there are subarrys end with current element that is divisible by K (0 modulo).

e.g. A = [4,5,0,-2,-3,1], K = 5
[4,5] has prefix sum of 4, which happens at index 0 [4], and index 1, [4,5]
[4,5,0] also has a prefix sum of 4, which means [4, {5,0}], [4,5, {0}] are divisible by K.

ans += (c[prefix_sum] – 1)
i = 0, prefix_sum = 0, c[(0+4)%5] = c[4] = 1, ans = 0
i = 1, prefix_sum = 4+5, c[(4+5)%5] = c[4] = 2, ans = 0+2-1=0 => [5]
i = 2, prefix_sum = 4+0, c[(4+0)%5] = c[4] = 3, ans = 1+3-1=3 => [5], [5,0], [0]
i = 3, prefix_sum = 4-2, c[(4-2)%5] = c[2] = 1, ans = 3
i = 4, prefix_sum = 2-3, c[(2-3+5)%5] = c[4] = 4, ans = 3+4-1=6 => [5],[5,0],[0],[5,0,-2,-3], [0,-2,-3],[-2,-3]
i = 5, prefix_sum = 4+1, c[(4+1)%5] = c[0] = 2, ans = 6 + 2 – 1 =>
[5],[5,0],[0],[5,0,-2,-3], [0,-2,-3],[-2,-3], [4,5,0,-2,-3,1]

Time complexity: O(n)
Space complexity: O(n)

C++

class Solution {

public:

int subarraysDivByK(vector<int>& A, int K) {

vector<int> c(K);

c[0] = 1;

int ans = 0;

int sum = 0;

for (int a : A) {

sum = (sum + a % K + K) % K;

ans += c[sum]++;

}

return ans;

}

};

Python3

class Solution:

def subarraysDivByK(self, A, K):

c = [0] * K

c[0] = 1

s = 0

ans = 0

for a in A:

s = (s + a % K + K) % K

ans += c[s]

c[s] += 1

return ans

花花酱 LeetCode 975. Odd Even Jump

By zxi on January 15, 2019

You are given an integer array A. From some starting index, you can make a series of jumps. The (1st, 3rd, 5th, …) jumps in the series are called odd numbered jumps, and the (2nd, 4th, 6th, …) jumps in the series are called even numbered jumps.

You may from index i jump forward to index j (with i < j) in the following way:

During odd numbered jumps (ie. jumps 1, 3, 5, …), you jump to the index j such that A[i] <= A[j] and A[j] is the smallest possible value. If there are multiple such indexes j, you can only jump to the smallest such index j.
During even numbered jumps (ie. jumps 2, 4, 6, …), you jump to the index j such that A[i] >= A[j] and A[j] is the largest possible value. If there are multiple such indexes j, you can only jump to the smallest such index j.
(It may be the case that for some index i, there are no legal jumps.)

A starting index is good if, starting from that index, you can reach the end of the array (index A.length - 1) by jumping some number of times (possibly 0 or more than once.)

Return the number of good starting indexes.

Example 1:

Input: [10,13,12,14,15] 
Output: 2

Example 2:

Input: [2,3,1,1,4] 
Output: 3

Example 3:

Input: [5,1,3,4,2] 
Output: 3

Note:

1 <= A.length <= 20000
0 <= A[i] < 100000

Solution: Binary Search + DP

Time complexity: O(nlogn)
Space complexity: O(n)

C++

class Solution {

public:

int oddEvenJumps(vector<int>& A) {

const int n = A.size();

map<int, int> m;

vector<vector<int>> dp(n + 1, vector<int>(2));

dp[n - 1][0] = dp[n - 1][1] = 1;

m[A[n - 1]] = n - 1;

int ans = 1;

for (int i = n - 2; i >= 0; --i) {

auto o = m.lower_bound(A[i]);

if (o != m.end()) dp[i][0] = dp[o->second][1];

auto e = m.upper_bound(A[i]);

if (e != m.begin()) dp[i][1] = dp[prev(e)->second][0];

if (dp[i][0]) ++ans;

m[A[i]] = i;

}

return ans;

}

};

花花酱 LeetCode 976. Largest Perimeter Triangle

By zxi on January 14, 2019

Given an array A of positive lengths, return the largest perimeter of a triangle with non-zero area, formed from 3 of these lengths.

If it is impossible to form any triangle of non-zero area, return 0.

Example 1:

Input: [2,1,2]
Output: 5

Example 2:

Input: [1,2,1]
Output: 0

Example 3:

Input: [3,2,3,4]
Output: 10

Example 4:

Input: [3,6,2,3]
Output: 8

Note:

3 <= A.length <= 10000
1 <= A[i] <= 10^6

Solution: Greedy

Answer must be 3 consecutive numbers in the sorted array
if A[i] >= A[i+1] + A[i+2], then A[i] >= A[i+j] + A[i+k], 1 < j < k
if A[i] < A[i+1] + A[i+2], then A[i] + A[i+1] + A[i+2] is the answer

C++

class Solution {

public:

int largestPerimeter(vector<int>& A) {

sort(rbegin(A), rend(A));

for (int i = 0; i < A.size() - 2; ++i)

if (A[i] < A[i + 1] + A[i + 2])

return A[i] + A[i + 1] + A[i + 2];

return 0;

}

};

花花酱 LeetCode 973. K Closest Points to Origin

By zxi on January 13, 2019

We have a list of points on the plane. Find the K closest points to the origin (0, 0).

(Here, the distance between two points on a plane is the Euclidean distance.)

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in.)

Example 1:

Input: points = [[1,3],[-2,2]], K = 1 
Output: [[-2,2]] 
Explanation:  The distance between (1, 3) and the origin is sqrt(10). The distance between (-2, 2) and the origin is sqrt(8). Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin. We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]].

Example 2:

Input: points = [[3,3],[5,-1],[-2,4]], K = 2 
Output: [[3,3],[-2,4]] (The answer [[-2,4],[3,3]] would also be accepted.)

Note:

1 <= K <= points.length <= 10000
-10000 < points[i][0] < 10000
-10000 < points[i][1] < 10000

Solution: Sort

Time complexity: O(nlogn)
Space complexity: O(n)

C++

// Author: Huahua, Running time: 180 ms

class Solution {

public:

vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {

vector<long> s(points.size());

for (int i = 0; i < points.size(); ++i)

s[i] = (static_cast<long>(points[i][0] * points[i][0] +

points[i][1] * points[i][1]) << 32) | i;

std::sort(begin(s), end(s));

vector<vector<int>> ans(K);

for (int i = 0; i < K; ++i)

ans[i] = points[static_cast<int>(s[i])];

return ans;

}

};

Python3

# Author: Huahua, running time: 528 ms

class Solution:

def kClosest(self, points, K):

return sorted(points, key = lambda p: p[0]**2 + p[1]**2)[0:K]

Huahua's Tech Road

花花酱 LeetCode 977. Squares of a Sorted Array

Solution: Two pointers + Merge two sorted arrays

c++

花花酱 LeetCode 974. Subarray Sums Divisible by K

C++

Python3

花花酱 LeetCode 975. Odd Even Jump

Solution: Binary Search + DP

C++

花花酱 LeetCode 976. Largest Perimeter Triangle

Solution: Greedy

C++

花花酱 LeetCode 973. K Closest Points to Origin

Solution: Sort

C++

Python3