71.10. 正则表达式匹配 - 力扣（LeetCode）

动态规划

题解：10. 正则表达式匹配题解 - 力扣（LeetCode）

72.5. 最长回文子串 - 力扣（LeetCode）

动态规划

1.dp数组及下标含义

dp[i][j] : 下标i到下标j的子串是否是回文串

2.递推方程

dp[i][j] = dp[i+1][j-1] && s.charAt(i) == s.charAt(j)

3.初始化

对于单个字母,dp[i][i] = true;

对于两个字母的子串，如果两个字母相同，dp[i][i+1] = true;

4.递推顺序

5.dp数组举例说明

public String longestPalindrome(String s) {if(s.length() < 2){return s;}boolean[][] dp = new boolean[s.length()][s.length()];for(int i = 0 ; i < s.length() ; i++){dp[i][i] = true;}int maxlen = 0,start = 0;for(int len = 2 ; len <= s.length() ; len++){for(int i = 0 ; i < s.length() - len + 1 ; i++){int j = i + len - 1;if(s.charAt(i) != s.charAt(j)){dp[i][j] = false;}else{if(j - i < 3){dp[i][j] = true;}else{dp[i][j] = dp[i+1][j-1];}}if(dp[i][j] && j - i + 1 > maxlen){maxlen = j - i + 1;start = i;}}}return s.substring(start,start +maxlen);}

方法二类似于使用滚动数组优化动态规划的空间复杂度的本质，只使用上一个状态，不必保留所有状态。

枚举出所有的中心，即可得到所有可能的回文子串（必由某一中心扩展而来）

class Solution {public String longestPalindrome(String s) {if (s == null || s.length() < 1) {return "";}int start = 0, end = 0;for (int i = 0; i < s.length(); i++) {int len1 = expandAroundCenter(s, i, i);int len2 = expandAroundCenter(s, i, i + 1);int len = Math.max(len1, len2);if (len > end - start) {start = i - (len - 1) / 2;end = i + len / 2;}}return s.substring(start, end + 1);}public int expandAroundCenter(String s, int left, int right) {while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {--left;++right;}return right - left - 1;}
}

73.

74.3. 无重复字符的最长子串 - 力扣（LeetCode）

滑动窗口

public int lengthOfLongestSubstring(String s) {int l = 0 , r = 0 , ans = 0 ;Set<Character> set = new HashSet<>();for(; r < s.length() ;r++){while(set.contains(s.charAt(r))){set.remove(s.charAt(l));l++;}set.add(s.charAt(r));int len = r - l + 1;ans = Math.max(ans,len);}return ans;}

滑动窗口题目汇总：3. 无重复字符的最长子串题解 - 力扣（LeetCode）

75.2. 两数相加 - 力扣（LeetCode）

链表，进位边界情况的处理分析

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {int carry = 0;ListNode head = new ListNode(-1);ListNode p = head;ListNode p1 = l1 , p2 = l2;while(p1 != null && p2 != null){int value = p1.val + p2.val + carry;carry = value/10;p.next = new ListNode(value % 10);p = p.next;p1 = p1.next;p2 = p2.next;}while(p1 != null){int value = p1.val + carry;carry = value/10;p.next = new ListNode(value % 10);p = p.next;p1 = p1.next;}while(p2 != null){int value = p2.val + carry;carry = value/10;p.next = new ListNode(value % 10);p = p.next;p2 = p2.next;}if(carry != 0){p.next = new ListNode(carry);}return head.next;}

时间复杂度O(m+n)

空间复杂度O(m+n)

76.79. 单词搜索 - 力扣（LeetCode）

回溯，dfs

int[][] directions = new int[][]{{1,0},{0,1},{-1,0},{0,-1}};boolean res = false;char[][] board;StringBuilder path = new StringBuilder();String word;boolean[][] isVisited;public boolean exist(char[][] board, String word) {this.board = board;this.word = word;isVisited = new boolean[board.length][board[0].length];char head = word.charAt(0);for(int i = 0 ; i < board.length ; i++){for(int j = 0 ; j < board[0].length ; j++){if(board[i][j] == head){isVisited[i][j] = true;path.append(board[i][j]);dfs(i,j,0);path.deleteCharAt(path.length() - 1);isVisited[i][j] = false;}if(res){return res;}}}return res;}public void dfs(int x , int y , int index){if(word.charAt(index) != path.charAt(path.length() - 1)){//剪枝，减去board[x][y]与word对应字符不匹配的搜索return ;}if(path.toString().equals(word)){res = true;//剪枝，减去找到正确答案以后得搜索return;}for(int i = 0 ; i < 4 ; i++){int newX = x + directions[i][0];int newY = y + directions[i][1];if(newX < 0 || newX >= board.length || newY < 0 || newY >= board[0].length || isVisited[newX][newY]){continue;}isVisited[newX][newY] = true;path.append(board[newX][newY]);dfs(newX,newY,path.length() - 1);path.deleteCharAt(path.length() - 1);isVisited[newX][newY] = false;}}

77.114. 二叉树展开为链表 - 力扣（LeetCode）

I创建一个新的链表，dfs，然后修改树

ListNode head;ListNode list;public void flatten(TreeNode root) {if(root == null) return;head = new ListNode(0);list = head;dfs(root);list = head.next.next;root.left = null;TreeNode node = root;while(list != null){node.right = new TreeNode(list.val);node = node.right;list = list.next;}}public void dfs(TreeNode root){list.next = new ListNode(root.val);list = list.next;if(root.left != null){dfs(root.left);}if(root.right != null){dfs(root.right);}}

II 根据先序遍历中左右的顺序，分析插入的顺序，进行模拟

1. 将左子树插入到右子树的地方
2. 将原来的右子树接到左子树的最右边节点
3. 考虑新的右子树的根节点，一直重复上边的过程，直到新的右子树为 null

    1/ \2   5/ \   \
3   4   6//将 1 的左子树插入到右子树的地方1\2         5/ \         \3   4         6        
//将原来的右子树接到左子树的最右边节点1\2          / \          3   4  \5\6//将 2 的左子树插入到右子树的地方1\2          \          3       4  \5\6   //将原来的右子树接到左子树的最右边节点1\2          \          3      \4  \5\6         ......

public void flatten(TreeNode root) {while(root != null){if(root.left == null){root = root.right;}else{TreeNode pre = root.left;while(pre.right != null){pre = pre.right;}pre.right = root.right;root.right = root.left;root.left = null;root = root.right;}}}

III原地修改

容易想到的方法是在先序遍历的过程中，把当前遍历的结点改成上一结点的右结点就能满足题目要求，但会发现原来还没有访问的右结点丢失了。那么可以想到如果先访问结点，再修改，就能避免修改造成的影响，只要按照右、左、中的顺序进行遍历，即后序遍历，将当前节点的右结点改成上一次访问的结点，即能满足题目要求，并且把左结点置为null，而左结点已经放问过了，不会有影响。

TreeNode pre;public void flatten(TreeNode root) {if(root == null) return;postOrder(root);}public void postOrder(TreeNode root){if(root.right != null){postOrder(root.right);}if(root.left != null){postOrder(root.left);}root.right = pre;root.left = null;pre = root;}

78.621. 任务调度器 - 力扣（LeetCode）

模拟 贪心

贪心：每次选择待执行次数最多的任务

class Solution {public int leastInterval(char[] tasks, int n) {Map<Character, Integer> freq = new HashMap<Character, Integer>();for (char ch : tasks) {freq.put(ch, freq.getOrDefault(ch, 0) + 1);}// 任务种类数int m = freq.size();List<Integer> nextValid = new ArrayList<Integer>();List<Integer> rest = new ArrayList<Integer>();Set<Map.Entry<Character, Integer>> entrySet = freq.entrySet();for (Map.Entry<Character, Integer> entry : entrySet) {int value = entry.getValue();nextValid.add(1);rest.add(value);}int time = 0;for (int i = 0; i < tasks.length; ++i) {++time;int minNextValid = Integer.MAX_VALUE;for (int j = 0; j < m; ++j) {if (rest.get(j) != 0) {minNextValid = Math.min(minNextValid, nextValid.get(j));}}time = Math.max(time, minNextValid);int best = -1;for (int j = 0; j < m; ++j) {if (rest.get(j) != 0 && nextValid.get(j) <= time) {if (best == -1 || rest.get(j) > rest.get(best)) {best = j;}}}nextValid.set(best, time + n + 1);rest.set(best, rest.get(best) - 1);}return time;}
}

另一种贪心策略：

 public int leastInterval(char[] tasks, int n) {//统计每个任务出现的次数，找到出现次数最多的任务int[] hash = new int[26];for(int i = 0; i < tasks.length; ++i) {hash[tasks[i] - 'A'] += 1;}Arrays.sort(hash);//因为相同元素必须有n个冷却时间，假设A出现3次，n = 2，任务要执行完，至少形成AXX AXX A序列（X看作预占位置）//该序列长度为int minLen = (n+1) *  (hash[25] - 1) + 1;//此时为了尽量利用X所预占的空间（贪心）使得整个执行序列长度尽量小，将剩余任务往X预占的空间插入//剩余的任务次数有两种情况：//1.与A出现次数相同，比如B任务最优插入结果是ABX ABX AB，中间还剩两个空位，当前序列长度+1//2.比A出现次数少，若还有X，则按序插入X位置，比如C出现两次，形成ABC ABC AB的序列//直到X预占位置还没插满，剩余元素逐个放入X位置就满足冷却时间至少为nfor(int i = 24; i >= 0; --i){if(hash[i] == hash[25]) ++ minLen;}//当所有X预占的位置插满了怎么办？//在任意插满区间（这里是ABC）后面按序插入剩余元素，比如ABCD ABCD发现D之间距离至少为n+1，肯定满足冷却条件//因此，当X预占位置能插满时，最短序列长度就是task.length，不能插满则取最少预占序列长度return Math.max(minLen, tasks.length);}

79.617. 合并二叉树 - 力扣（LeetCode）

递归

1.确定递归函数参数和返回值

参数：两个树的根节点

返回值：合并后树的根节点

2.终止条件

因为是传入了两个树，那么就有两个树遍历的节点t1 和 t2，如果t1 == NULL 了，两个树合并就应该是 t2 了（如果t2也为NULL也无所谓，合并之后就是NULL）。

反过来如果t2 == NULL，那么两个数合并就是t1（如果t1也为NULL也无所谓，合并之后就是NULL）。

3.确定单层逻辑

重复利用一下t1这个树，t1就是合并之后树的根节点（就是修改了原来树的结构）。

那么单层递归中，就要把两棵树的元素加到一起。

t1.val += t2.val;

接下来t1 的左子树是：合并 t1左子树 t2左子树之后的左子树。

t1 的右子树：是 合并 t1右子树 t2右子树之后的右子树。

最终t1就是合并之后的根节点。

public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if(root1 == null) return root2;if(root2 == null) return root1;root1.val += root2.val;root1.left = mergeTrees(root1.left,root2.left);root1.right = mergeTrees(root1.right,root2.right);return root1;}

80.105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）

首先回忆一下如何根据两个顺序构造一个唯一的二叉树，相信理论知识大家应该都清楚，就是以 后序数组的最后一个元素为切割点，先切中序数组，根据中序数组，反过来再切后序数组。一层一层切下去，每次后序数组最后一个元素就是节点元素。

如果让我们肉眼看两个序列，画一棵二叉树的话，应该分分钟都可以画出来。

流程如图：

那么代码应该怎么写呢？

说到一层一层切割，就应该想到了递归。

来看一下一共分几步：

• 第一步：如果数组大小为零的话，说明是空节点了。

• 第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。

• 第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点

• 第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）

• 第五步：切割后序数组，切成后序左数组和后序右数组

• 第六步：递归处理左区间和右区间

不难写出如下代码：（先把框架写出来）

TreeNode* traversal (vector<int>& inorder, vector<int>& postorder) {// 第一步if (postorder.size() == 0) return NULL;// 第二步：后序遍历数组最后一个元素，就是当前的中间节点int rootValue = postorder[postorder.size() - 1];TreeNode* root = new TreeNode(rootValue);// 叶子节点if (postorder.size() == 1) return root;// 第三步：找切割点int delimiterIndex;for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {if (inorder[delimiterIndex] == rootValue) break;}// 第四步：切割中序数组，得到 中序左数组和中序右数组// 第五步：切割后序数组，得到 后序左数组和后序右数组// 第六步root->left = traversal(中序左数组, 后序左数组);root->right = traversal(中序右数组, 后序右数组);return root;
}

难点大家应该发现了，就是如何切割，以及边界值找不好很容易乱套。

此时应该注意确定切割的标准，是左闭右开，还有左开右闭，还是左闭右闭，这个就是不变量，要在递归中保持这个不变量。

首先要切割中序数组，为什么先切割中序数组呢？

切割点在后序数组的最后一个元素，就是用这个元素来切割中序数组的，所以必要先切割中序数组。

中序数组相对比较好切，找到切割点（后序数组的最后一个元素）在中序数组的位置，然后切割，如下代码中我坚持左闭右开的原则：

// 找到中序遍历的切割点
int delimiterIndex;
for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {if (inorder[delimiterIndex] == rootValue) break;
}// 左闭右开区间：[0, delimiterIndex)
vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
// [delimiterIndex + 1, end)
vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end() );

接下来就要切割后序数组了。

首先后序数组的最后一个元素指定不能要了，这是切割点 也是 当前二叉树中间节点的元素，已经用了。

后序数组的切割点怎么找？

后序数组没有明确的切割元素来进行左右切割，不像中序数组有明确的切割点，切割点左右分开就可以了。

此时有一个很重的点，就是中序数组大小一定是和后序数组的大小相同的（这是必然）。

中序数组我们都切成了左中序数组和右中序数组了，那么后序数组就可以按照左中序数组的大小来切割，切成左后序数组和右后序数组。

代码如下：

// postorder 舍弃末尾元素，因为这个元素就是中间节点，已经用过了
postorder.resize(postorder.size() - 1);// 左闭右开，注意这里使用了左中序数组大小作为切割点：[0, leftInorder.size)
vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
// [leftInorder.size(), end)
vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());

此时，中序数组切成了左中序数组和右中序数组，后序数组切割成左后序数组和右后序数组。

接下来可以递归了，代码如下：

root->left = traversal(leftInorder, leftPostorder);
root->right = traversal(rightInorder, rightPostorder);

完整代码如下：

class Solution {Map<Integer, Integer> map;  // 方便根据数值查找位置public TreeNode buildTree(int[] inorder, int[] postorder) {map = new HashMap<>();for (int i = 0; i < inorder.length; i++) { // 用map保存中序序列的数值对应位置map.put(inorder[i], i);}return findNode(inorder,  0, inorder.length, postorder,0, postorder.length);  // 前闭后开}public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) {// 参数里的范围都是前闭后开if (inBegin >= inEnd || postBegin >= postEnd) {  // 不满足左闭右开，说明没有元素，返回空树return null;}int rootIndex = map.get(postorder[postEnd - 1]);  // 找到后序遍历的最后一个元素在中序遍历中的位置TreeNode root = new TreeNode(inorder[rootIndex]);  // 构造结点int lenOfLeft = rootIndex - inBegin;  // 保存中序左子树个数，用来确定后序数列的个数root.left = findNode(inorder, inBegin, rootIndex,postorder, postBegin, postBegin + lenOfLeft);root.right = findNode(inorder, rootIndex + 1, inEnd,postorder, postBegin + lenOfLeft, postEnd - 1);return root;}
}

前序和中序遍历的解决方法 和 上面讲解的中序和后序的解决方法思想一样。

Map<Integer,Integer> map = new HashMap<>();int[] preorder;int[] inorder;public TreeNode buildTree(int[] preorder, int[] inorder) {this.preorder = preorder;this.inorder = inorder;for(int i = 0 ; i < inorder.length ; i++){map.put(inorder[i],i);}return findNode(0,preorder.length,0,inorder.length);}public TreeNode findNode(int preBegin,int preEnd,int inBegin,int inEnd){if(preBegin >= preEnd || inBegin >= inEnd){return null;}int index = map.get(preorder[preBegin]);int lenOfLeft = index - inBegin;TreeNode node = new TreeNode(preorder[preBegin]);node.left = findNode(preBegin + 1, preBegin + lenOfLeft + 1,inBegin,index);node.right = findNode(preBegin + lenOfLeft + 1, preEnd,index + 1, inEnd);return node;}