public int candy(int[] ratings) { int[] left = new int[ratings.length]; int[]
right = new int[ratings.length]; Arrays.fill(left, 1); Arrays.fill(right, 1);
for(int i = 1; i < ratings.length; i++) if(ratings[i] > ratings[i - 1]) left[i]
= left[i - 1] + 1; int count = left[ratings.length - 1]; for(int i =
ratings.length - 2; i >= 0; i--) { if(ratings[i] > ratings[i + 1]) right[i] =
right[i + 1] + 1; count += Math.max(left[i], right[i]); } return count; }

public int longestConsecutive(int[] nums) { Set<Integer> num_set = new
HashSet<Integer>(); for (int num : nums) { num_set.add(num); } int
longestStreak = 0; for (int num : num_set) { //没有比它小的数字时 才进入,确保每次更新序列都是从最小的开始
if (!num_set.contains(num - 1)) { int cur = num; int res = 1;
//从一个序列最小的值开始不断更新序列长度 while (num_set.contains(cur + 1)) { cur += 1; res += 1; }
longestStreak = Math.max(longestStreak, res); } } return longestStreak; }

验证回文串是很简单的,用双指针就行了,但是这题需要把空格等符号也省去,所以要注意的是在双指针移动的时候时刻注意数组越界问题,同时注意到两个Character的API:判断是字母或者数字,转成小写字母
public boolean isPalindrome(String s) { int n = s.length(); int left = 0,
right = n - 1; while (left < right) { while (left < right &&
!Character.isLetterOrDigit(s.charAt(left))) { ++left; } while (left < right &&
!Character.isLetterOrDigit(s.charAt(right))) { --right; } if (left < right) {
if (Character.toLowerCase(s.charAt(left)) !=
Character.toLowerCase(s.charAt(right))) { return false; } ++left; --right; } }
return true; }

97题

dp[i][j]的定义为第一个字符串的前i-1个字符和第二个字符串的前j-1个字符是否能构成第三个字符串的i+j-2个字符;其base情况为当一个字符串为空串的时候,只需要对比另一个字符串是否与之完全相等就可以了;

dp[i][j]的状态从dp[i-1][j]和dp[i][j-1]两个状态获取,但前提条件是当前对应状态的对应字符与当前s3所对应的字符要相等
public boolean isInterleave(String s1, String s2, String s3) { int l1 =
s1.length(), l2 = s2.length(), l3 = s3.length(); //长度不等直接false if (l1 + l2 !=
l3) { return false; } //s1的前i个字符和s2的前j个字符是否额能构成s3的前i+j个字符 boolean[][] dp = new
boolean[l1 + 1][l2 + 1]; dp[0][0] = true; //base 一个为空串,只需要比对是否完全相等就可以了 for (int
i = 1; i < l1 + 1; i++) { dp[i][0] = dp[i - 1][0] && s1.charAt(i - 1) ==
s3.charAt(i - 1); } for (int i = 1; i < l2 + 1; i++) { dp[0][i] = dp[0][i - 1]
&& s2.charAt(i - 1) == s3.charAt(i - 1); } //构造dp for (int i = 1; i < l1 + 1;
i++) { for (int j = 1; j < l2 + 1; j++) {
//s1的前i格字符和s2的前j-1格字符是否能构成s3的前i+j-1位+... dp[i][j] = (dp[i][j - 1] &&
s2.charAt(j - 1) == s3.charAt(i + j - 1)) || (dp[i - 1][j] && s1.charAt(i - 1)
== s3.charAt(i + j - 1)); } } return dp[l1][l2]; }

115题

sasa和sa,当sas和sa进行匹配的时候s和a不等,所以sas和sa的情况就等于sa和sa的情况都为一种,当sasa和sa匹配的时候,a==a,它不仅可以继承sas==s的结果2,还可以继承sas和sa的结果1所以一共是3种

i\j" "rabbit
" "1000000
r1100000
a1110000
b1111000
b1112100
b1113300
i1113330
t1113333 public int numDistinct(String s, String t) { int n1=s.length(); int
n2=t.length(); //表示s的前i-1个字符 与t的前j-1个字符有几种方案可以得到 int[][] dp = new int[n1 +
1][n2 + 1]; //当两者字符相等 dp[i][j]=dp[i-1][j-1]+dp[i-1][j] //当两者字符不等
dp[i][j]=dp[i-1][j] //base for (int i = 0; i < n1 + 1; i++) {
dp[i][0]=1;//空集是所有字符串的子集 } //自己为空串的时候无法匹配任何字符串 for (int i = 1; i < n2 + 1; i++)
{ dp[0][i]=0; } for (int i = 1; i <= n1; i++) { for (int j = 1; j <= n2; j++) {
if(s.charAt(i-1)==t.charAt(j-1)){ dp[i][j]=dp[i-1][j]+dp[i-1][j-1]; }else{
dp[i][j]=dp[i-1][j]; } } } return dp[n1][n2]; }
二叉树最大路径和

二叉树的问题需要分清每个节点需要干的事情,每次达到一个节点的时候,对路径有三种选择,停在该节点,去他的左子节点,去它的右子节点

int res =Integer.MIN_VALUE; //采用先序遍历,每次到达一个节点有三种选择:停在当前节点,走到左节点,走到右子节点 public
int maxPathSum(TreeNode root) { dfs(root); return res; } private int
dfs(TreeNode root) { if(root==null)return 0; int left=dfs(root.left); int
right=dfs(root.right); //一个子树内部提供的最大路径等于左子树提供的最大路径和+右子树提供的最大路径和+当前值 res
=Math.max(res,root.val+left+right); //计算当前节点能为父亲提供的最大贡献 int
max=Math.max(root.val+left,root.val+right); //如果当前贡献小于0,直接全部舍弃 return
Math.max(max, 0); }

116-填充完美二叉树的右侧指针

使用深度有限遍历,由于是完美二叉树while循环里的条件可以是左指针也可以是右指针,对于每次dfs来说它需要连接自己的左右节点随后让自己的左子节点靠右走,右子节点靠左走,继续循环
public Node connect(Node root) { dfs(root); return root; } private void
dfs(Node root) { if(root==null)return; Node left=root.left; Node
right=root.right; while (left!=null){ left.next=right;//左指针指向右指针
left=left.right;//左指针走向右边 right=right.left;//右指针走向左边 } //递归调用左右节点
dfs(root.left); dfs(root.right); }
117-非完美二叉树填充右指针

这里主要使用的是bfs广度有限遍历,bfs的框架如下
public void levelOrder(TreeNode tree) { if (tree == null) return;
while (!queue.isEmpty()) { //poll方法相当于移除队列头部的元素 TreeNode node = queue.poll();
System.out.println(node.val); if (node.left != null) queue.add(node.left); if
(node.right != null) queue.add(node.right); } }
依靠该框架容易写出以下代码,在层序遍历的时候连接每个节点即可
public Node connect(Node root) { if (root == null) return root; Queue<Node>
//每一层的数量 int levelCount = queue.size(); //前一个节点 Node pre = null; for (int i =
0; i < levelCount; i++) { //出队 Node node = queue.poll();
//如果pre为空就表示node节点是这一行的第一个， //没有前一个节点指向他，否则就让前一个节点指向他 if (pre != null) {
pre.next = node; } //然后再让当前节点成为前一个节点 pre = node; //左右子节点如果不为空就入队 if (node.left
} return root; }

public Node connect(Node root) { if (root == null) return root;
//cur我们可以把它看做是每一层的链表 Node cur = root; while (cur != null) {
//遍历当前层的时候，为了方便操作在下一 //层前面添加一个哑结点（注意这里是访问 //当前层的节点，然后把下一层的节点串起来） Node dummy =
new Node(0); //pre表示访下一层节点的前一个节点 Node pre = dummy; //然后开始遍历当前层的链表 while (cur !=
null) { if (cur.left != null) { //如果当前节点的左子节点不为空，就让pre节点 //的next指向他，也就是把它串起来
pre.next = cur.left; //然后再更新pre pre = pre.next; } //同理参照左子树 if (cur.right !=
null) { pre.next = cur.right; pre = pre.next; } //继续访问这一行的下一个节点 cur = cur.next;
} //把下一层串联成一个链表之后，让他赋值给cur， //后续继续循环，直到cur为空为止 cur = dummy.next;//跳到下一行操作 }
return root; }

属于是最基本的层序遍历框架了,在for循环结束后加入层序遍历的list,在for循环里向list填充数据
public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>>
res=new ArrayList<>(); //帮助我们获取分层结构的工具人 ArrayDeque<TreeNode> queue = new
(!queue.isEmpty()){ int n=queue.size(); //最后要加入res的list List<Integer> level=new
ArrayList<>(); //对当前层的所有节点进行出队操作并且将下一层的节点加入queue for (int i = 0; i < n; i++) {

使用一个变量count来决定我们当前是从尾部加入节点还是从头部加入节点
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
ArrayDeque<TreeNode> queue = new ArrayDeque<>();
LinkedList<>(); //对当前层的所有节点进行出队操作并且将下一层的节点加入queue for (int i = 0; i < n; i++) {
res; }

public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> res=new ArrayList<>(); if(root==null)return res;
(!deque.isEmpty()){ int n=deque.size(); ArrayList<Integer> list= new
ArrayList<>(); for (int i = 0; i < n; i++) { TreeNode pop = deque.pop();
Collections.reverse(res); return res; }

112题和113题

public boolean hasPathSum(TreeNode root, int sum) { //到最后一个节点都没有找到 if(root ==
null){ return false; } //如果已经是叶子节点了,看当前值是不是和sum相等 if(root.left == null &&
root.right == null){ return root.val == sum; } //只要左边和右边有一边成功就行 return
hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum -
root.val); }

要求出具体值的集合基本就是用回溯算法来做,只在叶子节点增加结果
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<List<Integer>> res=new ArrayList<>(); Deque<Integer> path=new
ArrayDeque<>(); dfs(root,targetSum,path,res); return res; } private void
dfs(TreeNode root, int targetSum, Deque<Integer> path, List<List<Integer>> res)
ArrayList<>(path)); } } dfs(root.left,targetSum-root.val,path,res);
dfs(root.right,targetSum-root.val,path,res); path.removeLast(); }

false

height这个函数的定义是返回改节点子树的高度,只要最后的结果不是-1就说明运算完毕没有发现子树高度差大于1的情况
public boolean isBalanced(TreeNode root) { return height(root) !=-1; }
//后序遍历自底向上 public int height(TreeNode root) { if (root == null) { return 0; }
int leftHeight = height(root.left); int rightHeight = height(root.right); if
(leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) >
1) { return -1; } else { return Math.max(leftHeight, rightHeight) + 1; } }

使用深度优先遍历,dfs返回两个节点是否是对称的
public boolean isSymmetric(TreeNode root) { if(root==null)return true; return
dfs(root.left,root.right); } private boolean dfs(TreeNode left, TreeNode right)
{ if(left==null&&right==null)return true; if(left==null||right==null)return
false; if(left.val!=right.val)return false; return
dfs(left.left,right.right)&&dfs(left.right,right.left); }

找到中点递归的进行左子树和右子树的构建就行
public TreeNode sortedArrayToBST(int[] nums) { return
helper(nums,0,nums.length-1); } private TreeNode helper(int[] nums, int left,
int right) { if(left>right)return null; int mid=(left+right)>>1; TreeNode node
= new TreeNode(nums[mid]); node.left=helper(nums,left,mid-1);
node.right=helper(nums,mid+1,right); return node; }

由于是有序链表,其中点可以作为二叉搜索树的节点,使用快慢指针法求出链表的中点

!= null){ pre = slow; slow = slow.next; fast = fast.next.next; } //right指向中点的后继
ListNode right = slow.next; //断开链表(此题的核心) pre.next = null; TreeNode root = new
TreeNode(slow.val); root.left = sortedListToBST(head);//构建左树 root.right =
sortedListToBST(right);//构建右树 return root; }

public boolean isSameTree(TreeNode p, TreeNode q) { if (p == null && q ==
null) return true; else if (p == null || q == null) return false; if (p.val !=
q.val) return false; return isSameTree(p.right, q.right) && isSameTree(p.left,
q.left); }

//是否是合理的bst 由于bst要求所有的节点都比右子树的节点小,所以添加两个节点min和max用于比较 boolean
isValidBST(TreeNode node) { return isValidBST(node, null, null); } boolean
isValidBST(TreeNode node, TreeNode min, TreeNode max) { if (node == null)
return true; if (min != null && node.val <= min.val) return false; if (max !=
null && node.val >= max.val) return false; //比较左边的节点是否比当前最小节点要小并且比最小节点要大 return
isValidBST(node.left, min, node) && isValidBST(node.right, node, max); }

//通过BST查找一个数是否存在 boolean isInBST(TreeNode root, int target) { if (root ==
null) return false; if (root.val == target) return true; if (root.val > target)
return isInBST(root.left, target); else return isInBST(root.right, target); }

//通过BST插入一个数 TreeNode insertIntoBST(TreeNode root, int val) { if (root ==
null) return new TreeNode(val);//找到空位置插入新的节点 //BST中一般不会插入已经存在的元素 if (root.val <
val) root.right = insertIntoBST(root.right, val); if (root.val > val) root.left
= insertIntoBST(root.left, val); return root; }

* 删除一个二叉搜索树节点有三种情况:如果该节点
* 两个子节点都为空或者只有一个子节点:直接使用这个子节点来代替自己的位置
* 如果当前节点有左子树和右子树:需要找到最大的左子树或者最小的右子树来代替自己的位置

//在BST删除一个数 TreeNode deleteNode(TreeNode root, int key) { if (root == null)
return null; if (root.val == key) { //恰好是末端节点,两个子节点都为空,直接删除该节点

(root.right == null) return root.left; //如果当前节点有左子树和右子树 TreeNode
minNode=getMin(root.right); root.val=minNode.val;//交换节点 //删除已经替换掉值的节点
root.right=deleteNode(root.right,minNode.val); }else
if(root.val>key)root.left=deleteNode(root.left,key); else
root.right=deleteNode(root.right,key); return root; }
//获得左子树中最大的那个节点或者右子树最小的那个节点来代替自己(这里使用右子树最小的那个节点) TreeNode getMin(TreeNode
node){ while (node.left!=null) node=node.left; return node; }

List<TreeNode> res; public void recoverTree(TreeNode root) { res=new
ArrayList<>(); helper(root); TreeNode x=null; TreeNode y=null;
//扫描遍历的结果,找出可能存在错误节点交换的节点x和y for (int i = 0; i < res.size() - 1; i++) {
if(res.get(i).val>res.get(i+1).val){ y=res.get(i+1);//找到最后一个不满足升序的节点
if(x==null){ x=res.get(i);//锁定第一个不满足升序的节点 } } } //如果xy不为空交换两个节点值
if(x!=null&&y!=null){ int temp=x.val; x.val=y.val; y.val=temp; } } private void
helper(TreeNode root) { if(root==null)return; helper(root.left); res.add(root);
helper(root.right); }