数组

1 两数之和

public class Solution {
    public int[] twoSum (int[] numbers, int target) {
        // write code here
        for (int i = 0; i < numbers.length; i++) {
            for (int j = i + 1; j < numbers.length; j++) {
                if (numbers[i] + numbers[j] == target) return new int[]{i + 1, j + 1};
            }
        }
        return null;
    }
}

2 返回集合的所有子集

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> subsets(int[] S) {
        Arrays.sort(S);
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        dfs(S, 0, res, new ArrayList<>());
        return res;
    }
    
    private static void dfs(int[] s, int start, ArrayList<ArrayList<Integer>> res, ArrayList<Integer> list) {
        if (!res.contains(list)) res.add(new ArrayList<>(list));
        for (int i = start; i < s.length; i++) {
            list.add(s[i]);
            dfs(s, i + 1, res, list);
            list.remove(list.size() - 1);
        }
    }
}

3 加起来和为目标值得组合

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
        if (num == null || num.length == 0 || target <= 0) return new ArrayList();
        Arrays.sort(num);
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        dfs(num, target, 0, res, new ArrayList<Integer>());
        return res;
    }
    
    private static void dfs(int[] num, int target, int start, ArrayList<ArrayList<Integer>> res, ArrayList<Integer> list) {
        // 计算和
        int sum = 0;
        if (list.size() > 0 && !res.contains(list)) {
            for (int i = 0; i < list.size(); i++) {
                sum += list.get(i);
            }
        }
        if (sum == target) res.add(new ArrayList<>(list)); // 命中
        else if (sum < target) {
            for (int i = start; i < num.length; i++) {
                list.add(num[i]); 
                dfs(num, target, i + 1, res, list);
                list.remove(list.size() - 1);
            }
        }
    }
}

4 合并两个有序数组

public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        int res[] = new int[m + n];
        int m1 = 0;
        int n1 = 0;
        while (m1 < m || n1 < n) {
            if (m1 >= m) {
                res[m1 + n1] = B[n1];
                n1++;
            } else if (n1 >= n) {
                res[m1 + n1] = A[m1];
                m1++; 
            } else if (A[m1] < B[n1]) {
                res[m1 + n1] = A[m1];
                m1++;
            } else {
                res[m1 + n1] = B[n1];
                n1++;
            }
        }
        for (int i = 0; i < m + n; i++) {
            A[i] = res[i];
        }
    }
}

5 斐波那契数列

public class Solution {
    // f[0] = 0; f[1] = 1; f[n] = f[n - 1] + f[n - 2]; 
    public int Fibonacci(int n) {
        if (n <= 1) return n;
        int sum = 1;
        int one = 0;
        for (int i = 2; i <= n; i++) {
            // f[n] = f[n - 1] + f[n - 2];
            sum = sum + one;
            // f[n - 1] = f[n] - f[n - 2];
            one = sum - one;
        }
        return sum;
    }
}

6 螺旋矩阵

import java.util.*;
public class Solution {
    public ArrayList<Integer> spiralOrder(int[][] matrix) {
        ArrayList<Integer> res = new ArrayList<>();
        if (matrix.length == 0) return res;
        int top = 0;
        int left = 0;
        int bottom = matrix.length - 1;
        int right = matrix[0].length - 1;
        
        while (top <= bottom && left <= right) {
            // 1 上面 从左到右
            for (int i = left; i <= right; i++) {
                res.add(matrix[top][i]);
            }
            // 2 右面 从上到下
            for (int i = top + 1; i <= bottom; i++) {
                res.add(matrix[i][right]);
            }
            // 3 下面 从右到左 top == botom 时 在步骤1 时已处理过，不在重复处理
            for (int i = right - 1; i >= left && top != bottom; i--) {
                res.add(matrix[bottom][i]);
            }
            // 4 左面 从下到上 left == right 时 在步骤2时已处理过，不在重复处理
            for (int i = bottom - 1; i >= top + 1 && left != right; i--) {
                res.add(matrix[i][left]);
            }
            // 一圈走完 全部减1
            top++;
            right--;
            bottom--;
            left++;
        }
        return res;
    }
}

7 矩阵查找

请写出一个高效的在m*n矩阵中判断目标值是否存在的算法，矩阵具有如下特征：
每一行的数字都从左到右排序
每一行的第一个数字都比上一行最后一个数字大

public class Solution {
    /**
     * 
     * @param matrix int整型二维数组 
     * @param target int整型 
     * @return bool布尔型
     */
    public boolean searchMatrix (int[][] matrix, int target) {
        // write code here
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
        int start = 0;
        int end = matrix.length * matrix[0].length - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            int val = matrix[mid / matrix[0].length][mid % matrix[0].length];
            if (val == target) return true;
            if (val > target) {
                end = mid  - 1;
            } else {
                start = mid + 1;
            }
        }
        return false;
    }
}

8 数组中相加和为0的三元组

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        Arrays.sort(num);
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        int length = num.length;
        for (int i = 0; i < length; i++) {
            // 第一个数 num[i] 第二个数 num[mid] 第三个数 num[right]
            int mid = i + 1;
            int right = length - 1;
            while (mid < right) {
                int sum = num[i] + num[mid] + num[right];
                if (sum == 0) {
                    ArrayList<Integer> temp = new ArrayList<>();
                    temp.add(num[i]);
                    temp.add(num[mid]);
                    temp.add(num[right]);
                    res.add(temp);
                    // 去重 mid = mid + 1 时 已经被记录，不能重复记录
                    while (mid + 1 < right && num[mid] == num[mid + 1]) mid++;
                    // 去重 right = right - 1 时 已经被记录，不能重复记录
                    while (right - 1 > mid && num[right - 1] == num[right]) right--;
                    mid++;
                    right--;
                } else if (sum > 0) {
                    // 结果太大
                    right--;
                } else mid++;  // 结果太小
            }
            // 第一个数去重
            while (i < length - 2 && num[i + 1] == num[i]) i++;
        }
        return res;
    }
}

9 缺失数字

import java.util.*;
public class Solution {
    public int solve (int[] a) {
        // write code here
        int target = 0;
        int left = 0;
        int right = a.length - 1;
        while (left < right) {
            int mid = (right + left) >> 1;
            if (mid == a[mid]) left = mid + 1; // 相等 说明不在左边
            else if (mid < a[mid]) right = mid; // 小于 说明在左边
        }
        return left;
    }
}

10 在转动过的有序数组中寻找目标

public class Solution {
    public int search (int[] A, int target) {
        // write code here
        int left = 0;
        int right = A.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (A[mid] == target) return mid;
            if (A[mid] >= A[left]) {
                // 左侧有序
                if (A[mid] > target && A[left] <= target) right = mid - 1;
                else left = mid + 1;
            } else {
                // 右侧有序
                if (A[mid] < target && A[right] >= target) left = mid + 1;
                else right = mid - 1;
            }
        }
        return -1;
    }
}

11 买卖股票的最好时机

public class Solution {
    public int maxProfit (int[] prices) {
        // write code here
        if (prices.length == 0) return 0;
        int min = prices[0];
        int max = 0;
        for (int i = 1; i < prices.length; i++) {
            min = Math.min(min, prices[i]);
            max = Math.max(max, prices[i] - min);
        }
        return max;
    }
}

12 两个相等的排序数组中找到上中位数

public class Solution {
    public int findMedianinTwoSortedAray (int[] arr1, int[] arr2) {
        // write code here
        int a1 = 0, b1 = 0, mid = arr1.length;
        int res = arr1[0] < arr1[0] ? arr1[0] : arr2[0];
        while (a1 + b1 < mid) {
            if (arr1[a1] < arr2[b1]) res = arr1[a1++];
            else res = arr2[b1++];
        }
        return res;
    }
}

13 矩阵的最小路径和

public class Solution {
    public int minPathSum (int[][] matrix) {
        // write code here
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                // 第一个数 啥都不做 
                if (i == 0 && j == 0) {}
                // 第一行
                else if (i == 0) matrix[0][j] = matrix[0][j] + matrix[0][j - 1];
                // 第一列
                else if (j == 0) matrix[i][0] = matrix[i][0] + matrix[i - 1][0];
                else matrix[i][j] += Math.min(matrix[i - 1][j], matrix[i][j - 1]);
            }
        }
        return matrix[matrix.length - 1][matrix[0].length - 1];
    }
}

14 数组中未出现的最小正整数

public class Solution {
    public int minNumberdisappered (int[] arr) {
        // write code here
        int min = 1;
        int index = 0;
        while (index < arr.length) {
            if (arr[index] == min) {
                min++;
                index = 0;
            } else index++;
        }
        return min;
    }
}

15 合并区间

public class Solution {
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        intervals.sort((a, b) -> a.start - b.start);
        ArrayList<Interval> res = new ArrayList<>();
        int i = 0;
        int left = 0;
        int right = 0;
        while (i < intervals.size()) {
            left = intervals.get(i).start;
            right = intervals.get(i).end;
            while (i < intervals.size() - 1 && right >= intervals.get(i + 1).start) {
                right = Math.max(right, intervals.get(++i).end);
            }
            res.add(new Interval(left, right));
            i++;
        }
        return res;
    }
}

16 顺时针旋转矩阵

public class Rotate {
    public int[][] rotateMatrix(int[][] mat, int n) {
        // write code here
        // 行编号列编号从0开始
        // 顺时针 行编号 == 原列编号, 列编号 == 原行数 - 1 - 原行编号 
        int res[][] = new int[mat[0].length][mat.length];
        for (int i = 0; i < mat.length; i++) {
            for (int j = 0; j < mat[i].length; j++) {
                res[j][mat.length - 1 - i] = mat[i][j];
            }
        }
        return res;
    }
}

17 数组中的最长连续子序列

public class Solution {
    public int MLS (int[] arr) {
        // write code here
        if (arr == null || arr.length == 0) return 0;
        Arrays.sort(arr);
        int max = 1;
        int temp = 1;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i - 1] + 1 == arr[i]) {
                // 满足条件 获取最大值
                max = Math.max(max, ++temp);
            } else if (arr[i - 1] == arr[i]) continue; // 前后相等 跳过
            else temp = 1; // 重新计数
        }
        return max;
    }
}

18 寻找最后的山峰

山峰元素是指其值大于或等于左右相邻值的元素。给定一个输入数组nums，任意两个相邻元素值不相等，数组可能包含多个山峰。找到索引最大的那个山峰元素并返回其索引。

public class Solution {
    public int solve (int[] a) {
        // write code here
        if (a == null || a.length == 0) return -1;
        for (int i = a.length - 1; i >= 1; i--) {
            if (a[i] >= a[i - 1]) return i;
        }
        return 0;
    }
}