【問題描述】466. 統(tǒng)計(jì)重復(fù)個(gè)數(shù)

由 n 個(gè)連接的字符串 s 組成字符串 S，記作 S = [s,n]。例如，["abc",3]=“abcabcabc”。如果我們可以從 s2 中刪除某些字符使其變?yōu)?s1，則稱字符串 s1 可以從字符串 s2 獲得。例如，根據(jù)定義，"abc" 可以從 “abdbec” 獲得，但不能從 “acbbe” 獲得。現(xiàn)在給你兩個(gè)非空字符串 s1 和 s2（每個(gè)最多 100 個(gè)字符長(zhǎng)）和兩個(gè)整數(shù) 0 ≤ n1 ≤ 106 和 1 ≤ n2 ≤ 106。現(xiàn)在考慮字符串 S1 和 S2，其中 S1=[s1,n1] 、S2=[s2,n2] 。請(qǐng)你找出一個(gè)可以滿足使[S2,M] 從 S1 獲得的最大整數(shù) M 。示例： 輸入： s1 ="acb",n1 = 4 s2 ="ab",n2 = 2返回： 2

【解答思路】

1. 暴力解法

• 在s1的拼接字符串中 遍歷找到找到一個(gè) s2，記錄使用了s1的個(gè)數(shù)
• s1總個(gè)數(shù)/含單個(gè)s2循環(huán)體/s2總個(gè)數(shù)
  時(shí)間復(fù)雜度：O(N^2) 空間復(fù)雜度：O(1)

public int getMaxRepetitions(String s1, int n1, String s2, int n2) {char[] c1 = s1.toCharArray();char[] c2 = s2.toCharArray();/*** index為c2的索引， num1當(dāng)前使用了ss1的個(gè)數(shù)， num2當(dāng)前匹配的ss2的個(gè)數(shù)*/int index = 0 , num1 = 0, num2 = 0;while(num1 < n1){for(int i = 0 ; i < c1.length ; i++){if(c1[i] == c2[index]){if(index == c2.length - 1) {index = 0;num2 ++;}else{index ++;} }}num1++;}return num2 / n2;}

2. 優(yōu)化

1.分為 0 ~（n1-1）次拼接s1，記錄下第0次 時(shí)，count（即s2出現(xiàn)的次數(shù)） 和 index（即指向s2的坐標(biāo)）
2.循環(huán)找尋壞體，判斷為循壞體的條件是：i!=0（不是第0次） && indexpre_index （當(dāng)前指向s2的坐標(biāo)第0次拼接結(jié)束后指向s2的坐標(biāo)）
3.如果找到了循環(huán)體，那么return （循環(huán)體個(gè)數(shù) * (單個(gè)循環(huán)體包含的s2數(shù)目) + 除去所有循環(huán)體字符串后，剩余拼接在一起的形成的字符串可以找出s2個(gè)數(shù)）/ n2，可以配合代碼看
4.沒有找到循環(huán)體，那就直接返回迄今為止記錄到的count數(shù)/n2，即countRecorder[n-1]/n2
時(shí)間復(fù)雜度：O(N) 空間復(fù)雜度：O(1)

public int getMaxRepetitions(String s1, int n1, String s2, int n2) {int len1 = s1.length();int len2 = s2.length();// 有0的話不多說，直接滾0if (len1 == 0 || len2 == 0 || n1 == 0 || n2 == 0) {return 0;}char[] chars1 = s1.toCharArray();char[] chars2 = s2.toCharArray();int index = 0;//記錄s2的坐標(biāo)int count = 0;//記錄s1包含s2的個(gè)數(shù)int[] countRecorder = new int[n1 + 1];//記錄第i次拼接時(shí)候累積的countint pre_index=0;//記錄第0次結(jié)束后的index//開始拼接找循環(huán)體( 看作 0~n-1 次)for (int i = 0; i < n1; ++i) {// 第i次拼接s1,更新index和countfor (int j = 0; j < len1; ++j) {if (chars1[j] == chars2[index]) {//匹配成功，index++index++;}if (index == chars2.length) {//完成一個(gè)s2的匹配，count++index = 0;count++;}}countRecorder[i] = count;//記錄第0次到第i次拼接出現(xiàn)的s2匹配次數(shù)（count）if(i==0) {//記錄第0次的下標(biāo)indexpre_index = index;}//符合該條件，代表找到循環(huán)體了，可以縮短搜索時(shí)間if(i!=0 && pre_index == index) {//System.out.println(countRecorder[0]);int pre = countRecorder[0];//第一次拼接的時(shí)候記錄的countint loop_part = ((n1-1) / i) * (countRecorder[i]-pre);//除去循環(huán)體部分，其他部分合并在一起// x = (n1-1)%i --> 除去循環(huán)體還等于x個(gè)s2拼接 int other_part = countRecorder[(n1-1) % i];//返回值為出現(xiàn)的s2的總次數(shù)return (loop_part+other_part) / n2;}}//未找到循環(huán)，只能暴力了，裂開return countRecorder[n1-1] / n2;}

【總結(jié)】

1. 數(shù)組拼接題目 重復(fù)延長(zhǎng)思想 找規(guī)律

2. 完全不知道如何入手 過于菜 不斷總結(jié)整理歸納

參考鏈接：https://leetcode-cn.com/problems/count-the-repetitions/solution/tong-ji-zhong-fu-ge-shu-_jian-dan-yi-dong-by-xiang/

總結(jié)

以上是生活随笔為你收集整理的[Leedcode][JAVA][第466题][统计重复个数][数组]的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。