1. LeetCode373_查找和最小的k对数字_java实现

package com.leetcode;
 
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
 
/**
 * LeetCode373_查找和最小的k对数字
 */
public class LeetCode373 {
    /**
     * 采用优先队列（小顶堆）
     * @param nums1
     * @param nums2
     * @param k
     * @return
     */
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        //优先队列最多保存k个元素
        PriorityQueue<int[]> minPQ=new PriorityQueue<>(k,(o1,o2)->{
            return nums1[o1[0]]+nums2[o1[1]]-nums1[o2[0]]-nums2[o2[1]];
        });
 
        List<List<Integer>> res=new ArrayList<>();
        int m=nums1.length;
        int n=nums2.length;
        for(int i=0;i<Math.min(m,k);i++){
            minPQ.offer(new int[]{i,0});
        }
 
        while (k-->0&&!minPQ.isEmpty()){
            int[] idxPair=minPQ.poll();
            List<Integer> list = new ArrayList<>();
            list.add(nums1[idxPair[0]]);
            list.add(nums2[idxPair[1]]);
            res.add(list);
            if(idxPair[1]+1<n){
                minPQ.offer(new int[]{idxPair[0],idxPair[1]+1});
            }
        }
        return res;
    }
}

2. LeetCode42_接雨水_java实现

package com.leetcode;
 
import java.util.ArrayDeque;
import java.util.Deque;
 
/**
 * LeetCode42_接雨水
 */
public class LeetCode42 {
    /**
     * 采用单调栈实现
     * 解题思路：找上一个更大元素，在找的过程中填坑
     *
     * @param height
     * @return
     */
    public int trap(int[] height) {
        int res = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[i] >= height[stack.peek()]) {
                int bottonH = height[stack.pop()];
                if (stack.isEmpty()) {
                    break;
                }
                int left = stack.peek();
                int dh = Math.min(height[left], height[i])- bottonH;//面积高度
                res += dh * (i - left - 1);
            }
            stack.push(i);
        }
        return res;
    }
}

3.LeetCode274_H指数_java实现

package com.leetcode;
 
import java.util.Arrays;
 
/**
 * LeetCode274_H指数
 * <p>
 * h指数的定义：h代表“高引用次数”，
 * 一名科研人员的h指数是指他至少发表了h篇论文，并且至少有h篇论文被引用次数大于等于h。
 * 如果h有多种可能的值，h指数是其中最大的那个
 */
public class LeetCode274 {
    /**
     * 采用排序
     * @param citations
     * @return
     */
    public int hIndex(int[] citations) {
        Arrays.sort(citations);//排序引用次数
        int h = 0, i = citations.length - 1;//初始化引用次数h为0
 
        //从大到小遍历数组
        while (i >= 0 && citations[i] > h) {//citations[i]>h说明找到一篇被引用的至少h+1次的论文
            h++;
            i--;
        }
        return h;
    }
}

4.LeetCode373_查找和最小的k对数字_java实现

package com.leetcode;
 
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
 
/**
 * LeetCode373_查找和最小的k对数字
 */
public class LeetCode373 {
    /**
     * 采用优先队列（小顶堆）
     * @param nums1
     * @param nums2
     * @param k
     * @return
     */
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        //优先队列最多保存k个元素
        PriorityQueue<int[]> minPQ=new PriorityQueue<>(k,(o1,o2)->{
            return nums1[o1[0]]+nums2[o1[1]]-nums1[o2[0]]-nums2[o2[1]];
        });
 
        List<List<Integer>> res=new ArrayList<>();
        int m=nums1.length;
        int n=nums2.length;
        for(int i=0;i<Math.min(m,k);i++){
            minPQ.offer(new int[]{i,0});
        }
 
        while (k-->0&&!minPQ.isEmpty()){
            int[] idxPair=minPQ.poll();
            List<Integer> list = new ArrayList<>();
            list.add(nums1[idxPair[0]]);
            list.add(nums2[idxPair[1]]);
            res.add(list);
            if(idxPair[1]+1<n){
                minPQ.offer(new int[]{idxPair[0],idxPair[1]+1});
            }
        }
        return res;
    }
}

5.LeetCode71_简化路径_java实现

package com.leetcode;
 
import java.util.ArrayDeque;
import java.util.Deque;
 
/**
 * LeetCode71_简化路径
 */
public class LeetCode71 {
    /**
     * 采用栈实现
     *
     * @param path
     * @return
     */
    public String simplifyPath(String path) {
        String[] names = path.split("/");
        Deque<String> stack = new ArrayDeque<>();
        for (String name : names) {
            if ("..".equals(name)) {//两个点（目录名），采用栈维护路径中每一个目录名
 
                if (!stack.isEmpty()) {//如果栈不为空，弹出栈顶目录，将目录切换到上一级
                    stack.pollLast();
                }
            } else if (name.length() > 0 && !".".equals(name)) {
                stack.offerLast(name);
            }
        }
 
        StringBuilder res = new StringBuilder();
        //将栈底到栈顶的字符串/进行连接，在最前面加/表示根目录
        if (stack.isEmpty()) {
            res.append('/');
        } else {
            while (!stack.isEmpty()) {
                res.append('/');
                res.append(stack.pollFirst());
            }
        }
        return res.toString();
    }
 
}

6.LeetCode224_基本计算器_java实现

package com.leetcode;
 
 
import java.util.Stack;
 
/**
 * LeetCode224_基本计算器
 */
public class LeetCode224 {
    /**
     * 采用括号展开+栈实现
     * @param s
     * @return
     */
    public int calculate(String s) {
        Stack<Integer> ops=new Stack<>();
        ops.push(1);
        int sign=1;//定义当前符号
 
        int res=0;
        int n=s.length();
        int i=0;
        while (i<n){
            if(s.charAt(i)==' '){
                i++;
            }else if(s.charAt(i)=='+'){
                sign=ops.peek();
                i++;
            }else if(s.charAt(i)=='-'){
                sign=-ops.peek();
                i++;
            }else if(s.charAt(i)=='('){
                ops.push(sign);
                i++;
            }else if(s.charAt(i)==')'){
                ops.pop();
                i++;
            }else{
                long num=0;
                while (i<n&&Character.isDigit(s.charAt(i))){//是数字
                    num=num*10+s.charAt(i)-'0';
                    i++;
                }
                res+=sign*num;
            }
        }
        return res;
    }
}

7.LeetCode6_Z字形变换_java实现

package com.leetcode;
 
import java.util.ArrayList;
import java.util.List;
 
/**
 * LeetCode6_Z字形变换
 */
public class LeetCode6 {
    /**
     * 解题思路：模拟行索引的变化，在遍历s中每个字符填充到正确的行res[i]
     *
     * @param s
     * @param numRows
     * @return
     */
    public String convert(String s, int numRows) {
        if (numRows < 2) {
            return s;
        }
 
        List<StringBuilder> rows = new ArrayList<>();
 
        //给每行填充一个stringbuilder对象
        for(int i=0;i<numRows;i++){
            rows.add(new StringBuilder());
        }
 
        int i = 0, flag = -1;
        for (char c : s.toCharArray()) {
            rows.get(i).append(c);
            if (i == 0 || i == numRows - 1) {
                flag = -flag;//在达到 Z 字形转折点时，执行反向
            }
            i += flag;//更新行索引
        }
        StringBuilder res = new StringBuilder();
        for (StringBuilder row : rows) {
            res.append(row);//合并多行字符串
        }
 
        return res.toString();
    }
}

8.LeetCode13_罗马数字转整数_java实现

package com.leetcode;
 
/**
 * LeetCode13_罗马数字转整数
 */
public class LeetCode13 {
    /**
     * 解题思路：
     * 把一个小值放在大值的左边，就是做减法，否则为加法。
     *
     * @param s
     * @return
     */
    public int romanToInt(String s) {
        int sum = 0;
        int preNum = getValue(s.charAt(0));
        for (int i = 1; i < s.length(); i++) {
            int num = getValue(s.charAt(i));
            if (preNum < num) {
                sum -= preNum;
            } else {
                sum += preNum;
            }
            preNum = num;
        }
        sum += preNum;
        return sum;
    }
 
 
    private int getValue(char ch) {
        switch (ch) {
            case 'I':
                return 1;
            case 'V':
                return 5;
            case 'X':
                return 10;
            case 'L':
                return 50;
            case 'C':
                return 100;
            case 'D':
                return 500;
            case 'M':
                return 1000;
            default:
                return 0;
        }
    }
}

9.LeetCode55_跳跃游戏_java实现

package com.leetcode;
 
/**
 * LeetCode55_跳跃游戏
 */
public class LeetCode55 {
    /**
     * 实现思路：计算可以到达的最远位置
     * @param nums
     * @return
     */
    public boolean canJump(int[] nums) {
        int n=nums.length;
        int rightMost=0;//可以到达的最远位置
        for(int i=0;i<n;i++){
            if(i<=rightMost){
                rightMost=Math.max(rightMost,i+nums[i]);
                if(rightMost>=n-1){
                    return true;
                }
            }
        }
        return false;
    }
}

10.LeetCode103_二叉树的锯齿形层序遍历_java实现

package com.leetcode;
 
 
 
import java.util.*;
 
/**
 * LeetCode103_二叉树的锯齿形层序遍历
 */
public class LeetCode103 {
    /**
     * 层序遍历
     *
     * @param root
     * @return
     */
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList<List<Integer>>();
        }
 
        List<List<Integer>> res = new ArrayList<>();
        //添加根节点到第一层
        Queue<TreeNode> queue = new ArrayDeque<>();//构造队列
        queue.offer(root);
        boolean isOrderLeft = true;//默认从左到右遍历
 
        while (!queue.isEmpty()) {
            //双端队列可以在队列任意一端插入元素的队列
            Deque<Integer> levelList = new LinkedList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode curNode = queue.poll();
                if (isOrderLeft) {
                    levelList.offerLast(curNode.val);//从左到右遍历，元素插入双端队列队尾
                } else {
                    levelList.offerFirst(curNode.val);//从右到左遍历，元素插入双端队列的头部
                }
                if (curNode.left != null) {
                    queue.offer(curNode.left);
                }
                if (curNode.right != null) {
                    queue.offer(curNode.right);
                }
            }
            res.add((List<Integer>) levelList);
            isOrderLeft = !isOrderLeft;
        }
        return res;
    }
 
 
}

11.LeetCode222_完全二叉树的节点个数

package com.leetcode;
 
/**
 * LeetCode222_完全二叉树的节点个数
 * <p>
 * 完全二叉树定义：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。
 * 若最底层为第h层（从第 0 层开始）,则该层包含 1~ 2h 个节点。
 */
public class LeetCode222 {
    /**
     * 解题思路：采用朴素遍历
     * 求一棵完全二叉树的节点个数，其实就是递归遍历求左子树和右子树的个数，它们两个相加再加上根节点的个数1，就是完全二叉树的节点数。
     *
     * @param root
     * @return
     */
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return countNodes(root.left) + countNodes(root.right) + 1;
 
    }
}

12.LeetCode198_打家劫舍_java实现

package com.leetcode;
 
/**
 * LeetCode198_打家劫舍
 */
public class LeetCode198 {
    public int rob(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int[] res = new int[nums.length + 1];
        res[0] = 0;
        res[1] = nums[0];
 
        for (int i = 2; i < res.length; i++) {
            res[i] = Math.max(res[i - 2] + nums[i - 1], res[i - 1]);
        }
        return res[nums.length];
    }
 
}

13.LeetCode48_旋转图像_java实现

package com.leetcode;
 
/**
 * LeetCode48_旋转图像
 * 给定一个N×N的二维矩阵表示图像，90度顺时针旋转图像。
 */
public class LeetCode48 {
    public void rotate(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return;
        }
 
        int length = matrix.length;
        for (int i = 0; i < length / 2; i++) {
            for (int j = 0; j < (length + 1) / 2; j++) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[length - j - 1][i];
                matrix[length - j - 1][i] = matrix[length - i - 1][length - j - 1];
                matrix[length - i - 1][length - j - 1] = matrix[j][length - i - 1];
                matrix[j][length - i - 1] = tmp;
            }
        }
    }
}

14.LeetCode36_有效的数独_java实现

package com.leetcode;
 
import java.util.HashSet;
import java.util.Set;
 
/**
 * LeetCode36_有效的数独
 */
public class LeetCode36 {
    /**
     * 解题思路：
     * 请判定一个数独是否有效。该数独可能只填充了部分数字，其中缺少的数字用 . 表示。
     *
     * 采用：维护一个HashSet用来记同一行、同一列、同一九宫格是否存在相同数字
     *
     * @param board
     * @return
     */
    public boolean isValidSudoku(char[][] board) {
        Set seen=new HashSet();
        for(int i=0;i<9;++i){
            for(int j=0;j<9;++j){
                char num=board[i][j];
                if(num !='.'){
                    //行、列，同一九宫格已经包含,返回false
                    if(!seen.add(num+" in row "+i)||!seen.add(num+" in column "+j)|| !seen.add(num+" in block "+i/3+"-"+j/3)){
                        return false;
                    }
                }
            }
        }
        return true;//不包含返回true;
    }
}

15.LeetCode202_快乐数_java实现

package com.leetcode;
 
import java.util.HashSet;
import java.util.Set;
 
/**
 * LeetCode202_快乐数
 * <p>
 * 「快乐数」 定义为：
 * <p>
 * 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
 * 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
 * 如果这个过程 结果为 1，那么这个数就是快乐数。
 * 如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
 */
public class LeetCode202 {
    /**
     * 采用哈希集合检测循环方法
     *
     * @param n
     * @return
     */
    public boolean isHappy(int n) {
        Set<Integer> seen = new HashSet<>();
        while (n != 1 && !seen.contains(n)) {
            seen.add(n);
            n = getNext(n);
        }
        return n == 1;
 
    }
 
    private int getNext(int n) {
        int totalSum = 0;
        while (n > 0) {
            int d = n % 10;
            n = n / 10;
            totalSum += d * d;
        }
        return totalSum;
    }
}

16.LeetCode122_买卖股票的最佳时机II_java实现

package com.leetcode;
 
/**
 *LeetCode122_买卖股票的最佳时机II
 *
 * 解题思路：
 *     贪心：只要相邻的两天股票的价格是上升的,就进行一次交易, 获得一定利润
 */
public class LeetCode122 {
    public int maxProfit(int[] prices) {
        int profit=0;
        for(int i=0;i<prices.length-1;i++){
            int diff=prices[i+1]-prices[i];
            if(diff>0){
                profit+=diff;
            }
        }
        return profit;
    }
}

17.LeetCode150_逆波兰表达式求值_java实现

package com.leetcode;
 
import java.util.Stack;
 
/**
 * LeetCode150_逆波兰表达式求值
 * <p>
 * 逆波兰表达式的特点是：没有括号，运算符总是放在和它相关的操作数之后。
 * 逆波兰表达式也称后缀表达式。
 */
public class LeetCode150 {
    /**
     * 采用栈解题思路：
     * 逆波兰表达式严格遵循「从左到右」的运算。计算逆波兰表达式的值时，使用一个栈存储操作数，从左到右遍历逆波兰表达式，进行如下操作：
     *      如果遇到操作数，则将操作数入栈；
     *      如果遇到运算符，则将两个操作数出栈，其中先出栈的是右操作数，后出栈的是左操作数，使用运算符对两个操作数进行运算，将运算得到的新操作数入栈。
     * 整个逆波兰表达式遍历完后，栈内只有一个元素，该元素即为逆波兰表达式的值。
     *
     * @param tokens
     * @return
     */
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        String operators = "+-*/";
        for (String token : tokens) {
            if (!operators.contains(token)) {
                stack.push(Integer.valueOf(token));
                continue;
            }
 
            int a = stack.pop();
            int b = stack.pop();
            if (token.equals("+")) {
                stack.push(b + a);
            } else if (token.equals("-")) {
                stack.push(b - a);
            } else if (token.equals("*")) {
                stack.push(b * a);
            } else {
                stack.push(b / a);
            }
        }
        return stack.pop();
    }
}

18.LeetCode205_同构字符串_java实现

package com.leetcode;
 
 
 
/**
 * LeetCode205_同构字符串
*
*两个字符串同构的含义就是字符串 s 可以唯一的映射到 t ，同时 t 也可以唯一的映射到 s 。
*
 */
public class LeetCode205 {
    /**
     * 采用判断字符首次出现的索引对比法
     * @param s
     * @param t
     * @return
     */
    public  static   boolean isIsomorphic(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
 
        char[] ss=s.toCharArray();
        char[] tt=t.toCharArray();
 
        for (int i = 0; i < s.length(); i++) {
          if(s.indexOf(ss[i])!=t.indexOf(tt[i])){
              return false;
          }
        }
        return true;
    }
 
    public static void main(String[] args) {
        System.out.println("isIsomorphic(\"\",\"\") = " + isIsomorphic("egg", "add"));
        System.out.println("isIsomorphic(\"foo\", \"bar\") = " + isIsomorphic("foo", "bar"));
        System.out.println("isIsomorphic(\"paper\",\"title\") = " + isIsomorphic("paper", "title"));
    }
}

19.LeetCode209_长度最小的子数组_java实现

package com.leetcode;
 
/**
 * LeetCode209_长度最小的子数组
 */
public class LeetCode209 {
 
    /**
     * 采用滑动窗口实现
     * @param target
     * @param nums
     * @return
     */
    public static int minSubArrayLen(int target, int[] nums) {
       //0.处理basecase
        if(nums.length==0){
           return 0;
       }
        int res=Integer.MAX_VALUE;
        int start = 0, end = 0;
        int sum=0;
 
        for (end = 0; end < nums.length; end++) {//1.1.进：当前遍历的end进入窗口
           sum+=nums[end];
            while (sum>= target) {//2.出：当窗口不符合条件时start持续退出窗口
                res = Math.min(res, end - start + 1);//3.算：窗口有效，计算结果
                sum-=nums[start];
                start++;
            }
 
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }
 
    public static void main(String[] args) {
        int[] nums={2,3,1,2,4,3};
        System.out.println("minSubArrayLen(7,nums) = " + minSubArrayLen(7, nums));
        int[] nums2={1,4,4};
        System.out.println("minSubArrayLen(4, nums2) = " + minSubArrayLen(4, nums2));
        int[] nums3={1,1,1,1,1,1,1,1};
        System.out.println("minSubArrayLen(11,nums3) = " + minSubArrayLen(11, nums3));
 
    }
}

20.LeetCode290_单词规律_java实现

package com.leetcode;
 
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;
 
/**
 * LeetCode290_单词规律
 */
public class LeetCode290 {
    public static boolean wordPattern(String pattern, String s) {
        String[] words = s.split(" ");
        if (words.length != pattern.length()) {//字符数和单词数不一致，一定不匹配
            return false;
        }
 
        Map<Object, Integer> map = new HashMap<>();
        for (Integer i = 0; i < words.length; i++) {
            if (!Objects.equals(map.put(words[i], i), map.put(pattern.charAt(i), i))) {//patter中字符与words中单词存放结果匹配不一致
                return false;
            }
 
        }
        return true;
    }
 
    public static void main(String[] args) {
        System.out.println("wordPattern(\"abba\",\"dog cat cat dog\") = " + wordPattern("abba", "dog cat cat dog"));
        System.out.println("wordPattern(\"abba\",\"dog cat cat fish\") = " + wordPattern("abba", "dog cat cat fish"));
        System.out.println("wordPattern(\"aaaa\",\"dog cat cat dog\") = " + wordPattern("aaaa", "dog cat cat dog"));
        Map res=new HashMap();
        System.out.println("res.put(\"a\",\"a\") = " + res.put("a", "a"));
        System.out.println("res.put(\"b\",\"b\") = " + res.put("b", "b"));
    }
}

21.LeetCode137_只出现一次的数字II

package com.leetcode;
 
 
import java.util.HashMap;
import java.util.Map;
 
/**
 * LeetCode137_只出现一次的数字II
 */
public class LeetCode137 {
 
    /**
     * 方法1：采用有限状态自动机
     *
     * @param nums
     * @return
     */
    public int singleNumber(int[] nums) {
        int a = 0, b = 0;
        for (int n : nums) {
            a = a ^ n & ~b;
            b = b ^ n & ~a;
        }
 
        return a;
 
    }
 
    /**
     * 方法2：采用哈希表
     * 实现思路：使用哈希映射统计数组中每个元素的出现次数；
     * 键表示一个元素，值表示其出现的次数；
     * 在统计完成后，遍历哈希映射即可找出只出现一次的元素；
     *
     * @param nums
     * @return
     */
    public int singleNumber2(int[] nums) {
        Map<Integer, Integer> freq = new HashMap<>();
 
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }
 
        int result = 0;
 
        for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
            if (entry.getValue() == 1) {//找出值只出现一次的元素
                result = entry.getKey();
                break;
            }
        }
        return result;
    }
}

22.LeetCode112_路径总和_java实现

package com.leetcode;
 
 
/**
 * LeetCode112_路径总和
 * <p>
 * 叶子节点是指没有子节点的节点
 */
public class LeetCode112 {
    /**
     * 采用深度优先（DFS）递归
     *
     * @param root
     * @param targetSum
     * @return
     */
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {//1.如果根节点为空，直接返回false
            return false;
        }
        return dfs(root, targetSum, root.val);//2.调用dfs函数
 
    }
 
    /**
     * 查找是否存在一条从根节点到叶子节点的路径，且路径上的节点值之和等于给定的目标值
     *
     * @param root
     * @param targetSum
     * @param pathSum
     * @return
     */
    private boolean dfs(TreeNode root, int targetSum, int pathSum) {
        if (root == null) {//1.如果当前节点为空，直接返回false
            return false;
        }
 
        //2.查找从根节点到叶子节点的路径，且路径上的节点值之和等于给定的目标值
        if (pathSum == targetSum && root.left == null && root.right == null) {
            return true;
        }
 
        boolean leftFalg = false, rightFlag = false;//初始化左右子树的标准为false
 
 
        //3.如果左子节点不为空，递归在左子树中查找路径，路径和=当前路径和+左子节点的值
        if (root.left != null) {
            leftFalg = dfs(root.left, targetSum, pathSum + root.left.val);
        }
 
        //4.如果右子节点不为空，递归在右子树中查找路径，路径和=当前路径和+右子节点的值
        if (root.right != null) {
            rightFlag = dfs(root.right, targetSum, pathSum + root.right.val);
        }
 
        //5.如果左子树或右子树中存在满足条件的路径，返回true,否则false
        return leftFalg || rightFlag;
    }
}

23.leetcode50_Pow(x, n)_java实现

package com.leetcode;
 
/**
 * LeetCode50_Pow(x, n)
 */
public class LeetCode50 {
    public double myPow(double x, int n) {
        long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }
 
    private double quickMul(double x, long N) {
        if (N == 0) {
            return 1.0;
        }
 
        double y = quickMul(x, N / 2);
        return N % 2 == 0 ? y * y : y * y * x;
    }
}

24.leetcode219_存在重复元素||_java实现

class Solution {
    //采用hashset进行重复元素处理
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashSet<Integer> set=new HashSet<>();
        for(int i=0;i< nums.length;i++){
            if(set.contains(nums[i])){
                return true;
            }
            set.add(nums[i]);
 
            if(set.size() >k){ //哈希表的大小大于k,则移除最前面的元素
                set.remove(nums[i-k]);
            }
        }
        return false;
    }
}

25.leetcode191_位1的个数_java实现

class Solution {
    /**
    采用位运算优化
     */
    public int hammingWeight(int n) {
        int ret =0;
        while(n!=0){
            n &=n-1; //n&(n-1) 会把n的二进制位中的最低位1变为0
            ret++;
        }
        return ret;
    }
}

26.LeetCode637_二叉树的层平均值_java实现

package com.leetcode;
 
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
 
/**
 * LeetCode637_二叉树的层平均值
 */
public class LeetCode637 {
    /**
     * 采用二叉树的广度优先遍历
     *
     * @param root
     * @return
     */
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> avgs = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);//根节点加入队列
        while (!queue.isEmpty()) {
            double sum = 0;
            int size = queue.size();
            //遍历树每一层的节点
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                sum += node.val;
                if (node.left != null) {
 
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            avgs.add(sum / size);
        }
        return avgs;
    }
}

27. LeetCode80_删除有序数组中的重复项II_java实现

package com.leetcode;
 
/**
 * LeetCode80_删除有序数组中的重复项II
 */
public class LeetCode80 {
 
    /**
     * 采用快慢指针
     * @param nums
     * @return
     */
    public int removeDuplicates(int[] nums) {
        int j = nums.length;
        //1.base case
        if (j <= 2) {
            return j;
        }
 
        //2.初始化快慢指针
        int slow = 1;
        int fast = 2;
        while (fast < j) {
            if (nums[slow - 1] != nums[fast]) {
                slow++;
                nums[slow] = nums[fast];
            }
            fast++;
        }
        return slow + 1;
    }
}

28.LeetCode47_ 全排列II_回溯_java实现

package com.leetcode;
 
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
 
/**
 * LeetCode47_ 全排列II
 * 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
 */
public class LeetCode47 {
    /**
     * 采用回溯+hashset查重
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        permutation(res, nums, 0);
        return res;
    }
 
    private void permutation(List<List<Integer>> res, int[] nums, int index) {
        if (index == nums.length) {
            List<Integer> ans = new ArrayList<>();
            //复制数组nums到ans中
            for (int x : nums) {
                ans.add(x);
            }
            res.add(ans);
            return;
        }
 
        Set<Integer> visited = new HashSet<>();//hashset进行查重操作
        for (int i = index; i < nums.length; i++) {
            swap(nums, index, i);//交换index与i————>next_state
            if (visited.add(nums[index])) {//如果nums[index]还没有被搜索过，才进行搜索
                permutation(res, nums, index + 1);
            }
            swap(nums, index, i);//index与i交换回来-->restore state
        }
    }
 
    private void swap(int[] nums, int i1, int i2) {
        int tmp = nums[i1];
        nums[i1] = nums[i2];
        nums[i2] = tmp;
    }
}

29.LeetCode46_Permuatations(全排列)_java实现

package com.leetcode;
 
import java.util.ArrayList;
import java.util.List;
 
 
/**
 * LeetCode46_Permuatations(全排列)
 */
public class LeetCode46 {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        dfs(res, nums, 0);
        return res;
    }
 
    private void dfs(List<List<Integer>> res, int[] nums, int index) {
        if (index >= nums.length) {//出界了
            //把当前的nums数组，做一份copy添加到答案ans中
            List<Integer> ans = new ArrayList<>();
            for (int i = 0; i < nums.length; i++) {
                ans.add(nums[i]);
            }
            res.add(ans);
            return;
        }
 
        for (int i = index; i < nums.length; i++) {
            swap(nums, index, i);//交换index和i->next_state
            dfs(res, nums, index + 1); //backtrack(array,index)
            swap(nums, index, i);//将index和i交换回来-> restore state
        }
    }
 
    private void swap(int[] nums, int i1, int i2) {
        int tmp = nums[i1];
        nums[i1] = nums[i2];
        nums[i2] = tmp;
    }
}

30. LeetCode1143_最长公共子序列（longestCommonSubsequence)_java实现

package com.leetcode;
 
/**
 * LeetCode1143_最长公共子序列（longestCommonSubsequence）
 * <p>
 * 一个字符串的子序列是指一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下
 * 删除某些字符(也可以不删除任何字符)后组成的新字符串
 * <p>
 * 两个字符串的公共子序列是这两个字符串所共同拥有的子序列
 */
public class LeetCode1143 {
    Integer[][] memo;
 
    /**
     * DP逆向填表
     * @param text1
     * @param text2
     * @return
     */
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        memo = new Integer[m][n];
        return dfs(text1, text2, m - 1, n - 1);
    }
 
    private int dfs(String t1, String t2, int i, int j) {
        if (i < 0 || j < 0) {//越界了
            return 0;
        }
 
        if (memo[i][j] != null) {
            return memo[i][j];
        }
 
        int res = 0;
        if (t1.charAt(i) == t2.charAt(j)) {
            res = dfs(t1, t2, i - 1, j - 1) + 1;
        } else {
            res = Math.max(dfs(t1, t2, i - 1, j), dfs(t1, t2, i, j - 1));
        }
 
        return memo[i][j] = res;
    }
 
    /**
     * DP正向填表
     * @param text1
     * @param text2
     * @return
     */
    public int longestCommonSubsequence2(String text1, String text2){
        int m=text1.length(),n=text2.length();
        int[][]memo=new int[m+1][n+1];
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(text1.charAt(i-1)==text2.charAt(j-1)){
                    memo[i][j]=memo[i-1][j-1]+1;
                }else{
                    memo[i][j]=Math.max(memo[i-1][j],memo[i][j-1]);
                }
            }
        }
        return  memo[m][n];
    }
}

31. LeetCode63_不同路径II(Unique PathsII)_java实现

package com.leetcode;
 
 
/**
 * LeetCode63_不同路径II(Unique PathsII)
 */
public class LeetCode63 {
    Integer[][] memo;
    int m, n;
 
    /**
     * 采用二维逆向DP实现
     *
     * @param obstacleGrid
     * @return
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        //1.初始化记忆表
        m = obstacleGrid.length;
        n = obstacleGrid[0].length;
        memo = new Integer[m][n];
        //2.调用dfs(matrix,m-1,n-1)
        return dfs(obstacleGrid, m - 1, n - 1);
    }
 
    private int dfs(int[][] matrix, int i, int j) {
        //1.处理basecase
        //a或c. 如果i,j越界或matrix遇到障碍物，返回0
        if (i < 0 || i >= m || j < 0 || j >= n || matrix[i][j] == 1) {
            return 0;
        }
        //b. 如果(i,j)=(0,0),返回1
        if (i == 0 && j == 0) {
            return 1;
        }
 
        //2.判断记忆memo表不为空，则已经计算了，直接返回记忆表
        if (memo[i][j] != null) {
            return memo[i][j];
        }
 
        //3.查找子问题答案
        int res = 0;
        res += dfs(matrix, i - 1, j);//往矩阵的左边找答案（这里是唯一路径）
        res += dfs(matrix, i, j - 1);//往矩阵的上方找答案
 
        return memo[i][j] = res;//更新记忆表并返回结果
    }
 
    /**
     * 采用二维的正向DP
     *
     * @param obstacleGrid
     * @return
     */
    public int uniquePathsWithObstacles2(int[][] obstacleGrid) {
 
        //1.初始化memo表
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        int[][] memo = new int[m + 1][n + 1];
 
        //2.填充basecase到记忆表
        memo[1][1] = 1;
 
        //3.使用状态转移规则
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (obstacleGrid[i - 1][j - 1] == 1) {//如果遇到障碍物，更新记忆表为0
                    memo[i][j] = 0;
                } else {
                    memo[i][j] += memo[i - 1][j] + memo[i][j - 1];
                }
            }
 
        }
        return memo[m][n];
    }
}

32.LeetCode91_解码方法(decodeways)_DP_java实现

package com.leetcode;
 
/**
 * LeetCode91_解码方法(decodeways)
 */
public class LeetCode91 {
    Integer[] memo;
 
    public int numDecodings(String s) {
        int n = s.length();
        memo = new Integer[n + 1];
        return dfs(s, n);
    }
 
    private int dfs(String s, int n) {
        if (n == 0) {
            return 1;
        }
        if (n == 1) {
            return s.charAt(0) == '0' ? 0 : 1;
        }
 
        if (memo[n] != null) {
            return memo[n];
        }
 
        int res = 0;
        //获取倒数第一个和第二个字符
        char x = s.charAt(n - 1), y = s.charAt(n - 2);
 
        //case1.第一个子问题不等于0，要答案
        if (x != '0') {
            res += dfs(s, n - 1);
        }
 
        //case2.计算yx的的字符code,
        int yx = (y - '0') * 10 + (x - '0');
        if (yx >= 10 && yx <= 26) {//yx合法，要答案
            res += dfs(s, n - 2);
        }
 
        memo[n] = res;
        return res;
    }
 
    /**
     * 正向DP实现
     *
     * @param s
     * @return
     */
    public int numDecodings2(String s) {
        int n = s.length();
        if (n == 0 || s.charAt(0) == '0') {
            return 0;
        }
 
        //1.初始化memo
        int[] dp = new int[n + 1];
        //2.填充basecase到memo表
        dp[0] = dp[1] = 1;
 
 
        for (int i = 2; i <= n; i++) {
            //3.使用转移状态
            char cur = s.charAt(i - 1), prev = s.charAt(i - 2);
            //计算字符解码的code值
            int code = (prev - '0') * 10 + (cur - '0');
            if (cur == '0') {
                if (prev == '0' || prev > '2') {
                    return 0;
                }
                dp[i] = dp[i - 2];
            } else {
                dp[i] = dp[i - 1];
                if (code > 10 && code <= 26) {//如果字符xx是有效的，则计算记忆状态结果
                    dp[i] += dp[i - 2];
                }
            }
        }
        return dp[n];//返回memo
    }
}

LeetCode96_不同的二叉搜索树（uniqueBinaryTree)_DP_java实现

package com.leetcode;
 
/**
 * LeetCode96_uniqueBinaryTree(不同的二叉搜索树)
 */
public class LeetCode96 {
    Integer[] memo;//定义记忆表
 
    /**
     * 采用DP-逆向填报实现，推荐采用这种Botton-up方法，方便理解
     *
     * @param n:节点数
     * @return
     */
    public int numTrees(int n) {
        //1.初始化记忆表有n+1个slots
        memo = new Integer[n + 1];
        return dfs(n);
    }
 
    private int dfs(int n) {
        //1.base case
        if (n <= 1) {
            return 1;
        }
 
        //2.判断记忆表是否为空，不为空，说明已经计算过了
        if (memo[n] != null) {
            return memo[n];
        }
 
        //3.查找子问题答案
        int res = 0;
        for (int i = 1; i <= n; i++) {
            //问题分为左，右两部分
            int left = dfs(i - 1);
            int right = dfs(n - i);
            res += left * right;
        }
 
        //4.更新记忆表状态，返回结果
        memo[n] = res;
        return res;
    }
 
    /**
     * 采用DP正向填报实现
     * <p>
     * 正向填报：把dfs的flow反过来，从底层子问题开始往大计算，
     * 最终计算到顶层问题
     *
     * @param n
     * @return
     */
    public int numTrees2(int n) {
        //1.初始化记忆表
        int[] dp = new int[n + 1];
        //2.填充base case到记忆表
        dp[0] = dp[1] = 1;
        //3.遍历i从[2,n]
        for (int i = 2; i <= n; i++) {
            //使用转移规则，遍历j从[1,i]
            for (int j = 1; j <= i; j++) {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];//4.返回记忆表结果
    }
 
 
}

33.LeetCode139_单词拆分_DP_java实现

package com.leetcode;
 
import java.util.HashSet;
import java.util.List;
 
/**
 * LeetCode139_单词拆分
 */
public class LeetCode139 {
    Boolean[] memo;//1.定义记忆
 
    /**
     * 采用DP实现
     *
     * @param s
     * @param wordDict
     * @return
     */
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();//初始化dp状态
        memo = new Boolean[n + 1];
        return dfs(s, n, new HashSet<>(wordDict));
    }
 
    private boolean dfs(String s, int len, HashSet<String> dict) {
        //1.basecase 处理
        if (len == 0) {//字符串为空，返回true
            return true;
        }
 
        //2.记忆状态不为空，说明子问题已经被计算处理过了，直接返回记忆状态
        if (memo[len] != null) {
            return memo[len];
        }
 
        //3.遍历子问题
        memo[len] = false;
        for (int i = 0; i < len; i++) {
            //如果子字符串不包含在字典中false，直接跳过，否则true,包含在字典中，说明当前子问题是true
            boolean right = dict.contains(s.substring(i, len));
            if (!right) {
                continue;
            }
 
            boolean left = dfs(s, i, dict);
            if (left) {
                //记忆step3的子问题答案true，跳出循环，返回记忆答案（memo[len]）
                memo[len] = true;
                break;
            }
        }
        return memo[len];
    }
}

34.LeetCode78_子集_java实现

package com.leetcode;
 
import java.util.ArrayList;
import java.util.List;
 
/**
 * LeetCode78_子集
 * <p>
 * 一个集合有2^n的子集
 */
public class LeetCode78 {
    public List<List<Integer>> subsets(int[] nums) {
        //1.初始化状态,调用dfs
        List<List<Integer>> res = new ArrayList<>();
        dfs(res, nums, new ArrayList<>(), 0);
        return res;
    }
 
    /**
     * state=(index,cur)
     *
     * @param res
     * @param nums
     * @param cur
     * @param index
     */
    private void dfs(List<List<Integer>> res, int[] nums, List<Integer> cur, int index) {
        if (index >= nums.length) { //如果index>= nums.length,则添加子集到结果，返回
            res.add(new ArrayList<>(cur));
            return;
        }
 
        //更新子问题状态
        cur.add(nums[index]);
        dfs(res, nums, cur, index + 1);
        cur.remove(cur.size() - 1);
 
        dfs(res, nums, cur, index + 1);
    }
}

35.LeetCode332_重新安排行程_java实现

package com.leetcode;
 
import java.util.*;
 
/**
 * LeetCode332_重新安排行程
 */
public class LeetCode332 {
    /**
     * 采用图的dfs实现
     * @param tickets
     * @return
     */
    public List<String> findItinerary(List<List<String>> tickets) {
        //1.创建图,Adjacency Heap Map
        Map<String, PriorityQueue<String>> map = new HashMap<>();
        for (List<String> edge : tickets) {
            map.computeIfAbsent(edge.get(0), k -> new PriorityQueue<>()).offer(edge.get(1));
        }
 
        //2.初始化结果
        List<String> res = new LinkedList<>();//linkedlist结果可以直接插入开始，不需要对结果进行reverse
        dfs(res, map, "JFK");
        return res;
    }
 
    /**
     * @param res 记录结果
     * @param map adj_map
     * @param cur 当前节点
     */
    private void dfs(List<String> res, Map<String, PriorityQueue<String>> map, String cur) {
        PriorityQueue<String> neis = map.getOrDefault(cur, new PriorityQueue<>());
        //遍历当前城市的邻接节点
        while (!neis.isEmpty()) {
            dfs(res, map, neis.poll());
        }
        res.add(0, cur);//追加当前城市到结果
    }
}

36.LeetCode200_岛屿数量_java实现

package com.leetcode;
 
/**
 * LeetCode200_岛屿数量
 */
public class LeetCode200 {
    int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
 
    /**
     * 采用图的深度优先搜索-DFS
     *
     * @param grid
     * @return
     */
    public int numIslands(char[][] grid) {
        //1.初始化岛屿个数
        int count = 0;
        //2.遍历二维矩阵，
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j<grid[i].length; j++) {
                if (grid[i][j] == '1') {//判断是否是岛屿（等于1）
                    count++;//计数岛屿个数
                    //递归深度遍历矩阵
                    dfs(grid, i, j);
                }
            }
        }
        return count;
    }
 
 
    /**
     * @param grid
     * @param i    当前的位置
     * @param j    当前的位置
     */
    private void dfs(char[][] grid, int i, int j) {
        grid[i][j] = '0';//初始化为水0
 
        //1.遍历邻接点(矩阵的上下左右方向)
        for (int[] dir : dirs) {
            int x = i + dir[0], y = j + dir[1];
 
            //判断邻接点是否有效（邻接点出界或者邻接点是水），无效，连接点是水(0),直接跳过
            if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] == '0') {
                continue;
            }
 
            dfs(grid, x, y);
        }
    }
}

37.LeetCode787_k站中转内最便宜的航班_java实现

package com.leetcode;
 
 
import java.util.*;
 
/**
 * LeetCode787_k站中转内最便宜的航班
 */
public class LeetCode787 {
    /**
     * 采用graph的BFS(Best-First search)实现
     * @param n
     * @param flights
     * @param src     出发点
     * @param dst     到达点
     * @param k       站点数     ：
     * @return
     */
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        //1.构建图，adjacency List Map
        Map<Integer, List<int[]>> map = new HashMap<>();
        for (int[] flight : flights) {
            List<int[]> to = map.getOrDefault(flight[0], new ArrayList<>());
            to.add(new int[]{flight[1], flight[2]});
            map.put(flight[0], to);
        }
 
        //2.初始化堆和cost为0,采用hashset记录已经访问过的node(城市)
        PriorityQueue<Cell2> heap = new PriorityQueue<>();
        heap.offer(new Cell2(src, k, 0));
 
        //3.遍历堆
        while (!heap.isEmpty()) {
            Cell2 cur = heap.poll();
            if (cur.dst == dst) {//当前节点是终点，直接返回终点
                return cur.price;
            }
            if (cur.stop >= 0 && map.containsKey(cur.dst)) {
                //遍历当前节点的所有邻居节点，增加他们到heap并且flight cost=current node's cost(当前的price)+edge cost
                for (int[] next : map.get(cur.dst)) {
                    heap.offer(new Cell2(next[0], cur.stop - 1, cur.price + next[1]));
                }
            }
        }
        return -1;//起点无法到终点
    }
}
 
class Cell2 implements Comparable<Cell2> {
 
    int dst, stop, price;
 
    Cell2(int dst, int stop, int price) {
        this.dst = dst;
        this.stop = stop;
        this.price = price;
    }
 
    @Override
    public int compareTo(Cell2 other) {
        return price - other.price;
    }
}

38.LeetCode743_网络延迟时间_java实现

package com.leetcode;
 
import java.util.*;
 
/**
 * LeetCode743_网络延迟时间
 */
public class LeetCode743 {
    /**
     * 采用图的BFS(Best-First search)实现
     *
     * @param times
     * @param n :网络节点个数
     * @param k：初始化节点
     * @return
     */
    public int networkDelayTime(int[][] times, int n, int k) {
        //1.构建图，adjacency List Map
        Map<Integer, List<Cell>> map = new HashMap<>();
        for (int[] time : times) {
            List<Cell> edges = map.getOrDefault(time[0], new ArrayList<>());
            edges.add(new Cell(time[1], time[2]));
            map.put(time[0], edges);
        }
 
        //2.初始化堆，采用hashMap记录访问过的节点和costs
        Map<Integer, Integer> costs = new HashMap<>();
        PriorityQueue<Cell> heap = new PriorityQueue<>();
        heap.offer(new Cell(k, 0));
        //3.遍历堆
        while (!heap.isEmpty()) {
            Cell cur = heap.poll();//获取当前的node
            if (costs.containsKey(cur.node)) {//如果已经访问过，则跳过
                continue;
            }
            costs.put(cur.node, cur.time);//记录当前的节点为已经访问过，更新cost
            if (map.containsKey(cur.node)) {
                //遍历当前节点的邻接节点，添加邻接节点到heap并计算delaytime=cur.node's cost+edge cost
                for (Cell nei : map.get(cur.node)) {
                    if (!costs.containsKey(nei.node)) {//邻接节点未被访问过，则添加到heap
                        heap.offer(new Cell(nei.node, cur.time + nei.time));
                    }
                }
            }
        }
        if (costs.size() != n) {
            return -1;
        }
        int res = 0;
        for (int x : costs.values()) {
            res = Math.max(res, x);
 
        }
        return res;
    }
}
 
class Cell implements Comparable<Cell> {
 
    int node, time;
 
    Cell(int node, int time) {
        this.node = node;
        this.time = time;
    }
 
    @Override
    public int compareTo(Cell c2) {
        return time - c2.time;
    }
}

39.LeetCode127_单词接龙(wordladder)_java实现

package com.leetcode;
 
import java.util.*;
 
/**
 * LeetCode127_单词接龙
 */
public class LeetCode127 {
 
    /**
     * step1.构建图
     *
     * @param wordList
     * @return
     */
    private Map<String, List<String>> constructGraph(List<String> wordList) {
        Map<String, List<String>> graph = new HashMap<>();
        int n = wordList.size();
 
        //遍历单词列表
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                String w1 = wordList.get(i), w2 = wordList.get(j);
 
                //如果word1,word2有一个字母变更，则把w1和w2连接成一条边
                if (oneChangeAway(w1, w2)) {
 
                    //因为是无向图可以互连，w1->w2,w2->w1
                    graph.computeIfAbsent(w1, k -> new ArrayList<>()).add(w2);
                    graph.computeIfAbsent(w2, k -> new ArrayList<>()).add(w1);
                }
            }
        }
        return graph;
    }
 
    /**
     * 比较单词w1与w2之间的差异
     *
     * @param w1
     * @param w2
     * @return
     */
    private boolean oneChangeAway(String w1, String w2) {
        int diff = 0;
        for (int i = 0; i < w1.length(); i++) {
            char c1 = w1.charAt(i), c2 = w2.charAt(i);
            if (c1 != c2) {
                diff++;
            }
        }
        return diff == 1;//判断是否只有一个字符差异
    }
 
    /**
     * 实现方法：构建图，利用BFS从起点到终点的最短路径
     *
     * @param beginWord
     * @param endWord
     * @param wordList
     * @return
     */
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        //1.判断结尾单词是否在单词列表
        if (!wordList.contains(endWord)) {
            return 0;
        }
 
        //2.判断开始单词是否包含在列表，没有则添加beginword,方便创建图
        if (!wordList.contains(beginWord)) {
            wordList.add(beginWord);
        }
 
        //3.构建图
        Map<String, List<String>> grap = constructGraph(wordList);
 
        //4.利用BFS从起点找到终点的最短路径
        Set<String> visited = new HashSet<>();//记录图中单词是否已经被访问过
        Queue<String> queue = new LinkedList<>();//初始化队列
        visited.add(beginWord);
        queue.add(beginWord);
        int cost = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();//获取当前层的单词数量
            //遍历当前层的单词
            for (int i = 0; i < size; i++) {
                String cur = queue.poll();//获取单词
                if (cur.equals(endWord)) {//查找endword
                    return cost;
                }
 
                //遍历邻接节点,未被访问且有效的节点添加到队列，标记未已经访问
                for (String neighbor : grap.getOrDefault(cur, new ArrayList<>())) {
                    if (!visited.contains(neighbor)) {
                        queue.offer(neighbor);
                        visited.add(neighbor);
                    }
                }
            }
            cost++;
        }
        return 0;//没有
    }
 
}

40.LeetCode542_01矩阵_java实现

package com.leetcode;
 
import java.util.LinkedList;
import java.util.Queue;
 
/**
 * LeetCode542_01矩阵
 */
public class LeetCode542 {
    int[][] dirs = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
 
    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        int[][] res = new int[m][n];
 
        boolean[][] visited = new boolean[m][n];
        Queue<int[]> queue = new LinkedList<>();
 
        //初始化矩阵
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) {
                    queue.offer(new int[]{i, j});
                    visited[i][j] = true;
                }
            }
        }
 
        int cost = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int s = 0; s < size; s++) {
                int[] cur = queue.poll();
                int i = cur[0], j = cur[1];
                if (mat[i][j] == 1) {
                    res[i][j] = cost;
                }
 
                for (int[] dir : dirs) {
                    int x = i + dir[0], y = j + dir[1];
                    if (x >= 0 && x < m && y >= 0 && y < n && !visited[x][y]) {//判断矩阵是否出界以及节点是否已经被访问过
                        queue.offer(new int[]{x, y});
                        visited[x][y] = true;
                    }
                }
            }
            cost++;
        }
        return res;
 
    }
}

41.LeetCode129_求根节点到叶节点数字之和_java实现

package com.leetcode;
 
/**
 * LeetCode129_求根节点到叶节点数字之和
 */
public class LeetCode129 {
    int sum = 0;
 
    /**
     * 采用DFS实现
     *
     * @param root
     * @return
     */
    public int sumNumbers(TreeNode root) {
        if (root == null) {
            return 0;
        }
        dfs(root, 0);
        return sum;
    }
 
    private void dfs(TreeNode root, int num) {
        num = num * 10 + root.val;//节点进行一个concat操作
 
        if (root.left == null && root.right == null) {
            sum += num;//更新sum
            return;
        }
 
        if (root.left != null) {//向左递归
            dfs(root.left, num);
        }
        if (root.right != null) {
            dfs(root.right, num);
        }
    }
}

42.LeetCode124_二叉树中的最大路径和_java实现

package com.leetcode;
 
 
/**
 * LeetCode124_二叉树中的最大路径和
 */
public class LeetCode124 {
    int max = Integer.MIN_VALUE;
 
    /**
     * 采用深度优先算法实现
     * @param root
     * @return
     */
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return max;
    }
 
    private int dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }
 
        int left = dfs(node.left);
        int right = dfs(node.right);
 
        left = left < 0 ? 0 : left;
        right = right < 0 ? 0 : right;
 
        max = Math.max(max, left + right + node.val);//更新全局max值
        return Math.max(left + node.val, right + node.val);//更新当前层的答案
    }
}

43.leetcode199_二叉树的右视图_java实现

package com.leetcode;
 
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
 
/**
 * LeetCode199_二叉树的右视图
 */
public class LeetCode199 {
 
    /**
     *方法： tree的广度优先BFS实现
     * @param root
     * @return
     */
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res=new ArrayList<>();
 
        if(root==null){
            return res;
        }
 
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
 
        while (!queue.isEmpty()){
            int size=queue.size();
            res.add(queue.peek().val);//获取当前层中最右边的节点
 
            for(int i=0;i<size;i++){
                TreeNode cur=queue.poll();
                //从右往左添加节点
                if(cur.right!=null){
                    queue.offer(cur.right);
                }
                if(cur.left!=null){
                    queue.offer(cur.left);
                }
            }
        }
        return  res;
    }
}

44.LeetCode23_合并k个升序链表_java实现

package com.leetcode;
 
import java.util.PriorityQueue;
 
/**
 * LeetCode23_合并k个升序链表
 */
public class LeetCode23 {
    public ListNode mergeKLists(ListNode[] lists) {
        //定义小顶堆
        PriorityQueue<ListNode> heap=new PriorityQueue<>((a,b)->a.val-b.val);
 
        for (ListNode list : lists) {
            if(list!=null){
                heap.offer(list);
            }
        }
 
        ListNode res=new ListNode(0),cur=res;
        while (!heap.isEmpty()){
            ListNode top=heap.poll();//拿出堆顶元素
            cur.next=top;
            cur=cur.next;
            if(top.next!=null){
                heap.offer(top.next);
            }
        }
 
        return res.next;
    }
}

45. LeetCode739_每日温度_java实现

package com.leetcode;
 
 
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;
 
/**
 * LeetCode739_每日温度
 */
public class LeetCode739 {
    /**
     * 采用栈实现
     *
     * @param temperatures
     * @return
     */
    public static int[] dailyTemperatures(int[] temperatures) {
        //定义栈
        Stack<Integer> stack = new Stack<>();
        int length = temperatures.length;
        int[] result = new int[length];
 
        //遍历温度数组
        for (int i = 0; i < length; i++) {
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int pre = stack.pop();
                result[pre] = i - pre;//求下标差=当前下标-栈顶元素的数
            }
            stack.add(i);
        }
 
        return result;
    }
 
    public static int[] dailyTemperatures2(int[] temperatures) {
        int n = temperatures.length;
        int[] res = new int[n];
 
        //定义栈，所有的元素从右向左遍历
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && temperatures[i] >= temperatures[stack.peek()]) {//栈顶元素小于等于当前元素
                stack.pop();
            }
 
            if (stack.isEmpty()) {
                res[i] = 0;
            } else {
                res[i] = stack.peek() - i;//计算差距=栈顶-当前元素
            }
            stack.push(i);
 
        }
        return res;
    }
}

46. LeetCode380_O(1)时间插入、删除和获取随机元素_java实现

package com.leetcode;
 
 
import java.util.*;
 
/**
 * LeetCode380_O(1)时间插入、删除和获取随机元素
 * <p>
 * 实现方法：变长数组+哈希表
 * 为了满足插入、删除和获取随机元素操作的时间复杂度都是 O(1)，
 * 需要将变长数组和哈希表结合，变长数组中存储元素，
 * 哈希表中存储每个元素在变长数组中的下标。
 */
public class LeetCode380 {
    List<Integer> nums;
    Map<Integer, Integer> indices;
 
    Random random;
 
    /**
     * 初始化
     */
    public LeetCode380() {
        nums = new ArrayList<>();
        indices = new HashMap<>();
        random = new Random();
    }
 
    /**
     * 当元素 val 不存在时，向集合中插入该项，
     * 并返回 true ；否则，返回 false 。
     *
     * @param val
     * @return
     */
    public boolean insert(int val) {
        if (indices.containsKey(val)) {
            return false;
        }
        int index = nums.size();
        nums.add(val);
        indices.put(val, index);
        return true;
    }
 
    /**
     * 当元素 val 存在时，从集合中移除该项，
     * 并返回 true ；否则，返回 false 。
     *
     * @param val
     * @return
     */
    public boolean remove(int val) {
        if (!indices.containsKey(val)) {
            return false;
        }
        int index = indices.get(val);
        int last = nums.get(nums.size() - 1);
        nums.set(index, last);
        indices.put(last, index);
        nums.remove(nums.size()-1);
        indices.remove(val);
        return true;
    }
 
    /**
     *随机返回现有集合中的一项,每个元素应该有相同的概率被返回。
     *
     * @return
     */
    public int getRandom() {
        int randomIndex = random.nextInt(nums.size());
        return nums.get(randomIndex);
    }
}

47. LeetCode1062_最长重复子串 _java实现

package com.leetcode;
 
import java.util.HashSet;
import java.util.Set;
 
/**
 * LeetCode1062_最长重复子串
 */
public class LeetCode1062 {
	public static int longestRepeatingSubString(String s) {
		int l = 0, r = s.length() - 1;
		while (l < r) {
			int mid = l + (r - l + 1) / 2;
			if (f(s, mid)) {
				l = mid;
			} else {
				r = mid - 1;
			}
		}
		return l;
	}
 
	private static boolean f(String s, int length) {
		Set<String> seen = new HashSet<>();// 查重
 
		for (int i = 0; i <= s.length() - length; i++) {
			int j = i + length - 1;
			String sub = s.substring(i, j + 1);
			if (seen.contains(sub)) {
				return true;
			}
			seen.add(sub);
		}
		return false;
	}
 
	public static void main(String[] args) {
		String str1 = "abcd";
		System.out.println("result:" + longestRepeatingSubString(str1));
 
		String str2 = "abbaba";
		System.out.println("result:" + longestRepeatingSubString(str2));
 
		String str3 = "aabcaabdaab";
		System.out.println("result:" + longestRepeatingSubString(str3));
 
		String str4 = "aaaaa";
		System.out.println("result:" + longestRepeatingSubString(str4));
 
	}
}

48. LeetCode344_翻转字符串_反向双指针_java实现

package com.leetcode;
 
 
/**
 * LeetCode344_翻转字符串
 */
public class LeetCode344 {
    /**
     * 解题思路：
     * 反向双指针
     *
     * @param s
     */
    public static void reverseString(char[] s) {
        int i = 0, j = s.length - 1;//1.初始化双指针
        while (i < j) {//2.确定判断条件
            char tmp = s[i];
            s[i] = s[j];
            s[j] = tmp;
 
            //3.移动双指针的位置
            i++;
            j--;
        }
        for (char c : s) {
            System.out.println("##:" + c);
        }
 
 
    }
 
    public static void main(String[] args) {
        char[] s = {'h', 'e', 'l', 'l', 'o'};
        reverseString(s);
    }
}

49.LeetCode530_二叉搜索树的最小绝对差_java实现

package com.leetcode;
 
/**
 * LeetCode530_二叉搜索树的最小绝对差
 * 思路分析：
 * 考虑对升序数组 a 求任意两个元素之差的绝对值的最小值，答案一定为相邻两个元素之差的最小值
 */
public class LeetCode530 {
    int pre;
    int res;
 
    /**
     * 中序遍历
     * <p>
     * 中序遍历得到的值序列是递增有序的;
     *
     * @param root
     * @return
     */
    public int getMinimumDifference(TreeNode root) {
        res = Integer.MAX_VALUE;
        pre = -1;
        dfs(root);
        return res;
    }
 
    private void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
 
        dfs(root.left);//左
 
        //根
        if (pre == -1) {
            pre = root.val;
        } else {
            res = Math.min(res, root.val - pre);
            pre = root.val;
        }
 
        //右
        dfs(root.right);
 
    }
}

50.LeetCode415_字符串相加_java实现

package com.leetcode;
 
/**
 * LeetCode415_字符串相加
 */
public class LeetCode415 {
    public String addStrings(String num1, String num2) {
        StringBuilder sb = new StringBuilder();
        //记录进位的变量
        int carry = 0;
 
        //从尾部遍历， 从右边向左边加求和
        for (int i = num1.length() - 1, j = num2.length() - 1; i >= 0 || j >= 0 || carry == 1; i--, j--) {
 
            int x = i < 0 ? 0 : num1.charAt(i) - '0';//获取实际要处理的字符
            int y = j < 0 ? 0 : num2.charAt(j) - '0';
            sb.append((x + y + carry) % 10);
            carry = (x + y + carry) / 10;//
        }
        return sb.reverse().toString();//翻转获取结果，
    }
}

51.LeetCode461_汉明距离_java实现

package com.leetcode;
 
/**
 * LeetCode461_汉明距离
 * 两个整数之间的汉明距离 指的是这两个数字对应二进制位不同的位置的数目。
 * <p>
 * 给你两个整数 x 和 y，计算并返回它们之间的汉明距离。
 * <p>
 * 示例 1：
 * <p>
 * 输入：x = 1, y = 4
 * 输出：2
 * 解释：
 * 1   (0 0 0 1)
 * 4   (0 1 0 0)
 * ↑   ↑
 * 上面的箭头指出了对应二进制位不同的位置。
 * 示例 2：
 * <p>
 * 输入：x = 3, y = 1
 * 输出：1
 * <p>
 * 提示：
 * 0 <= x, y <= 231 - 1
 */
public class LeetCode461 {
    /**
     * java内置位计数功能
     *
     * @param x
     * @param y
     * @return
     */
    public int hammingDistance(int x, int y) {
        return Integer.bitCount(x ^ y);
    }
 
    /**
     * 采用异或
     *
     * @param x
     * @param y
     * @return
     */
    public int hammingDistance2(int x, int y) {
        int distance = 0;
        for (int xor = x ^ y; xor != 0; xor &= (xor - 1)) {
            distance++;
        }
        return distance;
    }
}

52.LeetCode338_比特位计数_java实现

package com.leetcode;
 
/**
 * LeetCode338_比特位计数
 */
public class LeetCode338 {
    /**
     * 使用位运算
     *
     * @param n
     * @return
     */
    public int[] countBits(int n) {
        int[] bits = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            bits[i] = bits[i & (i - 1)] + 1;
        }
        return bits;
    }
 
    /**
     * 使用奇偶性
     *
     * @param n
     * @return
     */
    public int[] countBits2(int n) {
        int[] bits = new int[n + 1];
        bits[0] = 0;
        for (int i = 1; i <= n; i++) {
            bits[i] = ((i & 1) == 1 ? bits[i - 1] + 1 : bits[i >> 1]);
        }
        return bits;
    }
}

53.LeetCode67_二进制求和_java实现

package com.leetcode;
 
/**
 * LeetCode67_二进制求和
 */
public class LeetCode67 {
    /**
     * 双指针
     *
     * @param a
     * @param b
     * @return
     */
    public String addBinary(String a, String b) {
        StringBuffer sb = new StringBuffer();
 
        //定义双指针i,j,从尾部开始，类似求和计算规律从右侧开始一样
        int i = a.length() - 1, j = b.length() - 1;
 
        int carry = 0;//初始化进位为0
 
        while (i >= 0 || j >= 0) {
            int sum = carry;
            if (j >= 0) {
                sum += b.charAt(j--) - '0';//减0获取字符的整数值从ascii中
            }
            if (i >= 0) {
                sum += a.charAt(i--) - '0';
            }
 
            sb.append(sum % 2);//二进制，除以2，取余数
            carry = sum / 2;//取进位数
        }
        if (carry != 0) {//判断进位的非零，添加进位
            sb.append(carry);
        }
 
        return sb.reverse().toString();
 
    }
}

54.LeetCode100_相同的树_java实现

package com.leetcode;
 
/**
 * LeetCode100_相同的树
 * <p>
 * 思路分析：
 * 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的
 */
public class LeetCode100 {
    /**
     * 深度优先搜索（DFS）
     *
     * @param p
     * @param q
     * @return
     */
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //1.两颗树都为空，则是相同的树
        if (p == null && q == null) {
            return true;
        } else if (p == null || q == null) { //2.如果任意一颗树为null,则不是相同的树
            return false;
        } else if (p.val != q.val) {
            return false;
        } else {
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }
    }
}

55.LeetCode383_赎金信_java实现

package com.leetcode;
 
 
/**
 * LeetCode383_赎金信
 *
 *
 * 给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
 * 如果可以，返回 true ；否则返回 false 。
 * magazine 中的每个字符只能在 ransomNote 中使用一次。
 *
 * 示例 1：
 *
 * 输入：ransomNote = "a", magazine = "b"
 * 输出：false
 * 示例 2：
 *
 * 输入：ransomNote = "aa", magazine = "ab"
 * 输出：false
 * 示例 3：
 *
 * 输入：ransomNote = "aa", magazine = "aab"
 * 输出：true
 */
public class LeetCode383 {
    /**
     * 哈希映射数组
     * @param ransomNote
     * @param magazine
     * @return
     */
    public static boolean canConstruct(String ransomNote, String magazine) {
        //1.定义哈希映射数组
        int[] record=new int[26];
 
        //2.遍历
        for (char c:magazine.toCharArray()) {
        record[c-'a']+=1;
        }
 
        for(char c:ransomNote.toCharArray()){
            record[c-'a']-=1;
        }
 
        //如果数组中存在负数，说明ransomNote字符串总存在magazine中没有的字符
        for(int i:record){
            if(i<0){
                return false;
            }
        }
 
        return true;
    }
 
    public static void main(String[] args) {
        System.out.println("canConstruct(\"a\",\"b\") = " + canConstruct("aa", "ab"));
    }
}

56.LeetCode242_有效的字母异位词_java实现

package com.leetcode;
 
/**
 * LeetCode242_有效的字母异位词
 * <p>
 * 示例 1:
 * <p>
 * 输入: s = "anagram", t = "nagaram"
 * 输出: true
 * <p>
 * 示例 2:
 * <p>
 * 输入: s = "rat", t = "car"
 * 输出: false
 * <p>
 * <p>
 * 提示:
 * <p>
 * 1 <= s.length, t.length <= 5 * 104
 * s 和 t 仅包含小写字母
 */
public class LeetCode242 {
    /**
     * 哈希映射
     *
     * @param s
     * @param t
     * @return
     */
    public boolean isAnagram(String s, String t) {
        //1.判断两个字符串是否相等，不相等则直接返回false
        if (s.length() != t.length()) {
            return false;
        }
        //2.初始化26个字母哈希表，遍历字符串s和t
        int[] alpha = new int[26];
        for (int i = 0; i < s.length(); i++) {
            alpha[s.charAt(i) - 'a']++;//s,对应位置加
            alpha[t.charAt(i) - 'a']--;//t,对应位置减少        }
        }
 
 
        //3.如果哈希表的值都为0，则s与t是字母异位词
        for (int i = 0; i < 26; i++) {
            if (alpha[i] != 0) {
                return false;
            }
        }
        return true;
    }
}

57.LeetCode172_阶乘后的零_java实现

package com.leetcode;
 
/**
 * LeetCode172_阶乘后的零
 */
public class LeetCode172 {
 
    /**
     * 统计被5整除的个数
     *
     * @param n
     * @return
     */
    public static int trailingZeroes(int n) {
        int count = 0;
        while (n > 0) {
            n /= 5;
            count += n;
        }
        return count;
    }
 
    public static void main(String[] args) {
        System.out.println("trailingZeroes(3) = " + trailingZeroes(0));
    }
}

58.LeetCode69_x的平方根_java实现

package com.leetcode;
 
 
/**
 * LeetCode69_x的平方根
 */
public class LeetCode69 {
    /**
     * 袖珍计算器法
     *
     * @param x
     * @return
     */
    public static int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
 
        int res = (int) Math.exp(0.5 * Math.log(x));
        return (long) (res + 1) * (res + 1) <= x ? res + 1 : res;
    }
 
    /**
     * 二分查找
     *
     * @param x
     * @return
     */
    public static int mySqrt2(int x) {
        int left = 0, right = x, res = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if ((long) mid * mid <= x) {
                res = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return res;
    }
 
    /**
     * 牛顿迭代（一种用来快速求解函数零点的方法；c的平方根就是y=f(x)=x*x-c）
     *
     * @param x
     * @return
     */
    public static int mySqrt3(int x) {
        if (x == 0) {
            return 0;
        }
 
        double C = x, x0 = x;
        while (true) {
            double xi = 0.5 * (x0 + C / x0);
            if (Math.abs(x0 - xi) < 1e-7) {
                break;
            }
            x0 = xi;
        }
        return (int) x0;
 
    }
 
    public static int mySqrt4(int x) {
        long a = 0;
        for (long i = 0; i * i <= x; i++) {
            a = i;
        }
        return (int) a;
    }
 
    public static void main(String[] args) {
        System.out.println("%%%:" + mySqrt4(9));
 
    }
}

59.LeetCode167_两数之和 II - 输入有序数组_java实现

package com.leetcode;
 
/**
 * LeetCode167_两数之和 II - 输入有序数组
 */
public class LeetCode167 {
    /**
     * 采用相向双指针
     *
     * @param numbers
     * @param target
     * @return
     */
    public static int[] twoSum(int[] numbers, int target) {
        //定义双指针left,right;
        int left = 0;
        int right = numbers.length - 1;
        while (left < right) {
            int res = numbers[left] + numbers[right];
            if (res == target) {
                return new int[]{left + 1, right + 1};//题目要求下班从1开始
            }
 
            if (res > target) {
                right--;//向左移动1位
            } else {
                left++;//向右移动1位
            }
        }
        return null;
 
    }
 
    public static void main(String[] args) {
       // int[]numbers = {2,7,11,15};
        int[]numbers = {-1,0};
       int[] result= twoSum(numbers,-1);
        for (int i : result) {
            System.out.println("$$$:"+i);
        }
 
    }
 
}

60.LeetCode28_找出字符串中第一个匹配项的下标_java实现

package com.leetcode;
 
/**
 * LeetCode28_找出字符串中第一个匹配项的下标
 */
public class LeetCode28 {
    /**
     * 方法1：使用java api实现
     *
     * @param haystack
     * @param needle
     * @return
     */
    public static int strStr1(String haystack, String needle) {
        if (haystack.contains(needle)) {
            return haystack.indexOf(needle);
        }
        return -1;
 
    }
 
 
 
    public static void main(String[] args) {
        System.out.println("strStr1() = " + strStr1("sadbutsad", "sad"));
    }
}

61.LeetCode14_最长公共前缀_java实现

package com.leetcode;
 
/**
 * LeetCode14_最长公共前缀
 */
public class LeetCode14 {
    /**
     * @param strs
     * @return
     */
    public String longestCommonPrefix(String[] strs) {
        //1.字符串数组为空，直接返回空字符串
        if (strs == null || strs.length == 0) {
            return "";
        }
 
        //2.初始化公共前缀为第一个字符串
        String commonPrefix = strs[0];
 
        //3.遍历剩余的字符串
        for (int i = 1; i < strs.length; i++) {
            //4.比较当前字符串与当前最长公共前缀，更新最长公共前缀
            commonPrefix = getCommonPrefix(commonPrefix, strs[i]);
 
            //5.如果最长公共前缀已经为空，直接返回
            if (commonPrefix.equals("")) {
                return "";
            }
        }
 
        return commonPrefix;//不为空，返回最长公共前缀
    }
 
    /**
     * 获取两个字符串的公共前缀
     *
     * @param str1
     * @param str2
     * @return
     */
    private String getCommonPrefix(String str1, String str2) {
        int index = 0;
        //查找两个字符串的公共前缀的长度
        while (index < str1.length() && index < str2.length() && str1.charAt(index) == str2.charAt(index)) {
            index++;
        }
 
        return str1.substring(0, index);//返回公共前缀
    }
}

62.LeetCode66_加1_java实现

package com.leetcode;
 
/**
 * LeetCode66_加一
 */
public class LeetCode66 {
    public int[] plusOne(int[] digits) {
        for (int i = digits.length - 1; i >= 0; i--) {
            //逢9改为0，不是9加1
            if (digits[i] == 9) {
                digits[i] = 0;
            } else {
                digits[i] += 1;
                return digits;
            }
        }
        //如果全进位，则数组长度+1，且第一位元素设置为1
        digits = new int[digits.length + 1];
        digits[0] = 1;
        return digits;
    }
}

63.LeetCode392_判断子序列_java实现

package com.leetcode;
 
/**
 * LeetCode392_判断子序列
 */
public class LeetCode392 {
    /**
     * 双指针实现
     *
     * @param s
     * @param t
     * @return
     */
    public boolean isSubsequence(String s, String t) {
        int i = 0, j = 0;//定义指针i,和j
        while (i < s.length() && j < t.length()) {
            if (s.charAt(i) == t.charAt(j)) {//如果s中字符与t中子字符匹配了，i++
                i++; //右移动
            }
            j++;//无论匹配与否右移
        }
        return i == s.length();//如果s==s.lenght(),则i移动到s的末尾，说明s是t的子序列
    }
}

64.LeetCode105_从前序与中序遍历序列构造二叉树_java实现

package com.leetcode;
 
import java.util.HashMap;
 
/**
 * LeetCode105_从前序与中序遍历序列构造二叉树
 */
public class LeetCode105 {
    public TreeNode13 buildTree(int[] preorder, int[] inorder) {
 
        //把中序遍历数组的每个元素的值和下标存起来，方便直接寻找根节点的位置
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
 
        return buildTreeHelper(preorder, 0, preorder.length, inorder, 0, inorder.length, map);
    }
 
    private TreeNode13 buildTreeHelper(int[] preorder, int pStart, int pEnd, int[] inorder, int iStart, int iEnd, HashMap<Integer, Integer> map) {
        if (pStart == pEnd) {
            return null;
        }
        int rootVal = preorder[pStart];
        TreeNode13 root = new TreeNode13(rootVal);
        int iRootIndex = map.get(rootVal);
        int leftNum = iRootIndex - iStart;
        root.left = buildTreeHelper(preorder, pStart + 1, pStart + leftNum + 1, inorder, iStart, iRootIndex, map);
        root.right = buildTreeHelper(preorder, pStart + leftNum + 1, pEnd, inorder, iRootIndex + 1, iEnd, map);
        return root;
    }
}
 
 
class TreeNode13 {
    int val;
    TreeNode13 left;
    TreeNode13 right;
 
    TreeNode13() {
    }
 
    TreeNode13(int val) {
        this.val = val;
    }
 
    TreeNode13(int val, TreeNode13 left, TreeNode13 right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

65.LeetCode230_二叉搜索树中第k小的元素_java实现

package com.leetcode;
 
import java.util.ArrayDeque;
import java.util.Deque;
 
/**
 * LeetCode230_二叉搜索树中第k小的元素
 */
public class LeetCode230 {
    /**
     * 采用中序遍历
     *
     * @param root
     * @param k
     * @return
     */
    public int kthSmallest(TreeNode12 root, int k) {
        Deque<TreeNode12> stack = new ArrayDeque<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            k--;
            if (k == 0) {
                break;
            }
            root = root.right;
        }
        return root.val;
    }
}
 
class TreeNode12 {
    int val;
    TreeNode12 left;
    TreeNode12 right;
 
    TreeNode12() {
    }
 
    TreeNode12(int val) {
        this.val = val;
    }
 
    TreeNode12(int val, TreeNode12 left, TreeNode12 right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}