LeetCode 62. Unique Paths

原题:https://leetcode.com/problems/unique-paths/

robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

思路

这是个经典的题目,反正就是动态规划的思路?说是动态规划,其实就是下一个状态怎么来的问题。此处的下一状态就是一个格子solution[m][n]他的结果是怎么来的问题,由于限定只能往右或者往下走,所以这个格子的走法无非是 从(m,n-1)和(m-1,n)走过来两种,只要把这两个状态的结果相加就是当前总的走法了。

解法

复杂度应该是O(m*n),做的时候在左侧和上侧加了个0边便于计算

 

LeetCode 278. First Bad Version

做点简单的题目练练手,最近天天在写Scope脚本,都快忘记怎么写其他代码了。

吐槽一下垃圾长城宽带,上LeetCode都要自己开代理,不然根本加载不了

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

分析

这其实就是个变种的二分查找,只要注意找到一个bad version的时候,往前多看一个版本就能决定是否要继续二分下去了。

代码

 

LeetCode 322. Coin Change

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

Note:
You may assume that you have an infinite number of each kind of coin.

思路

动态规划的问题,不过如果倒着做的话,似乎会超时…

所以考虑往前递推的情况,即当前要解决X元的找零问题的最佳解法且已知<X时的解法,手头有一堆面值为coins[i]的硬币的时候,对于每种可用的硬币我们要做的选择是:

  • 尝试使用coin[i],即当前的最优结果=(X-coins[i])元时的最优结果+1,这个1就是用了coins[i]这个硬币;
  • 保持现有结果不变

这两个方法当然是取最好的存下来了。

代码

 

LeetCode 217. Contains Duplicate

题目:https://leetcode.com/problems/contains-duplicate/

思路:弄个哈希表啊或者现成的用哈希(或者XX树)的容器就行了

代码: