LeetCode Adding Reversed Numbers

/**
 * The Antique Comedians of Malidinesia prefer comedies to tragedies. Unfortunately, most of the ancient
 * plays are tragedies. Therefore the dramatic advisor of ACM has decided to transfigure some tragedies
 * into comedies. Obviously, this work is very hard because the basic sense of the play must be kept intact,
 * although all the things change to their opposites. For example the numbers: if any number appears in
 * the tragedy, it must be converted to its reversed form before being accepted into the comedy play.
 * Reversed number is a number written in arabic numerals but the order of digits is reversed. The
 * first digit becomes last and vice versa. For example, if the main hero had 1245 strawberries in the
 * tragedy, he has 5421 of them now. Note that all the leading zeros are omitted. That means if the
 * number ends with a zero, the zero is lost by reversing (e.g. 1200 gives 21). Also note that the reversed
 * number never has any trailing zeros.
 * ACM needs to calculate with reversed numbers. Your task is to add two reversed numbers and
 * output their reversed sum. Of course, the result is not unique because any particular number is a
 * reversed form of several numbers (e.g. 21 could be 12, 120 or 1200 before reversing). Thus we must
 * assume that no zeros were lost by reversing (e.g. assume that the original number was 12).
 * Input
 * The input consists of N cases. The first line of the input contains only positive integer N. Then follow
 * the cases. Each case consists of exactly one line with two positive integers separated by space. These
 * are the reversed numbers you are to add. Numbers will be at most 200 characters long.
 * Output
 * For each case, print exactly one line containing only one integer — the reversed sum of two reversed
 * numbers. Omit any leading zeros in the output.
 * Sample Input
 * 3
 * 24 1
 * 4358 754
 * 305 794
 * Sample Output
 * 34
 * 1998
 * 1
 */

//https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=654

import java.math.BigInteger;
import java.util.Scanner;

public class AddingReversedNumbers {

public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int numberOfTestCases = input.nextInt();
while (numberOfTestCases != 0) {
BigInteger first = input.nextBigInteger();
BigInteger second = input.nextBigInteger();
StringBuilder firstString = new StringBuilder(first + "");
StringBuilder secondString = new StringBuilder(second + "");
BigInteger firstReversed = new BigInteger(firstString.reverse()
.toString());
BigInteger secondReversed = new BigInteger(secondString.reverse()
.toString());
BigInteger result = firstReversed.add(secondReversed);
String resultReversed = new StringBuilder(result + "").reverse()
.toString();
System.out.println(resultReversed.replaceFirst("^0*", ""));
numberOfTestCases--;
}
}
}

Binary Tree Maximum Path Sum

// Given a binary tree, find the maximum path sum.

// For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

// For example:
// Given the below binary tree,

//        1
//       / \
//      2   3
// Return 6.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class BinaryTreeMaximumPathSum {
    int max = Integer.MIN_VALUE;
   
    public int maxPathSum(TreeNode root) {
        maxPathSumRecursive(root);
        return max;
    }
   
    private int maxPathSumRecursive(TreeNode root) {
        if(root == null) {
            return 0;
        }
       
        int left = Math.max(maxPathSumRecursive(root.left), 0);
        int right = Math.max(maxPathSumRecursive(root.right), 0);
       
        max = Math.max(max, root.val + left + right);
       
        return root.val + Math.max(left, right);
    }
}

Multiply Strings

// Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.

// Note:

    // The length of both num1 and num2 is < 110.
    // Both num1 and num2 contains only digits 0-9.
    // Both num1 and num2 does not contain any leading zero.
    // You must not use any built-in BigInteger library or convert the inputs to integer directly.

public class MultiplyStrings {
    public String multiply(String num1, String num2) {
        int m = num1.length();
        int n = num2.length();
        int[] pos = new int[m + n];
       
        for(int i = m - 1; i >= 0; i--) {
            for(int j = n - 1; j >= 0; j--) {
                int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                int p1 = i + j;
                int p2 = i + j + 1;
                int sum = mul + pos[p2];
               
                pos[p1] += sum / 10;
                pos[p2] = (sum) % 10;
            }
        }
       
        StringBuilder sb = new StringBuilder();

        for(int p : pos) if(!(sb.length() == 0 && p == 0)) {
            sb.append(p);
        }
       
        return sb.length() == 0 ? "0" : sb.toString();
    }
}

Longest Substring With At Most K Distinct Characters

// Given a string, find the length of the longest substring T that contains at most k distinct characters.

// For example, Given s = “eceba” and k = 2,

// T is "ece" which its length is 3.

public class LongestSubstringWithAtMostKDistinctCharacters {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
       
    int[] count = new int[256];     // there are 256 ASCII characters in the world
   
    int i = 0;  // i will be behind j
    int num = 0;
    int res = 0;
   
    for (int j = 0; j < s.length(); j++) {
        if (count[s.charAt(j)] == 0) {    // if count[s.charAt(j)] == 0, we know that it is a distinct character
            num++;
        }
       
        count[s.charAt(j)]++;

        while (num > k && i < s.length()) {     // sliding window
            count[s.charAt(i)]--;

            if (count[s.charAt(i)] == 0){
                num--;
            }

            i++;
        }

        res = Math.max(res, j - i + 1);
    }

    return res;
    }
}

Longest Palindromic Substring

//Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

//Example:
//Input: "babad"
//Output: "bab"

//Note: "aba" is also a valid answer.

//Example:
//Input: "cbbd"
//Output: "bb"

class LongestPalindromicSubstring {
    public String longestPalindrome(String s) {
        if(s == null || s.length() == 0) {
            return "";
        }
       
        String longestPalindromicSubstring = "";
        for(int i = 0; i < s.length(); i++) {
            for(int j = i + 1; j <= s.length(); j++) {
                if(j - i > longestPalindromicSubstring.length() && isPalindrome(s.substring(i, j))) {
                    longestPalindromicSubstring = s.substring(i, j);
                }
            }
        }
       
        return longestPalindromicSubstring;
    }
   
    public boolean isPalindrome(String s) {
        int i = 0;
        int j = s.length() - 1;
        while(i <= j) {
            if(s.charAt(i++) != s.charAt(j--)) {
                return false;
            }
        }
       
        return true;
    }
}

Longest Palindrome

public class LongestPalindrome {
    public int longestPalindrome(String s) {
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
       
        int count = 0;
       
        for(int i = 0; i < s.length(); i++) {
            if(!map.containsKey(s.charAt(i))) {
                map.put(s.charAt(i), (int)(s.charAt(i)));
            } else {
                map.remove(s.charAt(i));
                count++;
            }
        }
       
        return map.isEmpty() ? count * 2 : count * 2 + 1;
    }
}

Longest Common Prefix

class LongestCommonPrefix {
    public String longestCommonPrefix(String[] strs) {
        if(strs == null || strs.length == 0) {
            return "";
        }
       
        String s = strs[0];
        for(int i = 0; i < s.length(); i++) {
            char current = s.charAt(i);
            for(int j = 1; j < strs.length; j++) {
                if(i >= strs[j].length() || strs[j].charAt(i) != current) {
                    return s.substring(0, i);
                }
            }
        }
       
        return s;
    }
}

Generate Parentheses

//Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
//
//For example, given n = 3, a solution set is:
//
//[
  //"((()))",
  //"(()())",
  //"(())()",
  //"()(())",
  //"()()()"
//]

class GenerateParentheses {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<String>();
        generateParenthesisRecursive(result, "", 0, 0, n);
       
        return result;
    }
   
    public void generateParenthesisRecursive(List<String> result, String current, int open, int close, int n) {
        if(current.length() == n * 2) {
            result.add(current);
            return;
        }
       
        if(open < n) {
            generateParenthesisRecursive(result, current + "(", open + 1, close, n);
        }
       
        if(close < open) {
            generateParenthesisRecursive(result, current + ")", open, close + 1, n);
        }
    }
}

Decode Ways

// A message containing letters from A-Z is being encoded to numbers using the following mapping:

// 'A' -> 1
// 'B' -> 2
// ...
// 'Z' -> 26

// Given an encoded message containing digits, determine the total number of ways to decode it.

// For example,
// Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

// The number of ways decoding "12" is 2.

public class DecodeWays {
    public int numDecodings(String s) {
        int n = s.length();

        if(n == 0) {
            return 0;
        }
       
        int[] dp = new int[n + 1];
        dp[n] = 1;
        dp[n - 1] = s.charAt(n - 1) != '0' ? 1 : 0;
       
        for(int i = n - 2; i >= 0; i--) {
            if(s.charAt(i) == '0') {
                continue;
            } else {
                dp[i] = (Integer.parseInt(s.substring(i, i + 2)) <= 26) ? dp[i + 1] + dp[i + 2] : dp[i + 1];
            }
        }
       
        return dp[0];
    }
}

Count And Say

// The count-and-say sequence is the sequence of integers beginning as follows:
// 1, 11, 21, 1211, 111221, ...

// 1 is read off as "one 1" or 11.
// 11 is read off as "two 1s" or 21.
// 21 is read off as "one 2, then one 1" or 1211.
// Given an integer n, generate the nth sequence.

// Note: The sequence of integers will be represented as a string.

public class CountAndSay {
    public String countAndSay(int n) {
        String s = "1";

        for(int i = 1; i < n; i++) {
            s = helper(s);
        }
       
        return s;
    }
   
    public String helper(String s) {
        StringBuilder sb = new StringBuilder();
        char c = s.charAt(0);
        int count = 1;
       
        for(int i = 1; i < s.length(); i++) {
            if(s.charAt(i) == c) {
                count++;
            } else {
                sb.append(count);
                sb.append(c);
                c = s.charAt(i);
                count = 1;
            }
        }
       
        sb.append(count);
        sb.append(c);

        return sb.toString();
    }
}

Add Binary

// Given two binary strings, return their sum (also a binary string).

// For example,
// a = "11"
// b = "1"
// Return "100"

public class AddBinary {
    public String addBinary(String a, String b) {
        StringBuilder result = new StringBuilder();
       
        int carry = 0;
        int i = a.length() - 1;
        int j = b.length() - 1;
       
        while(i >= 0 || j >= 0) {
            int sum = carry;

            if(i >= 0) {
                sum += a.charAt(i--) - '0';
            }

            if(j >= 0) {
                sum += b.charAt(j--) - '0';
            }

            result.append(sum % 2);
            carry = sum / 2;
        }

        if(carry != 0) {
            result.append(carry);
        }

        return result.reverse().toString();
    }
}

Flatten Nested List Iterator

// Given a nested list of integers, implement an iterator to flatten it.

// Each element is either an integer, or a list -- whose elements may also be integers or other lists.

// Example 1:
// Given the list [[1,1],2,[1,1]],

// By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

// Example 2:
// Given the list [1,[4,[6]]],

// By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return null if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
public class FlattenNestedListIterator implements Iterator<Integer> {
    Stack<NestedInteger> stack = new Stack<NestedInteger>();

    public NestedIterator(List<NestedInteger> nestedList) {
        for(int i = nestedList.size() - 1; i >= 0; i--) {
            stack.push(nestedList.get(i));
        }
    }

    @Override
    public Integer next() {
        return stack.pop().getInteger();
    }

    @Override
    public boolean hasNext() {
        while(!stack.isEmpty()) {
            NestedInteger current = stack.peek();

            if(current.isInteger()) {
                return true;
            }

            stack.pop();

            for(int i = current.getList().size() - 1;  i >= 0; i--) {
                stack.push(current.getList().get(i));
            }
        }
       
        return false;
    }
}

/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i = new NestedIterator(nestedList);
 * while (i.hasNext()) v[f()] = i.next();
 */

Exclusive Time Of Functions

//Given the running logs of n functions that are executed in a nonpreemptive single threaded CPU, find the exclusive time of these functions.

//Each function has a unique id, start from 0 to n-1. A function may be called recursively or by another function.

//A log is a string has this format : function_id:start_or_end:timestamp. For example, "0:start:0" means function 0 starts from the very beginning of time 0. "0:end:0" means function 0 ends to the very end of time 0.

//Exclusive time of a function is defined as the time spent within this function, the time spent by calling other functions should not be considered as this function's exclusive time. You should return the exclusive time of each function sorted by their function id.

//Example 1:
//Input:
//n = 2
//logs =
//["0:start:0",
 //"1:start:2",
 //"1:end:5",
 //"0:end:6"]
//Output:[3, 4]
//Explanation:
//Function 0 starts at time 0, then it executes 2 units of time and reaches the end of time 1.
//Now function 0 calls function 1, function 1 starts at time 2, executes 4 units of time and end at time 5.
//Function 0 is running again at time 6, and also end at the time 6, thus executes 1 unit of time.
//So function 0 totally execute 2 + 1 = 3 units of time, and function 1 totally execute 4 units of time.
//Note:
//Input logs will be sorted by timestamp, NOT log id.
//Your output should be sorted by function id, which means the 0th element of your output corresponds to the exclusive time of function 0.
//Two functions won't start or end at the same time.
//Functions could be called recursively, and will always end.
//1 <= n <= 100

class ExclusiveTimeOfFunctions {
    public int[] exclusiveTime(int n, List<String> logs) {
        Stack<Integer> stack = new Stack <Integer>();
        int[] result = new int[n];
        String[] current = logs.get(0).split(":");
        stack.push(Integer.parseInt(current[0]));
        int i = 1;
        int previous = Integer.parseInt(current[2]);
        while (i < logs.size()) {
            current = logs.get(i).split(":");
            if (current[1].equals("start")) {
                if (!stack.isEmpty()) {
                    result[stack.peek()] += Integer.parseInt(current[2]) - previous;
                }
                stack.push(Integer.parseInt(current[0]));
                previous = Integer.parseInt(current[2]);
            } else {
                result[stack.peek()] += Integer.parseInt(current[2]) - previous + 1;
                stack.pop();
                previous = Integer.parseInt(current[2]) + 1;
            }
            i++;
        }
        return result;
    }
}

Binary Search Tree Iterator

// Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

// Calling next() will return the next smallest number in the BST.

// Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

public class BinarySearchTreeIterator {
    Stack<TreeNode> stack;

    public BSTIterator(TreeNode root) {
        stack = new Stack<TreeNode>();
       
        while(root != null) {
            stack.push(root);
            root = root.left;
        }
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return stack.isEmpty() ? false : true;
    }

    /** @return the next smallest number */
    public int next() {
        TreeNode nextSmallest = stack.pop();
        TreeNode addToStack = nextSmallest.right;
       
        while(addToStack != null) {
            stack.add(addToStack);
            addToStack = addToStack.left;
        }
       
        return nextSmallest.val;
    }
}

/**
 * Your BSTIterator will be called like this:
 * BSTIterator i = new BSTIterator(root);
 * while (i.hasNext()) v[f()] = i.next();
 */

Meeting Rooms II

// Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.

// For example,
// Given [[0, 30],[5, 10],[15, 20]],
// return 2.

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class MeetingRoomsII {
    public int minMeetingRooms(Interval[] intervals) {
        int[] starts = new int[intervals.length];
        int[] ends = new int[intervals.length];

        for(int i=0; i<intervals.length; i++) {
            starts[i] = intervals[i].start;
            ends[i] = intervals[i].end;
        }

        Arrays.sort(starts);
        Arrays.sort(ends);

        int rooms = 0;
        int endsItr = 0;

        for(int i=0; i<starts.length; i++) {
            if(starts[i]<ends[endsItr]) {
                rooms++;
            } else {
                endsItr++;
            }
        }

        return rooms;
    }
}

Moving Average From Data Stream

// Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.

// For example,
// MovingAverage m = new MovingAverage(3);
// m.next(1) = 1
// m.next(10) = (1 + 10) / 2
// m.next(3) = (1 + 10 + 3) / 3
// m.next(5) = (10 + 3 + 5) / 3

/**
 * Your MovingAverage object will be instantiated and called as such:
 * MovingAverage obj = new MovingAverage(size);
 * double param_1 = obj.next(val);
 */

public class MovingAverageFromDataStream {
    double previousSum = 0.0;
    int maxSize;
    Queue<Integer> window;

    /** Initialize your data structure here. */
    public MovingAverage(int size) {
        this.maxSize = size;
        window = new LinkedList<Integer>();
    }
   
    public double next(int val) {
        if(window.size() == maxSize) {
            previousSum -= window.remove();
        }
       
        window.add(val);
        previousSum += val;

        return previousSum / window.size();
    }
}

Reverse Words In A String

//Given an input string, reverse the string word by word.
//For example,
//Given s = "the sky is blue",
//return "blue is sky the".

public class ReverseWordsInAString {
    public String reverseWords(String s) {
        String[] words = s.trim().split("\\s+");
        String result = "";
        for(int i = words.length - 1; i > 0; i--) {
            result += words[i] + " ";
        }
       
        return result + words[0];
    }
}

Permutations of Numbers in an Array

//Given a collection of distinct numbers, return all possible permutations.
//
//For example,
//[1,2,3] have the following permutations:
//[
  //[1,2,3],
  //[1,3,2],
  //[2,1,3],
  //[2,3,1],
  //[3,1,2],
  //[3,2,1]
//]

class Permutations {
    public List<List<Integer>> permute(int[] nums) {
        LinkedList<List<Integer>> result = new LinkedList<List<Integer>>();
        result.add(new ArrayList<Integer>());
        for (int n: nums) {
            int size = result.size();
            while(size > 0) {
                List<Integer> current = result.pollFirst();
                for (int i = 0; i <= current.size(); i++) {
                    List<Integer> temp = new ArrayList<Integer>(current);
                    temp.add(i, n);
                    result.add(temp);
                }
                size--;
            }
        }

        return result;
    }
}

Poor Pigs

//There are 1000 buckets, one and only one of them contains poison, the rest are filled with water.
//They all look the same. If a pig drinks that poison it will die within 15 minutes. What is the
//minimum amount of pigs you need to figure out which bucket contains the poison within one hour.

//Answer this question, and write an algorithm for the follow-up general case.

//Follow-up:
//If there are n buckets and a pig drinking poison will die within m minutes, how many pigs (x)
//you need to figure out the "poison" bucket within p minutes? There is exact one bucket with poison.

class PoorPigs {
    public int poorPigs(int buckets, int minutesToDie, int minutesToTest) {   
        int numPigs = 0;
        while (Math.pow(minutesToTest / minutesToDie + 1, numPigs) < buckets) {
            numPigs++;
        }
       
        return numPigs;
    }
}

Plus One in an Array

//Given a non-empty array of digits representing a non-negative integer, plus one to the integer.
//
//The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.
//
//You may assume the integer does not contain any leading zero, except the number 0 itself.
//
//Example 1:
//
//Input: [1,2,3]
//Output: [1,2,4]
//Explanation: The array represents the integer 123.
//Example 2:
//
//Input: [4,3,2,1]
//Output: [4,3,2,2]
//Explanation: The array represents the integer 4321.

class Solution {
    public int[] plusOne(int[] digits) {
        for(int i = digits.length - 1; i >= 0; i--) {
            if(digits[i] < 9) {
                digits[i]++;
                return digits;
            }

            digits[i] = 0;
        }

        int[] result = new int[digits.length + 1];
        result[0] = 1;

        return result;
    }
}