LeetCode Notes001

Albert Chen's Week001

• MergeSortedArray (Solution088)

http://oj.leetcode.com/problems/merge-sorted-array/
Merge from the end

• SingleNumberII (Solution137)

http://oj.leetcode.com/problems/single-number-ii/

（0）初始设定ones=0; twos=0;
（1）用twos记录到当前为止，二进制”1“出现3k+2次的位数；twos = twos | (ones & A[i]);
（2）用ones记录到当前为止，二进制“1”出现3k+1次的位数；ones = ones ^ A[i];
（3）当ones和twos的某一位同时为”1“时，即该位出现二进制”1“ 3k+3次（也就是3k次），清零该位。xthrees = ~(ones & twos); // xthrees 是二进制“1”没有出现3k次的位数ones = ones & xthrees;twos = twos & xthrees;
（4）遍历完数组中所有的数之后，ones记录的就是最终结果。

• SortColors (Solution075)

http://oj.leetcode.com/problems/sort-colors/
int i = 0; // for end of zeros
int j = n; // for start of twos;
int k = 0; // iterator

• Permutation(Solution045), PermuationII(Solution046), NextPermutation(Solution030)

http://oj.leetcode.com/problems/permutations/
http://oj.leetcode.com/problems/permutations-ii/
http://oj.leetcode.com/problems/next-permutation/

(0)  input: int[] num
(1) sort(num)
(1.5) do {add}while (nextPermutation is true)
(2-7) boolean nextPermutaion()

• (2-6) 循环体
• (2) 从后往前找到最大的倒序subarray of num (i, num.length-1)
• for i = num.length-1; i >0; i--
• if num[i-1]<num[i]
• (3) 从后往前在subarray里找到第一个num[j]大于num[i-1]
• for j = num.length-1; j>=i; j--
• if num[j]>num[i-1]
• (4) swap(num[j],num[i-1])
• (5) reverse subarray (i, num.length-1)
• (6) return true
• (7) 终止条件，并且维持next permutation的语义
• reverse num(0, num.length-1) and return false;