练习地址

46、用两个栈实现队列

左神算法课–算法 链表结构、栈、队列、递归行为、哈希表

import java.util.Stack;public class Solution {Stack<Integer> stack1 = new Stack<Integer>();//pushStack<Integer> stack2 = new Stack<Integer>();//poppublic void push(int node) {stack1.add(node);pushToPop();}public int pop() {pushToPop();return stack2.pop();}private void pushToPop() {if (stack2.isEmpty()) {while (!stack1.isEmpty()) {stack2.add(stack1.pop());}}}
}

47、包含min函数的栈

public class Solution {Stack<Integer> stack1 = new Stack<>(); //用于栈的push 与 popStack<Integer> stack2 = new Stack<>(); //min栈   public void push(int node) {stack1.push(node);if(stack2.isEmpty()||stack2.peek()>node){stack2.push(node);}else{stack2.push(stack2.peek());//保持两个栈长度一样，方便pop}}public void pop() {stack1.pop();stack2.pop();}public int top() {return stack1.peek();}public int min() {return stack2.peek();}
}

48、有效括号序列

public boolean isValid (String s) {// write code hereStack<Character> stack = new Stack<>();for (int i = 0; i < s.length(); i++) {//成对的放入，遇见左括号放入右括号if (s.charAt(i) == '(') stack.push(')');else if (s.charAt(i) == '[') stack.push(']');else if (s.charAt(i) == '{') stack.push('}');//结束条件：不匹配或者不是成对else if (stack.isEmpty() || stack.pop() != s.charAt(i)) return false;}//栈中是否还有元素return stack.isEmpty();
}

50、最小的K个数

import java.util.ArrayList;public class Solution {public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {quickSort(input, 0, input.length - 1, k);ArrayList<Integer> res = new ArrayList<Integer>();for(int i = 0; i < k; i++){res.add(input[i]);}return res;}private void quickSort(int[] input, int l, int r, int k){if(l >= r) return;int random = l + (int)(Math.random() * (r - l + 1));swap(input, random, r);int p = partion(input, l, r);if(p < k) quickSort(input, p + 1, r, k);//说明不够else if(p > k) quickSort(input, l, p - 1, k);//超了else return;}private int partion(int[] input, int l, int r){int target = input[r], left = l - 1;for(int i = l; i < r; i++){if(input[i] <= target){swap(input, ++left, i);}}swap(input, left + 1, r);return left + 1;}private void swap(int[] input, int a, int b){int temp = input[a];input[a] = input[b];input[b] = temp;}
}

51、寻找第K大

import java.util.*;public class Solution {public int findKth(int[] a, int n, int K) {// write code herereturn quickSort(a, 0, a.length - 1, a.length - K);}public int quickSort(int[] a, int l, int r, int index) {int i = l + (int) (Math.random() * (r - l + 1));swap(a, i, r);int q = partion(a, l, r);if (q == index) return a[q];else if (q < index) return quickSort(a, q + 1, r, index);else return quickSort(a, l, q  - 1, index);}public void swap(int[] a, int i, int j) {int temp = a[i];a[i] = a[j];a[j] = temp;}public int partion(int[] a, int l, int r) {int x = a[r];int left = l - 1;for (int i = l; i < r; i++) {if (a[i] <= x) {swap(a, ++left, i);}}swap(a, left + 1, r);return left + 1;}
}

52、数据流中的中位数

import java.util.*;
public class Solution {//小顶堆，元素数值都比大顶堆大private PriorityQueue<Integer> max = new PriorityQueue<>();//大顶堆，元素数值较小 private PriorityQueue<Integer> min = new PriorityQueue<>((o1, o2)->o2.compareTo(o1)); //维护两个堆，取两个堆顶部即与中位数相关public void Insert(Integer num) {//先加入较小部分min.offer(num);//将较小部分的最大值取出，送入到较大部分max.offer(min.poll());  //平衡两个堆的数量if(min.size() < max.size())  min.offer(max.poll());}public Double GetMedian() {//奇数个if(min.size() > max.size()) return (double)min.peek();else//偶数个return (double)(min.peek() + max.peek()) / 2; }}

53、表达式求值

1. 表达式转逆波兰表达式
2. 逆波兰表达式求值

import java.util.*;public class Solution {Map<String, Integer> priority = new HashMap<>();public int solve (String s) {// write code herepriority.put("+", 0);priority.put("-", 0);priority.put("*", 1);priority.put("(", 2);priority.put(")", 2);String[] change = change(s);//中缀变后缀return calculate(change);}public String[] change(String s) {Stack<String> resstack = new Stack<>();//逆波兰表达式栈Stack<String> opstack = new Stack<>();//运算符的临时栈boolean preNumFlag = false;String[] exp = s.split("");for (int i = 0; i < exp.length; i++) {if (isNum(exp[i])) {if (!preNumFlag) {resstack.add(exp[i]);} else {String join = resstack.pop() + exp[i];resstack.add(join);}preNumFlag = true;} else if ("(".equals(exp[i])) {preNumFlag = false;opstack.add(exp[i]);} else if (")".equals(exp[i])) {preNumFlag = false;while (!opstack.isEmpty() && !opstack.peek().equals("(")) {resstack.add(opstack.pop());}opstack.pop();} else {//+-*preNumFlag = false;// 当前运算符小于等于栈顶运算符 -> 栈顶运算符逐个弹入// 当前运算符大于栈顶运算符 -> 将当前运算符压入栈中while (!opstack.isEmpty() && priority.get(exp[i]) <= priority.get(opstack.peek()) && !opstack.peek().equals("(")) {resstack.add(opstack.pop());}opstack.add(exp[i]);}}while (!opstack.isEmpty()) {resstack.add(opstack.pop());}String[] res = new String[resstack.size()];for (int i = 0; i < resstack.size(); i++) {res[i] = resstack.get(i);}return res;//转成的后缀表达式}private boolean isNum(String s) {if ("+".equals(s) || "-".equals(s) || "*".equals(s) || "(".equals(s) || ")".equals(s)) {return false;}return true;}private int calculate(String[] list) {Stack<Integer> res = new Stack<>();for (int i = 0; i < list.length; i++) {String s = list[i];if ("+".equals(s)) {res.add(res.pop() + res.pop());} else if ("-".equals(s)) {res.add(-res.pop() + res.pop());} else if ("*".equals(s)) {res.add(res.pop() * res.pop());} else {res.add(Integer.parseInt(s));}}return res.pop();}
}

54、两数之和

import java.util.*;
public class Solution {public int[] twoSum (int[] numbers, int target) {int[] res = new int[0];//创建哈希表,两元组分别表示值、下标HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>(); //在哈希表中查找target-numbers[i]for(int i = 0; i < numbers.length; i++){int temp = target - numbers[i];//若是没找到，将此信息计入哈希表if(!hash.containsKey(temp)) hash.put(numbers[i], i);//否则返回两个下标+1else return new int[] {hash.get(temp) + 1, i + 1}; }return res;}
}

55、数组中出现次数超过一半的数字

import java.util.*;
public class Solution {public int MoreThanHalfNum_Solution(int [] array) {//哈希表统计每个数字出现的次数HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>(); //遍历数组for(int i = 0; i < array.length; i++){ //统计频率if(!mp.containsKey(array[i]))mp.put(array[i], 1);elsemp.put(array[i], mp.get(array[i]) + 1);//一旦有个数大于长度一半的情况即可返回if(mp.get(array[i]) > array.length / 2) return array[i];}return 0;}
}

56、数组中只出现一次的两个数字

import java.util.*;public class Solution {public int[] FindNumsAppearOnce (int[] array) {int eor = 0;for(int num : array){eor ^= num;}int a_b = 0;//找到最右边第一个不相等的1int rightOne = eor & (~eor + 1);for(int num : array){if((num & rightOne) == 0){a_b ^= num;}}int min = a_b < (a_b ^ eor) ? a_b : (a_b ^ eor);int max = min ^ eor;return new int[]{min, max};}
}

57、缺失的第一个正整数

import java.util.*;
public class Solution {public int minNumberDisappeared (int[] nums) {int n = nums.length;HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>(); //哈希表记录数组中出现的每个数字for(int i = 0; i < n; i++) mp.put(nums[i], 1);int res = 1;//从1开始找到哈希表中第一个没有出现的正整数while(mp.containsKey(res)) res++;return res;}
}

58、三数之和

1.先排序，便于后面去重

2.使用3个指针，i从第一个位置开始，left从i+1开始向后移动，right从数组末尾开始向前移动

3**.i去重，判断num[i] == num[i -1]

**left去重：判断num[left] == num[left + 1]

**right去重: 判断num[right] == num[right - 1]

过后再判断当前3个数之和， 大于0时，right向前移动，小于0时，left向后移动。知道三数之和为0，将num[i]，num[left]，num[right]加入到链表中，因为已经排序了，所以顺序就是从小到大的

import java.util.*;
public class Solution {public ArrayList<ArrayList<Integer>> threeSum(int[] num) {ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer>>();int n = num.length;//不够三元组if(n < 3) return res;//排序Arrays.sort(num); for(int i = 0; i < n - 2; i++){if(i != 0 && num[i] == num[i - 1])// i去重continue;//后续的收尾双指针int left = i + 1; int right = n - 1;//设置当前数的负值为目标int target = -num[i]; while(left < right){//双指针指向的二值相加为目标，则可以与num[i]组成0if(num[left] + num[right] == target){ArrayList<Integer> temp = new ArrayList<Integer>();temp.add(num[i]);temp.add(num[left]);temp.add(num[right]);res.add(temp);while (left < right && left < num.length - 1 && num[left] == num[left + 1])//left去重left++; while (left < right && right > 0  && num[right] == num[right - 1])//right去重right--; //双指针向中间收缩left++; right--;}//双指针指向的二值相加大于目标，右指针向左else if(num[left] + num[right] > target)right--;//双指针指向的二值相加小于目标，左指针向右else left++;}}return res;}
}

59、没有重复项数字的全排列

import java.util.*;public class Solution {ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();ArrayList<Integer> temp = new ArrayList<>();boolean[] used;public ArrayList<ArrayList<Integer>> permute(int[] num) {used = new boolean[num.length];Arrays.sort(num);//1、字典序dfs(num); //递归+回溯return res;}public void dfs(int[] num) {if (temp.size() == num.length) {res.add(new ArrayList<>(temp)); //6、临时数组长度到达原数组长度就是一种排列情况。新对象，需要temp会修改} for (int i = 0; i < num.length ; i++) {3、已经加入的元素不能再次加入了(对递归而言)if (used[i]) continue;//4、进入下一层递归前加入当前位置used[i] = true;temp.add(num[i]);dfs(num);//进入分枝，继续往后找//5、回溯 移除刚刚加入数组的元素，temp.remove(temp.size() - 1);used[i] = false;}}}

60、有重复项数字的全排列

import java.util.*;public class Solution {ArrayList<ArrayList<Integer>> res = new ArrayList<>();ArrayList<Integer> temp = new ArrayList<>();boolean[] used;public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {used = new boolean[num.length];Arrays.sort(num);dfs(num);return res;}public void dfs(int[] num) {if (temp.size() == num.length) {res.add(new ArrayList<Integer>(temp));return;}for (int i = 0; i < num.length; i++) {if (used[i]) continue;if (i > 0 && num[i] == num[i - 1] && !used[i - 1]) continue;used[i] = true;temp.add(num[i]);dfs(num);temp.remove(temp.size() - 1);used[i] = false;}}
}

61、岛屿数量

• step 1：优先判断空矩阵等情况。
• step 2：从上到下从左到右遍历矩阵每一个位置的元素，如果该元素值为1，统计岛屿数量。
• step 3：接着将该位置的1改为0，然后使用dfs判断四个方向是否为1，分别进入4个分支继续修改。

import java.util.*;public class Solution {/* 判断岛屿数量* @param grid char字符型二维数组* @return int整型*/public int solve (char[][] grid) {// write code hereint row = grid.length;if (row == 0) return 0; //空矩阵的情况int column = grid[0].length;//记录岛屿数int count = 0;for (int i = 0; i < row; i++) {for (int j = 0; j < column; j++) {if (grid[i][j] == '1') {//计数count++;//将与这个1相邻的所有1置为0dfs(grid, i, j, row, column);}}}return count;}private void dfs(char[][] grid, int i, int j, int row, int column) {if ( i < 0 || i >= row || j < 0 || j >= column //边界条件|| grid[i][j]  != '1' // 岛屿条件) return;grid[i][j] = 2;// 置为0//后续四个方向遍历dfs(grid, i - 1, j, row, column); //左边dfs(grid, i + 1, j, row, column); //右边dfs(grid, i, j - 1, row, column);  //上边dfs(grid, i, j + 1, row, column); //下边}
}

62、电影院座位推荐

抖音电影票业务支持电影院选座，需要在用户买票时自动推荐座位，如果一个用户买了多张票，则需要推荐相邻(上下相邻、左右相邻都可)的座位。现在使用一个二维数组来表示电影院的座位，数组中 0 表示未被选座，1 表示已被选座或者为障碍物，请实现一个方法求出给定影院中最大可推荐的相邻座位个数。

示例 输入：
[1,0,0,1,0,0,0]
[1,0,0,0,0,1,1]
[0,0,0,1,0,0,0]
[1,1,0,1,1,0,0]

输出：18

public int maxRecommend(int[][] cinema) {int r = cinema.length;if (r == 0) return 0; //空矩阵的情况int c = cinema[0].length;int res = 0;for (int i = 0; i < r; i++) {for (int j = 0; j < c; j++) {if (cinema[i][j] == 0) {//有空位res = Math.max(res, dfs(cinema, i, j));}}}return res;
}//用来统计从i,j开始的连续一片有多少个座位
private int dfs(int[][] cinema, int i, int j) { //c是记录数if (i < 0 || i >= cinema.length || j < 0 || j >= cinema[0].length //边界条件|| cinema[i][j] != 0 // 空位条件) {return 0;}int count = 1;//初始化推荐座位为1cinema[i][j] = 2;//dfs递归int l1 = dfs(cinema, i, j - 1);int l2 = dfs(cinema, i, j + 1);int l3 = dfs(cinema, i + 1, j);int l4 = dfs(cinema, i - 1, j);return count + l1 + l2 + l3 + l4;
}

63、字符串的排列

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-EcAkeJTa-1677381716373)(${img}/image-20221228095152222.png)]

import java.util.*;
public class Solution {ArrayList<String> res = new ArrayList<String>();StringBuilder sb = new StringBuilder();boolean[] used;public ArrayList<String> Permutation(String str) {if (str == null || str.length() == 0) return res;char[] charStr = str.toCharArray();//字典序Arrays.sort(charStr);//标记每个位置的字符是否被使用过used = new boolean[str.length()];recursion(charStr); //递归获取return res;}public void recursion(char[] charStr) {if (sb.length() == charStr.length) {res.add(new String(sb));//临时字符串满了加入输出} else {for (int i = 0; i < charStr.length; i++) {if (used[i]) continue; //如果该元素已经被加入了则不需要再加入了//当前的元素charStr[i]与同一层的前一个元素charStr[i-1]相同且charStr[i-1]没有用过（实际上已经用过了）if (i > 0 && charStr[i - 1] == charStr[i] && !used[i - 1]) continue;used[i] = true;sb.append(charStr[i]);recursion(charStr);//回溯used[i] = false;sb.deleteCharAt(sb.length() - 1);}}}
}

64、复原IP地址

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。

例如：“0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址，但是 “0.011.255.245”、“192.168.1.312” 和 “192.168@1.1” 是 无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 ‘.’ 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

示例 1：

输入：s = “25525511135”
输出：[“255.255.11.135”,“255.255.111.35”]
示例 2：

输入：s = “0000”
输出：[“0.0.0.0”]
示例 3：

输入：s = “101023”
输出：[“1.0.10.23”,“1.0.102.3”,“10.1.0.23”,“10.10.2.3”,“101.0.2.3”]

class Solution {List<String> res = new ArrayList<>();List<String> temp = new ArrayList<>();public List<String> restoreIpAddresses(String s) {dfs(s , 0);return res;}private void dfs(String s, int start){if(temp.size() == 4 && start == s.length()){res.add(String.join(".",temp));return;}for(int i = start; i < start + 3 && i < s.length() ; i++){String sub = s.substring(start,i + 1);if(!isIP(sub)) continue;temp.add(sub);dfs(s,i + 1);temp.remove(temp.size() - 1);}}public boolean isIP(String s){if(s.length() != 1 && s.charAt(0) == '0') return false;//前导零return Integer.parseInt(s) <= 255;}
}

65、验证IP地址

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5ZTZJ3WT-1677381716374)(${img}/image-20230102135240016.png)]

import java.util.*;public class Solution {/* 验证IP地址* @param IP string字符串 一个IP地址字符串* @return string字符串*/public String solve (String IP) {// write code hereif (IP.contains(".")) { //可能是IPV4String[] s = IP.split("\\.",-1);if (s.length != 4) return "Neither"; //必须为4组for (int i = 0; i < s.length; i++) {//位数要求 和 不能前缀0if (s[i].length() > 3 || s[i].length() < 1 || s[i].length() != 1 &&s[i].charAt(0) == '0') return "Neither";//遍历每个分割字符串，必须为数字for (int j = 0; j < s[i].length(); j++) {char c = s[i].charAt(j);if (c < '0' || c > '9')return "Neither";}int num = Integer.parseInt(s[i]);if (num < 0 || num > 255) return "Neither";}return "IPv4";} else if (IP.contains(":")) {String[] s = IP.split(":", -1);if (s.length != 8) return "Neither"; //必须为8组for (int i = 0; i < s.length; i++) {//位数要求if (s[i].length() > 4 || s[i].length() < 1) return "Neither";for (int j = 0; j < s[i].length(); j++) {char c = s[i].charAt(j);if (!(c >= '0' && c <= '9' || c >= 'a' && c <= 'f' || c >= 'A' && c <= 'F')) {return "Neither";}}}return "IPv6";}return "Neither";}
}

split(" “) 和 split(” ", -1) 的区别

1.如果字符串最后一位有值，则没有区别，
2.若干最后n位都是切割符，split(" “)不会继续切分，split(” ", -1)会继续切分

66、N皇后问题

import java.util.*;public class Solution {boolean[] col, dg, udg;int res = 0;public int Nqueen (int n) {// write code herecol = new boolean[n];dg = new boolean[2 * n];udg = new boolean[2 * n];dfs(0, n);return res;}public void dfs(int r, int n ) { //r是行号，c是列号if (r == n) {res++;return;}for (int c = 0; c < n ; c++) {//尝试第i行所有的列if (col[c] || dg[c + r] || udg[c - r + n]) continue;col[c] = dg[c + r] = udg[c - r + n] = true;dfs(r + 1, n);col[c] = dg[c + r] = udg[c - r + n] = false;}}
}

67、N皇后II

class Solution {boolean[] col;boolean[] dg;boolean[] udg;char[][] path;List<List<String>> res = new ArrayList<>();public List<List<String>> solveNQueens(int n) {col = new boolean[n];dg = new boolean[2 * n];udg = new boolean[2 * n];path = new char[n][n];for(int i = 0; i < path.length; i++){Arrays.fill(path[i],'.');}dfs(0,n);return res;}public void dfs(int r, int n ) { //r是行号，c是列号if (r == n) {res.add(toList(path));return;}for (int c = 0; c < n ; c++) {if (col[c] || dg[c + r] || udg[c - r + n]) continue;col[c] = dg[c + r] = udg[c - r + n] = true;path[r][c] = 'Q';dfs(r + 1, n);col[c] = dg[c + r] = udg[c - r + n] = false;path[r][c] = '.';}}public List<String> toList(char[][] path){List<String> res = new ArrayList<>();for(int i = 0; i < path.length; i++){res.add(String.valueOf(path[i]));}return res;}
}

68、括号生成

import java.util.*;public class Solution {ArrayList<String> res = new ArrayList<String>();StringBuilder sb = new StringBuilder();public ArrayList<String> generateParenthesis (int n) {// write code hererecursion(0, 0, n);return res;}private void recursion(int left, int right, int n) {if (left == n && right == n) { //左右括号都用完了，就加入结果res.add(new String(sb));return;}if (left < n) { //使用一次左括号sb.append('(');recursion(left + 1, right, n);sb.deleteCharAt(sb.length() - 1);//回溯}if (right < n && right < left) { //使用右括号个数必须少于左括号sb.append(')');recursion(left, right  + 1, n);sb.deleteCharAt(sb.length() - 1);}}
}

69、矩阵最长递增路径

import java.util.*;public class Solution {public int solve (int[][] matrix) {// write code hereint r = matrix.length, c = matrix[0].length;int res = 0;for (int i = 0; i < r; i++) {for (int j = 0; j < c; j++) {//记录路径长度res = Math.max(res, dfs(matrix, i, j, -1));}}return res;}//pre是记录上一个的值public int dfs(int[][] matrix,  int i, int j, int pre) {//dfs递归边界，超出二位边界，不满足大于条件if (i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length ||//边界条件matrix[i][j] <= pre) {  //递增条件//当越界到最后时，才记录最大值return 0;}int path = 1;//不论大不大，都是需要被改变的pre = matrix[i][j];//dfs递归int l1 = dfs(matrix, i, j - 1, pre);int l2 = dfs(matrix, i, j + 1, pre);int l3 = dfs(matrix, i + 1, j, pre);int l4 = dfs(matrix, i - 1, j, pre);path = path + Math.max(l1, Math.max(l2, Math.max(l3, l4)));return path;}
}

70、矩阵的最小路径和

import java.util.*;public class Solution {public int minPathSum (int[][] matrix) {// write code hereint r = matrix.length;int c = matrix[0].length;int[][] dp = new int[r][c];//创建一个和原矩阵大小一致//dp[i][j]表示以当前i，j位置为终点的最短路径长度dp[0][0] = matrix[0][0];//处理第一行for (int i = 1; i < r; i++) {dp[i][0] = dp[i - 1][0] + matrix[i][0];}for (int i = 1; i < c; i++) { //第一列dp[0][i] = dp[0][i - 1] + matrix[0][i];}//其他按照公式来for (int i = 1; i < r; i++) {for (int j = 1; j < c; j++) {dp[i][j] = matrix[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);}}return dp[r - 1][c - 1];}
}