数组

寻找数组的中心索引

给你一个整数数组 nums ，请计算数组的 中心下标 。

数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。

如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。

如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。

示例 1：

输入：nums = [1, 7, 3, 6, 5, 6]
输出：3
解释：
中心下标是 3 。
左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，
右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等。

示例 2：

输入：nums = [1, 2, 3]
输出：-1
解释：
数组中不存在满足此条件的中心下标。

示例 3：

输入：nums = [2, 1, -1]
输出：0
解释：
中心下标是 0 。
左侧数之和 sum = 0 ，（下标 0 左侧不存在元素），
右侧数之和 sum = nums[1] + nums[2] = 1 + -1 = 0 。

题解：

  1. 先求得数组中所有元素之和sum；
  2. 遍历数组，取当前下标左边的元素之和left_sum，同时sum减去已遍历元素，比较二者是否相等，相等则返回当前下标；
  3. 遍历结束，代表没有中心索引，返回-1；
class Solution {
    public int pivotIndex(int[] nums) {
        int sum = 0;
        for(int i=0;i<nums.length;i++){
            sum += nums[i];
        }
        int left_sum = 0;
        for(int i=0;i<nums.length;i++){
            sum -= nums[i];
            if(left_sum == sum){
                return i;
            }
            left_sum += nums[i];
        }
        return -1;
    }
}

搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

题解1：(二分法)

class Solution {
        public int searchInsert(int[] nums, int target) {
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            int midValue = nums[mid];
            if (midValue > target)
                hi = mid - 1;
            else if (midValue < target)
                lo = mid + 1;
            else
                return mid;
        }
        return lo;
    }
}

题解2：

  1. 如果数组中的值大于或者等于target，直接return
  2. 如果全部遍历完证明target是最大的数，直接插入末尾
class Solution {
    public int searchInsert(int[] nums, int target) {
        for(int i=0;i<nums.length;i++){
            if(nums[i]>=target) return i;
        }
        return nums.length;
    }
}

合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

题解：

  1. 对二维数组进行排序，按照第一列升序列排列
  2. 借用临时空间，判断是否需要何合并集合当前值，当前集合是否放入结果集触发点
class Solution {
    public int[][] merge(int[][] intervals) {
    if (intervals.length == 0) return intervals;
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        List<int []> list = new ArrayList<>();
        int term[] =intervals[0];
        for (int i = 1; i < intervals.length; i++) {
            if (term[1]>=intervals[i][0]){
                term[1]=Math.max(term[1],intervals[i][1]);
            }else {
                list.add(term);
                term=intervals[i];
            }
        }
        list.add(term);
        return list.toArray(new int[list.size()][2]);
    }
}

二维数组

旋转数组

给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。

不占用额外内存空间能否做到？

实例：

给定 matrix =
[
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
], 

原地旋转输入矩阵，使其变为:
[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]

题解：

class Solution {
    public static void rotate(int[][] matrix) {
        for (int i = 0; i < matrix.length/2; i++) {
            for (int j = i; j < matrix.length - 1 - i; j++) {
                exchange(matrix, i, j, j, matrix.length - 1 - i);
                exchange(matrix, i, j, matrix.length - 1 - i, matrix.length - 1 - j);
                exchange(matrix, i, j, matrix.length - 1 - j, i);
            }
        }
    }

    public static void exchange(int[][] matrix, int i1, int j1, int i2, int j2) {
        matrix[i1][j1] = matrix[i1][j1] + matrix[i2][j2];
        matrix[i2][j2] = matrix[i1][j1] - matrix[i2][j2];
        matrix[i1][j1] = matrix[i1][j1] - matrix[i2][j2];
    }
}

零矩阵

编写一种算法，若M × N矩阵中某个元素为0，则将其所在的行与列清零。

实例：

输入：
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
输出：
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]

题解：使用Boolean初始化时调用Arrays数组会影响运行速度，使用int数组即可。

import java.util.Arrays;
class Solution {
    public static void setZeroes(int[][] matrix) {
        Boolean[] row = new Boolean[matrix.length];
        Boolean[] col = new Boolean[matrix[0].length];
        Arrays.fill(row,Boolean.FALSE);
        Arrays.fill(col,Boolean.FALSE);
        for (int i=0;i<matrix.length;i++){
            for (int j=0;j<matrix[0].length;j++){
                if (matrix[i][j]==0){
                    row[i]=true;
                    col[j]=true;
                }
            }
        }
        for (int i=0;i<matrix.length;i++){
            for (int j=0;j<matrix[0].length;j++){
                if (col[j]||row[i]){
                    matrix[i][j]=0;
                }
            }
        }
    }
}

对角线遍历

给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。

实例：

img

输入：mat = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,4,7,5,3,6,8,9]

题解1：

class Solution {
    public int[] findDiagonalOrder(int[][] mat) {
        int n = mat.length;
        int m = mat[0].length;
        int[] result = new int[m*n];
        for(int l=0,i=0;l<=m+n-1;l++){
            if(l%2==0){
                for(int x=Math.min(l,n-1);x>=Math.max(0,l-m+1);x--){
                    result[i++] = mat[x][l-x];
                }
            }else{
                for(int x=Math.max(0,l-m+1);x<=Math.min(l,n-1);x++){
                    result[i++] = mat[x][l-x];
                }
            }
        }
        return result;
    }
}

题解2：

public static int[] findDiagonalOrder(int[][] matrix) {
        if (matrix.length == 0) {
            return new int[0];
        }
        int m = matrix.length;
        int n = matrix[0].length;
        //存放数组
        int[] ans = new int[m * n];
        //对角线方向次数
        int count = n + m - 1;
        //定义初始化 行标记，列标记，存放数组索引
        int row = 0, col = 0, Index = 0;
        //开始对角线循环
        for (int i = 0; i < count; i++) {
            //判断对角线方向（因题目初始从右上（即i=0）开始）：偶数右上，奇数左下
            if (i % 2 == 0) {
                //右上操作
                while (row >= 0 && col < n) {
                    //将矩阵数存入存放数组
                    ans[Index] = matrix[row][col];
                    //索引后移
                    Index++;
                    //右上规律：行减一，列加一
                    row--;
                    col++;
                }
                //判断是否为越界情况：不越界正常行加一，越界行加二，列减一；
                //（此处不理解的拿张草稿纸将循环中row和col的值遍历写一下对照矩阵图就明白了）
                if (col < n) {
                    row++;
                }
                else {
                    row += 2;
                    col--;
                }
            }
            //左下操作：按规律与右上相反即可
            else {
                while (row < m && col >= 0) {
                    ans[Index] = matrix[row][col];
                    Index++;
                    row++;
                    col--;
                }
                if (row < m) {
                    col++;

                } else {
                    row--;
                    col += 2;
                }
            }
        }
        // 返回存放数组
        return ans;
    }

字符串

最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例1：

输入：strs = ["flower","flow","flight"]
输出："fl"

示例2：

输入：strs = ["flower","flow","flight"]
输出："fl"

题解：

class Solution {
    public String longestCommonPrefix(String[] strs) {
        String str;
        String minStr = strs[0];
        int cnnt = 0;
        for (int i = 1; i < strs.length; i++) {
            if (strs[i].length() < minStr.length()) {
                minStr = strs[i];
            }
        }
        for (int i = 0; i < minStr.length(); i++) {
            str = minStr.substring(0, minStr.length() - i);
            cnnt = 0;
            for (String s : strs) {
                cnnt = s.indexOf(str) == 0 ? ++cnnt : cnnt;
            }
            if (cnnt >= strs.length) {
                return str;
            }
        }
        return "";
    }
}

最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

题解1：（中心延伸查找）

class Solution {
    public String longestPalindrome(String s) {
        if(s.length()<=1){
            return s;
        }
        int start=0,end=0,maxlen=1;
        int slen=s.length();
        for(int i=0;i<slen;i++){
            int left=i,right=i,len=1;
            while(left>0){
                if(s.charAt(left-1)==s.charAt(right)){
                    left--;len++;
                } else {
                    break;
                }
            }
            while(right<slen-1){
                if(s.charAt(left)==s.charAt(right+1)){
                    right++;len++;
                } else {
                    break;
                }
            }
            while(left>0&&right<slen-1){
                if(s.charAt(left-1)==s.charAt(right+1)){
                    left--;right++;len+=2;
                } else {
                    break;
                }
            }
            if(maxlen<len) {
                maxlen=len;
                start=left;
                end=right;
            }
        }
        return s.substring(start,end+1);
    }
}

题解2：（动态规划）

public String longestPalindrome(String s) {
        if (s == null|| s.length()<2) {
            return s;
        }
        int strLen=s.length();
        int maxStart=0,maxEnd=0,maxLen=1;
        boolean[][] dp = new boolean[strLen][strLen];
        for (int r=1;r<strLen;r++) {
            for (int l=0;l<r;l++) {
                if (s.charAt(l)==s.charAt(r)&&(r-l<=2||dp[l+1][r-1])) {
                    dp[l][r]=true;
                    if (r-l+1>maxLen) {
                        maxLen=r-l+1;
                        maxStart=l;
                        maxEnd=r;
                    }
                }
            }
        }
        return s.substring(maxStart, maxEnd + 1);
}

翻转字符串里的单词

给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 1：

输入：s = "the sky is blue"
输出："blue is sky the"

示例 2：

输入：s = "  hello world  "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。

示例 3：

输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

多题解：

class Solution {
    public String reverseWords(String s) {

    }
}
    // 方法一;思路：数组的翻转
    // 时间复杂度;O（n）
    // 空间复杂度：O（）
    public String reverseWords_1(String s) {
        String[] wordArray = s.split(" ");
        StringBuffer stringBuffer = new StringBuffer();
        int len = wordArray.length;
        // len-- 先执行表达式后赋值
        // --len 先赋值后执行表达式
        while (len-- > 0) {
            if (!wordArray[len].isEmpty()) {
                if (stringBuffer.length() > 0) {
                    stringBuffer.append(" ");
                }
                stringBuffer.append(wordArray[len]);
            }
        }
        return stringBuffer.toString();
    }

    // 方法二：双指针，原地解法
    // 时间复杂度：O(n)，n = s.length
    // 空间复杂度：O（1）
    public String reverseWords_2(String s) {
        // 删除任何前导和尾随空格。
        s = s.trim();
        // 字符串长度
        int len = s.length();
        // 单词起止坐标
        int begin = len, end = len;
        while (len-- > 0) {
            // 遇到非单词分隔的空格符的情况
            // 去掉空格符
            if (s.charAt(len) == ' ' && begin == end) {
                // 新的字符串
                s = s.substring(0, len) + s.substring(len + 1, s.length());
                begin--;
                end--;
                // 遇到单词分隔的空格符的情况
            } else if (s.charAt(len) == ' ' && begin != end) {
                String word = s.substring(begin, end);
                s = s.substring(0, len) + (end < s.length() ? s.substring(end, s.length()) : "") + word + " ";
                begin--;
                end = begin;
                // 非空格符的情况，寻找单词起始坐标
            } else {
                begin--;
            }
        }
        // 处理最后一个单词
        String word = s.substring(0, end);
        s = s.substring(end, s.length()) + word;
        return s;
    }

    public static void main(String[] args) {
        ReverseWords reverseWords = new ReverseWords();
        String s = "the sky is blue";
        reverseWords.reverseWords(s);
    }

    // 方法三：双指针,和方法二差不多，把需要返回的单词逐个加在s后面，最后截取s中需要返回的片段即可，比方法二简单很多
    // 时间复杂度：O(n)，n = s.length
    // 空间复杂度：O（1）
    // 方法四：递归
    public String reverseWords_4(String s) {
        s = s.trim();
        int len = s.length();
        while (len-- > 0) {
            if (s.charAt(len) == ' ') {
                String word = s.substring(len + 1, s.length());
                return word + " " + reverseWords(s.substring(0, len));
            }
        }
        return s;
    }

    // 方法五：栈
    public String reverseWords(String s) {
        // 设置一个栈存放单词
        Stack<String> stack = new Stack<>();
        s.trim();
        String[] wordArray = s.split(" ");
        for (String word : wordArray) {
            if (!word.isEmpty()) {
                stack.add(word);
            }
        }
        StringBuffer stringBuffer = new StringBuffer();
        while (!stack.isEmpty()) {
            stringBuffer.append(stack.pop());
            if (!stack.isEmpty()){
                stringBuffer.append(" ");
            }
        }
        return stringBuffer.toString();
    }

字符串匹配算法：KMP

实现 strStr()
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回  -1 。

示例 1：

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

示例 2：

输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

提示：

1 <= haystack.length, needle.length <= 104
haystack 和 needle 仅由小写英文字符组成

题解：（KMP）

class Solution {
    public int strStr(String haystack, String needle) {
        if(needle.length()==0){
            return 0;
        }
        int[] next = getNext(needle);
        int hlen = haystack.length();
        int nlen = needle.length();
        int i=0,j=0;
        while(i<hlen && j<nlen) {
            if(j<0||haystack.charAt(i)==needle.charAt(j)) {
                i++;j++;
            }else{
                j=next[j];
            }
        }
        if(j==nlen){
            return i-j;
        } else {
            return -1;
        }
    }
    public int[] getNext(String s) {
        int[] next = new int[s.length()];
        int i=0,j=-1;
        next[0]=-1;
        while(i<s.length()-1) {
            if(j<0||s.charAt(i)==s.charAt(j)){
                i++;
                j++;
                next[i]=j;
            }else{
                j=next[j];
            }
        }
        return next;
    }
}

双指针技巧

数组拆分 I

给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得从 1 到 n 的 min(ai, bi) 总和最大。

返回该 最大总和 。

示例 1：

输入：nums = [1,4,3,2]
输出：4
解释：所有可能的分法（忽略元素顺序）为：
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
所以最大总和为 4

示例 2：

输入：nums = [6,2,6,5,1,2]
输出：9
解释：最优的分法为 (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9

题解：（计数排序）

class Solution {
    public int arrayPairSum(int[] nums) {
        int[] sumTotal = new int[20001];
        for(int num:nums){
            sumTotal[num+10000]++;
        }
        int sum = 0;
        for(int i=20000;i>0;i--) {
            if((sumTotal[i]&1)==0) {
                sum += (i-10000)*sumTotal[i]/2;
            }else{
                sum += (i-10000)*(sumTotal[i]-1)/2;
                if(i!=0){
                    sumTotal[i-1]++;
                }
            }
        }
        return sum;
    }
}

两数之和 II - 输入有序数组

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列  ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。
示例 1：

输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

示例 2：

输入：numbers = [2,3,4], target = 6
输出：[1,3]
解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。

示例 3：

输入：numbers = [-1,0], target = -1
输出：[1,2]
解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

题解：

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int head=0,tail=numbers.length-1;
        while(true){
            int sum = numbers[head]+numbers[tail];
            if(sum>target){
                tail--;
            }else if(sum<target){
                head++;
            }else{
                break;
            }
        }
        return new int[] {head+1,tail+1};
    }
}

移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,3,0,4]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

题解：

class Solution {
    public int removeElement(int[] nums, int val) {
        int i=0;
        for(int j=0;j<nums.length;j++){
            if(nums[j]==val){
                continue;
            }else{
                nums[i++]=nums[j];
            }
        }
        return i;
    }
}

最大连续1的个数

给定一个二进制数组 nums ， 计算其中最大连续 1 的个数。

示例 1：

输入：nums = [1,1,0,1,1,1]
输出：3
解释：开头的两位和最后的三位都是连续 1 ，所以最大连续 1 的个数是 3.

示例 2:

输入：nums = [1,0,1,1,0,1]
输出：2

题解：

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int count=0,tmp=0;
        for(int num:nums){
            tmp = num==1 ? ++tmp : 0;
            count = count<tmp ? tmp : count;
        }
        return count;
    }
}

长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

 

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

 题解：

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int l=0,sum=0,tmp=0,count=nums.length;
        for(int num:nums){
            sum+=num;
            tmp++;
            while(sum-nums[l]>=target){
                sum-=nums[l];
                l++;tmp--;
            }
            if(sum>=target){
                count = tmp<count ? tmp:count;
            }
        }
        if(sum<target){
            return 0;
        }
        return count;
    }
}

小结

杨辉三角

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

示例 1:

输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2:

输入: numRows = 1
输出: [[1]]

题解：

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> arr = new ArrayList<>();
        arr.add(new ArrayList<>());
        arr.get(0).add(1);
        for(int i=1,numColumns=i+1;i<numRows;i++,numColumns++){
            arr.add(new ArrayList<>());
            for(int j=0;j<numColumns;j++){
                if(j==0||j==numColumns-1){
                    arr.get(i).add(1);
                }else{
                    arr.get(i).add(arr.get(i-1).get(j-1)+arr.get(i-1).get(j));
                }
            }
        }
        return arr;
    }
}

杨辉三角 II

给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。

示例 1:

输入: rowIndex = 3
输出: [1,3,3,1]

示例 2:

输入: rowIndex = 0
输出: [1]

示例 3:

输入: rowIndex = 1
输出: [1,1]

题解：

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> row = new ArrayList();
        row.add(1);
        if(rowIndex==0){
            return row;
        }
        for(int i=1;i<rowIndex+1;i++){
            row.add(1);
            for(int j=i-1;j>=0;j--){
                if(j==0){
                    row.set(0,1);
                }else{
                    row.set(j,row.get(j)+row.get(j-1));
                }
            }
        }
        return row;
    }
}

寻找旋转排序数组中的最小值

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

示例 2：

输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 3 次得到输入数组。

示例 3：

输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。

题解：（二分法）

class Solution {
    public int findMin(int[] nums) {
        // 旋转0次与旋转n次都是原升序数组，直接输出最小值即可
        if(nums[0]<nums[nums.length-1]||nums.length==1){
            return nums[0];
        }
        // 经过n次旋转后0到length-n-1都为左侧，其余为右侧，左侧区域数值永远大于右侧
        int l=0,r=nums.length-1,m;
        while(l!=r-1){ //l在最大值，r在最小值
            m=(l+r)/2;
            if(nums[m]>nums[r]&&nums[m]>nums[l]){
            // 左侧区域
                l=m;
            }else{
            // 右侧区域
                r=m;
            }
        }
        return nums[r];
    }
}
最后修改：2024 年 03 月 09 日
© 允许规范转载
如果觉得我的文章对你有用，就是对我最好的赞赏。