316. Remove Duplicate Letters ---- M ~~~~~~~~~

Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Note: This question is the same as 1081: https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/

 

Example 1:

Input: s = "cdadabcc"
Output: "adbc"

Example 2:

Input: s = "abcd"
Output: "abcd"

Example 3:

Input: s = "ecbacba"
Output: "eacb"

Example 4:

Input: s = "leetcode"
Output: "letcod"

 

Constraints:

• 1 <= s.length <= 104
• s consists of lowercase English letters.

A:
就是每次从后往前数，知道全部发现string里的字符，然后在该位置i之前的字符里找到最小的char。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
    string removeDuplicateLetters(string s) {
        int flag = 0;
        for(char ch : s){
            flag |= 1<<(ch-'a');
        }
        return helper(s,0, flag);
    }
private:
    // count backward, until we find all chars, then find all 
    string helper(string s, int start, int flag){// flag[i] == 0, means i+'a' need to be found
        if (start >= s.length() || flag ==0){ // stop condition
            return "";
        }
        int newFlag = 0;
        int i = s.size()-1;
        for( ; i>=start;i--){
            int mask = 1<<(s[i] -'a');
            if(mask & flag){// if exist
                newFlag |= mask;
            }
            if(newFlag == flag){
                break;
            }
        }
        // find the minChar;
        char minChar = s[i];
        int minIndex = i;
        for (int j = i-1; j >=start; j--) {
            int mask = 1<<(s[j] - 'a');
            if(mask&flag){
                if(s[j] <= minChar){
                    minChar = s[j];
                    minIndex = j;
                }
            }
        }
        flag -= 1<< (minChar - 'a');
        return string(1,minChar)+helper(s,minIndex+1,flag);
    }
};

Mistakes:

1: helper() 里没有做stop condition 检测。  

而且后来也没有做flag ==0 的检测

2：Line 30,  应该是从后向前检测的。  然而我写成从前向后了。 该死

3：同样的， line 33 ,应该有等号。

4： line 6, 第一遍写错了。写成了加号。  该死

***************第二遍的时候， 用了记录所有的位置 。然后每次寻找左右发生的最后一个位置。 并在所有char的最先一个位置。*****然而，速度才超过了22%.上面的超过97%

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

class Solution { public: string removeDuplicateLetters(string s) { unordered_map<char,vector<int>> M; for(int i =s.length()-1; i>=0; i--){ M[s[i]].push_back(i); } string res=""; while(not M.empty()){ //among the last appearance index of 'a'->'z', find the minIndex int minLastIndex = s.length()-1; for(char ch = 'a';ch<='z'; ch++){ if(M.find(ch) != M.end()){ minLastIndex = min(minLastIndex, M[ch].front()); } } // now among all values, if it is bool findMinChar=false; int deletedIndex = 0; for(char ch = 'a';ch<='z'; ch++){ if(M.find(ch) != M.end() ){ if(not findMinChar && ( M[ch].back() <= minLastIndex)){ res+= ch; deletedIndex = M[ch].back(); M.erase(ch); findMinChar = true; continue; } if(findMinChar ){ while((not M[ch].empty()) && M[ch].back()<deletedIndex){ M[ch].pop_back(); } if(M[ch].empty()) M.erase(ch); } } } } return res; } };

278. First Bad Version （easy)

Q:

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

A:

二分查找。 检测过得，标记出来，不去检查其邻居

// Forward declaration of isBadVersion API. bool isBadVersion(int version); class Solution { public: int firstBadVersion(int n) { int low = 1, high = n; // cannot use high as n+1, as it can overflow int res = n; while(low <= high) // low is inclusive, high is exclusive { int mid = low + (high -low)/2; // cannot use (high+low)/2, may overflow if(isBadVersion(mid)) { res = mid; // possible high= mid-1; }else{ low = mid+1; } } return res; } };

Mistakes:

关键是一开始isBadVersion（）的结果的意思没有搞清楚

另外， high = n+1 会造成overflow,  mid  = (low+high)/2 也会overflow

********就是简单的二分查找 ***********不是最优的，有重复call API **************

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        return helper(0,n);
    }
    private int helper(int base, int n){// n indcates from 0   while base is the result 
        if(n <= 1)
            return base+n;
        int mid = (n+1)/2;
        if(isBadVersion(base+mid)){
            if( mid == 1 || !isBadVersion(base+mid-1))
                return base+mid;
            else
                return helper(base,mid-1);
        }else
            return helper(base+mid, n-mid);
    }
}

Note:
其实上面这个 k==0 和 k==1 可以合并在一起， 算了，清晰可读更重要

Nim Game

Q:

You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.

Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.

For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.

A:

public class Solution {
    public boolean canWinNim(int n) {
        return n%4 != 0;
    }
}
 

313. Super Ugly Number ---M

Write a program to find the nth super ugly number.

Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k.

Example:

Input: n = 12, primes = [2,7,13,19]
Output: 32 
Explanation: [1,2,4,7,8,13,14,16,19,26,28,32] is the sequence of the first 12 
             super ugly numbers given primes = [2,7,13,19] of size 4.

Note:

• 1 is a super ugly number for any given primes.
• The given numbers in primes are in ascending order.
• 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000.
• The nth super ugly number is guaranteed to fit in a 32-bit signed integer.

A:

动态规划，ugly number一定是由一个较小的ugly number乘以2，3或5得到的。

先开一个数组记录所有的ugly number。

然后开一个变量数组A，一开始都是零，指向数组的第0位。    A[i]是ugly number的index，

A[i] * primes[i] > current ugly number

每一次取Min(A[i] * primes[i])，找到这个数之后，对应的A[i]加一，指向数组的下一位。

class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        vector<int> list{1};
        int m = primes.size();
        vector<int> Index(m, 0);
        while(list.size()<n){
            vector<int> V;
            int last = list.back();
            for(int i =0;i<m; i++){ // for each prime number
                while(list[Index[i]]*primes[i] <= last){
                    Index[i]++;
                }
                V.push_back(list[Index[i]]*primes[i]);
            }
            list.push_back(*min_element(V.begin(), V.end()));
        }
        return list[n-1];
    }
};

Mistakes:
第二遍的时候，
1：  在while中，以为不会有相等的。  因此只用了 < ，这样是不对的。
2：  如果res 改成list,  会超时

****************用 min-heap 会超时****************

public class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        Queue<Integer> minHeap = new PriorityQueue(n*primes.length,new Comparator<Integer>(){
            public int compare(Integer a, Integer b){
                return a-b;
            } 
        });
        minHeap.add(1);
        Set<Integer> set = new HashSet();
        int lastVal = 0, count = 0;
        while(count < n){
            int val = minHeap.poll();
            for(int i =0;i<primes.length; i++)
                if(val <= Integer.MAX_VALUE / primes[i] && !set.contains(val*primes[i])){
                    minHeap.add(val * primes[i]);
                    set.add(val* primes[i]);
                }
            count ++;
            lastVal = val;
        }
        return lastVal;
    }
}
 

264. Ugly Number II --------M

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. 

Example:

Input: n = 10
Output: 12
Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note:  

1. 1 is typically treated as an ugly number.
2. n does not exceed 1690.

A:

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> V{1,2,3,4,5};
        int i2=0,i3=0,i5=0;
        while(V.size()<n){
            int last = V.back();
            while(V[i2] * 2 <= last){
                i2++;
            }
            while(V[i3] * 3 <= last){
                i3++;
            }
            while(V[i5] * 5 <= last){
                i5++;
            }
            V.push_back(min( min(V[i2]*2, V[i3]*3), V[i5]*5));
        }
        return V[n-1];
    }
};

就是用最小堆保存已经发现了的数字的可能2,3,5乘积。

import java.util.*;
public class Solution {
    public int nthUglyNumber(int n) {
        Queue<Integer> queue = new PriorityQueue(3*n,new Comparator<Integer>(){
            public int compare(Integer a,Integer b){
                return a-b;
            }
        });
        Set<Integer> found = new HashSet<Integer>();
        queue.offer(1);
        found.add(1);
        for(int i =0;i<n-1;i++){
            int val = queue.poll();
            if(val <= Integer.MAX_VALUE/2)
                helper(found,2*val,queue);
            if(val <= Integer.MAX_VALUE/3)
                helper(found,3*val,queue);
            if(val <= Integer.MAX_VALUE/5)
                helper(found,5*val,queue);
        }
        return queue.poll();
    }
    private void helper(Set<Integer> set, int val,Queue<Integer> queue){
        if(!set.contains(val))
            queue.offer(val);
        set.add(val);
    }
}

Mistakes:

1： 最小堆的声明
2： 可能有重复，因此需要一个Set
3:   int 类型，终极计算过程，可能有溢出

Ugly Number

Q:

Write a program to check whether a given number is an ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

Example 1:

Input: 6
Output: true
Explanation: 6 = 2 × 3

Example 2:

Input: 8
Output: true
Explanation: 8 = 2 × 2 × 2

Example 3:

Input: 14
Output: false 
Explanation: 14 is not ugly since it includes another prime factor 7.

Note:

1. 1 is typically treated as an ugly number.
2. Input is within the 32-bit signed integer range: [−231,  231 − 1].

A:

递归检查即可

class Solution {
public:
    bool isUgly(int num) {
        if(num<=0)
            return false;
        
        if(num==1)
            return true;
        
        if( num %2 == 0) // can divided by 2
        {
            return isUgly(num /2);
        }else if(num %3 == 0)
        {
            return isUgly(num/3);
        }else if(num %5 ==0)
        {
            return isUgly(num/5);
        }
        return false;
    }
};

Mistakes:
 没有考虑0的情况，导致死循环

Valid Anagram

Q:

Given two strings s and t, write a function to determine if t is an anagram of s.

For example,
s = "anagram", t = "nagaram", return true.
s = "rat", t = "car", return false.

Note:
You may assume the string contains only lowercase alphabets.

Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case?

A:
 Using the fact that they are only lowercase alphabets

public class Solution {
    public boolean isAnagram(String s, String t) {
        int[] A = new int[26];
        int[] B = new int[26];
        for(int i =0;i<s.length();i++)
            A[s.charAt(i)-'a']++;
        for(int i =0;i<t.length();i++)
            B[t.charAt(i)-'a']++;
        for(int i =0;i<26;i++)
            if(A[i]!=B[i])
                return false;
        return true;
    }
}

Mistakes: