You only need 3 simple observations to solve this! Intuitive and well commented JAVA solution.


  • 2
    /*
    Observation 1: our highest prioirty is to move the number that is at index 0, with index 1 being 0
        For example, if we have 3004567 and we want to remove 1 digit, we defintely want to remove 3, so that we can
        get rid of the following 2 zeros, ending up with 4567, which will always give us the biggest decrease
    
    Observation 2: if there is no case of observation 1, then we want to remove the biggest number in the first ascenging sequence.
        For example, if we have 234543, we want to remove the 5 first, since after 5 the number starts going down.
        
    Observatino 3: if we have to remove more than 1 digit, every digit removal can use the same strategy, i.e we can use greedy algorithm here, aka not dp. 
    
    */
    
    public class Solution {
        public String removeKdigits(String num, int k) {
            //change to list
            List<Character> list = new ArrayList<Character>();
            for(char c : num.toCharArray()){
                list.add(c);
            }
            //we need to remove k digits
            for(int i = 0; i<k; i++){
                int size = list.size();
                //observation 1
                if(size > 1 && list.get(1) == '0'){
                    list.remove(0);
                    while(!list.isEmpty() && list.get(0) == '0'){
                        list.remove(0);
                    }
                }
                //if no observation 1, use observation 2
                if(size == list.size()){
                    for(int j = 0; j < size; j++){
                        if((j < size - 1 && list.get(j) > list.get(j+1)) || (j == size - 1)){
                            list.remove(j);
                            break;
                        }  
                    }
                }
            }
            //generate output
            if(list.size() == 0) return "0";
            StringBuilder result = new StringBuilder();
            for(Character c : list){
                result.append(c);
            }
            return result.toString();
        }
    }
    

  • 2
    B

    I think you can combine the observation1 with observation2 in a single inner loop like:

    int size = list.size();
    int j = 0;
    while(j<size-1) {
        // remaining the leading zeros, and skipping non-descending orders
        if(list.get(j) <= list.get(j+1) || list.get(j) == '0') j++;
        else{
            list.remove(j);
            break;
        }
    }
    if(j == size - 1) list.remove(j);
    

  • 0
    B

    Nice Name!~~~~~~~~~~~~~~~~


  • 1
    W

    Congrats. You are gonna be the first leetcode user who makes the U.S. president.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.