刷题记录

Problem:  and  T  are strings composed of lowercase letters. In  S , no letter occurs more than once. S  was sorted in some custom order previously. We want to permute the characters of  T  so that they match the order that  S  was sorted. More specifically, if  x  occurs before  y  in  S , then  x  should occur before  y  in the returned string. Return any permutation of  T  (as a string) that satisfies this property. Example : Input: S = "cba" T = "abcd" Output: "cbad" Explanation: "a", "b", "c" appear in S, so the order of "a", "b", "c" should be "c", "b", and "a". Since "d" does not appear in S, it can be at any position in T. "dcba", "cdba", "cbda" are also valid outputs. Note: S  has length at most  26 , and no character is repeated in  S . T  has length at most  200 . S  and  T  consist of lowercas...

Problem: Given an unsorted array, find the maximum difference between the successive elements in its sorted form. Return 0 if the array contains less than 2 elements. Example 1: Input: [3,6,9,1] Output: 3 Explanation: The sorted form of the array is [1,3,6,9], either   (3,6) or (6,9) has the maximum difference 3. Example 2: Input: [10] Output: 0 Explanation: The array contains less than 2 elements, therefore return 0. Analysis: Sort all numbers into buckets. Compare the min value of the current bucket with max value of the previous bucket, we get the possible maximum gap. The size of bucket is calc from (max - min) / length + 1. The numberOfBuckets is calc from (max - min) / bucketSize + 1.  Then we can easily know which bucket a number belongs to by (number - min) / bucketSize.  Not all buckets are filled with numbers, we need to skip those empty buckets when comparing for the maximum gap. Solution: class Solution { ...

Problem: Given a string, sort it in decreasing order based on the frequency of characters. Example 1: Input: "tree" Output: "eert" Explanation: 'e' appears twice while 'r' and 't' both appear once. So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer. Example 2: Input: "cccaaa" Output: "cccaaa" Explanation: Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer. Note that "cacaca" is incorrect, as the same characters must be together. Example 3: Input: "Aabb" Output: "bbAa" Explanation: "bbaA" is also a valid answer, but "Aabb" is incorrect. Note that 'A' and 'a' are treated as two different characters. Analysis: Bucket sort...... Solution: class Solution { public String frequencySort ( String s) { ...

Problem: Given a non-empty list of words, return the  k  most frequent elements. Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, then the word with the lower alphabetical order comes first. Example 1: Input: ["i", "love", "leetcode", "i", "love", "coding"], k = 2 Output: ["i", "love"] Explanation: "i" and "love" are the two most frequent words. Note that "i" comes before "love" due to a lower alphabetical order. Example 2: Input: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4 Output: ["the", "is", "sunny", "day"] Explanation: "the", "is", "sunny" and "day" are the four most frequent ...

Problem: Given a non-empty array of integers, return the  k  most frequent elements. For example, Given  [1,1,1,2,2,3]  and k = 2, return  [1,2] . Note:  You may assume  k  is always valid, 1 ≤  k  ≤ number of unique elements. Your algorithm's time complexity  must be  better than O( n  log  n ), where  n  is the array's size. Analysis: Bucket sort. Use List<Integer>[] to sort the frequency. Index is the frequency, the numbers in the bucket[frequency]  list have the frequency in the array. Solution: Note bucket has to initialize to be length of nums.length + 1. Frequency is 1 based.  class Solution { public List< Integer > topKFrequent ( int [] nums, int k) { List< Integer > res = new ArrayList<> (); if (nums == null || nums . length == 0 ) return res; Map< Integer , Integer > map = new Hash...