算法小结

从被要求每天做一道算法题以来，已经做了十七道不同难度的算法题了，涉及到树、链表、栈等数据结构的知识，也使用过动态规划、递归算法、贪心算法等常用解题思路。在做过了这些题后，也发现了自己的不足与知识的欠缺，同时也总结下来了一些小小的解题思路，在这里记录一下：

快速导航目录

算法小结

认清自己的实力

这点非常重要！！“Rome was not built in a day” 谁都是从菜鸟一步一步过来的,不要急于求成。既然是初学者就安安心心的从简单题目开始入手（大佬忽略），毕竟力扣上题目难度也不是写着玩的，在一遍遍的练习中分析自己的劣势与知识的欠缺，细心总结，查漏补缺，慢慢递增难度，将自己做不出的题目可以先放放，等日后自己羽翼丰满，再来挑战这道题。在自身能力薄弱的情况下，就算看着别人写的算法，自己也无法理解透彻，只会徒增烦恼。叫你去面对挑战，可不是去送死，不是每个新生的勇者都跳过新手村直接讨伐魔王。

优先分析题目

在我们着手于一道算法题时，一定不要急于去写代码，要先分析题目。分析算法的输入参数有哪些，输入的范围又为多少；要求的返回参数是什么，要求的运行效果又是什么，看清题目上的示例，明白到底要做什么。可不要一看题目思如泉涌，最后写完再看题目才发现是自己审错了题，白用功。
我就曾犯过这样的错误，在做算法题 Z-字型变换时，我就因为没有好好审题而陷入自己的思维误区。题目要求是：

输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P     I    N
A   L S  I G
Y A   H R
P     I

我将解释当做要求输出的结果，在那里抓耳挠腮的想了一下午，实在想不明白准备去找人询问时才发现题目不需要输出Z-字型变换的图形结果，只用输出Z-字型变换后的字符串结果。
Z-字型变换解题详解

分析简化操作与排错

再写了这十多道算法题后，我发现很多题都会有一些特殊的输入值，这些输入值没必要让算法程序去完整的走一遍。为了避免不必要的浪费，我们就要思考在这道题中，什么样的输入可以很简单的输出：
在 Z-字型变换中可以进行这样的简化操作：

//当s的长度小于numRows与numRows==1时，直接返回s
        if (s.length() < numRows || numRows == 1){
            return s;
        }

在跳跃游戏中可以进行这样的简化操作：

if (nums.length == 0 || (nums.length > 1 && nums[0] == 0)) return false;
        else if (nums.length == 1) return true;//只有一位时直接满足

其实看多了就知道这些简化操作大多都是限定只运行一次或两次的结果，是可预知的，可以直接弹出结果，避免不必要的浪费。
当然，排错也是同理，保证了算法运行的准确，不报错。

打好数据结构的基础

数据结构很重要！数据结构很重要！数据结构很重要！重要的事情说三遍！
数据结构的学习真的特别重要，在写算法时经常会使用到栈、队列、链表、树等数据结构，若自己没有打好数据结构的基础，算法书写起来就十分的难受。尤其像树、链表这种无法直接看到数值的数据结构，理解起来会很困难。
这里推荐练习下树的前序、中序、后续遍历和删除链表的倒数第N个结点

多找点经典算法题来做

很多算法题都是在经典算法题的基础上来进行变种的，在与之前有一定相似的基础上，每次都有新的挑战，这样的题可以更快的提升自己。而且经典算法题的解题思路很具有代表性，可以用于很多题的解法，所谓举一反三就是如此：
比如经典算法题中的杨辉三角

class Solution {
    public List<List<Integer>> generate(int numRows) {
       List<List<Integer>> list = new ArrayList<List<Integer>>();
        for (int i = 0 ; i < numRows ; i++){
            //存放每一行二维数组的list
            List<Integer> rowList = new ArrayList<Integer>();
            for (int j =0 ; j <= i ; j++){
                if (j == 0 || j == i) rowList.add(1);// 存入最左和最右的1
                else rowList.add(list.get(i - 1).get(j - 1) + list.get(i - 1).get(j));//存入中间，由上图可知为[i-1][j-1]+[i-1][j]
            }
            list.add(rowList);//把每一行存入整体
        }

        return list;
    }
}

就是经典的动态规划题目，同样的还有爬楼梯与斐波那契数列

还有就是经典的贪心算法题目——跳跃游戏系列

class Solution {
    public boolean canJump(int[] nums) {
        if (nums.length == 0 || (nums.length > 1 && nums[0] == 0)) return false;
        else if (nums.length == 1) return true;//只有一位时直接满足

        int maxDistance = nums[0];//读出第一位，暂为最大距离
        for (int i = 0; i <= maxDistance; i++) {
            maxDistance = Math.max(maxDistance, i + nums[i]);//把能跳到的最大位置存入maxDistance
            //当前最大距离大于数组最长距离
            if (maxDistance >= nums.length - 1) {
                return true;
            }
        }
        return false;
    }
}