剑指offer打卡

day1 二叉树和为某一路径

思路分析

• 初步想法：这个题就是一个典型的爆搜问题，我们最简单的一个想法就是，搜索所有路径，并求和进行判断，所以我们可以使用dfs模板
• 简化：为了判断是否于tar相等，我们需要每次递归时都传入，sum，tar两个参数，我们可以将加法转化为减法，与0进行比较
• 在这里我们需要使用递归函数，所以采用递归三步法进行分析：定义，终止条件，单层逻辑；

class Solution {static List<List<Integer>> ans;static List<Integer> res=new ArrayList<>();public List<List<Integer>> findPath(TreeNode root, int sum) {ans=new ArrayList<>();dfs(root,sum);return ans;}//1.定义:对路径进行搜索，无返回值public static void dfs(TreeNode root,int sum){//2.递归终止条件，当传入节点为null时，则无需进行下一步递归。if(root==null)return;//如果为null则直接返回//3.单层逻辑res.add(root.val);//3.1将该值加入ressum=sum-root.val;//3.2并用sum减去该值//3.3判断此时的节点是否符合要求//**********重点**********/*为什么在ans.add(new ArrayList<>(res)) 要重新建立一个list？*答:在该题中res为成员变量，所有的方法共享一个，指向同一地址；*如果直接加入，在后续语句中，依旧会修改res，导致其答案不一样**/if(root.left==null && root.right==null && sum==0)ans.add(new ArrayList<>(res));//3.4递归处理左右子树dfs(root.left,sum);dfs(root.right,sum);res.remove(res.size()-1);//恢复现状，如果该条路不同则，退出该值，}

day2复杂链表的复刻

思路分析

• 首先我们可以使用hash表存储每个点对应的来next指针 random指针，而后复现
• 在这里我们还有另一种做法：
  1. 在每个点对应的后面复制每一个点
  2. 遍历链表处理random指针
  3. 将这两条互相交叉的链分开（必须将原有链恢复原样，不然会报错）

class Solution {public ListNode copyRandomList(ListNode head) {//1.在原链表的每一个节点后加上节点的复制if(head==null)return null;for(ListNode p = head ; p != null;){ListNode q = new ListNode(p.val);//防止断链ListNode next = p.next;p.next = q;q.next = next;p = next;}//2.将新加入的节点的random指针指向原链表的random指针for(ListNode p = head ; p != null ; p = p.next.next){if(p.random != null){//新节点的random指针指向原节点random指针指向的下一个节点p.next.random = p.random.next;}}//3.将两条链分开ListNode dummy = new ListNode(-1);ListNode cur = dummy;for(ListNode p = head; p != null; p = p.next){cur.next = p.next;cur = cur.next;// 前面破坏了原head链表，恢复链表p.next = p.next.next;
}return dummy.next;}
}

day3二叉搜索树与双向链表

思路分析

• 我们可以知道对于一个二叉搜索树，中序遍历与有序列表的元素顺序相同
• 所以我们在这里使用中序遍历的模板
• 对于中序遍历会先重最左边的节点（4）开始处理

class Solution {//指针：用来记录前一个节点·static TreeNode pre=null;public TreeNode convert(TreeNode root) {if(root==null)return null;dfs(root);while(root.left!=null)root=root.left;return root;}//我们一第一个节点4[6]来讲解这个单层逻辑 //1.函数定义：将二叉搜索树变为有序的双向链表，无返回值public static void dfs(TreeNode root){//2.递归终止条件：若节点为空，则结束if(root==null)return;dfs(root.left);//由于中序遍历，所以root 会依次是 4 6 8 10 .。。。root.left=pre;//   null<—4(<-6)[4<—6]if(pre!=null)pre.right=root;//pre为空不执行  [4—>(<——)6]pre=root;//pre=4;[pre=6]dfs(root.right);}}

day4数字排列

思路分析

• 很容易知道这里应该使用回溯算法求解，很经典

class Solution {static List<Integer> path;static boolean[] st;//该数是否被使用static Set<List<Integer>> res;static int n;public List<List<Integer>> permutation(int[] nums) {path=new ArrayList<>();st=new boolean[nums.length];res=new HashSet<>();n=nums.length;dfs(0,nums);List<List<Integer>> ans=new ArrayList<>(res);return ans;}public static void dfs(int u,int[] nums){if(u==n){res.add(new ArrayList<>(path));return;}for(int i=0;i<n;i++){if(!st[i]){path.add(nums[i]);st[i]=true;dfs(u+1,nums);st[i]=false;path.remove(path.size()-1);}}}
}

day5找出出现次数超过一半的次数

class Solution {public int moreThanHalfNum_Solution(int[] nums) {int cnt=1,val=nums[0];for(int i=0;i<nums.length;i++){if(nums[i]==val)cnt++;else cnt--;//如果出现问题则进行重置if(cnt==0){val=nums[i];cnt=1;}}return val;}
}

测试例子解析

• 例1：input（[1,2,1,1,3]）
  i=0：nums[i]=1，val=1，cnt=2
  i=1：nums[i]=2，val=1，cnt=1
  i=2：nums[i]=1，val=1，cnt=2
  i=3：nums[i]=1，val=1，cnt=3
  i=4：nums[i]=3，val=1，cnt=2

例2：input（[2,0,1,1,3]）
i=0：nums[i]=2，val=2，cnt=2
i=1：nums[i]=0，val=2，cnt=1
i=2：nums[i]=1，val=2，cnt=0，重置，val=1，cnt=1
i=3：nums[i]=1，val=1，cnt=2
i=4：nums[i]=3，val=1，cnt=1

day6 二进制中1的个数

基本知识点

• 计算机中数的二进制表示

• 3:00000011

• -3:使用补码进行表示

先计算-3绝对值的二进制 00000011

取反：11111100

加1：11111101（这就是计算级的-3表示）

• 无符号整数：计算机里的数是用二进制表示的，最左边的这一位一般用来表示这个数是正数还是负数，这样的话这个数就是有符号整数。无符号整数包括0和正数。

举例：假设有一个 数据类型有8位组成
无符号整数：8位全部表示数值；范围位[0,2^8-1]
有符号整数：最左边表示符号，后7位表示数值；范围[-111 1111,+111 1111]

• 位运算

un&1:将二进制的个位取出
un>>>1:将个位删掉

思路分析

如果n位正数（0），我们直接挨个将每一位数字取出计算即可
负数：我们可以将负数先转换位无符号整数，在进行与正数相同操作

class Solution {public int NumberOf1(int n) {int res=0;int un=n & 0xffffffff;//将数字转换为无符号整数；0xffffffff表示32个1while(un!=0){res=res+(un&1);un=un>>>1;}return res;}
}

day7 二叉树的最近公共祖先

这里推荐一个大佬的题解
大佬题解（非常详细有用）
思路分析

day8 字符串转换为整数

思路分析

按照以下步骤就可以

• 最前面的空格
• 判断符号
• 数位相乘计算整数
• char 转换位数字 ：char-‘0’

class Solution {public int strToInt(String str) {long res=0;char[] ch=str.toCharArray();int k=0;//去除空格while(k<ch.length && ch[k]==' ')k++;int flag=1;if(k<ch.length && ch[k]=='-'){flag=-1;k++;}else if(k<ch.length && ch[k]=='+') k++;// System.out.println(k<ch.length && ch[k]>='0' && ch[k]<='9');while(k<ch.length && ch[k]>='0' && ch[k]<='9'){// System.out.println(ch[k]-'0');res=res*10+(ch[k]-'0');if (res > 1e11) break;k++;}// System.out.println(res);res=(res*flag);if (res > Integer.MAX_VALUE) res = Integer.MAX_VALUE;if (res < Integer.MIN_VALUE) res = Integer.MIN_VALUE;return (int)res;}
}

day9 构建乘积数组

思路分析

• B[i]主要由 A[0,i] 与A[i+1,n-1] 两个连续部分组成

• [0,i-1]的计算

  B[i-1]=A[0]…*A[i-2]
  B[i] =A[0]… *A[i-2] * A[i-1]
  观测可知 B[i]=B[i-1]*A[i-1]

• 在后半部分计算有着同样的规律，所以我们可以利用两个循环来实现答案的计算

class Solution {
/*分析可知
*1.B[i]的乘积有两部分组成，[0,i-1]与[i+1,r]
*2.我们可以注意到在计算[0,i-1]部分上的B[i]乘积时，可以利用前一个B[i-1]*a[i-1]得到
*3.第二部分倒序计算时，有着相同的规律
*5.所以我们可以利用两次循环来获得结果
*/public int[] multiply(int[] A) {int[] ans=new int[A.length];if(A.length==0)return ans;ans[0]=1;//循环计算第一部分for(int i=1;i<A.length;i++){ans[i]=ans[i-1]*A[i-1];}//计算第二部分循环int tmp=1;//tmp记录前一个循环的值for(int i=A.length-2;i>=0;i--){tmp=tmp*A[i+1];ans[i]*=tmp;}return ans;      }
}

day10不用加减乘除的加法

思路分析

• 这里我们利用位运算来求解
• 位运算根据值的不同可以分为4种情况
  | a(i) | b(i) | c(i) | c(i+1) |
  | ---- | ---- | ---- | ------ |
  | 0 | 0 | 0 | 0 |
  | 0 | 1 | 1 | 0 |
  | 1 | 0 | 1| 0 |
  | 1 | 1 | 0 | 1 |
• 本位：当两个同为1/0时，等于0；否则为1；即 本位 为 a^b
• 进位：两个数同为 1 时 为1 所以 进位 为 a&b
• 我们可以类比10进制，当知道10位数为a，个位数为b—> (a*10+b )
  同理，二进制即为：a&b<<1+a^b;
  由于不能用加法，我们可以多次循环值进位为0，则此时的 非进位即所求答案
  大佬详解

class Solution {public int add(int num1, int num2) {if(num2==0)return num1;return add(num1^num2,(num1&num2)<<1);}
}

day11求1+2…+n

思路分析

• 根据题意不能使用循环和乘除法，所以很容易想到使用递归
• 最小子问题 n=1 return 1；
• 单层逻辑：n+getSum(n-1)

class Solution {public int getSum(int n) {if(n==1)return 1;return n+getSum(n-1);}
}

day11 股票的最大价值

思路分析

• 状态表示
  • 状态集合：前i个元素中任选两个元素的所有选法
  • 属性：序号后-序号前的最大值
• 状态计算
  • 不包含 nums[i] 最大值为 dp[i-1]
  • 包含nums[i] 最大值 为 nums[i]-min(前i个元素的最小值)

所以状态转移方程为 dp[i]=Math.max(dp[i-1],nums[i]-min)

day13扑克牌的顺子

day14骰子的点数

day15滑动窗口的最大值