【LeetCode】代码模板，刷题必会

力扣Hot100

大数相乘

43. 字符串相乘 大数相乘
1、模拟乘法手算累加

      7 8 9 6 5 2
×         3 2 1 1
-----------------
      7 8 9 6 5 2   <---- 第1趟 
    7 8 9 6 5 2     <---- 第2趟 
   ..........       <---- 第n趟 
-----------------
  ? ? ? ? ? ? ? ?   <---- 最后的值用另一个数组表示 

2、模拟乘法累加 - 改进
先处理多*1，再推倒到多*多

        9  8
×       2  1
-------------
       (9)(8)  <---- 第1趟: 98×1的每一位结果 
  (18)(16)     <---- 第2趟: 98×2的每一位结果 
-------------
  (18)(25)(8)  <---- 这里就是相对位的和，还没有累加进位 

大数相除：
一种简单的思路就是：对于大数a/b，一般最多要求求到其整数解或者余数，即a/b=c……d（a,b,c,d均为整）;也就是a里面有c个b，并且还剩下d。核心是先求c是多少，对于程序来说，可以通过枚举啊，将除法变成减法，从a中不断减b，一直到不能减为止。

最长回文子串

最长回文子串
思路：动态规划
定义一个二维动态数组dp,dp[i][j]表示从第i个字符开始到第j个字符结尾的字符串是否为回文字符串，初始条件就是每个字符都是一个回文字符串，也就是dp[i][i] = true;
利用i,j两个指针遍历整个字符串，填满整个动态数组的状态值，取值范围为j: [1,len); i: [0,j)
s_i 不等于 s_j ==> false;
s_i 等于 s_j ==> i和j中间是否为空，为空则true;不为空，则取决于中间字符串是否为回文字符串的状态值；
【力扣Hot100】5. 最长回文子串

最长公共子序列

1143. 最长公共子序列
思路：动态规划
1、定义
dp[i][j] 表示text1[0:i-1] 和 text2[0:j-1] 的最长公共子序列的长度。 （注：text1[0:i-1] 表示的是 text1 的 第 0 个元素到第 i - 1 个元素，两端都包含）之所以 dp[i][j] 的定义不是 text1[0:i] 和 text2[0:j] ，是为了方便当 i = 0 或者 j = 0 的时候，dp[i][j]表示的为空字符串和另外一个字符串的匹配，这样 dp[i][j] 可以初始化为 0。
2.、状态转移方程
知道状态定义之后，我们开始写状态转移方程。
当 text1[i - 1] == text2[j - 1] 时，说明两个子字符串的最后一位相等，所以最长公共子序列又增加了 1，所以 dp[i][j] = dp[i - 1][j - 1] + 1；举个例子，比如对于 ac 和 bc 而言，他们的最长公共子序列的长度等于 a 和 b 的最长公共子序列长度 0 + 1 = 1。
当 text1[i - 1] != text2[j - 1] 时，说明两个子字符串的最后一位不相等，那么此时的状态dp[i][j]应该是 dp[i - 1][j] 和 dp[i][j - 1] 的最大值。举个例子，比如对于 ace 和 bc 而言，他们的最长公共子序列的长度等于 ① ace 和 b 的最长公共子序列长度0 与 ② ac 和 bc 的最长公共子序列长度1 的最大值，即 1。
解题参考
3、动态规划也是有套路的：
单个数组或者字符串要用动态规划时，可以把动态规划 dp[i] 定义为 nums[0:i] 中想要求的结果；当两个数组或者字符串要用动态规划时，可以把动态规划定义成两维的 dp[i][j] ，其含义是在 A[0:i] 与 B[0:j] 之间匹配得到的想要的结果。

最大子序和

53. 最大子序和
1、遍历思维
示例: [a, b , c, d , e]
解答这类题目, 省略不掉遍历, 因此我们先从遍历方式说起
通常我们遍历子串或者子序列有三种遍历方式：

1. 以某个节点为开头的所有子序列: 如 [a]，[a, b]，[ a, b, c] ... 再从以 b 为开头的子序列开始遍历 [b] [b, c]。
2. 根据子序列的长度为标杆，如先遍历出子序列长度为 1 的子序列，在遍历出长度为 2 的 等等。
3. 以子序列的结束点为基准，先遍历出以某个节点为结束的所有子序列，因为每个节点都可能会是子序列的结束节点，因此要遍历下整个序列，如: 以 b 为结束点的所有子序列: [a , b] [b] 以 c 为结束点的所有子序列: [a, b, c] [b, c] [ c ]。
   第一种遍历方式通常用于暴力解法, 第二种遍历方式 leetcode (5. 最长回文子串 ) 中的解法就用到了。
   第三种遍历方式 因为可以产生递推关系, 采用动态规划时, 经常通过此种遍历方式, 如 背包问题, 最大公共子串 , 这里的动态规划解法也是以先遍历出以某个节点为结束节点的所有子序列的思路。

2、思路：动态规划
定义状态：dp[i]表示索引从0到i的元素组成的数组中最大子序和；
初始状态：dp数组的第一个元素也就是数组的第一个元素本身，dp[0] = nums[0];
状态转移方程：按照上述的编译，则分为以i索引结尾、以i-1索引结尾。
· 以i索引结尾：dp[i-1] + nums[i]
· 以i-1索引结尾：dp[i-1]
如果dp[i-1]大于0，那么很显然dp[i]的值就是在其基础上再加上一个nums[i]；而当dp[i-1]小于0，那么dp[i-1]与nums[i]两者的和显然不如nums[i]本身的大，由于我们要连续数组最大和，所以直接抛弃这段就可以了，从当前元素nums[i]开始累计。
因此，转移方程为：dp[i] = min{dp[i-1],0} + nums[i]
根据dp[]的初始状态和转移方程，我们可以将dp[]数组填满，每个位置上的值代表着以这个位置元素结尾的最大连续子数组的最大和。因此，只需从dp[]中找到最大值即可。
参考

盛最多水的容器

盛最多水的容器

盛最多水的容器

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

思路：双指针法
设置双指针 i,j 分别位于容器壁两端，i,j向内移动时，丢弃较短的柱子。
1、为何丢弃较短的柱子

image.png

买卖股票的最佳时机

121. 买卖股票的最佳时机
思路：单调栈

思路一：
维护两个变量，只需要一次遍历，参考：
最小元素minVal代表着遍历过的元素中最小值；
最大利润变量maxPro代表截止目前所能获取的最大利润；
两个变量的转换：

maxPro = max{maxPro, nums[i] - minVal}
minVal = min{minVal, nums[i]}

对称二叉树

101. 对称二叉树

思路：使用递归方法，先实现判断两个树是否是对称的接口bool isSymmetric(TreeNode* a, TreeNode* b)
递归结束条件：
都为空指针则返回 true
只有一个为空则返回 false
当前节点不等返回false
递归过程：
判断 A 的右子树与 B 的左子树是否对称
判断 A 的左子树与 B 的右子树是否对称

bool isSymmetric(TreeNode* a, TreeNode* b) {
    if (!a && !b) {
        return true;
    }
    if (!a || !b) {
        return false;
    }
    if (a->val != b->val) {
        return false;
    }

    return isSymmetric(a->left, b->right) && isSymmetric(a->right, b->left);
}

只出现一次的数字

136. 只出现一次的数字
题目：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
思路：
异或^运算的特点就是：相同异或得0，不同异或得1，即与0异或等于本身；本身异或等于0；
对数组中所有元素进行异或，凡是出现偶数对相同的元素均消失；结果便是剩下的出现奇数对的元素之间的异或结果。而本题恰恰说明，只有一个元素是出现奇数次的，其他都是出现偶数次，因此异或的结果就是这个元素。
参考

最小栈

题目：最小栈
思路分析：
成员变量：定义两个队列stackA和stackB
构造方法：给两个队列创建对象
push: 添加元素e的时候，stackA正常添加，stackB需要比较一下，如果e小于等于栈顶元素的话，就添加，否则，过！！
pop: 弹出的时候stackA正常弹出栈顶元素e，如果stackB的栈顶元素和e相同，那么stackB也要弹出栈顶元素；
top: 直接读取stackA的栈顶元素；
getMin: 直接读取stackB的栈顶元素；
参考：【力扣Hot100】155. 最小栈

打家劫舍

题目 : 打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

思路:

1. 状态：dp[i]代表偷窃前i间房屋所能获得的最高金额；
2. 边界条件：
   dp[0] = nums[0], 只有一间屋子时，就只能盗窃这间屋子;
   dp[1] = max{nums[0] , nums[1]} 如果只有两件房屋，由于不能盗窃相邻的房屋，那么只能取最大的盗。
3. 转移方程：
   1. 盗第i间房屋，dp[i - 2] + nums[0];
   2. 不盗第i间房屋，dp[i - 1];
      取较大者，即 dp[i] = max{dp[i - 2] + nums[0] , dp[i - 1]};

参考：【力扣Hot100】198. 打家劫舍

翻转二叉树

思路：
应该使用后续遍历，先翻转左、右子树，再执行根节点的翻转。

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);    
        root.left = right;
        root.right = left;
        return root;
    }
}