解算法题的方法和步骤

审题

注意题目中的条件。不要放过任何一句话。了解题目的意图。

列举参数

列举多个测试参数，可以分析哪些需要特判。

分析可能的解题方法

可以用纸绘制草图、不管好的坏的，骡子马，能解决问题的放都列出来，有助于思考。

实现代码

选择一门擅长的编程语言。可以把退出条件写好，放在循环和递归的第一行，确保不会出现死循环。

计算时间复杂度、空间复杂度

寻找最优解

优化算法

查看优秀解题思路

重复上面一个步骤

下面以加一这道算法题来举例

题目：加一

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位，数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1:

输入: [1,2,3] 输出: [1,2,4] 解释: 输入数组表示数字 123。示例 2:

输入: [4,3,2,1] 输出: [4,3,2,2] 解释: 输入数组表示数字 4321。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/plus-one 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

审题

仔细阅读题目，发现这道题是一道普通数字加1的加法题，联想到这可以用来实现超过计算机数值精度的计算。

列举输入和输出

列出可能的输入，需要结合题目来。题目中有一句“除了整数0之外，这个整数不会以零开头”。那么可能的输入和输出：

[0] –> [1]
[1] –> [2]
[9] –> [1, 0]
[1, 0] –> [1, 1]
[1, 8 , 8] –> [1, 8, 9]
[1, 9, 8] –> [1, 9, 9]
[9, 9, 9] –> [1, 0, 0, 0]
[2, 3, 4, 5, 6, 9, 9, 9] –> [2, 3, 4, 5, 7, 0, 0, 0]
[9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9] –> [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

可以发现+1时，从右到左只有当需要进位的时候才出才需要遍历。

分析可能的解题方法

将数组转成字符串，然后转成数字，然后+1后转会数组。
遍历数组，对数据进行+1处理

实现代码

方法一，转成数字

var plusOne = function(digits) {
  let num = Number(digits.join('')) + 1
  return num.toString().split('');
};

这种解法把输入都带进去测试，发现[9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9]会丢失精度，所以这种方法不可取。

直接对数组处理

var plusOne = function(digits) {
  for (let i = digits.length - 1; i >= 0; i--) {
    // +1
    digits[i]++;
    // 取余数
    digits[i] = digits[i] % 10
    // 如果余数不是0，就说明就不用进位了，后面也不用遍历了，直接返回将结果返回函数体外
    if (digits[i] !== 0) return digits;
  }
  // 判断首位是不是需要进1
  // [10, 0, 0, ……, 0, 0]
  if (digits[0] % 10 === 0) {
    digits[0] = 0;
    digits.splice(0, 0, 1);
  }
  return digits;
}

计算时间复杂度、空间复杂度

直接对数组处理是在原数组上进行遍历，时间复杂度是O(n)，空间复杂度O(1)

寻找最优解

直接对数组处理代码中已经对不必要的循环进行了处理，貌似已经是最优解了，也没有其他二分、分治的处理方法了。

优化算法

对算法进行代码优化，比如编码风格、多余的判断等。

查看优秀解题思路

在leetcode看观看优秀题解，跟自己的思路进行比较，是不是还有更优的解法，甚至找到优秀题解的bug。

重复上面的过程

有时间就重复上面的过程，只要享受这个过程，时间就会过的特别快。

中间任何一个环境卡住了，千万不要死磕。

学算法不是解出题目就算完了，要学会解题思路，题目变种依然可以有思路可以解题。

学算法不是一个能速成的能力，要多多练习，持续进步。

不可一下就尝试太难的算法题，会打消积极性的，因该在容易和难的题目中穿插。

空间复杂度计算：开了新数组，数组的长度就是空间复杂度，如果数组是二维的，那就是n^2，如果有递归，递归的最深处就是空间复杂度的最大值，如果又有递归，又有数组，就取两者最大值。