替换空格
public void replaceSpace(){
String s="abc de f ";
String t= s.replace(" ","%20");
System.out.println(t);
}
顺时针打印矩阵
import java.util.ArrayList;
import java.util.List;
public class SpiralMatrix {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> list=new ArrayList<>();
int row=0;int col=0;
int rowlen=matrix.length-1;int collen=matrix[0].length-1;
while(row<=rowlen&&col<=collen) {
for (int j = col; j <= collen; j++) {
list.add(matrix[row][j]);
}
for(int i=row+1;i<=rowlen;i++){
list.add(matrix[i][rowlen]);
}
if(rowlen>row&&collen>col){
for(int j=collen-1;j>col;j--){
list.add(matrix[rowlen][j]);
}
for(int i=rowlen;i>row;i--){
list.add(matrix[i][row]);
}
}
row++;col++;rowlen--;collen--;
}
return list;
}
}
Ip的组成有几种
import java.util.ArrayList;
public class IpAddress {
public static void main(String[] args) {
String s = "25525511135";
System.out.println(restoreIpAddresses(s));
}
public static ArrayList<String> restoreIpAddresses(String s) {
ArrayList<String> res = new ArrayList<String>();
if (s.length() < 4) return res;
for (int i = 1; i < 4 && i < s.length() - 2; i++) {
for (int j = i + 1; j < i + 4 && j < s.length() - 1; j++) {
for (int k = j + 1; k < j + 4 && k < s.length(); k++) {
String s1 = s.substring(0, i);
String s2 = s.substring(i, j);
String s3 = s.substring(j, k);
String s4 = s.substring(k, s.length());
if (isValid(s1) && isValid(s2) && isValid(s3) && isValid(s4)) {
res.add(s1 + "." + s2 + "." + s3 + "." + s4);
}
}
}
}
return res;
}
private static boolean isValid(String s) {
if (s.length() == 0 || s.length() > 3 || (s.charAt(0) == '0' && s.length() > 1) || Integer.parseInt(s) > 255)
return false;
return true;
}
}
二维字符矩阵找单词
import java.util.Scanner;
public class WordSearch {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int m=sc.nextInt();
int n=sc.nextInt();
char[][] board=new char[m][n];
for (int i = 0; i < m; i++) {
board[i] = sc.next().toCharArray();
}
String word = sc.next();
boolean res=exist(board,word);
System.out.println(res);
}
public static boolean exist(char[][] board, String word) {
int m = board.length;
int n = board[0].length;
boolean[][] visited = new boolean[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (dfs(board, word, 0, i, j, visited))
return true;
}
}
return false;
}
public static boolean dfs(char[][] board, String word, int index, int rowindex, int colindex, boolean[][] visited) {
if (index == word.length())
return true;
if (rowindex < 0 || colindex < 0 || rowindex >=board.length || colindex >= board[0].length)
return false;
if (visited[rowindex][colindex])
return false;
if (board[rowindex][colindex] != word.charAt(index))
return false;
visited[rowindex][colindex] = true;
boolean res = dfs(board, word, index + 1, rowindex - 1, colindex,
visited)
|| dfs(board, word, index + 1, rowindex + 1, colindex, visited)
|| dfs(board, word, index + 1, rowindex, colindex + 1, visited)
|| dfs(board, word, index + 1, rowindex, colindex - 1, visited);
visited[rowindex][colindex] = false;
return res;
}
}
二十六进制加法
import java.util.ArrayList;
import java.util.Scanner;
public class Twentysix {
//全局变量进位
private static int jinWei = 0;
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
System.out.println(hexPlus26(sc.next(), sc.next()));
}
}
private static String hexPlus26(String str1, String str2) {
ArrayList<StringBuffer> arr;
StringBuffer sbResult = new StringBuffer();
//将两个字符串用'a'从最高位补全，并为可能出现最长字符串最高位进一的情况，在最高位补一个a
if (str1.length() >= str2.length()) {
arr = completeStr(str1, str2);
} else {
arr = completeStr(str2, str1);
}
StringBuffer sb1 = arr.get(0);
StringBuffer sb2 = arr.get(1);
for (int i = sb1.length() - 1; i >= 0; i--) {
int plusResult = (int) sb1.charAt(i) - 97 + (int) sb2.charAt(i) - 97 + jinWei;
//如果发生进位，将全局变量jinWei改成1，并在下一次循环中加上，否则为0
if (plusResult > 25) {
sbResult.append(Character.toString((char) (plusResult - 26 + 97)));
jinWei = 1;
} else {
sbResult.append((char) (plusResult + 97));
jinWei = 0;
}
}
//如果最后没发生进位，去掉之前加的a
if (sbResult.charAt(sbResult.length() - 1) == 'a') {
sbResult.deleteCharAt(sbResult.length() - 1);
}
return sbResult.reverse().toString();
}
private static ArrayList<StringBuffer> completeStr(String str1, String str2) {
StringBuffer sb1 = new StringBuffer();
StringBuffer sb2 = new StringBuffer();
ArrayList<StringBuffer> arr = new ArrayList<StringBuffer>();
int lengthDiff = str1.length() - str2.length();
//为可能出现最长字符串最高位进一的情况，在最高位先补一个a（代表0）
sb1.append("a");
sb2.append("a");
//将两个字符串长度用a补齐
for (int i = 0; i < lengthDiff; i++) {
sb2.append("a");
}
//将原字符串加到最后边
sb1.append(str1);
sb2.append(str2);
arr.add(sb1);
arr.add(sb2);
return arr;
}
}
包围的区域
输入：
4
X X X X
X O O X
X X O X
X O X X
输出:
X X X X
X X X X
X X X X
X O X X
import java.util.Scanner;
public class SurroundedRegions {
public static void main(String[] args) {
Scanner sc =new Scanner(System.in);
int n=sc.nextInt();
char[][] board=new char[n][n];
for (int i=0;i<n;i++){
board[i]=sc.next().toCharArray();
}
if (board==null||board.length==0) return;
int row = board.length;
int col = board[0].length;
for(int j=0;j<col;j++){
dfs(board,0,j);
dfs(board,row-1,j); //第一行和最后一行
}
for(int i=1;i<row-1;i++){
dfs(board,i,0);
dfs(board,i,col-1); //第一列和最后一列抛去和上一个循环相交的格子
}
for(int i=0;i<row;i++)
for(int j=0;j<col;j++){
if (board[i][j]=='D') board[i][j] = 'O';
else if (board[i][j]=='O') board[i][j] = 'X';
}
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
System.out.print(board[i][j]);
}
System.out.println();
}
}
public static void dfs(char[][] board, int x, int y){
if (x<0||x>=board.length||y<0||y>=board[0].length||board[x][y]!='O') return;
board[x][y] = 'D';
dfs(board,x-1,y);
dfs(board,x+1,y);
dfs(board,x,y-1);
dfs(board,x,y+1);
}
}
完成数独
public class Solution {
public void solveSudoku(char[][] board) {
ArrayList<Integer> empty = new ArrayList<Integer>();
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
if(board[i][j]=='.'){
empty.add(i*9+j);
}
int len = empty.size();
dfs(empty,board,0,len);
}
public boolean dfs(ArrayList<Integer> empty, char[][] board, int cur, int len){
if(cur==len) return true;
int index = empty.get(cur);
int row = index/9;
int col = index%9;
for(int v=1;v<=9;v++){
if(isValid(v,row,col,board)){
board[row][col] = (char)(v+'0');
if(dfs(empty,board,cur+1,len))
return true;
board[row][col] = '.';
}
}
return false;
}
public boolean isValid(int v, int row, int col, char[][] board){
for(int i=0;i<9;i++){
if(board[row][i] - '0'==v) return false;
if(board[i][col] - '0'==v) return false;
int row_s = 3*(row/3) + i/3;
int col_s = 3*(col/3) + i%3;
if(board[row_s][col_s] - '0'==v) return false;
}
return true;
}
}
N皇后问题
https://blog.csdn.net/u011095253/article/details/9158473
public class Solution {
public ArrayList<String[]> solveNQueens(int n) {
ArrayList<String[]> res = new ArrayList<String[]>();
int[] loc = new int[n];
dfs(res,loc,0,n);
return res;
}
public void dfs(ArrayList<String[]> res, int[] loc, int cur, int n){
if(cur==n)
printboard(res,loc,n);
else{
for(int i=0;i<n;i++){
loc[cur] = i;
if(isValid(loc,cur))
dfs(res,loc,cur+1,n);
}
}
}
public boolean isValid(int[] loc, int cur){
for(int i=0;i<cur;i++){
if(loc[i]==loc[cur]||Math.abs(loc[i]-loc[cur])==(cur-i))
return false;
}
return true;
}
public void printboard(ArrayList<String[]> res, int[] loc, int n){
String[] ans = new String[n];
for(int i=0;i<n;i++){
String row = new String();
for(int j=0;j<n;j++){
if(j==loc[i]) row += "Q";
else row += ".";
}
ans[i] = row;
}
res.add(ans);
}
}
验证一个字符串是否为回文
只看字母（忽略其它字符），不分大小写。如“A man, a plan, a canal: Panama”就是一个回文
class Solution {
public boolean isPalindrome(String s) {
if(s.isEmpty()) return true;
String str = s.replaceAll("\\W", ""); // 使用正则去除非字符数字的字符
str = str.toLowerCase();
for(int i = 0; i < str.length(); i++) {
if(str.charAt(i) != str.charAt(str.length() - i -1)) {
return false;
}
}
return true;
}
}
二叉树的镜像
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
return isSymmetric(root.left, root.right);
}
private boolean isSymmetric(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) return true;
if (t1 == null || t2 == null) return false;
if (t1.val != t2.val) return false;
return isSymmetric(t1.left, t2.right) && isSymmetric(t1.right, t2.left);
}
二叉树和为某一值的路径
public void findPath(BinaryTreeNode root,int k){
if(root == null)
return;
Stack<Integer> stack = new Stack<Integer>();
findPath(root,k,stack);
}
public void findPath(BinaryTreeNode root,int k,Stack<Integer> path){
if(root == null)
return;
if(root.leftNode == null && root.rightNode == null){
if(root.value == k){
System.out.println("路径开始");
for(int i :path)
System.out.print(i+",");
System.out.print(root.value);
}
}
else{
path.push(root.value);
findPath(root.leftNode,k-root.value,path);
findPath(root.rightNode,k-root.value,path);
path.pop();
}
}
二叉树的最大深度
public static int maxDepth(TreeNode root) {
if(root==null){
return 0;
}
if(root.left==null){
return maxDepth(root.right)+1;
}
if(root.right==null){
return maxDepth(root.left)+1;
}
return max(maxDepth(root.left),maxDepth(root.right))+1;
}
有序数组去除重复数字
package array;
public class RemoveDuplicates {
public static void main(String[] args) throws Exception {
int[] nums = {1,1,2,3,3,4};
int N = new RemoveDuplicates().removeDuplicates(nums);
for (int i = 0; i < N; i++)
System.out.print(nums[i] + " ");
}
public int removeDuplicates(int[] nums) {
if (nums.length == 1) return 1;
int size = 1;
for (int j = 0, i = 1; i < nums.length; i++) {
if (nums[i] != nums[i - 1]) {
size++;
j++;
nums[j] = nums[i];
}
}
return size;
}
}
搜索旋转有序数组
package binarySearch;
// 时间复杂度 O(log n)，空间复杂度 O(1)
public class SearchRotated { public static void main(String[] args) throws Exception {
int[] A = {11,12,13,15,17,22,28,30,2,4,5,6,9};
System.out.println(new SearchRotated().search(A, 17));
}
public int search(int[] A, int target) {
if(A==null || A.length==0)
return -1;
int l = 0;
int r = A.length-1;
while(l<=r)
{
int m = (l+r)/2;
if(target == A[m])
return m;
if(A[m]<A[r])
{
if(target>A[m] && target<=A[r])
l = m+1;
else
r = m-1;
}
else
{
if(target>=A[l] && target<A[m])
r = m-1;
else
l = m+1;
}
}
return (A[l] == target) ? l : -1;
}
}
分点心
给孩子们分饼干，每个人的需求量不同。现给定两个数组，第一个数组为每个孩子的需求量（可理解为质量），第二个数组为每个饼干的size（可理解为质量）。求能满足孩子个数的最大值
import java.util.Arrays;
public class AssignCookies {
public static int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int gIndex = 0, sIndex = 0;
while (gIndex < g.length && sIndex < s.length) {
if (g[gIndex] <= s[sIndex])
gIndex++;
sIndex++;
}
return gIndex;
}
public static void main(String[] args) {
int[] g={2,3};
int[] s={1,2,3};
System.out.println(findContentChildren(g,s));
}
}
删除多少字符使得两字符串相等
Given two words word1 and word2, find the minimum number of steps required to make word1 and word2 the same, where in each step you can delete one character in either string.
Input: "sea", "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".
Note:
The length of given words won't exceed 500.
Characters in given words can only be lower-case letters.
思路：两字符串总长-2倍最长公共字串LCS 即为删除的最小步数
import org.junit.Test;
public class DeleteOperationForTwoStrings {
public int minDistance(String word1, String word2) {
int m = word1.length(), n = word2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = word1.charAt(i - 1) == word2.charAt(j - 1) ?
dp[i - 1][j - 1] + 1 : Math.max(dp[i][j - 1], dp[i - 1][j]);
}
}
return m + n - 2 * dp[m][n];
}
@Test
public void test(){
String w1="eat";
String w2="sea";
System.out.println(minDistance(w1,w2));
}
}
最长公共子序列
public static int lcs(String str1,String str2){
int len1 = str1.length();
int len2 = str2.length();
int c[][] = new int[len1+1][len2+1];
for (int i = 1; i <= len1; i++) {
for( int j = 1; j <= len2; j++) {
if (str1.charAt(i-1) == str2.charAt(j-1)) {
c[i][j] = c[i-1][j-1] + 1;
} else {
c[i][j] = max(c[i-1][j],c[i][j-1]);
}
}
}
return c[len1][len2];
}
合并有序链表
public class CombinTwoList {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1==null)return l2;
if(l2==null)return l1;
if(l1.val<l2.val){
l1.next=mergeTwoLists(l1.next,l2);
return l1;
}else{
l2.next=mergeTwoLists(l1,l2.next);
return l2;
}
}
}
斐波那切数列
public class Fibo {
public static void main(String[] args) {
int n=11;
System.out.println(fibo(n));
}
static long fibo(Integer integer){
long fiboone=1;
long fibotwo=1;
if(integer==1) return 1;
if(integer==2) return 1;
long fiboN=1;
for(int i=3;i<=integer;i++){
fiboN=fiboone+fibotwo;
fiboone=fibotwo;
fibotwo=fiboN;
}
return fiboN;
}
}
二维数组中的查找
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix==null||matrix.length==0||matrix[0].length==0)
return false;
int row=0;
int col=matrix[0].length-1;
while(row<matrix.length&&col>=0){
if(target==matrix[row][col])
return true;
else if(target>matrix[row][col])
row++;
else
col--;
}
return false;
}
}
出现次数超过一半的数
import java.util.Scanner;
/**
* 输出出现次数超过一半的数，如果没有就输出0
*/
public class HalfNum {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = sc.nextInt();
}
int count = 1;
int num = -1;
for (int i = 0; i < n; i++) {
if (num != nums[i]) {
count--;
if (count == 0) {
num = nums[i];
count = 1;
}
} else {
count++;
}
}
if(count>1)
System.out.println(num);
else
System.out.println(0);
}
}
是否是子树
import org.junit.Test;
public class IsSubtree {
@Test
public boolean isSubtree(TreeNode s,TreeNode t){
if(s==null) return false;
return isSubtreeWithRoot(s,t)||isSubtree(s.left,t)||isSubtree(s.right,t);
}
public boolean isSubtreeWithRoot(TreeNode s, TreeNode t){
if(t==null&&s==null) return true;
if(t==null||s==null) return false;
if(t.val!=s.val) return false;
return isSubtreeWithRoot(s.left,s.left)&&isSubtreeWithRoot(s.right,t.right);
}
}
删除多少字符，留下来的是最长的回文串
import java.util.Scanner;
/**
* 给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。
* 如何删除才能使得回文串最长呢？
*
* 思路：翻转该串后与原串比较，求最长公共子序列，返回len-dp[len][len]
*/
public class MakeLongestPalindrome {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
while (sc.hasNextLine()) {
String s1 = sc.nextLine();
String s2 = new StringBuilder(s1).reverse().toString();
int len = s1.length();
int[][] dp = new int[len + 1][len + 1];
for (int i = 1; i <= len; i++) {
for (int j = 1; j <= len; j++) {
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
System.out.println(len - dp[len][len]);
}
}
}
能容纳的最大水量
import org.junit.Test;
/**
* leetcode11.Container With Most Water
* Input: [1,3,2] 最短板容纳水量
Output: 2
*/
public class MaxArea {
public int maxArea(int[] height) {
int i=0;
int j=height.length-1;
int water=0;
while(i<j){
water=Math.max(water,(j-i)*Math.min(height[j],height[i]));
if(height[i]<height[j])
i++;
else
j--;
}
return water;
}
@Test
public void test(){
int[] height={1,8,6,2,5,4,8,3,7};
System.out.println(maxArea(height));
}
}
子数组最大乘积
**
* 子数组的最大乘积
*/
public class MaxProductSubString {
public static void main(String[] args) {
int[] nums={6,2,-3,5};
int min=nums[0];
int max=nums[0];
int ans=nums[0];
for(int i=1;i<nums.length;i++){
int a=min*nums[i];
int b=max*nums[i];
max=Math.max(Math.max(a,b),nums[i]);
min=Math.min(Math.min(a,b),nums[i]);
ans=Math.max(ans,max);
}
System.out.println(ans);
}
}
纸币的组合数有多少种（美团2017）
import java.util.Scanner;
/**
* 给你六种面额 1、5、10、20、50、100 元的纸币，假设每种币值的数量都足够多，
* 编写程序求组成N元（N为0~10000的非负整数）的不同组合的个数。
*/
public class Meituan20172 {
public static void main(String[] args) {
int[] coins={1,5,10,20,50,100};
Scanner sc=new Scanner(System.in);
Integer n=sc.nextInt();
if(n<=0) System.out.println(0);
long[] dp=new long[n+1];
dp[0]=1;
for(int c:coins){
for(int i=c;i<=n;i++){
dp[i]=dp[i]+dp[i-c];
}
}
System.out.println(dp[n]);
}
}
柱状图矩形的最大面积（美团2017）
import java.util.Scanner;
/**
* 给定一组非负整数组成的数组h，代表一组柱状图的高度，其中每个柱子的
* 宽度都为1。 在这组柱状图中找到能组成的最大矩形的面积（如图所示）。
* 入参h为一个整型数组，代表每个柱子的高度，返回面积的值。
*/
public class Meituan20173 {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int[] nums=new int[n];
for(int i=0;i<n;i++){
nums[i]=sc.nextInt();
}
int max = 0;
int len = nums.length;
for(int i=0; i<len; i++){
int minH = nums[i];
for(int j=i; j<len; j++){
minH = Math.min(minH, nums[j]);
max = Math.max(max, (j-i+1)*minH);
}
}
System.out.println(max);
}
}
最长公共子串
import java.util.Scanner;
/**
* 给出两个字符串（可能包含空格）,找出其中最长的公共连续子串,输出其长度。
*/
public class Meituan20174 {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
String s1=sc.nextLine();
String s2=sc.nextLine();
int l1=s1.length();
int l2=s2.length();
int[][] dp=new int[l1+1][l2+1];
int res=0;
for(int i=1;i<=l1;i++){
for(int j=1;j<=l2;j++){
if(s1.charAt(i-1)==s2.charAt(j-1)){
dp[i][j]=dp[i-1][j-1]+1;
res=Math.max(res,dp[i][j]);
}
else{
dp[i][j]=0;
}
}
}
System.out.println(res);
}
}
二进制数中1的个数
public class NumbesOf1 {
public static void main(String[] args) {
int a=12;
int count=0;
while(a!=0){
a=a&(a-1);
count++;
}
System.out.println(count);
}
}
字符串的全排列
输入为数字数组，输出为二维列表
import org.junit.Test;
import java.util.ArrayList;
import java.util.List;
public class Solution {
// 最终返回的结果集
List<List<Integer>> res = new ArrayList<List<Integer>>();
@Test
public void permute() {
int[] nums={1,2,3};
int len = nums.length;
// 采用前后元素交换的办法，dfs解题
exchange(nums, 0, len);
System.out.println(res);
}
public void exchange(int[] nums, int i, int len) {
// 将当前数组加到结果集中
if(i==len-1) {
List<Integer> list = new ArrayList<>();
for (int j=0; j<len; j++){
list.add(nums[j]);
}
res.add(list);
return ;
}
// 将当前位置的数跟后面的数交换，并搜索解
for (int j=i; j<len; j++) {
swap(nums, i, j);
exchange(nums, i+1, len);
swap(nums, i, j);
}
}
public void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
输入为字符串，输出为console每行输出
/**
* 参数array:给定字符串的字符数组
* 参数start:开始遍历字符与其后面各个字符将要进行交换的位置
* 参数end:字符串数组的最后一位
* 函数功能：输出字符串数字的各个字符全排列
*
*/
public class PermutationAll {//方法1：递归实现
public static void main(String[] args){
String s = "abcd";
char[] array = s.toCharArray();
recursion(array,0,array.length-1);
}
public static void recursion(char[] array,int start,int end){
if(end <= 1)
return;
if(start == end){
for(int i = 0;i < array.length;i++)
System.out.print(array[i]);
System.out.println();
}
else{
for(int i = start;i <= end;i++){
swap(array,i,start);
recursion(array,start+1,end);
swap(array,i,start);
}
}
}
//交换数组m位置和n位置上的值
public static void swap(char[] array,int m,int n){
char temp = array[m];
array[m] = array[n];
array[n] = temp;
}
}
有重复数字的全排列
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Solution {
List<List<Integer>> res = new ArrayList<List<Integer>>();
public List<List<Integer>> permuteUnique(int[] nums) {
int len = nums.length;
if(len==0||nums==null) return res;
boolean[] used = new boolean[len];
List<Integer> list = new ArrayList<Integer>();
Arrays.sort(nums);
dfs(nums, used, list, len);
return res;
}
public void dfs(int[] nums, boolean[] used, List<Integer> list, int len) {
if(list.size()==len) {
res.add(new ArrayList<Integer>(list));
return ;
}
for (int i=0; i<len; i++) {
// 当前位置的数已经在List中了
if(used[i]) continue;
// 当前元素与其前一个元素值相同 且 前元素未被加到list中，跳过该元素
if(i>0 && nums[i]==nums[i-1] && !used[i-1]) continue;
// 深度优先搜索遍历
used[i]=true;
list.add(nums[i]);
dfs(nums, used, list, len);
list.remove(list.size()-1);
used[i]=false;
}
}
}
Z字型打印二叉树
import org.junit.Test;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;
/**
* Z字型打印二叉树
*/
public class PrintBintreeByZ {
@Test
public void print(TreeNode root) {
List<List> listall = new ArrayList<>();
Stack<TreeNode> nowStack = new Stack<>();
nowStack.push(root);
boolean flag=false;
while (!nowStack.isEmpty()) {
flag=!flag;
Stack<TreeNode> nextStack = new Stack<>();
List<Integer> listone = new ArrayList<>();
for(TreeNode node:nowStack) {
listone.add(node.val);
if (node.right != null)
nextStack.add(node.right);
if (node.left != null)
nextStack.add(node.left);
}
nowStack = nextStack;
if(flag)
Collections.reverse(listone);
listall.add(listone);
}
System.out.println(listall);
}
}
从尾到头打印链表
import java.util.Stack;
public class PrintListFromTail {
public static void main(String[] args) {
ListNode listNode=null;
Stack<Integer> sk=new Stack<>();
while(listNode!=null){
sk.push(listNode.val);
}
while(!sk.isEmpty()){
System.out.println(sk.pop()+" ");
}
}
}
翻转链表
import org.junit.Test;
public class ReverseList {
@Test
public ListNode reverseList(ListNode head){
if(head==null) return null;
ListNode pre=null;
ListNode cur=null;
while(head.next!=null){
pre=head.next;
head.next=cur;
cur=head;
head=pre;
}
return head;
}
}
单例模式
/**
*静态内部类实现单例
*/
public class Singleton {
private Singleton() {
}
private static class SingletonHolder{
public static final Singleton instance=new Singleton();
}
public static Singleton getInstance(){
return SingletonHolder.instance;
}
}
链表倒数第K个数
import org.junit.Test;
public class TheKthNodeFromTail {
@Test
public ListNode main(ListNode head,int k) {
ListNode listNode=head;
if(listNode==null||k<=0)
return null;
ListNode nodeA=head;
for(int i=1;i<k;i++) {
if (listNode != null) {
listNode=listNode.next;
}
else{
return null;
}
}
while(listNode.next!=null){
listNode=listNode.next;
nodeA=nodeA.next;
}
return nodeA;
}
}
收集雨水
import org.junit.Test;
/**
* leetcode42.
* Given n non-negative integers representing an elevation map where the
* width of each bar is 1, compute how much water it is able to trap
* after raining.
*/
public class TrappingRainWater {
public int trap(int[] height) {
int l = 0, r = height.length - 1, level = 0, res = 0;
while (l < r) {
int lower = height[(height[l] < height[r]) ? l++ : r--];
level = Math.max(level, lower);
res += level - lower;
}
return res;
}
@Test
public void test(){
int[] height={0,1,0,2,1,0,1,3,2,1,2,1};
System.out.println(trap(height));
}
}
两个栈实现队列
import java.util.Stack;
public class TwoStackQueue {
Stack<Integer> skpush=new Stack<>();
Stack<Integer> skpop=new Stack<>();
public void push(Integer integer){
skpush.push(integer);
}
public int pop(){
while(!skpush.isEmpty()){
skpop.push(skpush.pop());
}
return skpop.pop();
}
}
字符串能否由字符串数组中的小字符串拼接
import java.util.ArrayList;
import java.util.List;
public class WordBreak {
public static void main(String[] args) {
String s="leetcode";
List<String> wordDict=new ArrayList<>();
wordDict.add("leet");
wordDict.add("code");
int len=s.length();
boolean[] dp=new boolean[len+1];
dp[0]=true;
for(int i=1;i<=len;i++){
for(int j=0;j<i;j++){
String tmp=s.substring(j,i);
if(dp[j] && wordDict.contains(tmp)){
dp[i]=true;
break;
}
}
}
System.out.println(dp[len]);
}
}
01背包
public int knapsack(int cap, int N, int[] weights, int[] val) {
int[] dp = new int[cap+ 1];
for (int i = 1; i <= N; i++) {
int w = weights[i - 1], v = val[i - 1];
for (int j = cap; j >= 1; j--) {
if (j >= w) {
dp[j] = Math.max(dp[j], dp[j - w] + v);
}
}
}
return dp[cap];
}
最长的回文子串
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Input: "cbbd"
Output: "bb"
class Solution {
private static int low;
private static int maxLen;
public String longestPalindrome(String s) {
int len=s.length();
if(len<2){
return s;
}
for(int i=0;i<len;i++){
extend(s,i,i);
extend(s,i,i+1);
}
return s.substring(low, low+maxLen);
}
private static void extend(String s, int j, int k) {
while(j>=0&&k<s.length()&&s.charAt(j)==s.charAt(k)){
j--;
k++;
}
if(maxLen<k-j-1){
low=j+1;
maxLen=k-j-1;
}
}
}
