一、环绕字符串中唯一的子字符串（线性dp）
题意:
有一个base串，是a-z重复循环的。然后给你一个字符串，看这个字符串的子串是base串中出现的次数。
输入：s = "zab"
输出：6
解释：字符串 s 有六个子字符串 ("z", "a", "b", "za", "ab", and "zab") 在 base 中出现。
思路：
可以使用线性dp来做。这里要注意的是dp[i]，表示的是以这个字母为结尾对该答案的贡献值。说白了就是加上这个字母之后，增加了多少种可能的机会。
动规五部曲：
dp[i]:上面
递推式:当上一个字母和下一个字母可以连上，j++；并且只有在不连的时候才会置为1；(如果出现这种a,b,c 那么j就会变成3) dp[i]=Math.max(dp[i],j);
初始化：dp[ch[0]-''a]=1;
遍历顺序：从1开始到s.length()
代码:
class Solution {
public int findSubstringInWraproundString(String s) {
char[] cs=s.toCharArray();
int n=cs.length;
int[] dp=new int[26];
dp[cs[0]-'a']=1;
for(int i=1,j=1;i<n;i++){
if((cs[i]=='a'&&cs[i-1]=='z')||cs[i-1]+1==cs[i])j++;
else j=1;
dp[cs[i]-'a']=Math.max(dp[cs[i]-'a'],j);
}
int sum=0;
for(int i=0;i<26;i++){
sum+=dp[i];
}
return sum;
}
}二、最优除法
题意：
给定一正整数数组 nums，nums 中的相邻整数将进行浮点除法。
- 例如，
nums = [2,3,4]，我们将求表达式的值"2/3/4"。
但是，你可以在任意位置添加任意数目的括号，来改变算数的优先级。你需要找出怎么添加括号，以便计算后的表达式的值为最大值。
思路：
要想使表达式的值为最大值。
1.要么使分子变大，要么使分母变小。
2.这道题中每一个元素都是>=2的正整数，所以只能使分母变小
3.如何使分母变小：只能不断地将分母除以下一个数 类似于这样1/(2/3/4/5/6);
4.但是要注意一些冗余的符号。比如说只有两个元素的时候 就不需要加()
代码：
class Solution {
public String optimalDivision(int[] nums) {
int size=nums.length;
StringBuilder sb=new StringBuilder();
if(size==1)return nums[0]+"";
if(size==2)return nums[0]+"/"+nums[1];
for(int i=0;i<nums.length;i++){
if(i==0)sb.append(nums[0]).append("/(");
else if(i==nums.length-1)sb.append(nums[i]).append(")");
else{
sb.append(nums[i]).append("/");
}
}
return sb.toString();
}
}三、复数乘法(简单)
注意:
在String.split()方法中，可以使用正则表达式。eg:在这道题中 a+bi;
String.split("\\ + | i ");\\是转义字符，|代表或的意思。这个表示：将字符串a+bi分解成两个部分a.b;
代码：
/**
* i2是-1
* 分步骤 1.实部*实部 虚部*虚部 这个是看有没有实数
* 2.实部1*虚部2+实部2*虚部1 这个是i前面的系数
*/
class Solution {
public String complexNumberMultiply(String num1, String num2) {
String[] split1=num1.split("\\+|i");
String[] split2=num2.split("\\+|i");
//先计算实数
int number1=Integer.parseInt(split1[0]);//实数1
int number2=Integer.parseInt(split2[0]);//实数2
int number3=Integer.parseInt(split1[1]);//虚部实数1
int number4=Integer.parseInt(split2[1]);//虚部实数2
System.out.println("实数1:"+number1 +"虚数1:"+number3+"实数2:"+number2+"虚数2:"+number4);
StringBuilder sb=new StringBuilder();
int real=number1*number2-number3*number4;
int virtual=number1*number4+number2*number3;
sb.append(real).append("+").append(virtual).append("i");
return sb.toString();
}
}四、外观数列(一般)
输入：n = 4
输出："1211"
解释：
countAndSay(1) = "1"
countAndSay(2) = "1" 的行程长度编码 = "11"
countAndSay(3) = "11" 的行程长度编码 = "21"
countAndSay(4) = "21" 的行程长度编码 = "1211"
n是变换的次数(从普通数字变成行程长度编码)
eg:1->11(1个1)；11->21(2个1) 21->1211(1个2 1个1)...
思路：
从给出的字符串中我们需要进行判断，连续相同的数字有几个，然后把数字记录下来。如何判断连续相同的数字(nums[i]==nums[i+1]&&i+1<nums.length)
代码：
class Solution {
public String countAndSay(int n) {
String str = "1";
for (int i = 1; i < n; i++) {
str = encode(str);
System.out.println(str);
}
return str;
}
// 从原始字符串->行程长度编码
public String encode(String str) {
int count = 1;
StringBuilder sb = new StringBuilder();
for (int i = 0; i < str.length(); i++) {
if (i < str.length() - 1 && str.charAt(i) == str.charAt(i + 1)) {
count++;
}else{
sb.append(count).append(str.charAt(i));
count=1;
}
}
return sb.toString();
}
// 从行程长度编码->到原始字符串
public String decode(String str) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < str.length() - 1; i += 2) {
Integer count = str.charAt(i) - '0';
for (int j = 0; j < count; j++) {
sb.append(str.charAt(i + 1));
}
}
return sb.toString();
}
}五、整数转罗马数字(模拟)
思路：
将罗马数字可以组成的大小（从大到小）放到一个数组里面，然后字符串表示放到一个数组里面。然后按照从大到小进行对值抽离。
int[] arr=new int[]{1000,900,500,400,100,90,50,40,10,9,5,4,1};
eg 1994:1000(遍历) num-=value 还剩900(遍历) num-=value 还剩4(继续遍历) 然后num-=value。这样的话根据字符串数组里面对应的，使用StringBuilder sb拼接就行。
代码：
class Solution {
public String intToRoman(int num) {
int[] arr=new int[]{1000,900,500,400,100,90,50,40,10,9,5,4,1};
String[] strs=new String[]{"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
StringBuilder sb=new StringBuilder();
for(int i=0;i<arr.length&&num>0;i++){
int value=arr[i];
String str=strs[i];
while(num>=value){
num-=value;
sb.append(str);
}
}
return sb.toString();
}
}六、字符串转换整数(值的越界处理)
规则：
1.当遇到前置空格的时候，不用管，直接跳过
2.前置空格后会遇到‘+’，‘-’。如果是+就是正数，如果是-就是负数
3.如果后面出现的不是数字 直接返回已经出现过的数字
eg: +45aaa :返回45 eg:-4aa2 返回-4
注意：可能会遇到越界的问题（如何处理）
每当result=result*10+digit的时候，要对result进行判断。
if(result>(Integer.MAX_VALUE)/10||
result==(Integer.MAX_VALUE)/10&&digit<Integer.MAX_VALUE%10)
如果遇到这种情况就越界了。result*10+digit>Integer.MAX_VALUE;
代码：
class Solution {
public int myAtoi(String s) {
int size=s.length();
if (s == null || size == 0) {
return 0;
}
int i = 0;//指针
int sign = 1;//判断正负
int result = 0;//返回的结果
// 丢弃前导空格
while(i<size&&s.charAt(i)==' ')i++;
// 判断符号
if(i<size&&(s.charAt(i)=='+'||s.charAt(i)=='-')){
if(s.charAt(i)=='-')sign=-1;
i++;
}
// 转换数字
while(i<size&&Character.isDigit(s.charAt(i))){
//Character.isDigit(ch) 判断字符是否是数字的方法
int digit=s.charAt(i)-'0';
//防止溢出
if(result>(Integer.MAX_VALUE-digit)/10){
//出现这两种情况就有问题
return sign==1?Integer.MAX_VALUE:Integer.MIN_VALUE;
}
result=result*10+digit;
i++;
}
return result*sign;
}
}
七、压缩字符串(处理技巧)
从一个空字符串 s 开始。对于 chars 中的每组 连续重复字符 ：
- 如果这一组长度为
1，则将字符追加到s中。 - 否则，需要向
s追加字符，后跟这一组的长度。
压缩后得到的字符串 s 不应该直接返回 ，需要转储到字符数组 chars 中。需要注意的是，如果组长度为 10 或 10 以上，则在 chars 数组中会被拆分为多个字符。
题意:
对字符数组中的字符进行判断，如果只出现一次，只需要把字符添加到chars数组中；
如果出现了多次，就要把字符和次数都添加到chars数组中。aaaaaaaaaaaa12次。要添加‘a’,'1','2'
思路:
指针法：依然是统计连续相同的字符。但是不需要考虑i<length-1什么的
使用char ch=chars[index]记录初始的字符。然后挨个比较就行
代码:
class Solution {
public int compress(char[] chars) {
int size = chars.length;
int index = 0;
int cnt = 0;
while (index < size) {
char currentChar=chars[index];
int count=0;
//找连续相同的字母数量
while (index<size&&chars[index]==currentChar) {
count++;
index++;
}
chars[cnt++]=currentChar;
if (count >1){
String countStr=String.valueOf(count);
for(char c:countStr.toCharArray()){
chars[cnt++]=c;
}
}
}
return cnt;
}
}八、比较版本号(如何把情况综合在一起考虑？)
给你两个 版本号字符串 version1 和 version2 ，请你比较它们。版本号由被点 '.' 分开的修订号组成。修订号的值 是它 转换为整数 并忽略前导零。
比较版本号时，请按 从左到右的顺序 依次比较它们的修订号。如果其中一个版本字符串的修订号较少，则将缺失的修订号视为 0。
输入：version1 = "1.0", version2 = "1.0.0.0"
输出：0
version1 有更少的修订号，每个缺失的修订号按 "0" 处理。
思路：
使用String的split方法（注意这里要加转义字符\\）,字符串可能是没有.的，因此可能出现某一个版本字符串split后的长度为0；
所以在进行for循环的时候for(int i=0;i<ver1.length||i<ver2.length;i++)
if(x<ver1.length) or if(y<ver2.length) 如果长度为0的话,那么就是0；
如果两个字符串都带有"."。那么直接分割就行，然后对比每一个. .之间的大小，Integer.parseInt(ver1[i])已经是去掉前置0的情况了。直接比较就行
代码：
class Solution {
public int compareVersion(String version1, String version2) {
String[] split1 = version1.split("\\.");
String[] split2 = version2.split("\\.");
for (int i = 0; i < split1.length || i < split2.length; i++) {
int x = 0, y = 0;
if (i < split1.length) {
x = Integer.parseInt(split1[i]);
}
if (i < split2.length) {
y = Integer.parseInt(split2[i]);
}
if (x < y)
return -1;
if (x > y)
return 1;
}
return 0;
}
}九、罗马数字转整数
思路:
首先使用 map集合将罗马数字和数值联系在一起。然后根据所给的字符串进行判断，如果charAt(i)所对应的数值是小于charAt(i+1)的，这说明是两个字母组在一起表示的。那么这种情况就要把当前字母所表示的数值减去。
对比整数转罗马数字:
思路：整数转罗马数字是将所有表示数值的罗马字符从大到小都组合起来，然后根据一个一个试，如果当时罗马字符<number的。那么就while循环 --到>number。然后再用下一个字符试。
代码：
class Solution {
Map<Character, Integer> values = new HashMap<Character, Integer>() {{
put('I', 1);put('V', 5);put('X', 10); put('L', 50);
put('C', 100); put('D', 500);put('M', 1000);
}};
public int romanToInt(String s) {
int value=0;
int n = s.length();
for(int i=0;i<n;i++){
int preValue=values.get(s.charAt(i));
if(i+1<n&&values.get(s.charAt(i+1))>preValue){
value-=preValue;
}else{
value+=preValue;
}
}
return value;
}
}
