记录

1. Find All Duplicates in an Array
Not hard but very error-prone. Many small traps. Better write down the pseudo code first.

- If they don't do the shift for you, you need to do it.
- the current element could also be neg.

public class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        // there is a reason they plus one
        // zero has noe pos, neg
        // now do:
        // for each , get current,
        // use current - 1 as index, get target element
        // see if target is neg
        // is neg, add current
        // not neg, turn the position into neg
        List<Integer> list = new LinkedList();
        for (int i = 0; i < nums.length; i++) {
            // note the current could also be neg
            int current = Math.abs(nums);
            int target = nums[current - 1];
            if (target < 0) {
                list.add(current);
            } else {
                nums[current - 1] = - target;
            }
        }
        return list;
    }
}

Make up for Saturday's second one:

2. Beautiful Arrangement

public class Solution {
    private int count;
    public int countArrangement(int N) {
        // strategy: fix element, look for position
        // create a visited for taken position
        // loop from left to right, take one, put in one position, check if this position is ok, go to the next one
        // when reached N, count++
        // it's 1 -> N, N numbers, visited[0] is not used.
        count = 0;
        int[] visited = new int[N + 1];
        permute(1, N, visited);
        return count;
    }
   
    private void permute (int i, int N, int[] visited) {
        if (i == N + 1) {
            count++;
        }
        for (int j = 1; j <= N; j++) {
            if ((i % j == 0 || j % i == 0) && visited[j] != 1 ) {
                visited[j] = 1;
                permute(i + 1, N, visited);
                visited[j] = 0;
            }
        }
    }
}

TODO:
1. better the solution
2. allocate some time to investigate the complexity
3. wirte the permutation algorithm

1. Optimal Division

public class Solution {
    public String optimalDivision(int[] nums) {
        if (nums == null || nums.length == 0) {
            return "";
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < nums.length; i++) {
            if ((nums.length > 2) && i == 1) {
                sb.append("(");
            }
            sb.append(nums).append("/");
        }
        sb.deleteCharAt(sb.length() - 1);
        if (nums.length > 2) {
            sb.append(")");
        }
        return sb.toString();
    }
}

Ugly. Needs to improve. How to normalize the special cases?

2. Longest Uncommon Subsequence I

public class Solution {
    public int findLUSlength(String a, String b) {
        return a.equals(b) ? -1 : Math.max(a.length(), b.length());
    }
}

1. Find Largest Value in Each Tree Row

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
    public List<Integer> largestValues(TreeNode root) {
        // q
        // list
        // put one
        // q not empty
        // get one, put children to l,
        // put l into q
        Queue<TreeNode> q = new LinkedList();
        List<TreeNode> l = new LinkedList();
        List<Integer> results = new LinkedList();
        int max = Integer.MIN_VALUE;
        if (root == null) {
            return results;
        }
        q.add(root);
        while (!q.isEmpty()) {
            TreeNode node = q.remove();
            if (node.val > max) {
                max = node.val;
            }
            if (node.left != null) {
                l.add(node.left);
            }
            if (node.right != null) {
                l.add(node.right);
            }
            if (q.isEmpty()) {
                results.add(max);
                q.addAll(l);
                max = Integer.MIN_VALUE;
                l.clear();
            }
        }
        return results;
    }
}
TODO: clean it up

2. Arithmetic Slices

public class Solution {
    public int numberOfArithmeticSlices(int[] A) {
        // first look for the longest arithmetic sequence starting from each index
        // then, add up
        // loop from left, count three, yes,t continue, until not same
        // update the pointer here, go to next
        if (A == null || A.length < 3) {
            return 0;
        }
        int i = 0;
        int count = 0;
        while (i <= A.length - 3) {
            if (A[i + 2] - A[i + 1] == A[i + 1] - A) {
                int value = A[i + 1] - A[i];
                int j = i + 3;
                while (j < A.length && (A[j] - A[j - 1] == value)) {
                    j++;
                }
                int len = j - i;
                count += (len - 1) * (len - 2) / 2;
                i = j;
            } else {
                i = i + 1;
            }
        }
        return count;
    }
}[/i]
[i]TODO: [/i]
[i]1. dp solution[/i]
[i]2. normalize, they have shorter solutions but similar idea.[/i]

Celebrate one week!!! Pretty rare for me.

1. Single Element in a Sorted Array

public class Solution {
    public int singleNonDuplicate(int[] nums) {
        int start = 0;
        int end = nums.length - 1;
        while (start < end) {
            int middle = (start + end) / 2;
            if (nums[middle] == nums[middle - 1]) {
                int leftLen = middle - 1 - start;
                if (leftLen % 2 == 0) {
                    // in right
                    start = middle + 1;
                } else {
                    // in left
                    end = middle - 2;
                }
            } else if (nums[middle] == nums[middle + 1]) {
                int leftLen = middle - start;
                if (leftLen % 2 == 0) {
                    // in right
                    start = middle + 2;
                } else {
                    // in left
                    end = middle - 1;
                }
            } else {
                return nums[middle];
            }
        }
        int middle = (start + end) / 2;
        return nums[middle];
    }
}
Hate this kind of problem. So many branches. But need to do this more.

TODO: still I think it's better to extract the leftLen % 2 to a function though it's just one line.


__And__: signs of binary search:

1. sorted
2. log(n)
3. find an element

Tuesday

2. Single Number

public class Solution {
    public int singleNumber(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum = sum ^ num;
        }
        return sum;
    }
}
需要证明：
异或有交换律

1. 只需要关注某一位

2.
xor 0 keep
xor 1 flip

那么和多个数异或就转换为flip几次。只用关心flip了多少次，不用关心在那些位置flip。所以结果是一样的。是有交换律的。

Wednesday

1. Max Consecutive Ones

public class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int max = 0;
        int count = 0;
        for (int num : nums) {
            if (num == 1) {
                count++;
                max = Math.max(count, max);
            } else {
                count = 0;
            }
        }
        return max;
    }
}