easy Archives - Page 41 of 75 - Huahua's Tech Road

花花酱 LeetCode 1351. Count Negative Numbers in a Sorted Matrix

By zxi on February 16, 2020

Given a m * n matrix grid which is sorted in non-increasing order both row-wise and column-wise.

Return the number of negative numbers in grid.

Example 1:

Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
Output: 8
Explanation: There are 8 negatives number in the matrix.

Example 2:

Input: grid = [[3,2],[1,0]]
Output: 0

Example 3:

Input: grid = [[1,-1],[-1,-1]]
Output: 3

Example 4:

Input: grid = [[-1]]
Output: 1

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 100
-100 <= grid[i][j] <= 100

Solution 1: Brute Force

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

C++

// Author: Huahua, 16 ms, 10.4 MB

class Solution {

public:

int countNegatives(vector<vector<int>>& grid) {

int ans = 0;

for (const auto& row : grid)

for (const auto x : row)

ans += x < 0;

return ans;

}

};

Solution 2: Find the frontier

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

C++

// Author: Huahua, 16 ms, 10.4 MB

class Solution {

public:

int countNegatives(vector<vector<int>>& grid) {

int ans = 0;

int m = grid.size();

int n = grid[0].size();

int r = m - 1;

int c = 0;

while (r >= 0 && c < n) {

if (grid[r][c] < 0) {

ans += n - c;

--r;

} else {

++c;

}

return ans;

}

};

花花酱 LeetCode 1342. Number of Steps to Reduce a Number to Zero

By zxi on February 13, 2020

Given a non-negative integer num, return the number of steps to reduce it to zero. If the current number is even, you have to divide it by 2, otherwise, you have to subtract 1 from it.

Example 1:

Input: num = 14
Output: 6
Explanation: 
Step 1) 14 is even; divide by 2 and obtain 7. 
Step 2) 7 is odd; subtract 1 and obtain 6.
Step 3) 6 is even; divide by 2 and obtain 3. 
Step 4) 3 is odd; subtract 1 and obtain 2. 
Step 5) 2 is even; divide by 2 and obtain 1. 
Step 6) 1 is odd; subtract 1 and obtain 0.

Example 2:

Input: num = 8
Output: 4
Explanation: 
Step 1) 8 is even; divide by 2 and obtain 4. 
Step 2) 4 is even; divide by 2 and obtain 2. 
Step 3) 2 is even; divide by 2 and obtain 1. 
Step 4) 1 is odd; subtract 1 and obtain 0.

Example 3:

Input: num = 123
Output: 12

Constraints:

0 <= num <= 10^6

Solution: Simulation

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

C++

// Author: Huahua

class Solution {

public:

int numberOfSteps (int num) {

int steps = 0;

while (num) {

if (num & 1)

--num;

else

num >>= 1;

++steps;

}

return steps;

}

};

花花酱 LeetCode 108. Convert Sorted Array to Binary Search Tree

By zxi on February 2, 2020

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5

Solution: Recursion

Recursively build a BST for a given range.

def build(nums, l, r):
if l > r: return None
m = l + (r – l) / 2
root = TreeNode(nums[m])
root.left = build(nums, l, m – 1)
root.right = build(nums, m + 1, r)
return root

return build(nums, 0, len(nums) – 1)

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

C++

// Author: Huahua

class Solution {

public:

TreeNode* sortedArrayToBST(vector<int>& nums) {

function<TreeNode*(int l, int r)> build = [&](int l, int r) {

if (l > r) return static_cast<TreeNode*>(nullptr);

int m = l + (r - l) / 2;

TreeNode* root = new TreeNode(nums[m]);

root->left = build(l, m - 1);

root->right = build(m + 1, r);

return root;

};

return build(0, nums.size() - 1);

}

};

Java

// Author: Huahua

class Solution {

public TreeNode sortedArrayToBST(int[] nums) {

return buildBST(nums, 0, nums.length - 1);

}

private TreeNode buildBST(int[] nums, int l, int r) {

if (l > r) return null;

int m = l + (r - l) / 2;

TreeNode root = new TreeNode(nums[m]);

root.left = buildBST(nums, l, m - 1);

root.right = buildBST(nums, m + 1, r);

return root;

}

Python3

# Author: Huahua

class Solution:

def sortedArrayToBST(self, nums: List[int]) -> TreeNode:

def buildBST(l: int, r: int) -> TreeNode:

if l > r: return None

m = l + (r - l) // 2

root = TreeNode(nums[m])

root.left = buildBST(l, m - 1)

root.right = buildBST(m + 1, r)

return root

return buildBST(0, len(nums) - 1)

JavaScript

// Author: Huahua

var sortedArrayToBST = function(nums) {

var buildBST = function(l, r) {

if (l > r) return null;

let m = l + Math.floor((r - l) / 2);

let root = new TreeNode(nums[m]);

root.left = buildBST(l, m - 1);

root.right = buildBST(m + 1, r);

return root;

}

return buildBST(0, nums.length - 1);

};

花花酱 LeetCode 35. Search Insert Position

By zxi on January 31, 2020

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Example 1:

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

Example 2:

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

Example 3:

Input: [1,3,5,6], 7
Output: 4

Example 4:

Input: [1,3,5,6], 0
Output: 0

Solution: Binary Search

Find the number or upper bound if doesn’t exist.

Time complexity: O(logn)
Space complexity: O1)

C++

// Author: Huahua

class Solution {

public:

int searchInsert(vector<int>& nums, int target) {

int l = 0, r = nums.size();

while (l < r) {

int m = l + (r - l) / 2;

if (nums[m] == target)

return m;

else if (nums[m] > target)

r = m;

else

l = m + 1;

}

return l;

}

};

花花酱 LeetCode 235. Lowest Common Ancestor of a Binary Search Tree

By zxi on January 29, 2020

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given binary search tree: root = [6,2,8,0,4,7,9,null,null,3,5]

Example 1:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

Example 2:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Note:

All of the nodes’ values will be unique.
p and q are different and both values will exist in the BST.

Solution: Recursion

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

C++

// Author: Huahua

class Solution {

public:

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {

if (p->val < root->val && q->val < root->val)

return lowestCommonAncestor(root->left, p, q);

if (p->val > root->val && q->val > root->val)

return lowestCommonAncestor(root->right, p, q);

return root;

}

};

Posts tagged as “easy”

花花酱 LeetCode 1351. Count Negative Numbers in a Sorted Matrix

Solution 1: Brute Force

C++

Solution 2: Find the frontier

C++

花花酱 LeetCode 1342. Number of Steps to Reduce a Number to Zero

Solution: Simulation

C++

花花酱 LeetCode 108. Convert Sorted Array to Binary Search Tree

Solution: Recursion

C++

Java

Python3

JavaScript

花花酱 LeetCode 35. Search Insert Position

Solution: Binary Search

C++

花花酱 LeetCode 235. Lowest Common Ancestor of a Binary Search Tree

Solution: Recursion

C++