Press "Enter" to skip to content

Posts tagged as “easy”

花花酱 LeetCode 1128. Number of Equivalent Domino Pairs

By zxi on July 20, 2019

Given a list of dominoes, dominoes[i] = [a, b] is equivalent to dominoes[j] = [c, d] if and only if either (a==c and b==d), or (a==d and b==c) – that is, one domino can be rotated to be equal to another domino.

Return the number of pairs (i, j) for which 0 <= i < j < dominoes.length, and dominoes[i] is equivalent to dominoes[j].

Example 1:

Input: dominoes = [[1,2],[2,1],[3,4],[5,6]]
Output: 1

Constraints:

  • 1 <= dominoes.length <= 40000
  • 1 <= dominoes[i][j] <= 9

Solution: HashTable

Count how many times each key occurred so far.

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

C++

花花酱 LeetCode 1108. Defanging an IP Address

By zxi on July 11, 2019

Given a valid (IPv4) IP address, return a defanged version of that IP address.

A defanged IP address replaces every period "." with "[.]".

Example 1:

Input: address = "1.1.1.1"
Output: "1[.]1[.]1[.]1"

Example 2:

Input: address = "255.100.50.0"
Output: "255[.]100[.]50[.]0"

Constraints:

  • The given address is a valid IPv4 address.



Solution: String

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

C++

花花酱 LeetCode 1104. Path In Zigzag Labelled Binary Tree

By zxi on July 1, 2019

In an infinite binary tree where every node has two children, the nodes are labelled in row order.

In the odd numbered rows (ie., the first, third, fifth,…), the labelling is left to right, while in the even numbered rows (second, fourth, sixth,…), the labelling is right to left.

Given the label of a node in this tree, return the labels in the path from the root of the tree to the node with that label.

Example 1:

Input: label = 14
Output: [1,3,4,14]

Example 2:

Input: label = 26
Output: [1,2,6,10,26]

Constraints:

  • 1 <= label <= 10^6

Solution: Math

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

C++

花花酱 LeetCode 1051. Height Checker

By zxi on May 27, 2019

Students are asked to stand in non-decreasing order of heights for an annual photo.

Return the minimum number of students not standing in the right positions.  (This is the number of students that must move in order for all students to be standing in non-decreasing order of height.)

Example 1:

Input: [1,1,4,2,1,3]
Output: 3
Explanation: 
Students with heights 4, 3 and the last 1 are not standing in the right positions.

Note:

  1. 1 <= heights.length <= 100
  2. 1 <= heights[i] <= 100

Solution: Sorting

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

C++

花花酱 LeetCode 1041. Robot Bounded In Circle

By zxi on May 14, 2019

On an infinite plane, a robot initially stands at (0, 0) and faces north.  The robot can receive one of three instructions:

  • "G": go straight 1 unit;
  • "L": turn 90 degrees to the left;
  • "R": turn 90 degress to the right.

The robot performs the instructions given in order, and repeats them forever.

Return true if and only if there exists a circle in the plane such that the robot never leaves the circle.

Example 1:

Input: "GGLLGG"
Output: true
Explanation: 
The robot moves from (0,0) to (0,2), turns 180 degrees, and then returns to (0,0).
When repeating these instructions, the robot remains in the circle of radius 2 centered at the origin.

Example 2:

Input: "GG"
Output: false
Explanation: 
The robot moves north indefinitely.

Example 3:

Input: "GL"
Output: true
Explanation: 
The robot moves from (0, 0) -> (0, 1) -> (-1, 1) -> (-1, 0) -> (0, 0) -> ...

Note:

  1. 1 <= instructions.length <= 100
  2. instructions[i] is in {'G', 'L', 'R'}

Solution: Simulation

When instructions end, if the robot is back to (0,0) or is not facing north (which guarantees it will come back to 0, 0 for another 1 or 3 rounds)

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

C++