LeetCode 368. Largest Divisible Subset

思路:

想到一个词叫“传递性”,在这边应该也适用。就是如果b%a==0,然后c%b==0,那么肯定有c%a==0. 按照这个方法来构造一个集合就可以了,应该是动态规划的思想,results[i]保存包含数组元素nums[i]的最佳集合,构建集合的时候,首先从之前的results[j] (j=0…i-1)里面找到能够“传递”过来的集合(nums[i]%nums[i]==0)选作最佳(相当于找到c%b==0,当然这里的b是之前results[j]里面的最大元素,即nums[j])然后加上本身的nums[i]就构成了到第i个元素为止的最佳集合,如此继续…

时间复杂度应该是O(n^2)

 

最长递增子串 (只能忽略m个元素)

记录一道碰到的笔试题。

题目

给定一个int数组,求其最长的连续递增子序列,但递增过程中可以忽略m个数组元素。在最优子序列长度相同时,以子序列元素之和较小的一个为最优解*。

即实现方法

思路

八成是动态规划,参考最长连续子序列。

需要存储状态:第i个元素的{最优序列,忽略元素个数}

从i向前寻找m个位置的最优解(因为最多只能忽略m个)。假设那个“之前的”元素是array[j],那如果array[i]>array[j]并且array[j]+1>=当前最优序列长度,则判断限制条件*以确定是否更新最优解。

整个方法的复杂度应该是,其中n为array的长度。

代码

 

 

LeetCode 91. Decode Ways

思路

警告:千万注意’0’这个异类,当然了还有空输入:(。

其实也是个动态规划?的问题,有点像那个走楼梯的题

当前能decode的方法数与之前的两种状态有关,就是

  • 判断当前的字母s[i]能不能单个decode,如果可以,那方法数就要加上解码s[i-1]时的方法数,如果不能解那就不加;
  • 判断两个字符s[i-1]s[i]的组合能不能解码(就是在不在10-26的范围内),如果可以,拿加上解码s[i-2]时的方法数;

所以事实上只要保存s[i],s[i-1]两个方法数的结果就行,我的代码空间复杂度还比较大,但是不想改了。

代码

 

LeetCode 64. Minimum Path Sum

思路

动态规划的问题,某一格的状态由它左侧及上侧的状态决定,即

当然了,第一行只由左侧决定,第一列只由上侧决定。

代码

 

LeetCode 139. Word Break

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

思路

字符串处理的一个题目,首先想到的办法就是穷举:从头开始找N-letter word,查一下在不在字典里呗。但是纯穷举的话显然就会超时,因为这个问题可以分解成下面的子问题,即给定字符串s及起始位置start,寻找s[start…end]能不能够被拆分。这个子问题在暴力搜索的时候很容易被重复,所以得找个东西记录一下状态,碰到相同的子问题就不用再去查字典了。

所以,他是个动态规划的题。

代码

 

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 139. Word Break

题目

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

思路1

写的第一个版本是超时的,但是思路应当是正确的,反正就是动态规划,但我用的是递归方法。

就是如果找到s[start,end]是单词表中的单词时,有两种处理,一种是算入然后往后走;另一种是忽略这次匹配成功,继续往后寻找。

代码大概这样:

但是如果这里出现了超级多的单字,比如字符串是

然后字典是

这就搞笑了,得匹配死,所以肯定是超时。

思路2

这个是讨论组里看来的,突然发现一般来说DP递归能做的,就可以从后往前用非递归的方法写。对于这个问题来说,从后往前并不像做LCS那样时要完全倒着写。举个例子,有字符串str= thisisawesome 和字典 {this, is, a, we, some, awesome} 的时候,可以用一个缓存cache来记录是否在str[i]位置有单词结束,比如str[3]位置就是”this”这个词结束的地方。当顺着继续搜索的时候,往前查找缓存记录,可以知道如果cache[i]=true的话,那才有可能从i这个位置往后到当前位置组成新单词,接着去查找字典看看有没有这个单词,如果没有的话,就得继续往前找到新的可用的开头i。这里加黑的“才有可能”是比较关键的。

代码大概是这样

这里面向前迭代不断寻找cache[i]并尝试的情况,对应于之前思路1里面找到可用单词后的决定是否使用的分支情况。但是由于减少了一大堆递归调用,所以实际情况下的复杂度降低了不少。

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]这个硬币;
  • 保持现有结果不变

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

代码

 

M$ 2016 题目3 : Demo Day

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

You work as an intern at a robotics startup. Today is your company’s demo day. During the demo your company’s robot will be put in a maze and without any information about the maze, it should be able to find a way out.

The maze consists of N * M grids. Each grid is either empty(represented by ‘.’) or blocked by an obstacle(represented by ‘b’). The robot will be release at the top left corner and the exit is at the bottom right corner.

Unfortunately some sensors on the robot go crazy just before the demo starts. As a result, the robot can only repeats two operations alternatively: keep moving to the right until it can’t and keep moving to the bottom until it can’t. At the beginning, the robot keeps moving to the right.

While the FTEs(full-time employees) are busy working on the sensors, you try to save the demo day by rearranging the maze in such a way that even with the broken sensors the robot can reach the exit successfully. You can change a grid from empty to blocked and vice versa. So as not to arouse suspision, you want to change as few grids as possible. What is the mininum number?

输入

Line 1: N, M.

Line 2-N+1: the N * M maze.

For 20% of the data, N * M <= 16.

For 50% of the data, 1 <= N, M <= 8.

For 100% of the data, 1<= N, M <= 100.

输出

The minimum number of grids to be changed.

注记:

动态规划的一道题,后悔当时没有看通过率先做了第二道,第二题没有熟练掌握Trie结果处理超时了!

这题就是状态麻烦点,我的处理方式是在当前位置就判断右侧及下侧的通行情况,必要时做出改变,然后继续。因此注意点是一开始就被[0][0]位置blocked的情况。

以(x位置,y位置,当前方向)为一个三元组,可以保存唯一的状态结果,避免重复递归。

代码:

未经详细测试,待测试!感觉自己的编码能力还是有限,欢迎过客提出意见。

 

Longest Common Subsequence 最长公共子序列

这是个很老的问题了,最近总是碰到,大三时候学的算法好多都忘记了,不如重新学一遍。

比起XXblog上的教程,我最喜欢的还是这个版本:http://www.ics.uci.edu/~eppstein/161/960229.html

里面的代码干净利落,解释也非常的清晰,一步一步怎么来的都很好。

这个问题是个动态规划的问题,最基本的样子是这样的:

由于这样递归能弄出的子问题里面,好多是重复的,因此我们可以像计算斐波那契数列那样,采用自底向上的方法,用非递归的方式实现。即从字符的末尾往前推导LCS[i][j],这样当计算LCS[i][j]的时候, LCS[i+1][j]或LCS[i][j+1]已经计算好了。

具体还是看英文教程吧,这里给出C++实现的代码。因为下午例会还得讲PPT,下面的代码用了全局变量传递计算好的序列,有点丑。