一、通过删除字母匹配到字符字典中的最大值

给你一个字符串 s 和一个字符串数组 dictionary ，找出并返回 dictionary 中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。

如果答案不止一个，返回长度最长且字母序最小的字符串。如果答案不存在，则返回空字符串。

输入：s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
输出："apple"

思路:

遍历字符字典中的字符串，找到s串的子串，然后计算长度；

t串的长度大于res的长度，更新res；

t串的长度==res串的长度并且t串的字母序是靠前的，更新res；

注意:

使用String类中的compareTo()方法

返回值是整型，它是先比较对应字符的大小(ASCII码顺序)，如果第一个字符和参数的第一个字符不等，结束比较，返回他们之间的长度差值，如果第一个字符和参数的第一个字符相等，则以第二个字符和参数的第二个字符做比较，以此类推,直至比较的字符或被比较的字符有一方结束。

代码：

class Solution {public String findLongestWord(String s, List<String> dictionary) {String res = "";for (String str : dictionary) {int i = 0;int j = 0;while (i < s.length() && j < str.length()) {if (s.charAt(i) == str.charAt(j)) {j++;}i++;}if (j == str.length()) {if ((str.length() > res.length() || str.length() == res.length() && str.compareTo(res) < 0)) {// 说明是子串 然后判断长度res = str;}}}return res;}
}

二、最长特殊序列II

输入: strs = ["aba","cdc","eae"]
输出: 3

输入: strs = ["aaa","aaa","aa"]
输出: -1

题意：

给定字符串列表 strs ，返回其中 最长的特殊序列 的长度。如果最长特殊序列不存在，返回 -1 。

最长的特殊序列：该序列为某字符串 独有的子序列（即不能是其他字符串的子序列）。

思路：

就是判断每一个字符串是不是其它字符串的子串，如果是的话，该字符串的最长特殊序列的长度为0；如果都不是的话，那么最长特殊序列的长度为str.length();

代码：

class Solution {public int findLUSlength(String[] strs) {int max = -1;for (int i = 0; i < strs.length; i++) {boolean flag = true;String t = strs[i];for (int j = 0; j < strs.length; j++) {if (i != j) {String s = strs[j];System.out.println("t: "+t+" s: "+s+"是否为子串:"+isSonStr(t,s));if (isSonStr(t, s)) {flag = false;}}}if (flag)max = Math.max(max, strs[i].length());}return max;}public boolean isSonStr(String t, String s) {int i = 0;int j = 0;while (i < t.length() && j < s.length()) {if (t.charAt(i) == s.charAt(j)) {i++;}j++;}if (i == t.length())return true;return false;}
}

疑惑：

如果是aaa,aaa,aa。当进行判断字符串aaa是不是最长特殊序列的时候。先和aaa比较，发现是子串，flag直接为false；就不用和后面的aa进行比较了(尽管比较返回结果为true)；

只要它是剩下字符串中其中一个的子串，就直接flag=false;

三、加一

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。

代码十分巧妙:如果该位置是9的话，那么就把它变成0。(数组的其他位置还会发生变化，需要继续遍历，直到不==9，返回)

如果不是9的话，就直接+1并且return digits；因为此时数组其他位置上已经不会变化了，直接返回数组就行。

最后如果还没有return，那么就要在最开始进一位

代码：

class Solution {public int[] plusOne(int[] digits) {int size=digits.length;for(int i=size-1;i>=0;i--){if(digits[i]==9){digits[i]=0;}else{digits[i]++;return digits;}}//如果代码执行到这里 说明还没有return掉 遇到999这种情况int[] arr=new int[digits.length+1];arr[0]=1;return arr;}
}

四、字符串相乘

如何避免越界的情况:

之前我使用int类型的变量去累加每一位上相乘的结果，因此会越界异常。

每一位置上的数字使用数组存储，然后再用字符串将每一个位置上的数字拼接起来。

思路:

1.首先创建一个长度为len1+len2的数组，用于存放每一位上的数。m位数*n位数的结果最多是(m+n)位数

2.使用双重循环给数组的每一个位置上赋值。int multi=x*y+arr[i+j+1]; arr[i+j+1]=multi%10;

arr[i+j]=multi/10; i+j+1是根据i,j的大小决定的，并且表示的是multi个位上的数字。multi是x*y的乘积加上上一次相乘结果的进位。i+j+1是进位。

注意：

最后使用StringBuilder拼接的时候，首位可能为0(比如说33*30=999 只有三位数 但是数组的空间是4)，要考虑到这种情况

代码:

//会涉及到很大的数 超出int的范围
class Solution {public String multiply(String num1, String num2) {//如果出现0 直接返回0if(num1.equals("0")||num2.equals("0"))return "0";//其他情况int len1=num1.length();int len2=num2.length();int[] res=new int[len1+len2];//len1位数*len2位数 结果最多会有(len1+len2)位数for(int i=len1-1;i>=0;i--){int value1=num1.charAt(i)-'0';for(int j=len2-1;j>=0;j--){int value2=num2.charAt(j)-'0';int multi=value1*value2+res[i+j+1];res[i+j+1]=multi%10;res[i+j]+=multi/10;}}StringBuilder sb=new StringBuilder();for(int i=0;i<res.length;i++){if(i==0&&res[i]==0)continue;sb.append(res[i]);//拼接每一个数字}return sb.toString();}
}

五、累加数(回溯+剪枝)

累加数 是一个字符串，组成它的数字可以形成累加序列。

一个有效的 累加序列 必须 至少 包含 3 个数。除了最开始的两个数以外，序列中的每个后续数字必须是它之前两个数字之和。

给你一个只包含数字 '0'-'9' 的字符串，编写一个算法来判断给定输入是否是 累加数 。如果是，返回 true ；否则，返回 false 。

说明：累加序列里的数，除数字 0 之外，不会 以 0 开头，所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。101 这样也可以

回溯算法:

1.返回值:boolean 参数:String num(字符串)、int count(数字的个数)、int startIndex(遍历的起始位置)、int prev(前一个数)、int prevprev(前两个数)

2.终止条件:当startIndex>=num.length()的时候，说明遍历结束了。此时要判断count是否大于2，如果超过两个数字，就说明字符串中存在三个数字，符合x1+x2=x3这样的规律

3.单层递归逻辑：for循环中，每次根据遍历的位置计算当前数字的值。然后根据条件判断是否继续遍历(条件为:count>=2 然后current>prev+prevprev 或者current<prev+prevprev)。如果满足条件,就终止了(遍历到下一层自动终止了)

代码：

class Solution {public boolean isAdditiveNumber(String num) {return dfs(num,0,0,0,0);}public boolean dfs(String num,int count,int startIndex,long prev,long pprev){//终止条件if(startIndex>=num.length()){return count>2;}//单层递归逻辑long cur=0;for(int i=startIndex;i<num.length();i++){//剪枝1：如果碰到0开头的数字 直接return false;if(i>startIndex&&num.charAt(startIndex)=='0')return false;char ch=num.charAt(i);int number=ch-'0';cur=cur*10+number;//当前的数字if(count>=2){long sum=prev+pprev;if(cur>sum){return false;}else if(cur<sum){continue;}}//如果count<2或者满足条件 就需要继续遍历boolean flag=dfs(num,count+1,i+1,cur,prev);if(flag)return true;}return false;}
}

六、z字形变换

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

P   A   H   N
A P L S I I G
Y   I   R

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

思路：

使用List<StringBuilder>来存储每一行的字符串,最后将每一行的字符串拼接起来返回。

在遍历每一个字符串的字符的同时，把它加到对应的行中。(行是从上往下依次递增，如果在第一行或者最后一行就要转变方向 往下是++ 往上是--)

代码：

class Solution {public String convert(String s, int numRows) {//如果按照一行变换的话 直接返回if(numRows==1)return s;//创建存储行的集合List<StringBuilder> rows=new ArrayList<>();//初始化for(int i=0;i<Math.min(s.length(),numRows);i++){rows.add(new StringBuilder());}//控制方向的变量boolean up=false;int curRow=0;for(char ch:s.toCharArray()){rows.get(curRow).append(ch);//某一行进行拼接if(curRow==0||curRow==numRows-1){up=!up;}curRow+=up?1:-1;}StringBuilder res=new StringBuilder();for(StringBuilder sb:rows){res.append(sb);}return res.toString();}
}

七、回文子串类问题(二维dp)

1.dp[i][j]:a.从i->j这个范围内是否是回文子串。b.或者i->j里面最大回文子串的长度。

2.递推公式:

a.如果str.charAt(i)==str.charAt(j)。如果j-i<=1,dp[i][j]=true;如果j-i>1,dp[i][j]是否是回文子串需要看dp[i+1][j-1];

b.如果str.charAt(i)==str.charAt(j)。dp[i][j]=dp[i+1][j-1]+2; 如果不相等,dp[i][j]=Math.max(dp[i][j-1],dp[i+1][j])

八、最大回文数乘积()

给定一个整数 n ，返回 可表示为两个 n 位整数乘积的 最大回文整数 。因为答案可能非常大，所以返回它对 1337 取余 。

输入：n = 2
输出：987
解释：99 x 91 = 9009, 9009 % 1337 = 987

9009是2位数整数乘积的最大回文整数。

思路：

1.根据n的大小得出最大的n位数

2.从最大的n位数从大到小依次构建相应的回文数

3.如果回文数可以由两个n位数相乘得来，那么就return 回文数%1337

代码:

class Solution {public int largestPalindrome(int n) {if(n==1)return 9;//找到n位数字可以表示的最大值int max=(int)Math.pow(10,n)-1;for(int i=max;i>=0;i--){long num=i;long t=i;//找数的最大值while(t!=0){num=num*10+t%10;t/=10;}//找最大的回文数for(long j=max;j*j>=num;j--){if(num%j==0)return (int)(num%1337);    }}return -1;}
}

九、数字的补数（位运算）

对整数的二进制表示取反（0 变 1 ，1 变 0）后，再转换为十进制表示，可以得到这个整数的补数。

例如，整数 5 的二进制表示是 "101" ，取反后得到 "010" ，再转回十进制表示得到补数 2 。

位运算:(异或)

000^111=111 (异或)，只有当相同的位置上的数字不同时，得1；否则，得0；

思路：

这道题要我们求补数，就是让我们将num上的每一位有效值(不算前面补的0)都和1做异或运算，那么有多少位有效数字呢？就是num/2 可以被除几次。每除一次，就拼接一次1(二进制上的1)

代码：

class Solution {public int findComplement(int num) {int temp=num,c=0;//首先看temp有多少位while(temp>0){temp>>=1;//右移一位c=(c<<1)+1;//c每次都左移一位}return num^c;}
}

十、汉明距离(位运算)

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。

给你两个整数 x 和 y，计算并返回它们之间的汉明距离。

输入：x = 1, y = 4
输出：2
解释：
1   (0 0 0 1)
4   (0 1 0 0)

思路：

把xy异或之后 有多少个1 就有多少个二进制位不同的位置。(只有不同的二进制位异或后才会得1)。然后计算1的个数就可以。

(z&1)==1 count++;z>>>1;

代码:

class Solution {public int hammingDistance(int x, int y) {//异或一下 如果找为1的最小距离int c=x^y;int start=0,end=0;int count=0;while(c!=0){if((c&1)==1)count++;c>>>=1;//因为c可能是0 >>>不考虑符号位}return count;}
}