leetCode解题报告5道题(九)

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,

If n = 4 and k = 2, a solution is:

分析：

题意给我们一个数字n, 和一个数字k,让我们求出从 1~~n中取出k个数所能得到的组合数

所以这个题目给我们的第一感觉就是用递归是最方便的了，咱试试递归的方法哈。如果读者对递归方法有疑问，可以看看我之前总结的一个递归算法的集合。

AC代码：

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right.

The first integer of each row is greater than the last integer of the previous row.

Consider the following matrix:

Given target = <code>3</code>, return <code>true</code>.

分析：这道题目是剑指Offer上的老题目咯，但是解题的思路挺巧妙。本来不想把这题写在博文里的，后来想想也许有些同学没看过剑指Offer, 兴许因为这题而去看下这本挺不错的书哈，于是把这题写在博文里了。并附上剑指offer的下载地址（），这题便不做详细介绍。

AC代码：（复杂度O（m+n））

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = <code>"great"</code>:

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node <code>"gr"</code> and swap its two children, it

produces a scrambled string <code>"rgeat"</code>.

We say that <code>"rgeat"</code> is a scrambled string of <code>"great"</code>.

Similarly, if we continue to swap the children of nodes <code>"eat"</code> and <code>"at"</code>,

it produces a scrambled string <code>"rgtae"</code>.

We say that <code>"rgtae"</code> is a scrambled string of <code>"great"</code>.

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

这道题目的题意相信大家应该都看得懂，只是做起来的话有些蛋疼.

我一开始用暴力法TLE，之后用DP才可以的.

具体看代码：

暴力法TLE：

DP动态规划:

设数组flags[len][len][len]来存储每一个状态信息.

如flags[i][j][k] 表示s1字符串的第i个位置开始的k个字符和s2字符串的第j个位置开始的k个字符 是否满足scramble string 

满足：flags[i][j][k] == true

不满足: flags[i][j][k] == false

那么题目所要的最终结果的值其实就相当于是flags[0][0][len]的值了

那么状态转移方程是什么呢?

归纳总结法

如果k==1:

flags[i][j][1] 就相当于 s1的第i个位置起，取1个字符。s2的第j个位置起，取1个字符。那如果要使Scramble String成立的话，那么就只能是这两个字符相等了, s1.charAt(i) == s2.charAt(j)

因此 flags[i][j][1] = s1.charAt(i) == s2.charAt(j);

如果k==2:

flags[i][j][2] 就相当于 s1的第i个位置起，取2个字符。s2的第j个位置起，取2个字符。那如果要使Scramble String成立的话，那么情况有以下两种

一种是flags[i][j][1] &amp;&amp; flags[i+1][j+1][1] (就是两个位置的字符都相等 S1="TM" S2="TM")

一种是flags[i][j+1][1] &amp;&amp; flags[i+1][j][1] (两个位置的字符刚好对调位置 S1="TM" S2="MT")

如果k==n:

设个变量为x

flags[i][j][n] =( (flags[i][j][x] &amp;&amp; flags[i+x][j+x][k-x])  [第一种情况]

 || (flags[i][j+k-x][x] &amp;&amp; flags[i+x][j][k-x]) );  [第二种情况]

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:

Given <code>1-&gt;2-&gt;3-&gt;4-&gt;5-&gt;NULL</code> and k = <code>2</code>,

return <code>4-&gt;5-&gt;1-&gt;2-&gt;3-&gt;NULL</code>.

题意要求我们根据所给出的k值，把从最后一个非空结点向前的k个结点移动到链表的开头，重新组成一个新的链表之后返回。

这道题目有点像经典的面试题“只遍历一次，如何找到链表倒数的第K个结点”，采用的是两个指针不一样的起始位置，一个指针从head开始出发，另一个指针先让它走K步，当第2个指针为Null的时候，则第一个指针所指向的就是倒数第K个的值。

同理：

这里我们用两个指针就可以方便地搞定这个题目了，但是需要注意的是，这道题目

如果K大于了链表长度，比如K=3，Len=2的话，如果K步我们还没走完就碰到了Null结点，那么再从head开始走剩下的。直到K==0；

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

Given <code>1-&gt;4-&gt;3-&gt;2-&gt;5-&gt;2</code> and x = 3,

return <code>1-&gt;2-&gt;2-&gt;4-&gt;3-&gt;5</code>.

妈蛋，英文题目看着就是蛋疼，看了好久才理解它的题意：

题目要求我们说给出一个X的值，你要把所有的 小于X的值的结点放在所有大于或等于X的值的前面，关键这里X又等于3，跟题目里面给出的链表中其中一个结点的值一样，迷惑了。

一旦题意明白了，剩下的就好办了，居然这样的话，那我们只需要先找出第一个 “大于或等于X值”的结点，并记录下它的位置。

然后剩下的只要遍历一次链表，把小于X的插入到它的前面，大于或等于X 不变位置（因为我们这里找到的是第一个“大于或等于X值”的结点）。