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
Is ugly.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)