Posts tagged as “easy”

花花酱 LeetCode 989. Add to Array-Form of Integer

By zxi on February 10, 2019

For a non-negative integer X, the array-form of X is an array of its digits in left to right order. For example, if X = 1231, then the array form is [1,2,3,1].

Given the array-form A of a non-negative integer X, return the array-form of the integer X+K.

Example 1:

Input: A = [1,2,0,0], K = 34
Output: [1,2,3,4]
Explanation: 1200 + 34 = 1234

Example 2:

Input: A = [2,7,4], K = 181
Output: [4,5,5]
Explanation: 274 + 181 = 455

Example 3:

Input: A = [2,1,5], K = 806
Output: [1,0,2,1]
Explanation: 215 + 806 = 1021

Example 4:

Input: A = [9,9,9,9,9,9,9,9,9,9], K = 1
Output: [1,0,0,0,0,0,0,0,0,0,0]
Explanation: 9999999999 + 1 = 10000000000

Note：

1 <= A.length <= 10000
0 <= A[i] <= 9
0 <= K <= 10000
If A.length > 1, then A[0] != 0

Solution: Simulation

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

C++

// Author: Huahua, running time: 136 ms, 10.1 MB

class Solution {

public:

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

vector<int> ans;

ans.reserve(A.size() + 1);

for (int i = A.size() - 1; i >= 0 || K > 0; --i) {

K += (i >= 0 ? A[i] : 0);

ans.push_back(K % 10);

K /= 10;

}

reverse(begin(ans), end(ans));

return ans;

}

};

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

Posts tagged as “easy”

花花酱 LeetCode 989. Add to Array-Form of Integer

Solution: Simulation

C++

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