Leetcode: Ransom Note

Given
 an 
arbitrary
 ransom
 note
 string 
and 
another 
string 
containing 
letters from
 all 
the 
magazines,
 write 
a 
function 
that 
will 
return 
true 
if 
the 
ransom 
 note 
can 
be 
constructed 
from 
the 
magazines ; 
otherwise, 
it 
will 
return 
false. 



Each 
letter
 in
 the
 magazine 
string 
can
 only 
be
 used 
once
 in
 your 
ransom
 note.

简单题，只需判断magazine里是否包含ransom note。对于26个字母不需要使用hash map，直接用一个数组即可。

public class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] magazineCount = new int[26];
        for (int i = 0; i < magazine.length(); i++) {
            magazineCount[magazine.charAt(i) - 'a']++;
        }
        for (int i = 0; i < ransomNote.length(); i++) {
            if (--magazineCount[ransomNote.charAt(i) - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }
}

Leetcode: Shuffle an Array

Shuffle a set of numbers without duplicates.

将每个数与其之后的随机一个数互换。
注意reset的时候要使用clone。

public class Solution {
    private int[] originals;
    private int[] current;
    public Solution(int[] nums) {
        this.originals = nums.clone();
        this.current = nums;
    }
    
    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        current = originals.clone();
        return current;
    }
    
    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
        Random random = new Random();
        for (int i = 0; i < current.length; i++) {
            int a = current[i];
            int nextIndex = i + random.nextInt(current.length-i);
            current[i] = current[nextIndex];
            current[nextIndex] = a;
        }
        return current;
    }
}

Leetcode: Largest Divisible Subset

Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj % Si = 0.

If there are multiple solutions, return any subset is fine.
关键点是若b>a且b%a==0, c>b且c%b==0那么c%a==0
用dp保存在当前数字之前与当前数字符合条件的list。

public class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        if (nums.length == 0) {
            return new ArrayList<Integer>();
        }
        Arrays.sort(nums);
        List<Integer>[] dp = new List[nums.length];
        int resultIndex = 0;
        for (int i = 0; i < nums.length; i++) {
            List<Integer> curMax = new ArrayList<Integer>();
            for (int j = 0; j < i; j++) {
                if (nums[i] % nums[j] == 0) {
                    System.out.println(j);
                    List<Integer> tmp = new ArrayList<Integer>(dp[j]);
                    tmp.add(nums[i]);
                    curMax = curMax.size() > tmp.size() ? curMax : tmp; 
                }
            }
            // this number does not have any matched number yet, put this number into
            // the list so that it will be included in the following matches
            if (curMax.size() == 0) {
                curMax.add(nums[i]);
            }
            dp[i] = curMax;
            if (curMax.size() > dp[resultIndex].size()) {
                resultIndex = i;
            }
        }
        return dp[resultIndex];
    }
}

Leetcode: Valid Perfect Square

Given a positive integer num, write a function which returns True if num is a perfect square else False.

简单题，利用binary search 找square root。

public class Solution {
    public boolean isPerfectSquare(int num) {
        if (num < 0) {
            return false;
        }
        if (num <= 1) {
            return true;
        }
        return binarySearch(num, 2, num/2);
    }
    
    private boolean binarySearch(int val, int start, int end) {
        if (start > end) {
            return false;
        }
        int mid = (start + end) / 2;
        if (val/mid == mid && val % mid == 0) {
            return true;
        }
        if (val/mid >= mid) {
            return binarySearch(val, mid + 1, end);
        } else {
            return binarySearch(val, start, mid - 1);
        }
    }
}

Leetcode: Missing Number

Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.

For example,
Given nums = [0, 1, 3] return 2.

解法1:求和

public class Solution {
    public int missingNumber(int[] nums) {
        int total = nums.length;
        int sum = total * (total + 1 ) / 2;
        int actual = 0;
        for (int num : nums) {
            actual += num;
        }
        return sum - actual;
    }
}

解法2: bit manipulation， 将所有出现的数与所有应该出现的数亦或

public class Solution {
    public int missingNumber(int[] nums) {
        int xor = 0;
        for (int i = 0; i < nums.length; i++) {
            xor ^= nums[i] ^= (i + 1);
        }
        return xor;
    }
}

Leetcode: Ugly Number

Write a program to check whether a given number is an ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7.

Note that 1 is typically treated as an ugly number.

简单题

public class Solution {
    public boolean isUgly(int num) {
        if (num <= 0) {
            return false;
        }
        while (num % 2 == 0) {
            num /=2;
        }
        while (num % 3 == 0) {
            num /=3;
        }
        while (num % 5 == 0) {
            num /=5;
        }
        return num == 1;
    }
}

Leetcode: Ugly Number II

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note that 1 is typically treated as an ugly number.

https://my.oschina.net/Tsybius2014/blog/495962的解释比较好懂
注意里面的三个if不能是else if否则会出现duplicate，例如2*3 和 3*2得到的是同一个ugly number。

public class Solution {
public int nthUglyNumber(int n) {
int[] uglyNumbers = new int[n];
uglyNumbers[0] = 1;
int index2 = 0, index3 = 0, index5 = 0;

for (int nthUglyNumber = 2; nthUglyNumber <= n; nthUglyNumber++) {
int uglyNumber = Math.min(uglyNumbers[index2]*2, Math.min(uglyNumbers[index3]*3, uglyNumbers[index5]*5));
if (uglyNumber == uglyNumbers[index2]*2) {
index2++;
}
if (uglyNumber == uglyNumbers[index3]*3) {
index3++;
}
if (uglyNumber == uglyNumbers[index5]*5) {
index5++;
}
uglyNumbers[nthUglyNumber-1] = uglyNumber;
}
return uglyNumbers[n-1];
}
}

Move Zeroes

Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

public class Solution {
    public void moveZeroes(int[] nums) {
        int valid = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0 && i != valid + 1) {
                nums[++valid] = nums[i];
            } else if (nums[i] != 0) {
                valid++;
            }
        }
        for (int i = valid + 1; i < nums.length; i++) {
            nums[i] = 0;
        }
    }
}

Peeking Iterator

Given an Iterator class interface with methods: next() and hasNext(), design and implement a PeekingIterator that support the peek() operation — it essentially peek() at the element that will be returned by the next call to next().

思路是在每次取完当前元素后将下一个元素保存，这样peek以及next时可以直接返回这个元素

class PeekingIterator implements Iterator<Integer> {
    private Integer next;
    private Iterator<Integer> iterator;
	public PeekingIterator(Iterator<Integer> iterator) {
	    this.iterator = iterator;
	    // initialize any member here.
	    if (iterator.hasNext()) {
	        this.next = iterator.next();
	    }
	}

    // Returns the next element in the iteration without advancing the iterator.
	public Integer peek() {
        return next;
	}

	// hasNext() and next() should behave the same as in the Iterator interface.
	// Override them if needed.
	@Override
	public Integer next() {
	    System.out.println(next);
	    Integer result = next;
	    next = iterator.hasNext() ? iterator.next() : null;
	    return result;
	}

	@Override
	public boolean hasNext() {
	    return next != null;
	}
}

Power of Four

Given an integer (signed 32 bits), write a function to check whether it is a power of 4.

通过4， 16， 64找规律，1. num是power of two， 即一个1之后所有位都是0， 2， 0的个数是偶数

public class Solution {
    public boolean isPowerOfFour(int num) {
        return (num & (num -1)) == 0 && (num & 0x55555555) > 0;
    }
}