Leetcode–Permutation Sequence

The Problem:

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

  1. "123"
  2. "132"
  3. "213"
  4. "231"
  5. "312"
  6. "321"

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

Notes:

  1. The key is to use an array or list to record the numbers to be added, then can access that number just according to the index calculated from k. Also I used linkedlist to store the numbers which makes it easier to remove each number after chosen.
  2. input k should be decreased first before treating as index

Java Solution

public class Solution {
    public String getPermutation(int n, int k) {
        List<Integer> numbers = new LinkedList<Integer>();
        int multiplys = 1;
        for(int i= 0; i<n; i++){
            multiplys= multiplys*(i+1);
            numbers.add(i+1);
        }
        
        k--; //---!! k is not array index
        StringBuilder result  = new StringBuilder();
        for(int i =0; i < n; i++){
            multiplys = multiplys/(n-i);
            int index = k/multiplys;
            result.append(numbers.get(index));
            numbers.remove(index);
            k = k%multiplys;
        }
        return result.toString();
    }
}

Leetcode–Next Permutation

The Problem:

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

Notes:

  1. A tricky question that I think is too hard for an interview if haven’t met it before, it’s a classic one though.
  2. Steps:
    1. For an always descending array, it’s simple that only need to sort the array in ascending order.
    2. Otherwise means It has ascending pair somewhere, find the last index that with a larger number following. Note that beyond that “last index”, the array is in descending order. Then reverse the descending half to make it in ascending order, and swap the “last index” number with the smallest one that is greater than it in the latter half.

Java Solution

public class Solution {
    public void nextPermutation(int[] num) {
        if(num.length <=1)return;

        int indexInc = -1;
        for(int i = 1; i< num.length; i++){
            if(num[i] > num[i-1]){
                indexInc = i-1;
            }
        }
        
        if(indexInc ==-1){
            // decreaseing all the way
            Arrays.sort(num);
            return;
        }
        else{
            int i = indexInc+1;
            int j = num.length-1;
            while(i<j){
                int temp = num[i];
                num[i] = num[j];
                num[j] = temp;
                i++;
                j--;
            }
            for(int k = indexInc+1; k<num.length; k++){
                if(num[k] > num[indexInc]){
                    int temp = num[k];
                    num[k] = num[indexInc];
                    num[indexInc] = temp;
                    break;
                }
            }
            return;
        }
    }
}

Leetcode–Permutations II

The Problem:

Given a collection of 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], and [3,2,1].

Notes:

  1. Solution 1 is just same as Permutations, with a hash set to check if the list is already in the result. Could directly use list.toString() and store the string in set to check for duplicates.
  2. Solution 2 I will add later…

Java Solution I:

public class Solution {
    public List<List<Integer>> permuteUnique(int[] num) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if(num.length==0)return result;
        
        HashSet<String> set = new HashSet<String>();
        List<Integer> first = new LinkedList<Integer>();
        first.add(num[0]);
        result.add(first);
        
        for(int i = 1; i < num.length; i++){
            List<List<Integer>> temp = new ArrayList<List<Integer>>();
            for(int j = 0; j < result.size(); j++){
                List<Integer> one = result.get(j);
                for(int k = 0; k <= one.size(); k++){
                    List<Integer> newone = new LinkedList<Integer>(one);
                    newone.add(k, num[i]);
                    if(!set.contains(newone.toString())){
                        temp.add(newone);
                        set.add(newone.toString());
                    }
                }
            }
            result = temp;
        }
        return result;
    }
}

Leetcode–Permutations

The Problem:

Given a collection of 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], and [3,2,1].

Notes:

  1. In each iteration, add the next number in array to the existing list in result, insert at all possible locations.
  2. Use a linked list to easily insert new number at a given location.

Java Solution:

public class Solution {
    public List<List<Integer>> permute(int[] num) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if(num.length==0)return result;
        
        List<Integer> first = new LinkedList<Integer>();
        first.add(num[0]);
        result.add(first);
        
        
        for(int i = 1; i < num.length; i++){
            List<List<Integer>> temp = new ArrayList<List<Integer>>();
            for(int j = 0; j < result.size(); j++){
                List<Integer> one = result.get(j);
                for(int k = 0; k <= one.size(); k++){
                    List<Integer> newone = new LinkedList<Integer>(one);
                    newone.add(k, num[i]);
                    temp.add(newone);
                }
            }
            result = temp;
        }
        return result;
        
    }
}

Leetcode–Longest Substring Without Repeating Characters

The Problem:

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.

Notes:

  1. Check for repeating characters we can use an int or bool array of 256, no need for hash set.
  2. Remember to update the max length again when get out of while loop.

Java Solution:

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.length()<=1)return s.length();
        
        int start = 0;
        int end = start;
        int[] occur = new int[256];
        Arrays.fill(occur, 0);
        int maxLen = 0;
        while(start < s.length() && end < s.length()){
            if(occur[s.charAt(end)]==0){
                occur[s.charAt(end)]=1;
                end++;
            }
            else{
                maxLen = Math.max(maxLen,end-start);
                occur[s.charAt(start)]--;
                start++;
            }
        }
        maxLen = Math.max(maxLen,end-start);
        return maxLen;
    }
}

Leetcode–Partition List

The Problem:

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

Notes:

  1. A basic linked list question, use fake head to avoid the mess of dealing with head.
  2. Mistake I made: While nodes are all rearranged, don’t forget the set the next of tail to null, otherwise will link back to a cycle.

Java Solution:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode fkHead = new ListNode(0);
        ListNode pre1 = fkHead;
        ListNode fkHead2 = new ListNode(0);
        ListNode pre2 = fkHead2;
        
        fkHead.next = head;
        ListNode p = head;
        while(p!= null){
            if(p.val < x){
                pre1.next = p;
                pre1 = p;
            }
            else{
                pre2.next = p;
                pre2 = p;
            }
            p = p.next;
        }
        pre1.next = fkHead2.next;
        pre2.next = null; //---!!!---important
        return fkHead.next;
    }
}

Leetcode–Multiply Strings

The Problem:

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note: The numbers can be arbitrarily large and are non-negative.

Notes:

  1. The problem can be broken down to String add and String multiply by char. Multiply the first string by each character in second string from right to left, and add the result of each step.
  2. Special condition: if either input is zero then return zero, otherwise the result from multiplication would be a series of zeros.
  3. If the total number of digits of input number is less than 9, means the result can fit in a normal integer, can take them as int and do multiply.

Java Solution:

public class Solution {
    public String multiply(String num1, String num2) {
        int len1 = num1.length();
        int len2 = num2.length();
        
        if(len1 + len2 < 9){
            int res = Integer.parseInt(num1) * Integer.parseInt(num2);
            return String.valueOf(res);
        }
        if(num1.equals("0") || num2.equals("0"))return "0";
        String res = "0";
        for(int i = 0; i < len2; i++){
            String mult = multByChar(num1, num2.charAt(len2-1-i));
            int k = i;
            while(k>0){
                k--;
                mult = mult+"0";
            }
            res = addStr(mult, res);
        }
        return res;
    }
    
    private String addStr(String a, String b){
        int lena = a.length();
        int lenb = b.length();
        int len = Math.max(lena, lenb)+1;
        char[] res = new char[len];
        int carry = 0;
        int i;
        for(i = 1; i <= Math.min(lena, lenb); i++){
            int sum = (a.charAt(lena-i)-'0') + (b.charAt(lenb-i)-'0')+carry;
            res[len-i] = (char)(sum%10+'0');
            carry = sum/10;
        }
        while(i<=lena){
            int sum = (a.charAt(lena-i)-'0')+carry;
            res[len-i] = (char)(sum%10+'0');
            carry = sum/10;
            i++;
        }
        while(i<=lenb){
            int sum = (b.charAt(lenb-i)-'0')+carry;
            res[len-i] = (char)(sum%10+'0');
            carry = sum/10;
            i++;
        }
        if(carry==0){
            return new String(res).substring(1);
        }
        else{
            res[0] = (char)(carry+'0');
            return new String(res);
        }
    }
    
    private String multByChar(String num, char ch){
        if(ch=='0') return "0";
        int len = num.length();
        char[] res = new char[len+1];
        int carry = 0;
        int mul = ch-'0';
        for(int i = 0; i < len; i++){
            int pro = mul * (num.charAt(len-1-i)-'0') + carry;
            res[len-i] = (char)(pro%10+'0');
            carry = pro/10;
        }
        if(carry == 0){
            return new String(res).substring(1);
        }
        else{
            res[0] =(char)(carry+'0');
            return new String(res);
        }
    }
}