一些基本的数组操作

需要分清数组的index，长度（范围，个数），第k个数，间隔。

• index是从0开始，也就是k-1，最大的index为length-1
• 长度为max(index)+1，个数为最右的index减去最左的加1
• 间隔为数组元素个数减去1

数组合并

数组b合并到a后面并返回新数组:

public static void main(String []args){
    int[] a = {1,2,3};
    int[] b = {4,5};
    int lenA = a.length;
    int lenB = b.length;
    int[] res = new int[lenA + lenB];
    for (int i = 0; i < lenA; i++) {
        res[i] = a[i];
    }
    for (int i = lenA; i < lenA + lenB; i++) {
        res[i] = b[i - lenA];
    }
    System.out.println(Arrays.toString(res));
}

从前向后合并两个排序的数组:

public static int[] merge(int[] nums1, int[] nums2) {
    int lenA = nums1.length, lenB = nums2.length;
    int i = 0, j = 0, k = 0;
    int[] res = new int[lenA + lenB];
    while (i < lenA && j < lenB) {
        if (nums1[i] < nums2[j]) {
            res[k] = nums1[i++];
        } else {
            res[k] = nums2[j++];
        }
        k++;
    }
    while (i < lenA) {
        res[k++] = nums1[i++];
    }
    while (j < lenB) {
        res[k++] = nums2[j++];
    }
    return res;
}

inplace合并两个数组

public void merge(int[] nums1, int m, int[] nums2, int n) {
    int i = m - 1;
    int j = n - 1;
    int k = m + n - 1;
    while (i >= 0 && j >= 0) {
        if (nums1[i] > nums2[j]) {
            nums1[k--] = nums1[i--];
        } else {
            nums1[k--] = nums2[j--];
        }
    }
    while (j >= 0) {
        nums1[k--] = nums2[j--];
    }
    while (i >= 0) {
        nums1[k--] = nums1[i--];
    }
}

拆分数组并求和

将数组拆分成长度为3，和2的两个子数组，并求出各部分的和。

int[] len = {3, 2}; // sub-array length
int[] arr = {4, 4, 5, 4, 4};
int p = 0; // point to the current index
for (int i = 0; i < len.length; i++) {
    int sum = 0;
    int length = p + len[i];
    while (p < length) {
        sum += arr[p];
        p++;
    }
    System.out.println(sum);
}

将数组拆分成大小最多为n的chunk

// split from right to left
public static String[] split(String s, int n) {
    s = s.replaceAll("[,\\s+]", "");
    List<String> list = new ArrayList<>();
    int i = s.length() - 3;
    while (i > 0) {
        list.add(s.substring(i, i + 3));
        i -= 3;
    }
    list.add(0, s.substring(0, i + 3)); // add the first index
    return list.toArray(new String[0]);
}

public static String[] splitReserve(String s, int n) {
    List<String> list = new ArrayList<>();
    for (int i = s.length() - 1; i >= 0; i = i - n) {
        StringBuilder sb = new StringBuilder();
        int j = i;
        while (j >= 0 && j > i - n) {
            sb.insert(0, s.charAt(j));
            j--;
        }
        list.add(0, sb.toString());
    }
    return list.toArray(new String[0]);
}

// split from left to right
public static String[] split(String s, int n) {
    List<String> list = new ArrayList<>();
    for (int i = 0; i < s.length(); i = i + n) {
        StringBuilder sb = new StringBuilder();
        int j = i;
        while (j < s.length() && j < i + n) {
            sb.append(s.charAt(j));
            j++;
        }
        list.add(sb.toString());
    }
    return list.toArray(new String[0]);
}

public static String[] split2(String s, int n) {
    List<String> list = new ArrayList<>();
    for (int i = 0; i < s.length(); i += n) {
        if (i + n < s.length()) // check the boundary
            list.add(s.substring(i, i + n));
        else
            list.add(s.substring(i));
    }
    return list.toArray(new String[0]);
}

shuffle数组

生成一串范围内的随机数组

// return an array with size n range in [l, r]
public int[] randomArray(int n, int l, int r) {
    if (l >= r) {
        throw new ArrayIndexOutOfBoundsException();
    }
    int[] arr = new int[n];
    for (int i = 0; i < n; i++) {
        arr[i] = rand.nextInt(r - l + 1) + l;
    }
    return arr;
}
// int[] arr = s.randomArray(10000, 10, 100);
// rand.nextInt(100 - 50) + 50); // [50, 100)
// rand.nextInt(100 - 50 + 1) + 50); // [50, 101)

判断是否排序

// Ascending sort 
public boolean isSorted(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        if (arr[i + 1] < arr[i])
            return false;
    }
    return true;
}

数组reverse

• 造轮子: 双指针+交换;dfs
• Java: 要会写Comparator

public void reverseString(char[] s) {
    int l = 0, r = s.length - 1;
    while (l < r) {
        char tmp = s[l];
        s[l++] = s[r];
        s[r--] = tmp;
    }
}

public void reverseString1(char[] s) {
    dfs(s, 0, s.length - 1);
}

public void dfs(char[] s, int l, int r) {
    if (l >= r) return;
    char tmp = s[l];
    s[r] = s[l];
    s[l] = tmp;
    dfs(s, l + 1, r - 1);
}

注意++的意思，千万别写成dfs(s, l++, r--);

字典序最大

也就是寻找开头最大的串串

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    String s = in.nextLine();
    char max = 'a';
    StringBuilder sb = new StringBuilder();
    for (int i = s.length() - 1; i >= 0; i--) {
        if (s.charAt(i) >= max) {
            max = s.charAt(i);
            sb.append(max);
        }
    }
    System.out.println(sb.reverse().toString());
}

public String solution(String s) {
    int index = 0;
    String res = "";
    for (int j = 'z' - 'a' + 1; j >= 0; j--) {
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) - 'a' == j && i >= index) {
                res += s.charAt(i);
                index = i;
            }
        }
    }
    return res;
}