LeetCode: Generate Parentheses

https://leetcode.com/problems/generate-parentheses/

簡單的recursively call

キャプチャ

import java.util.List;
import java.util.LinkedList;

public class Solution {
    public List<String> generateParenthesis(int n) {
        
    	List<String> list = new LinkedList<>();
    	StringBuilder builder = new StringBuilder();
    	generate(list, builder, n, n);

    	return list;

    }

    void generate(List<String> list, StringBuilder builder,int left_n, int right_n) {
    	if (right_n == 0 && left_n == 0) {
    		list.add(builder.toString());
    		return;
    	} else if (left_n > right_n) {
    		return;
    	} else if (left_n < 0) {
    		return;
    	}

    	builder.append('(');
    	generate(list, builder, left_n-1, right_n);
    	builder.deleteCharAt(builder.length() - 1);
    	builder.append(')');
    	generate(list, builder, left_n, right_n-1);
    	builder.deleteCharAt(builder.length() - 1);
    }
}

連這個都要用DP做…DP魂嘛你!!

キャプチャ

import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;

public class Solution {
    public List<String> generateParenthesis(int n) {
        
    	List<List<String>> resultList = new ArrayList<>();
    	List<String> combines_0 = new LinkedList<>();
    	combines_0.add("");
    	resultList.add(combines_0);
    	
    	StringBuilder builder = new StringBuilder();
    	for (int i=1; i<=n; i++) {
    		List<String> combines = new LinkedList<>();
    		for (int j=0; j<i; j++) {
    			List<String> left = resultList.get(j);
    			List<String> right = resultList.get(i-1-j);
    			for (String l : left) {
    				for (String r : right) {
    					builder.delete(0, builder.length());
    					builder.append('(');
    					builder.append(l);
    					builder.append(')');
    					builder.append(r);
    					combines.add(builder.toString());
    				}
    			}
    		}
    		resultList.add(combines);
    	}

    	return resultList.get(n);
    }
}

LeetCode: Merge Two Sorted Lists

https://leetcode.com/problems/merge-two-sorted-lists/

跑一些簡單的東西來找回手感…

キャプチャ

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;

        ListNode head;
        ListNode node;
        if (l1.val < l2.val) {
        	node = l1;
        	head = node;
        	l1 = l1.next;
        } else {
        	node = l2;
        	head = node;
        	l2 = l2.next;
        }

        while (l1 != null || l2 != null) {
        	if (l1 == null) {
        		node.next = l2;
        		break;
        	} else if (l2 == null) {
        		node.next = l1;
        		break;
        	} else if (l1.val < l2.val) {
        		node.next = l1;
        		node = node.next;
        		l1 = l1.next;
        	} else {
        		node.next = l2;
        		node = node.next;
        		l2 = l2.next;
        	}
        }

        return head;
    }
}

LeetCode: Valid Parentheses

https://leetcode.com/problems/valid-parentheses/

放個假回來真的會很懶得動…先從簡單的開始跑吧

キャプチャ

import java.util.Stack;

public class Solution {
    public boolean isValid(String s) {
    	Stack<Character> stack = new Stack<>();

        for (char c : s.toCharArray()) {
        	switch (c) {
        		case '(':
        		case '{':
        		case '[':
        			stack.push(c);
        			break;
        		case ')':
					if (stack.empty() || stack.pop() != '(') {
						return false;
					}
					break;
				case '}':
					if (stack.empty() || stack.pop() != '{') {
						return false;
					}
					break;
				case ']':
					if (stack.empty() || stack.pop() != '[') {
						return false;
					}
					break;
				default:
					// Do nothing
					break;
        	}
        }

        if (stack.empty()) {
        	return true;
        } else {
        	return false;
        }
    }
}

SRM 664 Div1: BearAttacks

解法參考: http://mayokoex.hatenablog.com/entry/2015/08/03/091233
modulo復習: http://www.csie.ntnu.edu.tw/~u91029/Residue.html

靠竟然還要求inverse…讓我吐血吧

先推一下怎麼用DP求inverse, 剩下的有空再寫0rz(不用dp求inverse應該會跑到天荒地老哈哈)

回去翻數學課本, 看什麼是modulo的inverse定義QQ
A*B congruent 1 module M, 則B就是A的inverse
以M=11為例…
IMG_20150807_165630[1]
舉4為例子, 要推論4的inverse, 先看 M = i * (M/i) + r 這個式子, r = M%i
我們把2邊互乘r的inverse, 就可以得到
(int)(M/i) * inv[M%i] + inv[i] congruent 1 module M
的結論, 因此 inv[i] 就等於 M – (int)(M/i) * inv[M%i] module M
IMG_20150807_165651[1]

所以最後就得到公式…啊怎麼反過來了! 看得懂就好
IMG_20150807_165706[1]

剩下的改天再寫, 先去重新培養一下腦細胞_(:3」∠)_

SRM 664 Div1: BearPlays

screenshot

覺得這根本就是數學…不是很喜歡做這種題目>”<

一大堆mod的推論法就不說了, 單純以4, 7, 12舉例

Round 0 4, 7
Round 1 8, 3
Round 2 5, 6
Round 3 10, 1
Round 4 9, 2
Round 5 7, 4
Round 6 3, 8
Round 7 6, 5
Round 8 1,10
Round 9 2, 9
Round 10 4, 7
Round 11 8, 3
Round 12 5, 6

不論大小, 根據鴿籠原理(天哪我的數學老師真該誇獎我一下…), 左邊的數字一定會在A+B之間跳動
因此只要算出第K回左邊的數字會是多少, 再取該數字和(A+B減掉該數字)較小的一方就是答案
左邊的數字規律就是每個Round都會乘以2(數字如果為大就是T-2A), 因此第K回的數字即為A*(2^K) mod (A+B)
因此4*(2^7) mod (4+7) = 6, 取 11-6 = 5

又 A*B mod T = ((A mod T) * (B mod T)) mod T (把A和B設為aT+b下去推論)
所以在算2^K的時候把mod也一起算進去就可以減少overflow的風險

減少執行時間的最大因素是 A^K = (A*A)^(K/2)
有這個就差很多了

public class BearPlays {

	public long pow(long base, int times, int mod) {
		if (times == 0) return 1;
		if (times == 1) return base % mod;
		if (times % 2 == 0) {
			return pow((base*base % mod), times/2, mod);
		} else {
			return (base * pow(base, times-1, mod)) % mod;
		}
	}
	
	public int pileSize(int A, int B, int K) {
		int total = A + B;
		long powt = pow(2, K, total);
		int ans = (int)((A * powt) % total);
		return Math.min(ans, total - ans);
	}
}

SRM 664 Div2: BearPlaysDiv2

用recursively call做果然stackoverflow了…以後要盡量避免recursively call的寫法QQ

1000 points的看到題目直接關掉= =|||

OSXDaily 2015-08-02 9.43.13

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.List;
import java.util.LinkedList;

public class BearPlaysDiv2 {
	
	int[] tmp = new int[3];
	Set<String> caled = new HashSet<>();

	public String equalPiles(int A, int B, int C) {
		tmp[0] = A; tmp[1] = B; tmp[2] = C;
		Arrays.sort(tmp);

		return cal(tmp[0], tmp[1], tmp[2]) ? "possible" : "impossible";

	}

	private boolean cal(int aa, int bb, int cc) {
		if (aa == bb && bb == cc) {
			return true;
		}

		if ((aa + bb + cc) % 3 != 0) {
			return false;
		}

		List<List<Integer>> toCheck = new LinkedList<>();
		toCheck.add(Arrays.asList(aa, bb, cc));
		List<List<Integer>> next = new LinkedList<>();;
		int a, b, c;
		while (toCheck.size() > 0) {
			next.clear();

			for (List<Integer> numbers: toCheck) {

				a = numbers.get(0);
				b = numbers.get(1);
				c = numbers.get(2);

				// for a, b
				tmp[0] = a*2; tmp[1] = b-a; tmp[2] = c;
				if (areEqual(tmp)) {
					return true;
				} else {
					Arrays.sort(tmp);
					if (caled.add(createKey(tmp))) {
						next.add(Arrays.asList(tmp[0], tmp[1], tmp[2]));
					}
				}

				// for a, c
				tmp[0] = a*2; tmp[1] = b; tmp[2] = c-a;
				if (areEqual(tmp)) {
					return true;
				} else {
					Arrays.sort(tmp);
					if (caled.add(createKey(tmp))) {
						next.add(Arrays.asList(tmp[0], tmp[1], tmp[2]));
					}
				}

				// for b, c
				tmp[0] = a; tmp[1] = b*2; tmp[2] = c-b;
				if (areEqual(tmp)) {
					return true;
				} else {
					Arrays.sort(tmp);
					if (caled.add(createKey(tmp))) {
						next.add(Arrays.asList(tmp[0], tmp[1], tmp[2]));
					}
				}
			}

			toCheck.clear();
			for (List<Integer> l : next) {
				toCheck.add(l);
			}
		}

		return false;

	}

	private String createKey(int[] nums) {
		return String.format("%d %d %d", nums[0], nums[1], nums[2]);	
	}

	private boolean areEqual(int[] nums) {
		if (nums[0] == nums[1] && nums[1] == nums[2]) {
			return true;
		} else {
			return false;
		}
	}
}

SRM 394: ProperDivisors

http://topcoder.bgcoder.com/print.php?id=2061

OSXDaily 2015-08-01 11.22.02

為了time limit在那邊修半天…真是太有成就感了T^T

對於從2到a+b(exclusive)的數一一檢查
先找出第一個可以被整除的位置,然後陸續往下加
概念很簡單,但重要的是(1000000,10000000,10)這個case不能跑超過2秒

public class ProperDivisors {
	
	public int analyzeInterval(int a, int b, int n) {

		int total = 0;

		for (int i=2; i<a+b; i++) {
			int head;
			if (a % i == 0 && i < a) {
				head = a;
			} else {
				head = a + (i - (a % i));
				if (head > a+b) {
					continue;
				}
			}

			for (int j=head; j<a+b+1; j += i) {
				if (j == i) continue;
				int tmp = j / i;
				int tmp_p = 1;
				for (int p=1; p<n; p++) {
					if (tmp % i == 0) {
						tmp = tmp / i;
						tmp_p++;
					} else {
						break;
					}
				}
				if (tmp_p != n) {
					//System.out.printf("j = %d, i = %d%n", j, i);
					total++;
				}
			}
		}

		return total;
	}
}