日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時(shí)間：8:30-17:00
你可能遇到了下面的問(wèn)題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營(yíng)銷解決方案
面試官給我個(gè)字符串問(wèn)里面有多少個(gè)"bigsai"子序列給我難住了

 本文轉(zhuǎn)載自微信公眾號(hào)「bigsai」，作者bigsai。轉(zhuǎn)載本文請(qǐng)聯(lián)系bigsai公眾號(hào)。

林芝網(wǎng)站制作公司哪家好，找創(chuàng)新互聯(lián)！從網(wǎng)頁(yè)設(shè)計(jì)、網(wǎng)站建設(shè)、微信開(kāi)發(fā)、APP開(kāi)發(fā)、成都響應(yīng)式網(wǎng)站建設(shè)等網(wǎng)站項(xiàng)目制作，到程序開(kāi)發(fā)，運(yùn)營(yíng)維護(hù)。創(chuàng)新互聯(lián)自2013年創(chuàng)立以來(lái)到現(xiàn)在10年的時(shí)間，我們擁有了豐富的建站經(jīng)驗(yàn)和運(yùn)維經(jīng)驗(yàn)，來(lái)保證我們的工作的順利進(jìn)行。專注于網(wǎng)站建設(shè)就選創(chuàng)新互聯(lián)。

前言

一次面試官笑嘻嘻的問(wèn)我一個(gè)問(wèn)題，場(chǎng)景還原一下：

然后我把這個(gè)問(wèn)題透徹的研究了一下，并由淺入深的分析了一下這種問(wèn)題的思路，分別是有幾個(gè)pat和不同子序列問(wèn)題。

有幾個(gè)pat

這是pat的一道題。

分析

如何求一個(gè)字符串中有多少個(gè)pat。不要想著三重for循環(huán)去枚舉所有情況了，那不是好的方法。這這種題如果有靈感的話應(yīng)該能猜出來(lái)這應(yīng)該是一種動(dòng)態(tài)規(guī)劃的問(wèn)題。

首先將問(wèn)題簡(jiǎn)單分解一下，如果問(wèn)原串中有多少個(gè)p。那么很容易枚舉一遍即可。例如序列ppp就是三個(gè)p。

如果帶上a，求串pa的個(gè)數(shù)呢?pa是由p和a組成。求pa的個(gè)數(shù)肯定和a有很大的關(guān)系，每個(gè)a可能會(huì)組成若干個(gè)pa取決于這個(gè)a前面p的數(shù)量。將所有a位置組成的pa相加即可。例如pppapa 總共可以組合3+4=7個(gè)pa.

同理想知道有幾個(gè)pat那也很容易啊，pat的求解需要找到每個(gè)t，然后知道當(dāng)前位置前面有多少個(gè)pa，疊加求解獲得結(jié)果即可。結(jié)合下圖流程看更好。

不同的子序列

題目描述：

給定一個(gè)字符串 s 和一個(gè)字符串 t ，計(jì)算在 s 的子序列中 t 出現(xiàn)的個(gè)數(shù)。

字符串的一個(gè) 子序列 是指，通過(guò)刪除一些(也可以不刪除)字符且不干擾剩余字符相對(duì)位置所組成的新字符串。(例如，"ACE" 是 "ABCDE" 的一個(gè)子序列，而 "AEC" 不是)

題目數(shù)據(jù)保證答案符合 32 位帶符號(hào)整數(shù)范圍。

示例 1：

 
 
 
 
    
  
  
  
  
  1. 輸入：s = "rabbbit", t = "rabbit" 
    2. 
  
  
  
  
  2. 輸出：3 
    3. 
  
  
  
  
  3. 解釋： 
    4. 
  
  
  
  
  4. 如下圖所示, 有 3 種可以從 s 中得到 "rabbit" 的方案。 
    5. 
  
  
  
  
  5. (上箭頭符號(hào) ^ 表示選取的字母) 
    6. 
  
  
  
  
  6. rabbbit 
    7. 
  
  
  
  
  7. ^^^^ ^^ 
    8. 
  
  
  
  
  8. rabbbit 
    9. 
  
  
  
  
  9. ^^ ^^^^ 
    10. 
  
  
  
  
  10. rabbbit 
    11. 
  
  
  
  
  11. ^^^ ^^^ 
    12.

示例 2：

 
 
 
 
    
  
  
  
  
  1. 輸入：s = "babgbag", t = "bag" 
    2. 
  
  
  
  
  2. 輸出：5 
    3. 
  
  
  
  
  3. 解釋： 
    4. 
  
  
  
  
  4. 如下圖所示, 有 5 種可以從 s 中得到 "bag" 的方案。  
    5. 
  
  
  
  
  5. (上箭頭符號(hào) ^ 表示選取的字母) 
    6. 
  
  
  
  
  6. babgbag 
    7. 
  
  
  
  
  7. ^^ ^ 
    8. 
  
  
  
  
  8. babgbag 
    9. 
  
  
  
  
  9. ^^    ^ 
    10. 
  
  
  
  
  10. babgbag 
    11. 
  
  
  
  
  11. ^    ^^ 
    12. 
  
  
  
  
  12. babgbag 
    13. 
  
  
  
  
  13.   ^  ^^ 
    14. 
  
  
  
  
  14. babgbag 
    15. 
  
  
  
  
  15.     ^^^ 
    16.

提示：

 
 
 
 
    
  
  
  
  
  1. 0 <= s.length, t.length <= 1000 
    2. 
  
  
  
  
  2.  
    3. 
  
  
  
  
  3. s 和 t 由英文字母組成 
    4.

分析：

這個(gè)問(wèn)題其實(shí)就是上面有幾個(gè)pat的變形拓展，其基本思想其實(shí)是一致的，上面那題問(wèn)的是有幾個(gè)pat，固定、且很短。但這里面t串的長(zhǎng)度不固定，所以處理上就要使用數(shù)組來(lái)處理而不能直接if else。

這題的思路肯定也是動(dòng)態(tài)規(guī)劃dp了，dp[j]的意思就是t串中[0,j-1]長(zhǎng)字符在s中能夠匹配的數(shù)量(當(dāng)然這個(gè)值從前往后是動(dòng)態(tài)變化的)，數(shù)組大小為dp[t.length+1]。在遍歷s串的每一個(gè)元素都要和t串中所有元素進(jìn)行對(duì)比看看是否相等，如果s串枚舉到的這個(gè)串和t串中的第j個(gè)相等。那么dp[j+1]+=dp[j]。你可能會(huì)問(wèn)為啥是dp[j+1],因?yàn)榈谝粋€(gè)元素匹配到需要將數(shù)量+1，而這里為了避免(判斷是否為首字符)這樣的判斷我們將dp[0]=1,這樣t串的每個(gè)元素都能正常的操作。

但是有一點(diǎn)需要注意的就是在遍歷s串中第i個(gè)字母的時(shí)候，遍歷t串比較不能從左向右而必須從右向左。因?yàn)樵诒闅vs串的第i個(gè)字符在枚舉dp數(shù)組時(shí)候要求此刻數(shù)據(jù)是相對(duì)靜止的疊加(即同一層次不能產(chǎn)生影響)，而從左往右進(jìn)行遇到相同字符會(huì)對(duì)后面的值產(chǎn)生影響。區(qū)別的話可以參考下圖這個(gè)例子：

實(shí)現(xiàn)的代碼為：

 
 
 
 
    
  
  
  
  
  1. class Solution { 
    2. 
  
  
  
  
  2.     public int numDistinct(String s, String t) { 
    3. 
  
  
  
  
  3.        char s1[]=s.toCharArray(); 
    4. 
  
  
  
  
  4.         char t1[]=t.toCharArray(); 
    5. 
  
  
  
  
  5.  
    6. 
  
  
  
  
  6.         int dp[]=new int[t1.length+1]; 
    7. 
  
  
  
  
  7.         dp[0]=1;//用來(lái)疊加 
    8. 
  
  
  
  
  8.  
    9. 
  
  
  
  
  9.         for(int i=0;i
  
  
  
  
  10.         { 
    11. 
  
  
  
  
  11.             for(int j=t1.length-1;j>=0;j--) 
    12. 
  
  
  
  
  12.             { 
    13. 
  
  
  
  
  13.                 if(t1[j]==s1[i]) 
    14. 
  
  
  
  
  14.                 { 
    15. 
  
  
  
  
  15.                     dp[j+1]+=dp[j]; 
    16. 
  
  
  
  
  16.                 } 
    17. 
  
  
  
  
  17.             } 
    18. 
  
  
  
  
  18.         } 
    19. 
  
  
  
  
  19.         return dp[t1.length]; 
    20. 
  
  
  
  
  20.     } 
    21. 
  
  
  
  
  21. } 
    22.

網(wǎng)頁(yè)標(biāo)題：面試官給我個(gè)字符串問(wèn)里面有多少個(gè)"bigsai"子序列給我難住了
分享鏈接：http://m.5511xx.com/article/ccdpiji.html