This is the 24th day of my participation in the August More Text Challenge

Offer 49

The title

We call numbers that contain only the prime factors 2, 3, and 5 Ugly numbers. Find the NTH ugly number in ascending order.

Example:

Input: n = 10 Output: 12 Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 are the first 10 ugly numbers.Copy the code

Description:

  1. 1Is ugly.
  2. n No more than1690.

Methods a

Simple method: according to the definition of ugly number, contains only qualitative factor 2,3,5 number, then we can according to the first count 1 output afterlife behind all the ugly ugly, because 2,3,5 contains only qualitative factor, so we give the minimum number of ugly respectively 1 2,3,5 on qualitative factor, then produced a number of three ugly;

The problem is to find the NTH ugly number from small to large. According to the above method of ugly number production, we can add the smallest ugly number of the three numbers to the array each time for subsequent production. Set three Pointers to three quality factors which ugly number is used to produce;

class Solution { public int nthUglyNumber(int n) { int[] res = new int[n]; res[0] = 1; int i = 0, j = 0, k = 0, len = 1; while(len < n) { int t = Math.min(2 * res[i], Math.min(3 * res[j], 5 * res[k])); if (2 * res[i] == t) i ++; if (3 * res[j] == t) j ++; if (5 * res[k] == t) k ++; res[len ++] = t; } return res[n - 1]; }}Copy the code

Time complexity: O(n)

Space complexity: O(n)

The sword refers to Offer 50. The first character that appears only once

The title

Find the first character in the string s that occurs only once. If not, a single space is returned. The s contains only lowercase letters.

Example:

S = "abaccdeff" return "b" s = "return ""Copy the code

Limitations:

0 <= the length of s <= 50000Copy the code

Methods a

Hash table: Iterate over a string, recording the number of occurrences of each character; When the second time is traversed from the beginning, the number of occurrences of the character is 1, and the character is returned. Otherwise, if no character appears only once, return ‘ ‘;

class Solution { public char firstUniqChar(String s) { HashMap<Character, Integer> map = new HashMap<>(); for (int i = 0; i < s.length(); i ++ ) { char c = s.charAt(i); map.put(c, map.getOrDefault(c, 0) + 1); } for (int i = 0; i < s.length(); i ++ ) if (map.get(s.charAt(i)) == 1) return s.charAt(i); return ' '; }}Copy the code

Time complexity: O(n)

Space complexity: O(1)