Posts tagged as “easy”

花花酱 LeetCode 985. Sum of Even Numbers After Queries

By zxi on February 2, 2019

Problem

We have an array A of integers, and an array queries of queries.

For the i-th query val = queries[i][0], index = queries[i][1], we add val to A[index]. Then, the answer to the i-th query is the sum of the even values of A.

(Here, the given index = queries[i][1] is a 0-based index, and each query permanently modifies the array A.)

Return the answer to all queries. Your answer array should have answer[i] as the answer to the i-th query.

Example 1:

Input: A = [1,2,3,4], queries = [[1,0],[-3,1],[-4,0],[2,3]]
Output: [8,6,2,4]
Explanation: 
At the beginning, the array is [1,2,3,4].
After adding 1 to A[0], the array is [2,2,3,4], and the sum of even values is 2 + 2 + 4 = 8.
After adding -3 to A[1], the array is [2,-1,3,4], and the sum of even values is 2 + 4 = 6.
After adding -4 to A[0], the array is [-2,-1,3,4], and the sum of even values is -2 + 4 = 2.
After adding 2 to A[3], the array is [-2,-1,3,6], and the sum of even values is -2 + 6 = 4.

Note:

1 <= A.length <= 10000
-10000 <= A[i] <= 10000
1 <= queries.length <= 10000
-10000 <= queries[i][0] <= 10000
0 <= queries[i][1] < A.length

Solution: Simulation

Time complexity: O(n + |Q|)
Space complexity: O(n)

C++

// Author: Huahua, Running time: 100 ms / 6.5 MB

class Solution {

public:

vector<int> sumEvenAfterQueries(vector<int>& A, vector<vector<int>>& queries) {

int sum = 0;

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

if (A[i] % 2 == 0)

sum += A[i];

vector<int> ans;

for (const auto& query : queries) {

int& a = A[query[1]];

if (a % 2 == 0)

sum -= a;

a += query[0];

if (a % 2 == 0)

sum += a;

ans.push_back(sum);

}

return ans;

}

};

Python3

# Author: Huahua, running time: 188 ms / 16.4MB

class Solution:

def sumEvenAfterQueries(self, A: 'List[int]', queries: 'List[List[int]]') -> 'List[int]':

s = sum(x for x in A if x % 2 == 0)

ans = []

for val, index in queries:

if A[index] % 2 == 0: s -= A[index]

A[index] += val

if A[index] % 2 == 0: s += A[index]

ans.append(s)

return ans

花花酱 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]

花花酱 LeetCode 970. Powerful Integers

By zxi on January 5, 2019

Given two non-negative integers x and y, an integer is powerful if it is equal to x^i + y^j for some integers i >= 0 and j >= 0.

Return a list of all powerful integers that have value less than or equal to bound.

You may return the answer in any order. In your answer, each value should occur at most once.

Example 1:

Input: x = 2, y = 3, bound = 10
Output: [2,3,4,5,7,9,10]
Explanation: 
2 = 2^0 + 3^0
3 = 2^1 + 3^0
4 = 2^0 + 3^1
5 = 2^1 + 3^1
7 = 2^2 + 3^1
9 = 2^3 + 3^0
10 = 2^0 + 3^2

Example 2:

Input: x = 3, y = 5, bound = 15
Output: [2,4,6,8,10,14]

Note:

1 <= x <= 100
1 <= y <= 100
0 <= bound <= 10^6

Solution: Brute Force

Time complexity: O(log(bound) / log(x) * log(bound) / log(y))
Space complexity: O(log(bound) / log(x) * log(bound) / log(y))

C++

// Author: Huahua, running time: 4 ms

class Solution {

public:

vector<int> powerfulIntegers(int x, int y, int bound) {

unordered_set<int> ans;

for (int a = 1; a < bound; a *= x) {

for (int b = 1; a + b <= bound; b *= y) {

ans.insert(a + b);

if (y == 1) break;

}

if (x == 1) break;

}

return {begin(ans), end(ans)};

}

};

花花酱 LeetCode 965. Univalued Binary Tree

By zxi on December 30, 2018

Problem

A binary tree is univalued if every node in the tree has the same value.

Return true if and only if the given tree is univalued.

Example 1:

Input: [1,1,1,1,1,null,1]
Output: true

Example 2:

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

Note:

The number of nodes in the given tree will be in the range [1, 100].
Each node’s value will be an integer in the range [0, 99].

Solution: Recursion

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

C++

// Author: Huahua, running time: 0 ms

class Solution {

public:

bool isUnivalTree(TreeNode* root) {

if (!root) return true;

if (root->left && root->val != root->left->val) return false;

if (root->right && root->val != root->right->val) return false;

return isUnivalTree(root->left) && isUnivalTree(root->right);

}

};

Python3

# Author: Huahua, running time: 68 ms

class Solution:

def isUnivalTree(self, root):

if not root: return True

if root.left and root.left.val != root.val: return False

if root.right and root.right.val != root.val: return False

return self.isUnivalTree(root.left) and self.isUnivalTree(root.right)

花花酱 LeetCode 961. N-Repeated Element in Size 2N Array

By zxi on December 23, 2018

In a array A of size 2N, there are N+1 unique elements, and exactly one of these elements is repeated N times.

Return the element repeated N times.

Example 1:

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

Example 2:

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

Example 3:

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

Note:

4 <= A.length <= 10000
0 <= A[i] < 10000
A.length is even

Solution: Randomization

Randomly pick two numbers in the array, if they are the same (25% probability) return the number, do it until the two numbers are the same.

Time complexity: O(1) expected 4
Space complexity: O(1)

C++

// Author: Huahua, running time: 72 ms

class Solution {

public:

int repeatedNTimes(vector<int>& A) {

int i = 0;

int j = 0;

while (i == j || A[i] != A[j]) {

i = rand() % A.size();

j = rand() % A.size();

}

return A[i];

}

};

Posts tagged as “easy”

花花酱 LeetCode 985. Sum of Even Numbers After Queries

Problem

Solution: Simulation

C++

Python3

花花酱 LeetCode 973. K Closest Points to Origin

Solution: Sort

C++

Python3

花花酱 LeetCode 970. Powerful Integers

Solution: Brute Force

C++

花花酱 LeetCode 965. Univalued Binary Tree

Problem

Solution: Recursion

C++

Python3

Related Problems

花花酱 LeetCode 961. N-Repeated Element in Size 2N Array

Solution: Randomization

C++