Array

Initialize

• Initialize array with values

  • for int int[] arr = {1,2,2}
  • for String String[] arr = new String[]{"a", "b"}

• Initialize arraylist with values

  • List<Integer> list = Arrays.asList(1,2,3)

Copy

Copy from another array

for loop

deep copy

new ArrayList<>(list)

in place move/swap

Move Zeroes

要求把0放到数组的最后

• brute force, two loops, O(n)
• realize the two requirements are mutually exclusively, and can be solved individually and then combine
  • move all the non-zero to the beginning of the array 可以发现我们关心的是第一个0之前的位置
  • fill the remaining end to be zeroes
• optimization:
  • 直接进行两个指针(cur, lastNonZero)的交换, lastNonZero递增

    // almost 2n, when it is [0,0, ..., 1]
    public void moveZeroes(int[] nums) {
        int lastNotZeroIndex = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[lastNotZeroIndex++] = nums[i];
            }
        }        

        for (int i = lastNotZeroIndex; i < nums.length; i++) {
            nums[i] = 0;
        }
    }

    // optimization
    for (int i = 0, lastNotZeroIndex = 0; i < nums.length; i++) {
        if (nums[i] != 0) {
            swap(nums[lastNotZeroIndex++], nums[i]);
        }
    }

Remove Element

• 非常类似，但是不需要交换，直接赋值即可
• 当val值非常少，充分利用顺序无关的要求进行优化，把val的值扔到最后

        int length = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != val) {
                nums[length++] = nums[i];
            }
        }
        return length;

        //optimization
        int i = 0, n = nums.length;
        while (i < n) {
            if (nums[i] == val) {
                nums[i] = nums[n-1];
                n--;
            } else {
                i++;
            }
        }
        return n;

Merge

Merge Sorted Array

关键在于从末端开始merge，这样坐标是确定的

public void mergeSortedArray(int[] A, int m, int[] B, int n) {
        int i = m-1, j = n-1, index = m + n - 1;
        while (i >= 0 && j >= 0) {
            if (A[i] > B[j]) {
                A[index--] = A[i--];
            } else {
                A[index--] = B[j--];
            }
        }
        while (i >= 0) {
            A[index--] = A[i--];
        }
        while (j >= 0) {
            A[index--] = B[j--];
        }
    }

如果是对某一个Array的排序，用两个指针即可视为2 arrays

Reverse

三步翻转法
1 翻转全部
2 翻转前k个
3 翻转剩下n-k个

Rotate Array

注意要处理k值的可能大于数组长度的情况

public class Solution {
    public void rotate(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }
    public void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}

Sort

看似要排序，其实是有限个值

Sort Colors

数组里有随机排列的0，1，2，要排序成按顺序的0,0,...,0,1,...,1,2,...,2

• 知道值是有限种的，并且因为最后是要有序，所以只需要知道每个值出现过多少次即可
• 异或知道每个数应该出现的区间（a.k.a 起始和终止坐标区间），直接在那一次中进行赋值，(最终会被正确的值override)
• 实现one pass的思路是通过发现1s的坐标们都是在0s的个数后再加上1s个数，2s的坐标们就是0s,1s,2s的所有个数加起来，所以可以发现在遍历的过程中，遇到0，所有的坐标都要++，遇到1，1和2的坐标要++，遇到2，2的坐标++；并且这里有个技巧是对于每个点都赋上相应的值，从2开始，这样最终每个点都会被overwrite成正确的值

class Solution {
    public void sortColors(int[] nums) {
        int len = nums.length;
        int n0 = 0, n1 = 0, n2 = 0;

        for (int i = 0; i < len; i++) {
            if (nums[i] == 0) n0++;
            if (nums[i] == 1) n1++;
            if (nums[i] == 2) n2++;
        }

        for (int i = 0; i < n0; i++) nums[i] = 0;
        for (int i = n0; i < n0+n1; i++) nums[i] = 1;
        for (int i = n0+n1; i < len; i++) nums[i] = 2;
    }
}

// one pass in place solution
void sortColors(int A[], int n) {
    int n0 = -1, n1 = -1, n2 = -1;
    for (int i = 0; i < n; ++i) {
        if (A[i] == 0) 
        {
            //永远先赋值2，然后1，然后0
            A[++n2] = 2; A[++n1] = 1; A[++n0] = 0;
        }
        else if (A[i] == 1) 
        {
            A[++n2] = 2; A[++n1] = 1;
        }
        else if (A[i] == 2) 
        {
            A[++n2] = 2;
        }
    }
}

// one pass in place solution
void sortColors(int nums[]) {
    int tmp = 0, low = 0, mid = 0, high = nums.length()-1;
    while(mid <= high) {
        if (nums[mid] == 0) {
            swap(low, mid);
            low++;
            mid++;
        } else if (nums[mid] == 1) {
            mid++;
        } else {
            swap(mid, high);
            high--;
        }
    }

}

Equals

// compare by object, if they are the same obj
arr1.equals(arr2)
arr1 == arr2
// compare by content/value
Arrays.equals(arr1, arr2)