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值”的結點）。