Press "Enter" to skip to content

Posts published in “Easy”

花花酱 LeetCode 783. Minimum Distance Between BST Nodes

Given a Binary Search Tree (BST) with the root node root, return the minimum difference between the values of any two different nodes in the tree.

Example :

Note:

  1. The size of the BST will be between 2 and 100.
  2. The BST is always valid, each node’s value is an integer, and each node’s value is different.

Solution 1: In order traversal 

Time complexity: O(n)

Space complexity: O(n)

C++

Related Problems:

花花酱 LeetCode 766. Toeplitz Matrix

A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same element.

Now given an M x N matrix, return True if and only if the matrix is Toeplitz.
Example 1:

Example 2:

Note:

  1. matrix will be a 2D array of integers.
  2. matrix will have a number of rows and columns in range [1, 20].
  3. matrix[i][j] will be integers in range [0, 99].

Idea:

Check m[i][j] with m[i-1][j-1]

Solution: Brute Force

Time complexity: O(n*m)

Space complexity: O(1)

C++

Java

Python3

 

 

花花酱 LeetCode 762. Prime Number of Set Bits in Binary Representation

题目大意:求给定范围内,数的二进制形式中1的个数为素数个的数字的个数。

Given two integers L and R, find the count of numbers in the range [L, R] (inclusive) having a prime number of set bits in their binary representation.

(Recall that the number of set bits an integer has is the number of 1s present when written in binary. For example, 21 written in binary is 10101 which has 3 set bits. Also, 1 is not a prime.)

Example 1:

Example 2:

Note:

  1. L, R will be integers L <= R in the range [1, 10^6].
  2. R - L will be at most 10000.

Solution 1: Brute Force

C++

 

 

Java

Python2

Python2

 

花花酱 LeetCode. 69 Sqrt(x)

题目大意:让你实现开根号函数,只需要返回整数部分。

Problem:

Implement int sqrt(int x).

Compute and return the square root of x.

x is guaranteed to be a non-negative integer.

Example 1:

Example 2:

 

 

Solution 1: Brute force

Time complexity: sqrt(x)

C++

C++ div

Java

Python3 TLE

Solution 2: Binary search

Time complexity: O(logn)

C++

Java

Python3

Solution 3: Newton’s method

C++ / float

C++ / int

Java

Python3

花花酱 LeetCode 758. Bold Words in String

题目大意:给你一个字符串和一些要加粗的单词,返回加粗后的HTML代码。

Problem:

Given a set of keywords words and a string S, make all appearances of all keywords in S bold. Any letters between <b> and </b> tags become bold.

The returned string should use the least number of tags possible, and of course the tags should form a valid combination.

For example, given that words = ["ab", "bc"] and S = "aabcd", we should return "a<b>abc</b>d". Note that returning "a<b>a<b>b</b>c</b>d" would use more tags, so it is incorrect.

Note:

  1. words has length in range [0, 50].
  2. words[i] has length in range [1, 10].
  3. S has length in range [0, 500].
  4. All characters in words[i] and S are lowercase letters.

Solution:

C++

Time complexity: O(nL^2)

Space complexity: O(n + d)

d: size of dictionary

L: max length of the word which is 10.