31.给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
输入: word1 = "horse", word2 = "ros"
输出: 3
解释:
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
package wg;
public class Solution {
public static int minthree(int a,int b,int c){
return Math.min(Math.min(a,b),c);
}
public static int minDistance(String s1,String s2){
int m = s1.length();
int n = s2.length();
int[][] dp = new int[m+1][n+1];
for(int i=1;i<=m;i++){
dp[i][0]=i;
}
for(int j=1;j<=n;j++){
dp[0][j]=j;
}
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(s1.charAt(i-1)==s2.charAt(j-1))
dp[i][j]=dp[i-1][j-1];
else{
//分别对应 插入 删除 替换
dp[i][j]=minthree(dp[i][j-1]+1,dp[i-1][j]+1,dp[i-1][j-1]+1);
}
}
}
return dp[m][n];
}
public static void main(String[] args) {
System.out.println(minDistance("horse","ros"));
//3
}
}
32.给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
注意:
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
不能使用代码库中的排序函数来解决这道题。
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
用三个指针（
p0,p2和curr）来分别追踪0的最右边界，2的最左边界和当前考虑的元素。沿着数组移动curr指针，若nums[curr] = 0，则将其与nums[p0]互换；若nums[curr] = 2，则与nums[p2]互换。
算法
1.初始化0的最右边界：p0 = 0。在整个算法执行过程中 nums[idx < p0] = 0.
2.初始化2的最左边界 ：p2 = n - 1。在整个算法执行过程中 nums[idx > p2] = 2.
3.初始化当前考虑的元素序号 ：curr = 0.
4.While curr <= p2 :
5.若 nums[curr] = 0 ：交换第 curr个 和 第p0个 元素，并将指针**都**向右移。
6.若 nums[curr] = 2 ：交换第 curr个和第 p2个元素，并将 p2指针左移 。
7.若 nums[curr] = 1 ：将指针curr右移。
package wg;
import java.util.Arrays;
public class Solution {
public static void sortColors(int[] nums) {
// 对于所有 idx < i : nums[idx < i] = 0
// j是当前考虑元素的下标
int p0 = 0, curr = 0;
// 对于所有 idx > k : nums[idx > k] = 2
int p2 = nums.length - 1;
int tmp;
while (curr <= p2) {
if (nums[curr] == 0) {
// 交换第 p0个和第curr个元素
// i++，j++
tmp = nums[p0];
nums[p0++] = nums[curr];
nums[curr++] = tmp;
}
else if (nums[curr] == 2) {
// 交换第k个和第curr个元素
// p2--
tmp = nums[curr];
nums[curr] = nums[p2];
nums[p2--] = tmp;
}
else curr++;
}
}
public static void main(String[] args) {
int[] nums = {2,0,2,1,1,0};
sortColors(nums);
System.out.println(Arrays.toString(nums));
//[0, 0, 1, 1, 2, 2]
}
}
33.给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。
输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
package wg;
public class Solution {
public static String minWindow(String s, String t) {
int m=s.length(),n=t.length();
if(m<n){
return "";
}
//转化成数组，提升查找速度
char[] S=s.toCharArray();
char[] T=t.toCharArray();
int[] map=new int[256];//利用ASSII码做映射，比hashmap效率高
for(int i=0;i<n;i++){
map[T[i]]++;
}
int start=-1;
int L=0,R=0;//滑动窗口[L,R]
int count=0;//保存窗口里已经找到了多少个字符
int min=m+1;
//左边不能越过m-n 不然字符串短于查找的 右边不能越过m
while(L<=m-n&&R<m){
//找到一个T中的
map[S[R]]--;
//减减过后>=0 说明开始这个位置有加加 说明T中有这个字母
if(map[S[R]]>=0){
count++;
}
//当找到总字符等于T的长度时
if(count==n){
//L左移一个相当于取消一个字符 不能=是因为里面会进行L++
//当遇到map[S[L]]>=0时，说明这个字符是T中的，因为不是T中的不会一开始的判断就是>=0，都是负数，前面减的 首先明确map[S[L]]肯定是前面map[S[R]]操作过的数
while(map[S[L]]<0){//L尽量往左移动
map[S[L]]++;
L++;
}
//取消字符后是否需要更新结果
if(R-L<min){//记录位置
min=R-L;//因为L位于的位置是刚好在T中的字符
//比如s= abcde t=cd; L位于2 R位于3 3-2=1；所以结果在return要+1
start=L;
}
map[S[L]]++;//L继续右移一位，且此时S[L]是需要的那个字符（在T中）进行下次寻找
L++;
count--;
}
R++;
}
if(min<m+1){
return s.substring(start,start+min+1);
}
return "";
}
public static void main(String[] args) {
System.out.println(minWindow("aasdfghj","gfd"));
//dfg
}
}
34.给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
回溯算法:每个数都可以选择放或者不放
package wg;
import java.util.*;
public class Solution {
private static List<List<Integer>> res = new ArrayList<>();
public static List<List<Integer>> subsets(int[] nums) {
List<Integer> list = new ArrayList<>();
res.add(list);//先把空放进去
if(nums==null||nums.length==0){
return res;
}
numsziji(0,nums,list);
return res;
}
public static void numsziji(int start, int[] nums, List<Integer> list){
if(start>=nums.length){
return;
}
//选择放
list.add(nums[start]);
res.add(new ArrayList<>(list));//注意这里
numsziji(start+1,nums,list);
//选择不妨
list.remove(list.size()-1);
numsziji(start+1,nums,list);
}
public static void main(String[] args) {
int[] nums = {1,2,3};
List<List<Integer>> result = new ArrayList<>();
result=subsets(nums);
System.out.println(result);
//[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
}
}
35.给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.
在二维平面上使用回溯法 DFS+状态置换
package wg;
public class Solution {
private boolean[][] marked;
// x-1,y
// x,y-1 x,y x,y+1
// x+1,y
private int[][] direction = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
// 盘面上有多少行
private int m;
// 盘面上有多少列
private int n;
private String word;
private char[][] board;
public boolean exist(char[][] board, String word) {
m = board.length;
if (m == 0) {
return false;
}
n = board[0].length;
marked = new boolean[m][n];
this.word = word;
this.board = board;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (dfs(i, j, 0)) {
return true;
}
}
}
return false;
}
private boolean dfs(int i, int j, int start) {
if (start == word.length() - 1) {
//返回最后一位是否相等
return board[i][j] == word.charAt(start);
}
if (board[i][j] == word.charAt(start)) {
marked[i][j] = true;
for (int k = 0; k < 4; k++) {
int newX = i + direction[k][0];
int newY = j + direction[k][1];
if (inArea(newX, newY) && !marked[newX][newY]) {
if (dfs(newX, newY, start + 1)) {
return true;
}
}
}
marked[i][j] = false;
}
return false;
}
private boolean inArea(int x, int y) {
return x >= 0 && x < m && y >= 0 && y < n;
}
public static void main(String[] args) {
char[][] board =
{
{'A', 'B', 'C', 'E'},
{'S', 'F', 'C', 'S'},
{'A', 'D', 'E', 'E'}
};
String word = "ABCCED";
Solution solution = new Solution();
boolean exist = solution.exist(board, word);
System.out.println(exist);
}
}
36.给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
输入: [2,1,5,6,2,3]
输出: 10
我们维护一个栈。一开始，我们把
-1(有深意的请看代码) 放进栈的顶部来表示开始。初始化时，按照从左到右的顺序，我们不断将柱子的序号放进栈中，直到遇到相邻柱子呈下降关系，也就是a[i−1]>a[i]。现在，我们开始将栈中的序号弹出，直到遇到stack.peek()满足a[stack.peek()] <a[i]。每次我们弹出序号时，我们用弹出序号在数组中表示的值作为最大面积高,宽是当前走到的序号与stack[top-1],从栈顶开始数的第二个之间的那些柱子。也就是当我们弹出stack[top]时，记当前走到的元素在原数组中的下标为 i ，当前弹出元素为高的最大矩形面积为：
(i-stack[top-1]-1) *height[stack[top]]
更进一步，当我们到达数组的尾部时，我们将栈中剩余元素全部弹出栈。
此时每个元素代表的高度都成递增的每弹出每一个元素，我们用下面的式子来求面积：(height.length-stack[top-1]-1) *height[stack[top]]，其中，stack[top]表示刚刚被弹出的元素知道遇到弹出的元素为-1停止。因此，我们可以通过每次比较新计算的矩形面积来获得最大的矩形面积
package wg;
import java.util.Stack;
public class Solution {
public int largestRectangleArea(int[] heights){
Stack<Integer> stack = new Stack<>();
stack.push(-1);
//这个-1有深意的 被当作+1用的 因为数组下标从0开始 7和5之间的举例是6的宽度 所以是7-5-1 但是2和0之间的举例是0 1 如果是 2-0-1就成了1 所以-1当作+1
int len = heights.length;
int area = 0;
for(int i=0;i<len;i++){
//满足弹栈的要求
while(stack.peek()!=-1&&heights[stack.peek()]>=heights[i]){
area = Math.max(area,heights[stack.pop()]*(i-stack.peek()-1));
}
stack.push(i);
}
while (stack.peek()!=-1){
area=Math.max(area,heights[stack.pop()]*(len-stack.peek()-1));
}
return area;
}
public static void main(String[] args) {
Solution solution = new Solution();
System.out.println(solution.largestRectangleArea(new int[]{2,1,5,6,2,3}));
//10
}
}
37.给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
输入:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
输出: 6
化成橙色部分，完全是上一题
注意求高度的时候，以每一行为基准，找到这个每一行的最大高度，如果是以0为底，则为0，有0就可以断了。
package wg;
import java.util.Stack;
public class Solution {
public int largestRectangleArea(int[] heights){
Stack<Integer> stack = new Stack<>();
stack.push(-1);
//这个-1有深意的 被当作+1用的 因为数组下标从0开始 7和5之间的举例是6的宽度 所以是7-5-1 但是2和0之间的举例是0 1 如果是 2-0-1就成了1 所以-1当作+1
int len = heights.length;
int area = 0;
for(int i=0;i<len;i++){
//满足弹栈的要求
while(stack.peek()!=-1&&heights[stack.peek()]>=heights[i]){
area = Math.max(area,heights[stack.pop()]*(i-stack.peek()-1));
}
stack.push(i);
}
while (stack.peek()!=-1){
area=Math.max(area,heights[stack.pop()]*(len-stack.peek()-1));
}
return area;
}
public int maximalRectangle(char[][] matrix) {
int m = matrix.length;
if(m==0)
return 0;
int n = matrix[0].length;
int[] heights = new int[n];//整数类型数组的默认值为0
int res = 0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(matrix[i][j]=='1'){
heights[j]+=1;
}else{
heights[j]=0;
}
}
res = Math.max(res,largestRectangleArea(heights));
}
return res;
}
public static void main(String[] args) {
Solution solution = new Solution();
System.out.println(solution.maximalRectangle(new char[][]{{'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'},{'1','0','0','1','0'}}));
//6
}
}
38.给定一个二叉树，返回它的中序 遍历。
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,3,2]
递归遍历就不说了。
基于栈的中序遍历
//递归
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
TreeNode(){}
}
private List<Integer> res = new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
if(root==null){
return res;
}
else{
helper(root,res);
}
return res;
}
public void helper(TreeNode treeNode,List<Integer> list){
if(treeNode!=null){
if(treeNode.left!=null){
helper(treeNode.left,list);
}
list.add(treeNode.val);
if(treeNode.right!=null){
helper(treeNode.right,list);
}
}
}
基于栈的中序遍历
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
if (cur != null) {
stack.push(cur);
cur = cur.left;
} else {
cur = stack.pop();
list.add(cur.val);
cur = cur.right;
}
}
return list;
}
39.给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
动态规划
假设n个节点存在二叉排序树的个数是G(n)，令f(i)为以i为根的二叉搜索树的个数
即有:G(n) = f(1) + f(2) + f(3) + f(4) + ... + f(n)
n为节点总数，当i为根节点时，其左子树节点个数为[1,2,3,...,i-1]，右子树节点个数为[i+1,i+2,...n]，所以当i为根节点时，其左子树节点个数为i-1个，右子树节点为n-i，即f(i) = G(i-1)*G(n-i),
上面两式可得:G(n) = G(0)*G(n-1)+G(1)*(n-2)+...+G(n-1)*G(0)
public static int numTrees(int n) {
int[] dp = new int[n+2];//这里注意了 +2防止dp[2]=2;越界
dp[0]=1;//这里注意了
dp[1]=1;
dp[2]=2;
for(int i=3;i<=n;i++){
for(int j=1;j<=i;j++){
dp[i]+=dp[j-1]*dp[i-j];
}
}
return dp[n];
}
40.给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
输入:
5
/ \
1 4
/ \
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。
中序遍历二叉树，遍历结果如果按照从小到大的顺序排列，则表明是二叉搜索树，否则不是二叉搜索树。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private double small = - Double.MAX_VALUE;//这样子更小 int 会出错
public boolean isValidBST(TreeNode root) {
Stack<TreeNode> stack = new Stack();
while (!stack.isEmpty() || root != null) {
while (root != null) {
stack.push(root);//栈是先进后出哦
root = root.left;
}
//此时已经到达最最最左边的节点
root = stack.pop();
if (root.val <= small) return false;
small = root.val;
root = root.right;//再换右边
}
return true;
}
}
