Press "Enter" to skip to content

Posts tagged as “easy”

花花酱 LeetCode 83. Remove Duplicates from Sorted List

By zxi on September 30, 2019

Given a sorted linked list, delete all duplicates such that each element appear only once.

Example 1:

Input: 1->1->2
Output: 1->2

Example 2:

Input: 1->1->2->3->3
Output: 1->2->3

Solution:

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

C++

花花酱 LeetCode 58. Length of Last Word

By zxi on September 30, 2019

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.

If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

Example:

Input: "Hello World"
Output: 5

Solution:

There can be tailing spaces, e.g. “abc “, we need to trim the string first and then scan the string in reverse order until a space or reach the beginning of the string.

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

C++

花花酱 LeetCode 190. Reverse Bits

By zxi on September 30, 2019

Reverse bits of a given 32 bits unsigned integer.

Example 1:

Input: 00000010100101000001111010011100
Output: 00111001011110000010100101000000
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

Example 2:

Input: 11111111111111111111111111111101
Output: 10111111111111111111111111111111
Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10101111110010110010011101101001.

Note:

  • Note that in some languages such as Java, there is no unsigned integer type. In this case, both input and output will be given as signed integer type and should not affect your implementation, as the internal binary representation of the integer is the same whether it is signed or unsigned.
  • In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 2 above the input represents the signed integer -3 and the output represents the signed integer -1073741825.

Follow up:

If this function is called many times, how would you optimize it?

Solution: Bit operation

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

C++

花花酱 LeeCode 1207. Unique Number of Occurrences

By zxi on September 29, 2019

Given an array of integers arr, write a function that returns true if and only if the number of occurrences of each value in the array is unique.

Example 1:

Input: arr = [1,2,2,1,1,3]
Output: true
Explanation: The value 1 has 3 occurrences, 2 has 2 and 3 has 1. No two values have the same number of occurrences.

Example 2:

Input: arr = [1,2]
Output: false

Example 3:

Input: arr = [-3,0,1,-3,1,1,1,-3,10,0]
Output: true

Constraints:

  • 1 <= arr.length <= 1000
  • -1000 <= arr[i] <= 1000

Solution: HashTable

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

C++

花花酱 LeetCode 1200. Minimum Absolute Difference

By zxi on September 22, 2019

Given an array of distinct integers arr, find all pairs of elements with the minimum absolute difference of any two elements. 

Return a list of pairs in ascending order(with respect to pairs), each pair [a, b] follows

  • a, b are from arr
  • a < b
  • b - a equals to the minimum absolute difference of any two elements in arr

Example 1:

Input: arr = [4,2,1,3]
Output: [[1,2],[2,3],[3,4]]
Explanation: The minimum absolute difference is 1. List all pairs with difference equal to 1 in ascending order.

Example 2:

Input: arr = [1,3,6,10,15]
Output: [[1,3]]

Example 3:

Input: arr = [3,8,-10,23,19,-4,-14,27]
Output: [[-14,-10],[19,23],[23,27]]

Constraints:

  • 2 <= arr.length <= 10^5
  • -10^6 <= arr[i] <= 10^6

Solution: Sorting

The min abs difference could only happen between consecutive numbers in sorted form.

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

C++