Leetcode动态规划之PHP解析(120. Triangle)

2019-5-18 星期六  开始吧上一题链接: Leetcode动态规划之PHP解析(70. Climbing Stairs)动态规划题第二天题目描述给定一个三角形,好吧,其实就是一个二维数组,让我们求从上至下的最小路径和,往下一层,你只能移动相邻之间的两个数。题目解析还是使用动态规划的两个步骤。1.定义好状态2.求出递推的公式。递归和动态规划有一个不同的地方就是递归是自上而下,比如在...

Leetcode PHP题解--D64 292. Nim Game

D64 292. Nim Game 题目链接 292. Nim Game 题目分析 假设你和朋友玩一个捡石头的游戏,你和朋友轮流拿1~3颗石头。拿到最后一颗石头的一方为剩方。第一轮由你开始捡石头。 同时假设你和你的朋友都足够聪明,每次都能采取最优策略。 现给定一个石头数量,判断你最终是否能取得胜利。 思路 我们先从少一点开始推广到n个石头。 如果有1~3颗石头,因为规定了是你开始、还假设...

Leetcode PHP题解--D63 917. Reverse Only Letters

D63 917. Reverse Only Letters 题目链接 917. Reverse Only Letters 题目分析 给定一个包含符号的字符串,仅倒转字母的出现顺序,不改变符号的出现位置。 思路 先把字符串分成字母和符号两部分,保留下标。 抽离字母数组的键和值,对值部分进行倒转,合并到键数组中。 再覆盖原数组中对应键即可。 最终代码 ...

Leetcode PHP题解--D62 976. Largest Perimeter Triangle

D62 976. Largest Perimeter Triangle 题目链接 976. Largest Perimeter Triangle 题目分析 给定数字数组,任取三条边形成三角形,返回最大边长。 思路 对给定的数组进行降序排序,使最大的数字在前面。 取最大的前三条,判断任两边之和是否大于第三边。 是则返回周长即可。 最终代码 ...

Leetcode基础刷题之PHP解析(5. Longest Palindromic Substring )

我们可以维护一个二维数组来表示一个区间内是否为回文串($[$i][$j]),当$i=$j的时候,说明此时只是一个字符串,那么肯定是回文串,如果$i-$j等于1说明此时他们是相邻的两个字符串,只需要判断$s[$i]是否等于$s[$j],如果相减大于等于2的话,说明他们之间不是相邻的,相当于此时$i位于当前字符串的最右侧,$j位于当前字符串的最左侧,我们除了判断他们自身是否相等之外,还需要判...

Leetcode PHP题解--D61 953. Verifying an Alien Dictionary

D61 953. Verifying an Alien Dictionary 题目链接 953. Verifying an Alien Dictionary 题目分析 给定一个单词数组和一个字符串,判断给定的数组是否满足给定字符串的顺序。 思路 按给定字符串,替换成正常顺序的单词。 再判断sort之前和之后的数组是否相同。 最终代码 ...

Leetcode PHP题解--D60 824. Goat Latin

D60 824. Goat Latin 题目链接 824. Goat Latin 题目分析 给定一个句子,由大小写英文字母组成,以空格为单词的分割。 按以下规则修改单词: 如果一个单词以元音开头(即AEIOU),那么在这个单词末尾添加ma; 如果不是以元音开头,那么将第一个字母移动到当前单词末尾,并在后面添加ma; 在所有单词末尾再额外添加n个a。n为当前单词在句子中的次序,从1开始。...