theme: channing-cyan
1 字符串相加
字符串相加，将单个字符串进行加和，如果是空位补 0，从字符串的最后面进行相加操作，然后最终条件是两个字符串都遍历完成，如果有一个字符串提前遍历完成 那么他的字符都是 0，
class Solution {
public String addStrings(String num1, String num2) {
//字符串相加，思路1转换为数字然后相加
//思路2单个字符进行相加，双指针，首先长度长的先和0相加
StringBuilder res=new StringBuilder("");
int i= num1.length()-1;
int j=num2.length()-1;
int carry=0;//是否进位
while(i>=0||j>=0){
//int n1=i>=0?nums.charAt(i)-'0':0;
int n1 = 0; // 初始化 n1
int n2 = 0; // 初始化 n2
// 如果 i 没有越界，取出 num1 对应位置的字符转换为数字
if (i >= 0) {
n1 = num1.charAt(i) - '0';
}
// 如果 j 没有越界，取出 num2 对应位置的字符转换为数字
if (j >= 0) {
n2 = num2.charAt(j) - '0';
}
//int n2=j>=0?nums.charAt(j)-'0':0;
int tmp=n1+n2+carry;
carry=tmp/10;
res.append(tmp % 10);
i--; j--;
}
if(carry == 1) res.append(1);//数据是倒着加入的所以是可以加到最后
return res.reverse().toString();
}
}
2 旋转字符串
解法：这个的冲要条件是长度相同并且，这个字符串 goalgoal 当中保护原字符串，就是这一句话
```java
class Solution {
public boolean rotateString(String s, String goal) {
//依次寻找位置，进行遍历查看有没有这个数据
//这个的冲要条件是长度相同并且，这个字符串goalgoal当中保护原字符串
return s.length()==goal.length()&&(goal+goal).contains(s);
}
}
# 模拟验证栈序列
思路：就是找个栈进行模拟其操作就可以，如果入栈就入栈，出栈就出栈，
入栈，按照顺利入栈
出栈: 当前 top 元素是否等于弹出序列元素
如果栈无法清空的话，说明不等于
```java
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
//判断一个序列是否是栈的序列，找到不满足的规则，直接进行栈操作来模拟
Stack<Integer>stack=new Stack<>();
int i=0;
for(int num:pushed){
stack.push(num);
while(!stack.isEmpty()&&stack.peek()==popped[i]){//这里只有当目前的元素等于pop元素才进行
//执行次数和这个有关而非只有1次的if
stack.pop();
i++;
}
}
return stack.isEmpty();
}
}
3 N 字形变化
最大的问题是读懂题目，大问题是读不懂题目，这里是将字符串设置成为原来竖着读取的字符串，转换成为水平读取的字符串
class Solution {
public String convert(String s, int numRows) {
//读取这个编号的函数，思路还是模拟，假设numRows为4，那就是那s每一位的行数就是：1234321234321
if(numRows<2)
return s;
List<StringBuilder> rows=new ArrayList<StringBuilder>();
for(int i=0;i<numRows;i++){
rows.add(new StringBuilder());
}
//定义了n行的空字符串
int i=0;
int falg=-1;//设置为-1，刚开始正好进行转向
for(char c:s.toCharArray()){
rows.get(i).append(c);//字符串列表第n个字符串添加一个字符
if(i==0||i==numRows-1)//当达到头或者位的时候反向
falg=-falg;///具体反向操作
i+=falg;//每次行索引变化
}
StringBuilder res = new StringBuilder();//结构字符串
for(StringBuilder row : rows) res.append(row);
return res.toString();
}
}
4 螺旋矩阵
就是模拟来实现，具体的是边界值的记忆
具体的算法流程感觉整理的特别的好，这题思路就是从上到下从左向右，if 检查检查的是下一个 for 会不会越界
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
//这道题目给出的条件是m行n列，和上一题区别是
if(matrix.length==0)
return new ArrayList<Integer>();
int l=0;
int r= matrix[0].length-1;
int t=0;
int b= matrix.length-1;
int x=0;//具体的索引
Integer[]res=new Integer[(r+1)*(b+1)];
while(true){
for(int i=l;i<=r;i++){//从左向右进行打印
res[x]=matrix[t][i];
x++;
}//从左向右打印完成之后上边界向内搜索，所以是++b
if(++t>b) break;
for(int i=t;i<=b;i++){
res[x]=matrix[i][r];
x+=1;
}//这里判断的收缩条件是向左的收缩
if(l>--r) break;
//接下来是向左的收缩
for(int i=r;i>=l;i--){
res[x]=matrix[b][i];
x++;
}
if(t>--b) break;
for(int i=b;i>=t;i--){
res[x]=matrix[i][l];
x++;
}
if(++l>r)
break;
}
return Arrays.asList(res);
}
}
5 螺旋矩阵 ２
和上一题思路一致，不过是一个从数组里面取数字，一个向数组里面填数字的不同罢了。
class Solution {
public int[][] generateMatrix(int n) {
//这题和上题的思路类似，一个取数，一个填数罢了
int l=0,r=n-1,t=0,b=n-1;
int[][]mat=new int[n][n];
int num=1,tar=n*n;
while(num<=tar){
for(int i=l;i<=r;i++){
mat[t][i]=num++;
}
t++;
for(int i=t;i<=b;i++){
mat[i][r]=num++;
}
r--;
for(int i=r;i>=l;i--){
mat[b][i]=num++;
}
b--;
for(int i=b;i>=t;i--){
mat[i][l]=num++;
}
l++;
}
return mat;
}
}
6 旋转图像
原地转换的思路很巧妙，必须要推出来一点
class Solution {
public void rotate(int[][] matrix) {
// 设矩阵行列数为 n
int n = matrix.length;
// 起始点范围为 0 <= i < n / 2 , 0 <= j < (n + 1) / 2
// 其中 '/' 为整数除法
for (int i = 0; i < n / 2; i++) {
for (int j = 0; j < (n + 1) / 2; j++) {
// 暂存 A 至 tmp
int tmp = matrix[i][j];
// 元素旋转操作 A <- D <- C <- B <- tmp
matrix[i][j] = matrix[n - 1 - j][i];
matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
matrix[j][n - 1 - i] = tmp;
}
}
}
}
下一步都是上一步导入的推出了 iade，比如第二部分的数据将 i 和 j 带入上面的值，得到第二部分的值，用于记得 i=n-1-j j 等于 i，这个也是符合情况的，比如 最初的左下角，这种情况下才会到左上角
7 字符串转整数
思路比较繁琐：
- 取出前面的空格 trim（）
- 判断正数还是负数 flag
- 判断第一位是符号还是数字，符号从 1 开始，数字从 0 开始
- 数据= res=res*10+(c[j]-'0');
- 数据需要阶段 Integer_MaxVALUE 通过截断的方式来进行处理 if(res>max_num||res==max_num&&c[j]>'7') {
- 非数字字符直接跳出break
class Solution {
public int myAtoi(String s) {
int flag=1;//默认符号位，如果是负数乘以-1就可以，否则就没有影响
//rss=10*res+x,x=S.charAt(i)-S.charAt('0')
//每一轮进行判断数是否越界了
char []c=s.trim().toCharArray();
if(c.length==0) return 0;
int res=0;
int max_num=Integer.MAX_VALUE/10;
int i=1;
if(c[0]=='-') flag=-1;
else if(c[0]!='+')i=0;//如果开始的符号不是加号的话，那么数据实际上向前一位也是数据
for(int j=i;j<c.length;j++){
if(c[j]<'0'||c[j]>'9') break;//如果非数字字符直接跳出
if(res>max_num||res==max_num&&c[j]>'7') {
if(flag==1){
return Integer.MAX_VALUE;
}else{
return Integer.MIN_VALUE;
}
}//如果数据超过了最大的字符或者小于最小字符，将其阶段
res=res*10+(c[j]-'0');
}
return flag*res;
}
}
8 二分查找
记住一种写法就行 left《= right，然后不断下面+1 和-1 的数据了
int left=0,right=nums.length-1;
while(left<=right){
int mid=left+(right-left)/2;
if(nums[mid]==target)
return mid;
if(nums[mid]>target){
right=mid-1;
}
if(nums[mid]<target){
left=mid+1;
}
}
return -1;
*/
9 版本号的查找
思路：二分查找的变形，只要有序的数据都可以使用二分查找
/* The isBadVersion API is defined in the parent class VersionControl.
boolean isBadVersion(int version); */
public class Solution extends VersionControl {
public int firstBadVersion(int n) {
//一个二值数字 true和false组成找到第一个false，二分查找
int i=1,j=n;
while(i<=j){
int tmp=i+(j-i)/2;
if(isBadVersion(tmp)){
//如果是错误版本,正确版本在左边
j=tmp-1;
}else{
i=tmp+1;
}
}
return i;
}
}
10 数组的中位索引
使用前缀和和后缀和的思路，不过要记住 i 位置不参计算，所以先 right，然后比较 然后再left
class Solution {
public int pivotIndex(int[] nums) {
//前缀和遍历数组
int sumLeft=0,sumright=Arrays.stream(nums).sum();//记住这个通过array的流计算和
for(int i=0;i<nums.length;i++){
sumright-=nums[i];//i 位置不参与运算
if(sumLeft==sumright){
return i;
}
sumLeft += nums[i];
}
return -1;
}
}
11 寻找重复数
O (1) 空间复杂度，只能使用本身作为一个哈希表是的 nums[1]=1, nums[2]=2 如果存在 nums[nums[x]]=nums[x] 就跳出
class Solution {
public int findDuplicate(int[] nums) {
//寻找重复的数，和自己的位置进行交换，使得x[i]=i
int i=0;
while(i<nums.length){
if(nums[i]==i){
i++;
continue;
}
if(nums[nums[i]]==nums[i]) return nums[i];
int tmp=nums[i];
nums[i]=nums[tmp];
nums[tmp]=tmp;
}
return -1;
}
}
思路 2：不能修改数组本身的情况下，使用快慢指针的思路 使用环形链表 II 的方法解题（142. 环形链表 II），使用 142 题的思想来解决此题的关键是要理解如何将输入的数组看作为链表。 首先明确前提，整数的数组 nums 中的数字范围是 [1, n]。考虑一下两种情况：
如果数组中没有重复的数，以数组 [1,3,4,2]为例，我们将数组下标 n 和数 nums[n] 建立一个映射关系 f (n) f (n) f (n)， 其映射关系 n->f (n)为： 0->1 1->3 2->4 3->2 我们从下标为 0 出发，根据 f (n) f (n) f (n) 计算出一个值，以这个值为新的下标，再用这个函数计算，以此类推，直到下标超界。这样可以产生一个类似链表一样的序列。 0->1->3->2->4->null
如果数组中有重复的数，以数组 [1,3,4,2,2] 为例, 我们将数组下标 n 和数 nums[n] 建立一个映射关系 f (n) f (n) f (n)， 其映射关系 n->f (n) 为： 0->1 1->3 2->4 3->2 4->2 同样的，我们从下标为 0 出发，根据 f (n) f (n) f (n) 计算出一个值，以这个值为新的下标，再用这个函数计算，以此类推产生一个类似链表一样的序列。 0->1->3->2->4->2->4->2->…… 这里 2->4 是一个循环，那么这个链表可以抽象为下图：
从理论上讲，数组中如果有重复的数，那么就会产生多对一的映射，这样，形成的链表就一定会有环路了，
综上
- 数组中有一个重复的整数 <==> 链表中存在环
- 找到数组中的重复整数 <==> 找到链表的环入口
至此，问题转换为 142 题。那么针对此题，快、慢指针该如何走呢。根据上述数组转链表的映射关系，可推出 142 题中慢指针走一步 slow = slow. Next ==> 本题 slow = nums[slow] 142 题中快指针走两步 fast = fast. Next. Next ==> 本题 fast = nums[nums[fast]]
class Solution {
public int findDuplicate(int[] nums) {
//寻找重复的数，和自己的位置进行交换，使得x[i]=i
int slow = 0, fast = 0;
while(true) {
slow = nums[slow];
fast = nums[nums[fast]];
if (slow == fast) {
break;
}
}
slow = 0;
while(slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
}
思路：下面当作一个链表来进行处理，x=nums[x] 就等价于 x=x.next
12 移动数组的最小值
二分法来解决，重点是区间，当中间的值大于 nums[j]的值的时候，中间值一定不是旋转点的值，所以 i=m+1;，但是当 nums[m]小于 nums[j]的值的时候，不一定是不是这个值，因此给与保留的操作。
class Solution {
public int findMin(int[] nums) {
//选择一次就会将数据左边的一个数据向右移动一次，所以这个数据一定是相对有序的，二分法解决
int i=0;
int j=nums.length-1;
while(i<=j){
int m=i+(j-i)/2;
if(nums[m]>nums[j])//中间部分大于最右边，说明最小点在右
i=m+1;
else if(nums[m]<nums[j])
j=m;
else j--;
}
return nums[i];
}
}