20200504
Plan
leetcode 每日一题
Notes
- 复原IP地址 给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
示例:
输入: "25525511135" 输出: ["255.255.11.135", "255.255.111.35"]
这道题时比较经典的回溯法解决的问题： 1.每次取长度为1/2/3的字符串放入当前字符串数组中，注意如果长度为3，则当前的字符串要<="255"，长度为1/2没有限制。 2.判断当前字符串数组中的个数是否已经到达4个，如果是且剩余的字符串为空，则将当前的字符串数组中的字符串用"."链接并放入结果数组中；如果剩余的字符串不为空，则返回。 3.将当前字符串数组的最后一个字符串删除，重复上述操作。 比较经典的回溯法，很久没写记录一下。需要注意的是，go把数组当做参数传入函数中时，传的是形参，在函数内改变数组的值函数外是不会改变的，所以需要传指针。
- 水壶问题 有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？如果可以，最后请用以上水壶中的一或两个来盛放取得的 z升 水。
你允许： 装满任意一个水壶 清空任意一个水壶 从一个水壶向另外一个水壶倒水，直到装满或者倒空
示例 1: (From the famous "Die Hard" example) 输入: x = 3, y = 5, z = 4 输出: True
这个题看题解可以用DFS或者BFS来做，首先定义八种状态。如果用BFS则用栈来保存状态。具体没有细看。想记录的是数学方法： 如果z是x和y的最大公约数的倍数，那么z是可以满足的。但注意z需要<x+y. 最大公约数可以用辗转相除法来算，即假设x<y。 gcd(x,y)为 1.x,if y%x==0 2.gcd(x,y%x)
- 日期之间隔几天 请你编写一个程序来计算两个日期之间隔了多少天。
日期以字符串形式给出，格式为 YYYY-MM-DD，如示例所示。
示例 1： 输入：date1 = "2019-06-29", date2 = "2019-06-30" 输出：1
示例 2： 输入：date1 = "2020-01-15", date2 = "2019-12-31" 输出：15
这道题想法比较简单，假设date1<date2,则从date2一天一天往下减就可以，有一个判断条件： 1.当天数减到0时，月份-1，如果月份为0，年份-1；如果月份不为0，但是是2月，需要判断是否是闰年（闰年的判断条件是year%400==0或者year%100!=0&&year%4==0），然后把当月的天数重新赋值给当前天数就可以。 只到两个日期年月日都相等，就停止循环。