1.3 模擬/dp|大話移動(dòng)通信
686 重復(fù)疊加字符串的匹配
鏈接
一題四解
首先，可以分析復(fù)制次數(shù)的上界和下界。
下界：至少將a復(fù)制長度大于等于b的長度，才有可能匹配。
在明確了下界后，再分析經(jīng)過多少次復(fù)制，能夠明確得到答案，能夠明確得到答案的最小復(fù)制次數(shù)即是上界
由于主串是由a復(fù)制多次而來，并且是從主串中找到子串b，因此可以明確子串的起始位置，不會超過a的長度。
即長度越過a長度的起始匹配位置，必然在此前已經(jīng)被匹配過了。 ？?
由此，我們可知復(fù)制次數(shù)【上界】最多為【下界+1】
令a的長度為n，b的長度為m，下界次數(shù)為c1，上界次數(shù)為c2=c1+1
因此我們可以對a復(fù)制c2次，得到主串后匹配b，如果匹配成功后的結(jié)束位置不超過n*c1，說明復(fù)制c1即可，返回c1，超過則返回c2；匹配不成功則返回-1。
上下界性質(zhì)
? ?public int repeatedStringMatch(String a, String b) {
? ?StringBuilder sb = new StringBuilder(); ? ?int ans=0; ? ?while(sb.length()<b.length()){
? ? ? ?ans++; //統(tǒng)計(jì)疊加的次數(shù)
? ? ? ?sb.append(a);
? ?}
? ?sb.append(a); //加一個(gè)達(dá)到上界 注意 這個(gè)疊加并沒有進(jìn)行ans的統(tǒng)計(jì)。
? ?int idx = sb.indexOf(b); //得到第一次出現(xiàn)的索引
? ?if(idx==-1) return -1; // 如果索引是-1 說明不存在 返回-1
? ?return idx+b.length()>a.length()*ans?ans+1:ans; // 得到結(jié)束的位置 即初始位置（idx）+b.length() ?如果結(jié)束的位置大于 c1次，則返回ans+1
? ?
?}
字符串哈希
結(jié)合[基本分析]，我們知道這本質(zhì)是一個(gè)子串匹配問題，我們可以使用[字符串哈希]來解決。
仍然是先將a復(fù)制[上界]次，得到子串ss，目的是從ss中檢測是否存在子串b。
在字符串哈希中，為了方便，我們將ss和b進(jìn)行拼接，設(shè)拼接后長度為len，那么b串的哈希值為[len-m+1,len]部分（下標(biāo)從1開始），記為target。
然后在[1,n]范圍內(nèi)枚舉起點(diǎn)，嘗試找長度為m的哈希值與target相同的哈希值。
public ?int repeateStringMatch(String a,String b){
? ?StringBuilder sb = ?new StringBuilder(); ? ?int ans=0; ? ?while(sb.length()<b.length()){
? ? ? ?ans++;
? ? ? ?sb.append(a);
? ?}
? ?sb.append(a); ? ?int idx = strHash(sb.toString(),b); ? ?if(idx==-1) return -1; ? ?return inx+b.length()>a.length()*ans?ans+1:ans;
? ?} ? ?
? int strHash(String ss, String b) { ? ? ? ?int P = 131; ? ? ? ?int n = ss.length(), m = b.length();
? ? ? ?String str = ss + b; ? ? ? ?int len = str.length(); ? ? ? ?int[] h = new int[len + 10], p = new int[len + 10];
? ? ? ?p[0] = 1; ? ? ? ?for (int i = 0; i < len; i++) {
? ? ? ? ? ?p[i + 1] = p[i] * P;
? ? ? ? ? ?h[i + 1] = h[i] * P + str.charAt(i);
? ? ? ?} ? ? ? ?int r = len, l = r - m + 1; ? ? ? ?int target = h[r] - h[l - 1] * p[r - l + 1]; // b 的哈希值
? ? ? ?for (int i = 1; i <= n; i++) { ? ? ? ? ? ?int j = i + m - 1; ? ? ? ? ? ?int cur = h[j] - h[i - 1] * p[j - i + 1]; // 子串哈希值
? ? ? ? ? ?if (cur == target) return i - 1;
? ? ? ?} ? ? ? ?return -1;
? ?}
}
模擬
5 最長回文子串
https://leetcode-cn.com/problems/longest-palindromic-substring/
樸素解法
枚舉字符串
回文串長度是奇數(shù)，則依次判斷s[i-k]==s[i+k],k=1,2,3...
回文串長度是偶數(shù)，則依次判斷s[i-k]==[i+k-1],k=1,1,3...
? ?public String longestPalindrome(String s){
? ? ? ?String ans = ""; ? ? ? ?for(int i=0;i<s.length();i++){ ? ? ? ? ? ?//回文串為奇數(shù)
? ? ? ? ? ?int l = i-1,r=i+1;
? ? ? ? ? ?String sub = getString(s,l,r); ? ? ? ? ? ?if(sub.length()>ans.length()) ans = sub; ? ? ? ? ? ?
? ? ? ? ? ?//回文串為偶數(shù)
? ? ? ? ? ?l = i-1;
? ? ? ? ? ?r = i+1-1;
? ? ? ? ? ?sub = getString(s,l,r); ? ? ? ? ? ?if(sub.length()>ans.length()) ans = sub;
? ? ? ? ? ?
? ? ? ?} ? ? ? ?return ans;
? ?} ? ?
? ?String getString(String s,int l ,int r){ ? ? ? ?while(l>=0&&r<s.length()&&s.charAt(l)==s.charAt(r)){
? ? ? ? ? ?l--;
? ? ? ? ? ?r++;
? ? ? ?} ? ? ? ?return s.substring(l+1,r); // l+1 是因?yàn)?/span> l--了，對應(yīng)的范圍應(yīng)該要+1，而r因?yàn)?/span>api的原因，是取不到的，所以不用處理。
? ? ? ?//即 substring為 左閉右開的。
? ? ? ?
? ?}
動(dòng)態(tài)規(guī)劃
https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/
走進(jìn)現(xiàn)代通信
香農(nóng)-韋弗模式
構(gòu)建了一個(gè)直線單向的框架，描述了一般化的通信系統(tǒng)的信息傳播過程。此模式包含了信源、發(fā)射器、信道、噪聲、接收器、信宿6個(gè)部分。
信源與信宿：信源即信息的源頭；信宿即信息的歸宿，是接收信息的實(shí)體。這兩個(gè)概念是相對的，在不同的場景下可以發(fā)生轉(zhuǎn)換，例如，收音機(jī)接收電臺信號時(shí)是信宿；發(fā)出節(jié)目聲音時(shí)是信源，此時(shí)聽收音機(jī)的人則成了信宿。
發(fā)射器與接收器：編碼和解碼。
信道和噪聲：
通信方式：雙工、半雙工、單工。
當(dāng)代通信
3G
分為WCDMA、cdma2000、TD-SCDMA
WCDMA和cdma2000屬于頻分雙工方式（FDD），而TD-SCDMA屬于時(shí)分雙工方式（TDD）。WCDMA和cdma2000是上下行獨(dú)享相應(yīng)的帶寬，上下行之間需要一定的頻率間隔做“隔離帶”以避免干擾；TD-SCDMA則上下行采用同一頻譜，上下行之間需要時(shí)間間隔做”紅綠燈“以避免干擾。
4G
LTE
LTE系統(tǒng)引入了正交頻分復(fù)用（OFDM,orthogonal?frequency?division?multiplexing)和多輸入多輸出（MIMO），顯著提高了頻譜效率和數(shù)據(jù)傳輸速率。
根據(jù)雙工方式的不同，LTE系統(tǒng)分為FDD-LTE和TDD-LTE。二者技術(shù)的主要區(qū)別在于空口的物理層上（例如，幀結(jié)構(gòu)、時(shí)分設(shè)計(jì)、同步等）。FDD空口上下采用成對的、不同的頻段接收、發(fā)送數(shù)據(jù)，而TDD系統(tǒng)上下行使用相同的頻段在不同的時(shí)隙上傳輸，TDD比FDD有著更高的頻率利用率。
LTE-A：
LTE-A采用了載波聚合（CA，Carrier Aggregation）、上/下行多天線增強(qiáng)、多點(diǎn)協(xié)作傳輸、中繼、異構(gòu)網(wǎng)干擾協(xié)調(diào)增強(qiáng)等關(guān)鍵技術(shù)，能大大提高無線通信系統(tǒng)的峰值數(shù)據(jù)速率、峰值頻譜效率、小區(qū)平均頻譜效率以及小區(qū)邊界用戶性能。所謂多載波聚合，就是將多個(gè)頻段的網(wǎng)絡(luò)信號聚合起來，相當(dāng)于公路從“單車道”變?yōu)榱恕岸嘬嚨馈啊?/p>
5G
根據(jù)3GPP的定義，5G的三大應(yīng)用場景為eMBB、mMTC、URLLC。eMBB即為增強(qiáng)移動(dòng)寬帶，超高速，為大流量移動(dòng)寬帶業(yè)務(wù)提供支持；mMTC指海量機(jī)器類通信，物聯(lián)網(wǎng)；URLLC,低時(shí)延。
一般天線的尺寸為電磁波信號的1/4波長為佳。
