1.3 模拟/dp|大话移动通信
686 重复叠加字符串的匹配
链接
一题四解
首先，可以分析复制次数的上界和下界。
下界：至少将a复制长度大于等于b的长度，才有可能匹配。
在明确了下界后，再分析经过多少次复制，能够明确得到答案，能够明确得到答案的最小复制次数即是上界
由于主串是由a复制多次而来，并且是从主串中找到子串b，因此可以明确子串的起始位置，不会超过a的长度。
即长度越过a长度的起始匹配位置，必然在此前已经被匹配过了。 ？
由此，我们可知复制次数【上界】最多为【下界+1】
令a的长度为n，b的长度为m，下界次数为c1，上界次数为c2=c1+1
因此我们可以对a复制c2次，得到主串后匹配b，如果匹配成功后的结束位置不超过n*c1，说明复制c1即可，返回c1，超过则返回c2；匹配不成功则返回-1。
上下界性质
public int repeatedStringMatch(String a, String b) {
StringBuilder sb = new StringBuilder(); int ans=0; while(sb.length()<b.length()){
ans++; //统计叠加的次数
sb.append(a);
}
sb.append(a); //加一个达到上界 注意 这个叠加并没有进行ans的统计。
int idx = sb.indexOf(b); //得到第一次出现的索引
if(idx==-1) return -1; // 如果索引是-1 说明不存在 返回-1
return idx+b.length()>a.length()*ans?ans+1:ans; // 得到结束的位置 即初始位置（idx）+b.length() 如果结束的位置大于 c1次，则返回ans+1
}
字符串哈希
结合[基本分析]，我们知道这本质是一个子串匹配问题，我们可以使用[字符串哈希]来解决。
仍然是先将a复制[上界]次，得到子串ss，目的是从ss中检测是否存在子串b。
在字符串哈希中，为了方便，我们将ss和b进行拼接，设拼接后长度为len，那么b串的哈希值为[len-m+1,len]部分（下标从1开始），记为target。
然后在[1,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/
朴素解法
枚举字符串
回文串长度是奇数，则依次判断s[i-k]==s[i+k],k=1,2,3...
回文串长度是偶数，则依次判断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++){ //回文串为奇数
int l = i-1,r=i+1;
String sub = getString(s,l,r); if(sub.length()>ans.length()) ans = sub;
//回文串为偶数
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 是因为 l--了，对应的范围应该要+1，而r因为api的原因，是取不到的，所以不用处理。
//即 substring为 左闭右开的。
}
动态规划
https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/
走进现代通信
香农-韦弗模式
构建了一个直线单向的框架，描述了一般化的通信系统的信息传播过程。此模式包含了信源、发射器、信道、噪声、接收器、信宿6个部分。
信源与信宿：信源即信息的源头；信宿即信息的归宿，是接收信息的实体。这两个概念是相对的，在不同的场景下可以发生转换，例如，收音机接收电台信号时是信宿；发出节目声音时是信源，此时听收音机的人则成了信宿。
发射器与接收器：编码和解码。
信道和噪声：
通信方式：双工、半双工、单工。
当代通信
3G
分为WCDMA、cdma2000、TD-SCDMA
WCDMA和cdma2000属于频分双工方式（FDD），而TD-SCDMA属于时分双工方式（TDD）。WCDMA和cdma2000是上下行独享相应的带宽，上下行之间需要一定的频率间隔做“隔离带”以避免干扰；TD-SCDMA则上下行采用同一频谱，上下行之间需要时间间隔做”红绿灯“以避免干扰。
4G
LTE
LTE系统引入了正交频分复用（OFDM,orthogonal frequency division multiplexing)和多输入多输出（MIMO），显著提高了频谱效率和数据传输速率。
根据双工方式的不同，LTE系统分为FDD-LTE和TDD-LTE。二者技术的主要区别在于空口的物理层上（例如，帧结构、时分设计、同步等）。FDD空口上下采用成对的、不同的频段接收、发送数据，而TDD系统上下行使用相同的频段在不同的时隙上传输，TDD比FDD有着更高的频率利用率。
LTE-A：
LTE-A采用了载波聚合（CA，Carrier Aggregation）、上/下行多天线增强、多点协作传输、中继、异构网干扰协调增强等关键技术，能大大提高无线通信系统的峰值数据速率、峰值频谱效率、小区平均频谱效率以及小区边界用户性能。所谓多载波聚合，就是将多个频段的网络信号聚合起来，相当于公路从“单车道”变为了“多车道“。
5G
根据3GPP的定义，5G的三大应用场景为eMBB、mMTC、URLLC。eMBB即为增强移动宽带，超高速，为大流量移动宽带业务提供支持；mMTC指海量机器类通信，物联网；URLLC,低时延。
一般天线的尺寸为电磁波信号的1/4波长为佳。
