off-line minimum problem - llhuii's Blog

 The off-line minimum problem asks us to maintain a dynamic set of elements from the domain under the operations INSERT and EXTRACT-MIN. We are given a sequence S of n INSERT and m EXTRACT-MIN calls, where each key in is inserted exactly once. We wish to determine which key is returned by each EXTRACT-MIN call. Specifically, we wish to fill in an array , where for is the key returned by the th EXTRACT-MIN call.
static int[] offlineMinimum(int[] A, int[] E) {
int[] R = new int[A.length];
Arrays.fill(R, E.length);
int pre = 0;

// Initialize the collection of subsets.
for (int i = 0; i < E.length; ++i) {
for (int j = pre; j <= E[i]; ++j) {
R[A[j]] = i;
}
pre = E[i] + 1;
}

int[] ret = new int[E.length];
Arrays.fill(ret, -1); // stores the answer
int[] set = new int[E.length + 1]; // the disjoint-set
iota(set, 0, set.length, 0); // initializes the disjoint-set
for (int i = 0; i < A.length; ++i) {
if (findSet(set, R[i]) != E.length && ret[findSet(set, R[i])] == -1) {
ret[set[R[i]]] = i;
unionSet(set, set[R[i]], set[R[i]] + 1);
}
}
return ret;
}
Read full article from off-line minimum problem - llhuii's Blog

LeetCode - Multiply Strings | Darren's Blog

Given two numbers represented as strings, return multiplication of the numbers as a string. Note that the numbers can be arbitrarily large and are non-negative.
we can simulate the process as the way we do multiplication by hand: sum up all products at each position, leave a single digit there and add carry to a higher position. Note that if the number of digits of the two numbers is m and n , respectively, the number of digits of their product is normally m+n or m+n−1 except the case when either is zero.
Time: O(mn)

public String multiply(String num1, String num2) {

        if (num1 == null || num1.length() == 0 ||

                num2 == null || num2.length() == 0)

            return "";

        if (num1.equals("0") || num2.equals("0"))   // Either one is 0

            return "0";

        int m = num1.length(), n = num2.length();

        // Multiply single digit of each number and add up products at each position

        int[] prods = new int[m+n];

        for (int i = n-1; i >= 0; i--)

            for (int j = m-1; j >= 0; j--)

                prods[i+j+1] += (num2.charAt(i)-'0') * (num1.charAt(j)-'0');

        // Keep a single digit at each position and add carry to a higher position

        StringBuilder result = new StringBuilder();

        for (int i = n+m-1; i >= 0; i--) {

            result.insert(0, prods[i]%10);

            if (i > 0)

                prods[i-1] += prods[i] / 10;    // Carry

        }

        // Get rid of one leaing "0" (if any)

        if (result.charAt(0) == '0')

            result.deleteCharAt(0);

 

        return result.toString();

    }

Read full article from LeetCode - Multiply Strings | Darren's Blog