学习笔记

广度优先的方法，使用队列，这个模板写过好多遍了，此处就不写了。

据说这是一道经典的广度优先搜索的题目。首先，为什么要用广度优先？先明确这个题需要我们得到的是单个单个单词变化后的最短路径，此时使用广度优先一层一层计算下去，得到的结果必然是最短的；如果使用深度优先，那么我们必须遍历所有路径并存储他们的所有路径长度，最后再选出最短的（或者每次得到一个路径就和当前最小的那个路径作比较并更新最小路径）。代码思路采用比较暴力所有字母遍历检查。不过看到答案中有用到虚拟结点的方法，可以说非常妙。

由于零钱面值成倍数关系，因此可以证明此时使用贪心算法是正确的，即找零的时候优先选择先找面值大的（就此题而言，是优先选择找零10元）。 因此我设计了一个尾递归函数bill_func来检验最后是否能够找零。 在这个递归中，递归的终止条件我设计了两个，第一个是首先遍历哈希表中每个面值的张数，如果有小于0的话，就可以直接返回false了，由于尾递归的传递性，这个false就会一直传到最上面。如果面值为5就不需要找零了，由于前者判断在前，如果前者那个判断没有返回false，那么就说明此时找零状态正常，那么可以返回true。其他递归就是比较正常的了，具体代码注释也写得很清楚了。

这个题的题干中明确规定了一个孩子只能分发一个饼干，因此直接对胃口和饼干大小排序，然后从最大胃口和最大饼干开始分发就行。总体思路比较简单。但是如果把此题条件改为“一个孩子可以分发多个饼干”，那么问题就会变得更加复杂

这题也可以使用二分查找，但是判断情况会比较复杂。我做的时候分了四种情况，四种情况都写在代码注释中了。

我一开始采用了时间复杂度较高的动态规划（O(n^2)），通过了大部分测试例，但是在一个数组长度为25000的测试上超时。 但是还是稍微总结一下动态规划的思路。 dp数组是一个存放bool值的数组 dp[i]表示能否跳到第i个结点 转移方程dp[i]的值需要进行一个循环来判断 具体代码如下：

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        vector<bool> dp(n, false);
        dp[0] = 1;
        for (int i = 1; i < n; ++i)
        {
            for (int j = 0; j < i; ++j)
            {
                if (j + nums[j] >= i && dp[j] == true)
                    dp[i] = true;
            }
        }
        return dp[n-1];
    }
};

但是题解中有时间复杂度为O（n）的解法，就是说先设定一个临时变量k，用来存储当前能够到达的最远距离，然后遍历所有位置，在遍历的过程中，如果当前位置大于最大位置，就说明无法达到最终位置，然后每次遍历都要更新k，k = max(k, nums[i] + i)