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.