660. Remove 9

Start from integer 1, remove any integer that contains 9 such as 9, 19, 29…

Now, you will have a new integer sequence [1, 2, 3, 4, 5, 6, 7, 8, 10, 11, …].

Given an integer n, return the nth (1-indexed) integer in the new sequence.

745. Prefix and Suffix Search

Design a special dictionary with some words that searchs the words in it by a prefix and a suffix.

Implement the WordFilter class:

• WordFilter(string[] words) Initializes the object with the words in the dictionary.
• f(string prefix, string suffix) Returns the index of the word in the dictionary, which has the prefix prefix and the suffix suffix. If there is more than one valid index, return the largest of them. If there is no such word in the dictionary, return -1.

302. Smallest Rectangle Enclosing Black Pixels

You are given an m x n binary matrix image where 0 represents a white pixel and 1 represents a black pixel.

The black pixels are connected (i.e., there is only one black region). Pixels are connected horizontally and vertically.

Given two integers x and y that represents the location of one of the black pixels, return the area of the smallest (axis-aligned) rectangle that encloses all black pixels.

You must write an algorithm with less than O(mn) runtime complexity

1632. Rank Transform of a Matrix

Given an m x n matrix, return a new matrix answer where answer[row][col] is the rank of matrix[row][col].

The rank is an integer that represents how large an element is compared to other elements. It is calculated using the following rules:

• The rank is an integer starting from 1.
• If two elements p and q are in the same row or column, then:

• If p < q then rank(p) < rank(q)
• If p == q then rank(p) == rank(q)
• If p > q then rank(p) > rank(q)

• The rank should be as small as possible.

The test cases are generated so that answer is unique under the given rules.

664. Strange Printer

There is a strange printer with the following two special properties:

• The printer can only print a sequence of the same character each time.
• At each turn, the printer can print new characters starting from and ending at any place and will cover the original existing characters.

Given a string s, return the minimum number of turns the printer needed to print it.

726. Number of Atoms

Given a string formula representing a chemical formula, return the count of each atom.

The atomic element always starts with an uppercase character, then zero or more lowercase letters, representing the name.

One or more digits representing that element’s count may follow if the count is greater than 1. If the count is 1, no digits will follow.

• For example, “H2O” and “H2O2” are possible, but “H1O2” is impossible.

Two formulas are concatenated together to produce another formula.

• For example, “H2O2He3Mg4” is also a formula.

A formula placed in parentheses, and a count (optionally added) is also a formula.

• For example, “(H2O2)” and “(H2O2)3” are formulas.

Return the count of all elements as a string in the following form: the first name (in sorted order), followed by its count (if that count is more than 1), followed by the second name (in sorted order), followed by its count (if that count is more than 1), and so on.

The test cases are generated so that all the values in the output fit in a 32-bit integer.

1691. Maximum Height by Stacking Cuboids

Given n cuboids where the dimensions of the ith cuboid is cuboids[i] = [widthi, lengthi, heighti] (0-indexed). Choose a subset of cuboids and place them on each other.

You can place cuboid i on cuboid j if widthi <= widthj and lengthi <= lengthj and heighti <= heightj. You can rearrange any cuboid’s dimensions by rotating it to put it on another cuboid.

Return the maximum height of the stacked cuboids.

1610. Maximum Number of Visible Points

You are given an array points, an integer angle, and your location, where location = [posx, posy] and points[i] = [xi, yi] both denote integral coordinates on the X-Y plane.

Initially, you are facing directly east from your position. You cannot move from your position, but you can rotate. In other words, posx and posy cannot be changed. Your field of view in degrees is represented by angle, determining how wide you can see from any given view direction. Let d be the amount in degrees that you rotate counterclockwise. Then, your field of view is the inclusive range of angles [d - angle/2, d + angle/2].

You can see some set of points if, for each point, the angle formed by the point, your position, and the immediate east direction from your position is in your field of view.

There can be multiple points at one coordinate. There may be points at your location, and you can always see these points regardless of your rotation. Points do not obstruct your vision to other points.

Return the maximum number of points you can see.

1240. Tiling a Rectangle with the Fewest Squares

Given a rectangle of size n x m, return the minimum number of integer-sided squares that tile the rectangle.

818. Race Car

Your car starts at position 0 and speed +1 on an infinite number line. Your car can go into negative positions. Your car drives automatically according to a sequence of instructions ‘A’ (accelerate) and ‘R’ (reverse):

• When you get an instruction ‘A’, your car does the following:

  • position += speed
  • speed *= 2

• When you get an instruction ‘R’, your car does the following:

  • If your speed is positive then speed = -1
  • otherwise speed = 1

Your position stays the same.
For example, after commands “AAR”, your car goes to positions 0 —> 1 —> 3 —> 3, and your speed goes to 1 —> 2 —> 4 —> -1.

Given a target position target, return the length of the shortest sequence of instructions to get there.