【006-week4】算法训练营第四周学习总结 #209

208

• 定义节点类，根节点定义为空，数据结构为

class TrieNode
{
    public $children = [];
    public $is_word = false;
    public $val = null;

    function __construct($val = null)
    {
        $this->val = $val;
    }
}

• insert时，构建Trie树，最后一个节点 is_word设置为true，代表这里是单词结尾。
• search时，遍历单词每一个字符，依次从根节点判断下来，当有一个节点不匹配则判断不存在，到最后一个节点，若is_word为true，那么判断为找到。
• startWith原理同search类似，只是不用最后判断is_word。

211

同样是字典树的问题，只是由于涉及到通配符.，所以遇到.时需要递归求解。

212

在208题trie树的基础上，使用trie树+DFS实现。
基于words构建trie树，遍历board二维数组，对每一个遍历到的点，进行深度优先dfs搜索，成功匹配的点标记为已访问入visited数组，保证不重复访问之前遍历到的点。
在每一个点遍历结束后，要记得清空visited已访问数组。
基于一个点向上下左右四个方向进行DFS搜索时，每当一个方向DFS结束后，要重置当前点的visited值为0，切记！（在这里卡了我好久才发现问题）

455

1. 将输入的两个数组g,s有小到大排序。
2. 依次遍历g内元素，依次取s内元素比较，当s内元素>=g内元素，次数+1并删除s内元素，依次循环下去。

714

从头开始，先取第一个元素作为最小值，向后依次遍历比较；
当遇到当前价格<最小值的时候，设置当前价格为最小值；
当遇到当前价格-最小值>手续费的时候，便交易出去；
然后以当前价格-手续费作为新的最小值，继续遍历比较。

53

对输入数组从头依次进行遍历，初始化以第一位数为max，每次累加遍历的数字得到和为sum。
每次循环判断sum是否大于0，大于0则跟max进行比较，置max为两者最大值；小于0则判断前面的队列非最大值队列，置sum为当前num值，再继续进行比较，最后得出max。

78

回溯法。
依次遍历输入数组，对遍历到的数字进行递归求子集，将每次所得放入结果集合中。

70

经典的爬楼梯问题。

709

动态规划。
从第一个价格开始向后遍历到最后一个价格，依次计算出当前价格卖出能获得的最大收益。
因为要隔一天才能买入售卖后的新股票，所以总结出dp方程为：

// j为当前价格向前遍历到第0个元素的每一个元素位置
// $profit = $prices[$i] - $prices[$j]
// j<2时，无法进行新的买入操作，所以最大值是max(当前差额与之前所求当前位置最大值)
// j>=2时，最大值是max(当前卖出的差价+隔一天前所求最大值与当前位置之前所求最大值)
if ($j >= 2) {
    $dp[$i] = max($profit + $dp[$j - 2], $dp[$i]);
} else {
    $dp[$i] = max($profit, $dp[$i]);
}