043、复习Day01

力扣：

剑指 Offer 19. 正则表达式匹配

剑指 Offer 19. 正则表达式匹配： 感觉还挺难的，又是一个动态规划的问题；
动态规划问题重点，就是找到基于A条件下，发生选择后，到达了什么样子的新的状态。

思路：

• 将给定的字符串记为s，字符规律串为p；
• s 的下标从 0 到 i ，p 的下标从 0 到 j ；
• 记录一个动态规划的dp数组，为dp[i][j]，意思是字符串s从0到下标i能否被p从0到下表j处进行匹配成功；
• 如果想要知道dp[i][j]，就需要去比较s的i位置和p的j位置字符的关系；

两种关系：

s的i位置和p的j位置关系只有两种，是不是’*'；

• 不是，就只需要判断是不是’.'了，这种比较简单；
• 是，又有两种情况；
  • 不需要使用 j-1 位置的字符；
  • 需要使用 j-1 位置的字符

class Solution {public boolean isMatch(String s, String p) {int m = s.length();int n = p.length();// dp数组boolean[][] dp = new boolean[m+1][n+1];// base casedp[0][0] = true;// traversefor(int i = 0; i <= m; i++){for(int j = 1; j<=n ; j++){// 判断 j 位置字符if(p.charAt(j - 1) == '*'){// 不使用当前位置p字符串的前一个字符dp[i][j] = dp[i][j - 2];// 使用前一个字符if(match(s , i , p ,j - 1)){dp[i][j] = dp[i][j] || dp[i -1][j];}}else{if(match(s , i , p , j)){dp[i][j] = dp[i - 1][j - 1];}}}}// returnreturn dp[m][n];}// 判断字符串 s 位置i 和 p 位置 j 的字符关系boolean match(String s, int i, String p, int j){if(i == 0){return false;}if(p.charAt(j - 1) == '.'){return true;}return s.charAt(i - 1) == p.charAt(j - 1);}
}

剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

剑指 Offer 21. 调整数组顺序使奇数位于偶数前面;

思路：

• 这个题目比较简单，我直接用的双指针做的，在原来数组上进行交换元素位置；

class Solution {public int[] exchange(int[] nums) {// 使用双指针吗？int length = nums.length;int left = 0 , right = length - 1;while(left < right){while(left < length && nums[left] % 2 != 0){left++;}while(right >=0 && nums[right] % 2 ==0){right--;}if(left < right){swap(nums, left, right);}}return nums;}// 交换void swap(int[] nums , int  i , int j){int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}
}

剑指 Offer 26. 树的子结构

剑指 Offer 26. 树的子结构；

思路：

• 逐个遍历A节点，看是否能找到以A树上任意一个节点为头节点和B树结构保持一致；
• 需要一个函数，判断两棵树结构是否完全一致；

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {// 判断二叉树B是不是二叉树A的子结构；public boolean isSubStructure(TreeNode A, TreeNode B) {// base casereturn (A != null && B!=null ) && (isSame(A,B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));}// 判断头节点为A 和头节点为B的两棵二叉树是不是同一颗二叉树boolean isSame(TreeNode A, TreeNode B){// base caseif(B == null){// 只有当全部遍历完B后，证明在A树上可以找到B结构作为紫薯return true;}// 如果A为空，或者A节点和B节点值不同if(A == null || A.val != B.val){return false;}return isSame(A.left, B.left) && isSame(A.right, B.right);}
}

剑指 Offer 27. 二叉树的镜像

剑指 Offer 27. 二叉树的镜像；

思路：

• 二叉树的回溯；

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {public TreeNode mirrorTree(TreeNode root) {if(root == null ||(root.left == null && root.right == null)){return root;}TreeNode left = mirrorTree(root.left);TreeNode right = mirrorTree(root.right);root.left = right;root.right = left;return root;}
}