LeetCode7-53

LeetCode07 整数反转

LeetCode53 最大子序和

leetcode7 整数反转

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−2^31, 2^31 − 1] ，就返回 0。

假设环境不允许存储 64 位整数（有符号或无符号）。

class Solution {
public:
    int reverse(int x) {
        int result = 0;
        while(x != 0){
            if(result > INT_MAX / 10 || result < INT_MIN / 10)
                return 0;
            int a = x % 10;
            x /= 10;
            result = result * 10 + a;
        }
        return result;
    }    
};

这道题的算法思想为通过数学的方法，模拟数字的弹出和推入，关键点在于溢出的检测。

2^31-1=2147483647 -2^31=-2147483648

我们要保证返回的result不会溢出，就要在数字推入result前检测，方法为

if(result > INT_MAX / 10 || result < INT_MIN / 10)

不能使用result * 10 < INT_MAX.

• 这条语句同时也保证了推入数字a时也不会溢出，因为若要溢出，原数据x为10位数并且也小于INT_MAX，则最后推入的数字一定小于等于2，不会大于7而导致溢出，小于零时同理。

  复杂度分析

• 时间复杂度：O(log |x|)。翻转的次数即 x十进制的位数

---

leetcode53 最大子序和

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

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

• 动态规划

  我们通常的惯性思维是以子序列的开头为基准，先遍历出以 a 为开头的所有子序列，再遍历出以 b 为开头的…但是动态规划为了找到不同子序列之间的递推关系，恰恰是以子序列的结束点为基准的

  为了保证计算子问题能够按照顺序、不重复地进行，动态规划要求已经求解的子问题不受后续阶段的影响。这个条件也被叫做「无后效性」

定义状态（定义子问题）

dp[i]：表示以 nums[i] 结尾 的 连续 子数组的最大和。

状态转移方程

$$
dp[i]=
\begin{cases}
dp[i-1]+nums[i],dp[i-1]>0\
nums[i],dp[i-1]\le0
\end{cases}
$$

还可以写成这样

$dp[i] = max{dp[i-1]+nums[i],,,,nums[i]}$

输出

把所有的 dp[0]、dp[1]、……、dp[n - 1] 都看一遍，取最大值

优化空间

dp[i] 的值只与dp[i-1]有关，可以只使用一个变量来维护dp[i-1], 空间复杂度优化到O(1)。