# 数组与矩阵

所谓数组，是有序的元素序列。若将有限个类型相同的变量的集合命名，那么这个名称为数组名。组成数组的各个变量称为数组的分量，也称为数组的元素，有时也称为下标变量。用于区分数组的各个元素的数字编号称为下标。数组是在程序设计中，为了处理方便，把具有相同类型的若干元素按无序的形式组织起来的一种形式。

# 1 搜索二维数组

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。
示例 1:
输入:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3
输出: true

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        if(m == 0)  return false;
        int n = matrix[0].length;
        int lo =0, hi = m*n-1;
        while(hi >= lo){
            int mid = (hi+lo)/2;
            int r = mid/n;
            int l = mid%n;
            if(matrix[r][l] == target){
                return true;
            }
            else if(matrix[r][l] > target){
                
                hi = mid-1;
            }
            else{
                lo = mid+1;
            }
        }
        return false;
    }
}

# 2搜索二维矩阵 II

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
现有矩阵 matrix 如下：
[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。

idea: 先从第一行最后一列开始，比target小就row++，比target小 cl--、else return true；

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix == null || matrix.length < 1 || matrix[0].length <1 ){
            return false;
        }
        int cl = matrix[0].length-1;
        int len =matrix.length;
        int row = 0;
        while(row< len && cl >=0){
            if(matrix[row][cl] < target ){
                row++;
            }
            else if( matrix[row][cl] > target){
                cl--;
            }
            else{
                return true;
            }
        }
        return false;        
    }
}

# 3 在排序数组中查找元素的第一个和最后一个位置

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置

你的算法时间复杂度必须是 O(log n) 级别。

如果数组中不存在目标值，返回 [-1, -1]。

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8

输出: [3,4]

class Solution {
     private int extremeInsertionIndex(int[] nums, int target, boolean left) {
        int lo = 0;
        int hi = nums.length;
        while (lo < hi) {
            int mid = (lo+hi)/2;          
             if((nums[mid] > target)  || (left && nums[mid] == target)   ){
                 hi = mid;
             }
            else if((nums[mid] < target)  || (!left && nums[mid] == target)   ){
                lo = mid+1;
            }
            }
        return lo;
    }
    public int[] searchRange(int[] nums, int target) {
        int[] targetRange = {-1, -1};

        int leftIdx = extremeInsertionIndex(nums, target, true);

        // assert that `leftIdx` is within the array bounds and that `target`
        // is actually in `nums`.
        if(leftIdx ==nums.length || nums[leftIdx] != target){
            return targetRange;
        }
        targetRange[0] = leftIdx;
        targetRange[1] = extremeInsertionIndex(nums, target, false)-1;
        return targetRange;
    }
}

# 4最长连续递增序列

给定一个未经排序的整数数组，找到最长且连续的的递增序列。

示例 1:

输入: [1,3,5,4,7]

输出: 3

解释: 最长连续递增序列是 [1,3,5], 长度为3。

尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为5和7在原数组里被4隔开。

idea: 当i= 0的时候 , i>0;

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int ans = 0, anchor = 0;
        for (int i = 0; i < nums.length; ++i) {
            if (i > 0 && nums[i-1] >= nums[i]) anchor = i;
            ans = Math.max(ans, i - anchor + 1);
        }
        return ans;
    }
}

# 5 最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],

输出: 6

解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

idea: ans 保存以前的最大值， sum代表当前节点的最大值，动态更新ans;

class Solution {
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        int sum = 0;
        int ans = nums[0];
        for(int i =0; i<len; i++){
            if(sum > 0){
                sum +=nums[i];
            }else{
                sum = nums[i];
            }
            ans = Math.max(sum, ans);
        }
        return ans;
    }
}

# 6 汇总区间

给定一个无重复元素的有序整数数组，返回数组区间范围的汇总。

示例 1:

输入: [0,1,2,4,5,7]

输出: ["0->2","4->5","7"]

解释: 0,1,2 可组成一个连续的区间; 4,5 可组成一个连续的区间。

idea: 双指针用 i表示开始节点， j表示结束节点，用 j+1动态更新i点的值。

public class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> summary = new ArrayList<>();
        for (int i = 0, j = 0; j < nums.length; ++j) {
            // check if j + 1 extends the range [nums[i], nums[j]]
            if (j + 1 < nums.length && nums[j + 1] == nums[j] + 1)
                continue;
            // put the range [nums[i], nums[j]] into the list
            if (i == j)
                summary.add(nums[i] + "");
            else
                summary.add(nums[i] + "->" + nums[j]);
            i = j + 1;
        }
        return summary;
    }
}

# 7按奇偶排序数组

给定一个非负整数数组 A，返回一个数组，在该数组中， A 的所有偶数元素之后跟着所有奇数元素。
你可以返回满足此条件的任何数组作为答案。
输入：[3,1,2,4]
输出：[2,4,3,1]
输出 [4,2,3,1]，[2,4,1,3] 和 [4,2,1,3] 也会被接受。

idea: 双指针 lo 偶数指针， hi奇数指针。 while( lo < hi) 动态更新lo， hi。

# 类型题

可以被3整除，与不可以的。

class Solution {
    public int[] sortArrayByParity(int[] A) {
        int  len =A.length;
        int[] B = new int[len];
        int index = 0;
        int lenB = len-1;
        for(int  i = 0; i<len; i++){
            if(A[i] % 2 == 0){
                B[index++] = A[i];
            }
            else{
                B[lenB--] = A[i];
            }
        }
        return B;
    }
}

# 8 嵌套的数组

索引从0开始长度为N的数组A，包含0到N - 1的所有整数。找到并返回最大的集合S，S[i] = {A[i], A[A[i]], A[A[A[i]]], ... }且遵守以下的规则。
假设选择索引为i的元素A[i]为S的第一个元素，S的下一个元素应该是A[A[i]]，之后是A[A[A[i]]]... 以此类推，不断添加直到S出现重复的元素。
示例 1:
输入: A = [5,4,0,3,1,6,2]
输出: 4
解释: 
A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.
其中一种最长的 S[K]:
S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}

idea: 双重循环，

class Solution {
    public int arrayNesting(int[] nums) {
        int len = nums.length;
        int max=0;
        for(int i =0; i<len; i++){
            int count = 0;
            int j = i;
            while(nums[j] != -1){
                count++;
                int t = nums[j];
                nums[j] = -1;
                j = t;
            }
            max= Math.max(max, count);
        }
        return max;
    }
}

← 常见算法与数据结构的总结 DFS与BFS →