2 different solutions in JAVA (with explanation)


  • 0
    T
    • First solution: dynamic progrmingng
    public class NestedIterator implements Iterator<Integer> {
        //In construction method, this program converts given nestedInteger sequence to a queue recursively
        Queue<Integer> q = new LinkedList<Integer>();
        public NestedIterator(List<NestedInteger> nestedList) {
            openList(nestedList);
        }
        
        public void openList(List<NestedInteger> nestedList){
            for(NestedInteger list : nestedList){
                if(list.isInteger() ){
                    q.add(list.getInteger() );
                }
                else{
                    openList(list.getList());
                }
            }
        }
    
        @Override
        public Integer next() {
            return q.poll();
        }
    
        @Override
        public boolean hasNext() {
            return !q.isEmpty();
        }
    }
    
    • Second solution: mathematical combination
      For any given situation m x n, the numbers of left moving and down moving are fixed, namely n and m. Thus, for the total m+n moves, our task is to find n left shifts and the reminding moves are down move.
    import java.math.BigInteger;
    public class Solution {
        public int uniquePaths(int m, int n) {
            m -= 1;
            n -= 1;
            return combination(m+n, n);
        }
        
        public int combination(int total, int n){
            BigInteger result = BigInteger.valueOf(1);
            for(int i = total; i >total-n;i--){
                result = result.multiply(BigInteger.valueOf(i));
            }
            BigInteger numerator = BigInteger.valueOf(1);
            for(int i = n; i > 0; i--){
                numerator = numerator.multiply(BigInteger.valueOf(i));
            }
            result = result.divide(numerator);
            return result.intValue();
        }
    }
    

Log in to reply
 

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