[LeetCode] 49. Group Anagrams

	class Solution {
	public List<List<String>> groupAnagrams(String[] strs) {
	List<List<String>> result = new ArrayList<>();
	Map<Character, Integer> characterMap;
	Map<Map<Character, Integer>, List<String>> groupMap = new HashMap<>();
	if (strs == null || strs.length == 0) {
	return result;
	}
	for (String s : strs) {
	characterMap = new HashMap<>();
	for (Character c : s.toCharArray()) {
	if (characterMap.get(c) == null) {
	characterMap.put(c, 1);
	} else {
	characterMap.put(c, characterMap.get(c) + 1);
	}
	}
	if (groupMap.get(characterMap) == null) {
	groupMap.put(characterMap, new ArrayList<>());
	}
	groupMap.get(characterMap).add(s);
	}
	for (List<String> group : groupMap.values()) {
	result.add(group);
	}
	return result;
	}
	}

view raw groupAnagrams.java hosted with ❤ by GitHub

[LeetCode] 18. 4Sum

\(▔▽▔)/

	class Solution {
	public List<List<Integer>> fourSum(int[] nums, int target) {
	List<List<Integer>> result = new ArrayList<>();
	Set<List<Integer>> resultSet = new HashSet<>();
	if (nums == null || nums.length < 4) {
	return result;
	}
	Arrays.sort(nums);
	for (int i = 0; i < nums.length - 3; i++) {
	for (int j = i + 1; j < nums.length - 2; j++) {
	if (j > i + 1 && nums[j] == nums[j - 1]) {
	continue;
	}
	int left = j + 1;
	int right = nums.length - 1;
	while (left < right) {
	int sum = nums[i] + nums[j] + nums[left] + nums[right];
	if (sum == target) {
	resultSet.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
	left++;// Attn!
	right--;
	} else if (sum > target) {
	right--;
	} else {
	left++;
	}
	}
	}
	}
	for (List<Integer> solution : resultSet) {
	result.add(solution);
	}
	return result;
	}
	}

view raw fourSum.java hosted with ❤ by GitHub

[LeetCode] 60. Permutation Sequence

有点想不明白，为什么要做 k = k - 1 ┑(￣▽ ￣)┍

	class Solution {
	public String getPermutation(int n, int k) {
	String chooseFrom = "123456789";
	int[] factorial = new int[n + 1];
	factorial[0] = 1;
	factorial[1] = 1;
	for (int i = 2; i <= n; i++) {
	factorial[i] = factorial[i - 1] * i;
	}
	k = k - 1; // Why?
	StringBuilder sb = new StringBuilder();
	for (int i = n; i >= 1; i--) {
	int x = k / factorial[i - 1];
	k = k % factorial[i - 1];
	sb.append(chooseFrom.charAt(x));
	chooseFrom = chooseFrom.substring(0, x) + chooseFrom.substring(x + 1, chooseFrom.length());
	}
	return sb.toString();
	}
	}

view raw getPermutation.java hosted with ❤ by GitHub

[LeetCode] 312. Burst Balloons

好难啊，不会做\(▔▽▔)/

	class Solution {
	public int maxCoins(int[] nums) {
	// dp[i][j] - max coins could get when burst all the balloons between i to j
	// dp[i][j] = max(dp[i][j], dp[i][k - 1] + nums[i - 1] * nums[k] * nums[j + 1] + dp[k + 1][j]), i <= k <= j
	if (nums == null || nums.length == 0) {
	return 0;
	}
	int[][] dp = new int[nums.length][nums.length];
	for (int len = 1; len <= nums.length; len++) {
	for (int i = 0; i + len <= nums.length; i++) {
	int j = i + len - 1;
	for (int k = i; k <= j; k++) {
	int left = i == 0 ? 1 : nums[i - 1];
	int right = j == nums.length - 1 ? 1 : nums[j + 1];
	int current = left * nums[k] * right;
	if (k - 1 >= i) {
	current = current + dp[i][k - 1];
	}
	if (k + 1 <= j) {
	current = current + dp[k + 1][j];
	}
	dp[i][j] = Math.max(dp[i][j], current);
	}
	}
	}
	return dp[0][nums.length - 1];
	}
	}

view raw maxCoins.java hosted with ❤ by GitHub

[LeetCode] 58. Length of Last Word

lol，工作很繁重，脑子不是很清楚，只能拿一道简单到逆天的题目充数了 ╮(￣▽￣)╭　

	class Solution {
	public int lengthOfLastWord(String s) {
	int end = s.length() - 1;
	while (end >= 0 && s.charAt(end) == ' ') {
	end--;
	}
	int start = end;
	while (start >= 0 && s.charAt(start) != ' ') {
	start--;
	}
	if (end >= 0) {
	return end - start;
	}
	return 0;
	}
	}

view raw lengthOfLastWord.java hosted with ❤ by GitHub

[LeetCode] 338. Counting Bits

要累晕啦，做一道简单的，本来想用一个循环来数一个整型的二进制有多少个1，但是超时了。只能用个投机取巧的方法了……
查了一下Integer.bitCount()的实现，肯定是记不住的啊ㄟ(▔▽▔)ㄏ

	class Solution {
	public int[] countBits(int num) {
	int[] result = new int[num + 1];
	for (int i = 0; i <= num; i++) {
	result[i] = Integer.bitCount(i);
	}
	return result;
	}
	}

view raw countBits.java hosted with ❤ by GitHub

[LeetCode] 279. Perfect Squares

啦啦啦，四平方和定理是啥，我不懂啊～(￣▽￣～)(～￣▽￣)～

	class Solution {
	public int numSquares(int n) {
	int[] dp = new int[n + 1]; //dp[i] - the least number of perfect square number of i
	for (int i = 1; i <= n; i++) {
	dp[i] = Integer.MAX_VALUE;
	}
	for (int i = 0; i <= n; i++) {
	for (int j = 1; i + j * j <= n; j++) {
	dp[i + j * j] = Math.min(dp[i] + 1, dp[i + j * j]);
	}
	}
	return dp[n];
	}
	}

view raw numSquares.java hosted with ❤ by GitHub

初始化还把值搞错了，竟然溢出啦～
报名参加比赛，然后不做题，排名竟然会倒退！！！

[LeetCode] 31. Next Permutation

这道题卡了好久，终于做出来了，都要绕晕了ㄟ(▔▽▔)ㄏ

	class Solution {
	public void nextPermutation(int[] nums) {
	// Find longest non-increasing suffix
	int i = nums.length - 1;
	while (i > 0 && nums[i] <= nums[i - 1]) {
	i--;
	}
	int pivot = i - 1;
	if (pivot != -1) {
	// Find rightmost successor to pivot in the suffix
	int rightmostSuccessor = nums.length - 1;
	while (nums[rightmostSuccessor] <= nums[pivot]) {
	rightmostSuccessor--;
	}
	// Swap with pivot
	int tmp = nums[pivot];
	nums[pivot] = nums[rightmostSuccessor];
	nums[rightmostSuccessor] = tmp;
	}
	// Reverse the suffix
	int start = pivot + 1;
	int end = nums.length - 1;
	while (start < end) {
	int tmp = nums[start];
	nums[start] = nums[end];
	nums[end] = tmp;
	start++;
	end--;
	}
	}
	}

view raw nextPermutation.java hosted with ❤ by GitHub

比较无聊的一点是，如果没有看到这个算法，是不太可能做出来的 Next lexicographical permutation algorithm

[LeetCode] 134. Gas Station

O(n^2) 的复杂度好像有些高，不知道有没有更快的方法解决 \(▔▽▔)/

	class Solution {
	public int canCompleteCircuit(int[] gas, int[] cost) {
	for (int i = 0; i < gas.length; i++) {
	int gasInCar = gas[i];
	for (int traveled = 1; traveled <= gas.length; traveled++) { // Attn: Made mistake here. traveled should be range from 1 to gas.length (rather than 1 to gas.length - 1)
	int j = (i + traveled) % gas.length;
	int currentCost = j == 0 ? cost[cost.length - 1] : cost[j - 1];
	gasInCar = gasInCar - currentCost;
	if (gasInCar < 0) {
	break;
	}
	gasInCar = gasInCar + gas[j];
	}
	if (gasInCar >= 0) {
	return i;
	}
	}
	return -1;
	}
	}

view raw canCompleteCircuit.java hosted with ❤ by GitHub

更新：找到了很巧妙的方法。确实一次遍历就可以解决。～(￣▽￣～)(～￣▽￣)～
https://blog.csdn.net/JackZhang_123/article/details/78008439

[LeetCode] 95. Unique Binary Search Trees II

https://leetcode.com/problems/unique-binary-search-trees-ii/

递归(～o▔▽▔)～o o～(▔▽▔o～)

	/**
	* Definition for a binary tree node.
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	class Solution {
	public List<TreeNode> generateTrees(int n) {
	if (n < 1) {
	return new ArrayList<>();
	}
	return generateBST(1, n);
	}
	private List<TreeNode> generateBST(int start, int end) {
	List<TreeNode> result = new ArrayList<>();
	if (start > end) {
	result.add(null); // !!!
	return result;
	}
	if (start == end) {
	result.add(new TreeNode(start));
	return result;
	}
	for (int i = start; i <= end; i++) {
	List<TreeNode> leftChildren = generateBST(start, i - 1);
	List<TreeNode> rightChildren = generateBST(i + 1, end);
	for (TreeNode left : leftChildren) {
	for (TreeNode right : rightChildren) {
	TreeNode root = new TreeNode(i);
	root.left = left;
	root.right = right;
	result.add(root);
	}
	}
	}
	return result;
	}
	}

view raw generateTrees2.java hosted with ❤ by GitHub

[LeetCode] 198. House Robber

https://leetcode.com/problems/house-robber/

动态规划\(▔▽▔)/ 

	class Solution {
	public int rob(int[] nums) {
	// dp[i] = the maximum amount of money you can rob until index i
	// dp[i] = Max(dp[i - 1], nums[i - 1] + dp[i - 2])
	if (nums == null || nums.length == 0) {
	return 0;
	}
	int dp[] = new int[nums.length + 1];
	dp[0] = 0;
	dp[1] = nums[0];
	for (int i = 2; i <= nums.length; i++) {
	dp[i] = Math.max(dp[i - 1], nums[i - 1] + dp[i - 2]);
	}
	return dp[nums.length];
	}
	}

view raw rob.java hosted with ❤ by GitHub

[LeetCode] 190. Reverse Bits

https://leetcode.com/problems/reverse-bits/

最简单的想法是位运算一位一位的挪，用for循环搞定（要注意优先级和结合性的问题）：

	public class Solution {
	// you need treat n as an unsigned value
	public int reverseBits(int n) {
	int result = 0;
	for (int i = 0; i < 32; i++) {
	result = (result << 1) + (n & 1);
	n = n >> 1;
	}
	return result;
	}
	}

view raw reverseBits.java hosted with ❤ by GitHub

然后看到了别人一个不用循环的解法：
https://leetcode.com/problems/reverse-bits/discuss/54741/O(1)-bit-operation-C++-solution-(8ms)
很巧妙的利用了交换的时候这种特性：abcdefgh -> efghabcd -> ghefcdab -> hgfedcba 好困啊，只好用简单题交差啦 ～(￣▽￣～)(～￣▽￣)～