LeetCode热题 100整理

53. 最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1]
输出：1

 示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

提示： 

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

 题目分析：

思考1：从第一个数开始累加，找到累加最大的数和最小的数，然后用最大的减去最小的。其中最大的数要在最小的数右边。结果失败，忽略了一个数字的时候以及整个数列都是负数时，会运行错误。

代码如下：

class Solution {
public:int maxSubArray(vector<int>& nums) {int len = nums.size();int sum = 0;int a[100002];a[0] = 0;int max = a[0];int min = a[0];if (len <= 1) {return nums[0];}else{for (int i = 0; i < len; i++) {sum += nums[i];a[i + 1] = sum;}int maxi;for (int i = 0; i < len + 1; i++) {if (a[i] >= max) {max = a[i];maxi = i;}}for (int j = 0; j < maxi; j++) {if (a[j] <= min) {min = a[j];}}int res = max - min;return res;}}
};

思考2：通过动态规划的思想，依旧是从前往后加，但是如果前一个是负数，就不要累加，重新加当前的值。最后找最大的累加值即可。

代码如下：

class Solution {
public:int maxSubArray(vector<int>& nums) {int n = nums.size();int maxnum = nums[0];for (int i = 1; i < n; i++) {if (nums[i - 1] > 0) {nums[i] += nums[i - 1];}maxnum = max(maxnum, nums[i]);}return maxnum;}};

118. 杨辉三角

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例 1:

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

示例 2:

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

提示:

• 1 <= numRows <= 30

 

代码如下：

class Solution {
public:vector<vector<int>> generate(int numRows) {vector<vector<int>> a(numRows);// a[0][0]=1;// a[1][0]=1;// a[1][1]=1;for (int i = 0; i < numRows; i++) {a[i].resize(i + 1);for (int j = 0; j <= i; j++) {if (i == 0 || i == 1 || j == 0 || j == i) {a[i][j] = 1;}else{a[i][j] = a[i - 1][j] + a[i - 1][j - 1];}}}return a;}
};