Archive for August 3rd, 2013
这应该是DFS，和CC上那道题也很像，但是实在是做不出来。。而且用binary分解那种方法想出来了，但是时间复杂度也弄不明白。崩溃了。这样下去，周一的MS会挂把。。。
———————–两个月之后———————-
一次Bugfree。看来人真是会成长的。。和word break一样做，abaa先分成a, baa，然后再分成ab, aa，左边是palindrome才recurse on右边：
public ArrayList<ArrayList<String>> partition(String s) {
Map<String, ArrayList<ArrayList<String>>> cache = new HashMap<String, ArrayList<ArrayList<String>>>();
return partition(s, cache);
}
private ArrayList<ArrayList<String>> partition(String s, Map<String, ArrayList<ArrayList<String>>> cache) {
if (cache.containsKey(s))
return cache.get(s);
ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
if (s.isEmpty()) {
result.add(new ArrayList<String>());
}
for (int i = 0; i < s.length(); i++) {
String left = s.substring(0, i + 1);
if (isPalindrom(left)) {
String right = s.substring(i + 1);// right maybe empty
ArrayList<ArrayList<String>> rightPartitions = partition(right);
for (ArrayList<String> rightPartition : rightPartitions) {
rightPartition.add(0, left);
result.add(rightPartition);
}
}
}
cache.put(s, result);
return cache.get(s);
}
private boolean isPalindrom(String left) {
for (int i = 0; i < left.length() / 2; i++) {
if (left.charAt(i) != left.charAt(left.length() - 1 - i))
return false;
}
return true;
}
- In: leetcode
- 2 Comments
这题八月份做的太复杂了，中心思想还是如何render两头的digit，不过leetcode的方法最简单：
- 最左边的digit = x / 1000..(长度为x的长度）
- 最右边的digit= x % 10
- 然后把x两头chop掉。这个做的挺巧妙的，先是x = x % 1000…，把后几位留下，然后x / 10，把最后一位扔了。
- 感觉还是对除、余不熟练。记住x/10000..最长就是10000..那么长。所以%10就是显示一位。%是要后面的，/是要前面的。
public boolean isPalindrome(int x) {
if (x < 0)
return false;
int len = 0, temp = x;
while (temp > 0) {
temp /= 10;
len++;
}
int pow = (int)Math.pow(10, len - 1);
while (x > 0) {
int firstDigit = x / pow;
int lastDigit = x % 10;
if (firstDigit != lastDigit)
return false;
x = (x % pow) / 10; //chop first then chop last;
pow /= 100; //two digits gone, so pow shrinks by 100 times
}
return true;
}
——————————————————————–八月份——————————————————————-
这题其实思路挺简单，就是不断把两头的digit（通过/10^x, %10^y）弄出来比较，若有不等的时候，就返回false。
重点是怎么render两头的digit。index什么的非常容易错位，写出来了其实也不直观make sense，所以一定要写好了算法之后，自己好好试试，跑几个case才能发现问题。
int i = 1;
while (i <= bitCount / 2) {
int tenPowerI = (int) Math.pow(10, i); // 10^i
int p = x % tenPowerI; //p = x % 10^i
p = p * 10 / tenPowerI; //p = p / 10^(i - 1), render the first digit of p
int tenPowerBitCountMinusI = (int) Math.pow(10, bitCount - i); //10^(bitCount - i)
int q = x / tenPowerBitCountMinusI; // q = x / 10^(bitCount - i))
q = q % 10; //render the last digit of q
if (p != q)
return false;
i++;
}
- In: leetcode
- 3 Comments
example: {1, 3, 1, 4, 2, 0} => {1, 3, 2, 0, 1, 4}
这题有点类似于CC上做的“同样的0和1组成的immediate next“那道题。曾经被问过原题两次，都做出来了，但是这次居然要看答案才会！！还是不扎实啊。。
和CC那道题的区别：100110 – 从右往左找第一个”后面有1的0“，然后变成1，后面自排就行了。但是这道题是数字，难说“从右往左找第一个比谁大的呢？”——其实找到一个比右边的某个数小的就行了，这样保证找到的这位i还算比较低位（从后往前找的嘛），然后右面那个比它大的数j可以和它swap，剩下的那些数在右边排列成升序就行了。
但是这么做，发现不能不用额外空间还O(n)（最后那些数要sort，要么费时间要么费空间）。于是看别人答案，是”从右开始找第一个升序排列的紧挨着的两个数i – 1和i“，说明越过的最右边的都是降序的。然后让从第i位（这里是第二个1）开始往后找，找到j使j是i的immediate next（arr[j] > arr[i] &&arr[j] 小于其他右边的>arr[j]的数，这里是2）。然后i, j swap， 这样arr[i]就到了”他应该属于的位置（j的位置）“，此时右边这些就正好降序排列了，可以直接两两swap使O(n)的升序sort成功。
private void getNext(int[] arr) {
int pivot = -1;
for (int i = arr.length - 1; i > 0; i--) {
if (arr[i] > arr[i - 1]) {
pivot = i - 1;
break;
}
}
if (pivot < 0) {
arrangeToIncreaseOrder(arr, 0);
return;
}
// the index of the number that is immediate next of pivot
int nextToPivot = pivot + 1;
for (int i = nextToPivot + 1; i < arr.length; i++) {
if (arr[i] > arr[pivot] && arr[i] <= arr[nextToPivot])
nextToPivot = i;
}
swap(arr, pivot, nextToPivot);
// arrange arr to be increase from index i
arrangeToIncreaseOrder(arr, pivot + 1);
}
Lexi's Leetcode solutions 