LeetCode刷题笔记

[TOC]

LeetCode刷题笔记（现仅供参考。。。）

---

岛屿问题

//    给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
//    岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
//    此外，你可以假设该网格的四条边均被水包围。
    public int algo8(char[][] grid) {
        //DPS
//        遍历数组中的每一个值，如果是1就说明是岛屿，然后把它
//    置为0或者其他的字符都可以，只要不是1就行，然后再遍历他的上下左右4个位置。
//        如果是1，说明这两个岛屿是连着的，只能算是一个岛屿，我们还要把它置为0，然后再以它为
//    中心遍历他的上下左右4个位置……。如果是0，就说明不是岛屿，就不在往他的上下左右4个位置遍历了。
        //遍历原则，下-右-上-左
        if (grid == null) {
            return 0;
        }
        int res = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    dfs(i, j, grid);
                    res += 1;
                }
            }
        }
        return res;
    }

    public void dfs(int i, int j, char[][] grid) {
        if (i<0||i>=grid.length||j<0||j>=grid[0].length||grid[i][j] == '0' {
          return;
        }
         grid[i][j] = '0';
         dfs(i + 1, j, grid);
         dfs(i, j + 1, grid);
         dfs(i - 1, j, grid);
         dfs(i, j - 1, grid);
    }
    //如果用这种方式些，运行时间会变长
    public void dfs(int i, int j, char[][] grid) {
        if (i>=0&&i<grid.length&&j>=0&&j<grid[0].length&&grid[i][j] == '1' {
           grid[i][j] = '0';
           dfs(i + 1, j, grid);
           dfs(i, j + 1, grid);
           dfs(i - 1, j, grid);
           dfs(i, j - 1, grid);
        }
    }
            

转盘锁

//    你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。
//
//    锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。
//
//    列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。
//
//    字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。
//    下面是自己写的，太逊了，时间开销太长了，而且还没有考虑重复节点，会陷入死循环
    public int algo9(String[] strs,String target){
        if(strs==null||target==null){
            return -1;
        }
        int res=0;
        String str="0000";
        if(str!=target) {
            dfs1(strs, target, str, res);
        }
        return res;
    }

    public void dfs1(String[] strs,String target,String str,int res){
        for(int i=0;i<str.length();i++){
            if(i!=0){
                res-=1;
            }
            String add="";
            add+=str.substring(0,i);
            char ch=str.charAt(i);
            add+=(ch=='9')?'0':(ch-'0'+1);
            add+=str.substring(i+1);
            if(!isLegal1(strs,add)){
                continue;
            }
            res+=1;
            if(add==target){
                break;
            }
            else {
                dfs1(strs,target,add,res);
            }
        }
    }

    public boolean isLegal1(String[] strs,String str){
        for(String rec:strs){
            if(rec==str)return false;
        }
        return true;
    }

    //    如下标答
    public int openLock(String[] deadends,String target){
        Set<String> set=new HashSet<>(Arrays.asList(deadends));
        Set<String> visited=new HashSet<>();//保存已经访问过的节点，防止陷入死循环
        Queue<String> queue =new LinkedList<>();//保存当前层的各个节点
        String startStr="0000";
        int level=0;
        queue.offer(startStr);
        while(!queue.isEmpty()){
            int size= queue.size();
            while(size-->0){
                String str= queue.poll();
                if(str.equals(target)){
                    return level;
                }
                for(int i=0;i<target.length();i++){
                    char ch=str.charAt(i);
                    String strAdd=str.substring(0,i)+((ch=='9')?'0':ch-'0'+1)+str.substring(i+1);
                    String strSub=str.substring(0,i)+((ch=='0')?'9':ch-'0'-1)+str.substring(i+1);
                    if(!visited.contains(strAdd)&&!set.contains(strAdd)){//如果已经访问过或是死亡组合，均不能添加
                        queue.offer(strAdd);
                    }
                    if(!visited.contains(strSub)&&!set.contains(strSub)){
                        queue.offer(strSub);
                    }
                }
            }
            level+=1;
        }
        return level;
    }

合法的字符串

 //    给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
//
//    有效字符串需满足：
//
//    左括号必须用相同类型的右括号闭合。
//    左括号必须以正确的顺序闭合。
    public static boolean isValid(String s) {
        Stack<Character> stack=new Stack<>();
        int i=0;
        while(i<s.length()){
            char ch=s.charAt(i);
            i+=1;
            if(ch=='('||ch=='['||ch=='{'){
                stack.push(ch);
            }else{
                if(stack.isEmpty()){
                    return false;
                }else{
                    char head=stack.pop();
                    if((head=='['&&ch==']')||(head=='('&&ch==')')||(head=='{'&&ch=='}')){
                        continue;
                    }else{
                        return false;
                    }
                }
            }
        }
        if(stack.isEmpty()){
            return true;
        }else{
            return false;
        }
    }

更高的温度

//    给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指在第 i 天之后，才会
//    有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。
//    输入: temperatures = [73,74,75,71,69,72,76,73]
//    输出: [1,1,4,2,1,1,0,0]
    public int[] dailyTemperatures(int[] temperatures) {
        //重点是：stack存放的是各个温度对应的下标而不是温度，这样的就根据下标在res中找到位置，
        //如果存放的是温度，依然可以比较温度大小，但比较后的res的值以及对应的下标都不知道
        Stack<Integer> stack=new Stack<>();
        int[] res=new int[temperatures.length];
        for(int i=0;i<temperatures.length;i++){
            while(!stack.isEmpty()&&temperatures[i]>temperatures[stack.peek()]){
                res[stack.peek()]=i-stack.peek();
                stack.pop();
            }
            stack.push(i);
        }
        return res;
    }

逆波兰表达式求值

 //    根据 逆波兰表示法，求表达式的值。
//    输入：tokens = ["2","1","+","3","*"]
//    输出：9
//    解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
*/
    public static int evalRPN(String[] tokens) {
        Stack<String> stack=new Stack<>();
        for(int i=0;i<tokens.length;i++){
            if(!tokens[i].equals("*")&&!tokens[i].equals("/")&&!tokens[i].equals("+")&&!tokens[i].equals("-")){
                stack.push(tokens[i]);
            }else {
                int a=Integer.parseInt(stack.pop());
                int b=Integer.parseInt(stack.pop());
                if(tokens[i].equals("+")){
                    stack.push(Integer.toString(b+a));
                }else if(tokens[i].equals("-")){
                    stack.push(Integer.toString(b-a));
                }else if(tokens[i].equals("*")){
                    stack.push(Integer.toString(b*a));
                }else if(tokens[i].equals("/")){
                    stack.push(Integer.toString(b/a));
                }
            }
        }
        return Integer.parseInt(stack.peek());
    }

图的深度克隆

/**
//   给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。
//    图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。
//    class Node {
//        public int val;
          public List<Node> neighbors;
//    }
 */

    public Node cloneGraph(Node node) {
        return clone(node,new HashMap<>());
    }

    public Node clone(Node node,HashMap<Integer,Node> visited){
        if(node==null){
            return null;
        }
        if(visited.containsKey(node.val)){
            return visited.get(node.val);
        }
        Node newNode=new Node(node.val,new ArrayList<>());
        visited.put(newNode.val,newNode);
        for(Node each:node.neighbors){
            newNode.neighbors.add(clone(each,visited));
        }
        return node;
    }

    class Node {
        public int val;
        public List<Node> neighbors;
        public Node() {
            val = 0;
            neighbors = new ArrayList<Node>();
        }
        public Node(int _val) {
            val = _val;
            neighbors = new ArrayList<Node>();
        }
        public Node(int _val, ArrayList<Node> _neighbors) {
            val = _val;
            neighbors = _neighbors;
        }
    }

合法的数独

 /**
    请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

写完了下面的才记得可以用一个3*9*9的数组用一次遍历来做，大意了
     */
    public boolean isValidSudoku(char[][] board) {
        HashSet<Character> hashSet=new HashSet<>();
        for(int i=0;i<board.length;i++){
            for(int j=0;j<board[0].length;j++){
                if(hashSet.contains(board[i][j])&&board[i][j]!='.'){
                    return false;
                }else{
                    hashSet.add(board[i][j]);
                }
            }
            hashSet.clear();
        }
        for(int j=0;j<board.length;j++){
            for(int i=0;i<board[0].length;i++){
                if(hashSet.contains(board[i][j])&&board[i][j]!='.'){
                    return false;
                }else{
                    hashSet.add(board[i][j]);
                }
            }
            hashSet.clear();
        }
        for(int k=0;k<9;k++){
            for(int i=k/3*3;i<k/3*3+3;i++){
                for(int j=k%3*3;j<k%3*3+3;j++){
                    if(hashSet.contains(board[i][j])&&board[i][j]!='.'){
                        return false;
                    }else{
                        hashSet.add(board[i][j]);
                    }
                }
            }
            hashSet.clear();
        }
        return true;
    }

合并数组

/**
     * 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
     *
     * 请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
     *
     * 注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，
     * 其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
     */
    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] res=new int[m+n];
        int up=0;
        int down=0;
        int i=0;
        while(up<m&&down<n){
            if(nums1[up]<=nums2[down]){
                res[i]=nums1[up];
                up++;
            }else{
                res[i]=nums2[down];
                down++;
            }
            i++;
        }
        if(up==m){
            for(;down<n;down++,i++){
                res[i]=nums2[down];
            }
        }else if(down==n){
            for(;up<m;up++,i++){
                res[i]=nums1[up];
            }
        }
        nums1=res;
        for(i=0;i< nums1.length;i++){
            nums1[i]=res[i];
        }
    }

随机打乱数组

/**
     * 给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。打乱后，数组的所有排列应该是 等可能 的。
     *
     * 实现 Solution class:
     *
     * Solution(int[] nums) 使用整数数组 nums 初始化对象
     * int[] reset() 重设数组到它的初始状态并返回
     * int[] shuffle() 返回数组随机打乱后的结果
     */
    class Solution {
        private int[] nums=null;
        private int[] recoder=null;
        private int length;

        public Solution(int[] nums) {
            this.length=nums.length;
            this.nums=new int[length];
            this.recoder=new int[length];
            for(int i=0;i<length;i++){
                this.nums[i]=nums[i];
                this.recoder[i]=nums[i];
            }
        }

        public int[] reset() {
            if(nums==null)return null;
            for(int i=0;i<length;i++){
                this.nums[i]= recoder[i];
            }
            return nums;
        }

        public int[] shuffle() {
            if(nums==null)return null;
            for(int i=0;i<length-1;i++){
                int random=(int)(Math.random()*(length-i-1))+i+1;
                int sign=0;
                sign=nums[i];
                nums[i]=nums[random];
                nums[random]=sign;
            }
            return nums;
        }
    }

类atoi函数

/**
     * 请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。
     *
     * 函数 myAtoi(string s) 的算法如下：
     *
     * 读入字符串并丢弃无用的前导空格
     * 检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
     * 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
     * 将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
     * 如果整数数超过 32 位有符号整数范围 [−231,  231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
     * 返回整数作为最终结果。
     * 注意：
     *
     * 本题中的空白字符只包括空格字符 ' ' 。
     * 除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。
     */
    public static int myAtoi(String s) {
        int off=0;
        int length=0;
        boolean sign=false;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='-'||(s.charAt(i)-'0'<10&&s.charAt(i)-'0'>=0)) {
                if(!sign)off=i;
                sign=true;
                length++;
            }
        }
        String s1 = new String(s.toCharArray(), off, length);
        return Integer.valueOf(s1).intValue();

    }

求算数平方根

/**
    * 给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
    *
    * 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
    *
    * 注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
    */
   public static int mySqrt(int x) {
       if(x==0){
           return 0;
       }
       int left=1;
       int right=x;
       while(left<=right){
           int mid = left + ((right - left) >> 1);
           if (mid == x / mid) {
               return mid;
           }
           // 两边*mid后: mid * mid < x, 利用除法代替乘法避免溢出
           else if (mid < x / mid) {
               left = mid + 1;
           } else {
               right = mid - 1;
           }
       }
       return right;
   }

三数之和（15）

/**
     * 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，
     * 使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
     * <p>
     * 注意：答案中不可以包含重复的三元组。
     * 思路：先确定一个数，再找另外另外两个数使其和等于0
     * 每次都从certain之后的数里找，就可以防止重复
     */
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        if (nums.length < 3) {
            return list;
        }
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1])
                continue;
            if (nums[i] > 0)
                break;
            int certain = nums[i];
            int low = i + 1;
            int high = nums.length - 1;
            while (low < high) {
                int sum = nums[low] + nums[high] + certain;
                if (sum < 0) {
                    low++;
                    if (low == i || low == high) low++;
                } else if (sum > 0) {
                    high--;
                    if (high == i || high == low) high--;
                } else {
                    List<Integer> l = new ArrayList<>();
                    l.add(certain);
                    l.add(nums[low]);
                    l.add(nums[high]);
                    list.add(l);

                    //可能之后还有
                    low++;
                    high--;
                    while (low < high && nums[low] == nums[low - 1]) {
                        low++;
                    }
                    while (low < high && nums[high] == nums[high + 1]) {
                        high--;
                    }
                }
            }
        }
        return list;
    }

矩阵置零

/**
     * 给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
     * 你能想出一个仅使用常量空间的解决方案吗？
     *
     * @param
     */
    public void setZeroes(int[][] matrix) {
        //标记第一行是否有数字0
        boolean row = false;
        //标记第一列是否有数字0
        boolean col = false;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0) {
                    //如果第一行或者第一列本来就有0，就把他标记一
                    //下，最后再把第一行或者第一列全部置为0
                    if (i == 0)
                        row = true;
                    if (j == 0)
                        col = true;
                    //把最上面一行和最左边一列对应的位置标注为0
                    matrix[0][j] = matrix[i][0] = 0;
                }
            }
        }
        //把那些应该为0的行和列全部置为0
        for (int i = 1; i < matrix.length; i++) {
            for (int j = 1; j < matrix[0].length; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0)
                    matrix[i][j] = 0;
            }
        }
        //如果第一列本来就有0，把第一列全部变为0
        if (col) {
            for (int i = 0; i < matrix.length; i++)
                matrix[i][0] = 0;
        }
        //如果第一行本来就有0，把第一行全部变为0
        if (row) {
            for (int j = 0; j < matrix[0].length; j++)
                matrix[0][j] = 0;
        }
    }

字母异位词

/**
     * 给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
     * <p>
     * 字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。
     * <p>
     * 输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
     * 输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
     *
     * @param
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> list = new ArrayList<>();
        String[] newStrs = new String[strs.length];
        for (int i = 0; i < newStrs.length; i++) {
            char[] chs = newStrs[i].toCharArray();
            Arrays.sort(chs);
            String newStr = new String(chs);
            newStrs[i] = newStr;
        }
        int[] sign = new int[strs.length];
        for (int i = 0; i < newStrs.length; i++) {
            if (sign[i] == 0) {
                sign[i] = 1;
                List<String> list1 = new ArrayList<>();
                list1.add(strs[i]);
                for (int j = i + 1; j < newStrs.length; j++) {
                    if (sign[j] == 0 && newStrs[j].equals(newStrs[i])) {
                        list1.add(strs[j]);
                        sign[j] = 1;
                    }
                }
                list.add(list1);
            }
        }
        return list;
    }

    //这个好，显得上面的我很呆
    public List<List<String>> groupAnagrams1(String[] strs) {
        if (strs == null || strs.length == 0)
            return new ArrayList<>();
        Map<String, List<String>> map = new HashMap<>();
        for (String s : strs) {
            // 将字符串转化为字符数组后排序
            char[] ch = s.toCharArray();
            Arrays.sort(ch);
            // 将排序后的字符串作为key
            String strKey = String.valueOf(ch);
            // 如果map中不存在排序后的字符串的key，创建一个list
            if (!map.containsKey(strKey))
                map.put(strKey, new ArrayList<>());
            // 将原字符串添加到key对应的列表中
            map.get(strKey).add(s);
        }
        return new ArrayList<>(map.values());
    }

不重复的最长字串

/**
    * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
    *
    * @param
    */
   //来一手刚学的正则表达式
   public static int lengthOfLongestSubstring(String s) {
       int low = 0;
       int high = s.length();
       int max = 0;
       int res = 0;
       String regex = "(.)\\1+";
       Pattern pattern = Pattern.compile(regex);
       Matcher matcher = pattern.matcher(s);

       while (matcher.find()) {
           res = matcher.start() - low;
           low = matcher.start() + matcher.group(0).length();
           max = (max > res) ? max : res;
       }
       res = high - low;
       max = (max > res) ? max : res;
       return max;
   }

递增子序列

/**
     * 给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。
     * <p>
     * 如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。
     * <p>
     * 循环求解不难
     * <p>
     * 实现时间复杂度为 O(n) ，空间复杂度为 O(1) 的解决方案
     *
     * @param
     */
    /**
     * 其实可以简化
     * 强啊
     *
     * @param
     */
    public boolean increasingTriplet1(int[] nums) {
        //3个数字，small记录最小的数字
        int small = Integer.MAX_VALUE;
        //mid记录中间的数字
        int mid = Integer.MAX_VALUE;
        for (int num : nums) {
            if (num <= small) {
                //记录遍历过的最小值
                small = num;
            } else if (num <= mid) {
                //记录比small大的最小值，也就是mid的值
                mid = num;
            } else {
                //mid如果赋值了，那么之前肯定有个比
                //mid小的值，这里又有个比mid大的值，
                //所以他们三个可以构成递增的三元子序列
                return true;
            }
        }
        return false;
    }

数字相加

/**
     * 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
     * <p>
     * 请你将两个数相加，并以相同形式返回一个表示和的链表。
     * <p>
     * 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
     */
    class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int isJinWei = 0;
        ListNode tail = new ListNode(0, null);
        ListNode res = new ListNode(0, tail);
        while (l1 != null || l2 != null || isJinWei == 1) {
            int val1 = (l1 == null) ? 0 : l1.val;
            int val2 = (l2 == null) ? 0 : l2.val;
            int val = (val1 + val2 + isJinWei) % 10;
            isJinWei = (val1 + val2 + isJinWei > 9) ? 1 : 0;
            ListNode newNode = new ListNode(val, null);
            tail.next = newNode;
            tail = newNode;
            l1 = (l1 == null) ? null : l1.next;
            l2 = (l2 == null) ? null : l2.next;
        }
        return res.next.next;
    }

奇偶链表合并

/**
     * 给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。
     * <p>
     * 第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。
     * <p>
     * 请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。
     * <p>
     * 你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。
     * 输入: head = [1,2,3,4,5]
     * 输出: [1,3,5,2,4]
     * <p>
     * 我们自然想到的是把奇数节点串到一起，我们称之为奇数链表，偶数节点串到一起，我们称之为偶数链表。最后再把偶数链表挂到奇数链表的后面即可。
     */
    class ListNode1 {
        int val;
        ListNode1 next;

        ListNode1() {
        }

        ListNode1(int val) {
            this.val = val;
        }

        ListNode1(int val, ListNode1 next) {
            this.val = val;
            this.next = next;
        }
    }

    public ListNode1 oddEvenList(ListNode1 head) {
        if (head == null) {
            return null;
        }
        ListNode1 oddHead = head;
        ListNode1 evenHead = head.next;
        ListNode1 node = null;
        ListNode1 next = head;
        while (next != null) {
            node = next;
            next = node.next;
            node.next = (next == null) ? null : next.next;
        }
        ListNode1 listNode1 = null;
        next = oddHead;
        while (next.next != null) {
            next = next.next;
        }
        next.next = evenHead;
        return oddHead;
    }

链表相交

/**
     * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
     * 整个链式结构中不存在环。
     * 注意，函数返回结果后，链表必须 保持其原始结构 。
     * <p>
     * 能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案
     */
    class ListNode2 {
        int val;
        ListNode2 next;

        ListNode2(int x) {
            val = x;
            next = null;
        }
    }
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
    
    //the way i to do
     public ListNode2 getIntersectionNode(ListNode2 headA, ListNode2 headB) {
        if (headA == null || headB == null) {
            return null;
        }
        HashSet<ListNode2> hashSet = new HashSet<>();
        ListNode2 nextA = headA;
        while (nextA != null) {
            hashSet.add(nextA);
            nextA = nextA.next;
        }
        ListNode2 nextB = headB;
        while (nextB != null) {
            if (hashSet.contains(nextB)) {
                return nextB;
            }
            nextB = nextB.next;
        }
        return null;
    }

可生成的所有字符串

/**
     * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
     *
     * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
     * 2:abc
     * 3:def
     * 4:ghi
     * 5:jkl
     * 6:mno
     * 7:pqrs
     * 8:tuv
     * 9:wxyz
     * @param
     */
    public List<String> letterCombinations(String digits) {
        List<String> list=new ArrayList<>();
        if(digits.equals(""))return list;
        String[] numberToChar=new String[]{"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        String add="";
        dfs1(digits,0,list,add,numberToChar);
        return list;
    }
    public void dfs1(String digits,int index,List<String> list,String add,String[] numberToChar){
        if(index+1<=digits.length()-1) {
            String str = numberToChar[digits.charAt(index) - '2'];
            for (int i = 0; i < str.length(); i++) {
                dfs1(digits, index + 1, list, add + str.charAt(i), numberToChar);
            }
        }else{
            String str = numberToChar[digits.charAt(index) - '2'];
            for (int i = 0; i < str.length(); i++) {
                list.add(add+str.charAt(i));
            }
        }
    }

所有的括号组合

/**
     * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
     *
     *  
     *
     * 示例 1：
     *
     * 输入：n = 3
     * 输出：["((()))","(()())","(())()","()(())","()()()"]
     * 示例 2：
     *
     *
     * 输入：n = 1
     * 输出：["()"]
     *
     * 作者：力扣 (LeetCode)
     * 链接：https://leetcode.cn/leetbook/read/top-interview-questions-medium/xv33m7/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * @param
     */
    public List<String> generateParenthesis(int n) {
        List<String> list=new ArrayList<>();
        int consume=0;
        int legalRemain=0;
        String add="";
        dfs2(0,0,n,add,list);
        return list;
    }
    public void dfs2(int consume,int legalRemain,int n,String add,List<String> list){
        if(n-consume>0){
            dfs2(consume+1,legalRemain+1,n,add+"(",list);
            if(legalRemain>0){
                dfs2(consume,legalRemain-1,n,add+")",list);
            }
        }else{
            for(int i=0;i<legalRemain;i++){
                add+=")";
            }
            list.add(add);
        }
    }

全部幂集

/**
     * 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
     *
     * 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
     * @param
     */
    public static List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> list=new ArrayList<>();
        List<Integer> add=new ArrayList<>();
        if(nums.length==0)return list;
        List<Integer> check=new ArrayList<>();
        list.add(add);

        for(int i=0;i<nums.length;i++){
            check.add(nums[i]);
        }

        for(int i=1;i<=nums.length;i++){
            dfs4(i,add,check,list);
        }
        return list;

    }
    public static void dfs4(int size,List<Integer> add,List<Integer> check,List<List<Integer>> list){
        if(size-add.size()>0){
            if(check.size()==0)return;
            int length=check.size();
            for(int i=0;i<length;i++) {
                List<Integer> add1=new ArrayList<>();
                for(Integer integer:add){
                    add1.add(integer);
                }
                Integer integer1=check.get(0);
                check.remove(integer1);
                if((add.size()>0&&add.get(add.size()-1)<integer1)|| add.size()==0) {
                    add1.add(integer1);
                    dfs4(size, add1, check, list);
                }
                check.add(integer1);
            }
        }else{
            list.add(add);
        }
    }

单词搜索

/**
     * 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
     *
     * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
     *
     *  
     *
     * 作者：力扣 (LeetCode)
     * 链接：https://leetcode.cn/leetbook/read/top-interview-questions-medium/xvkwe2/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * @param
     */
   public boolean exist(char[][] board, String word) {
        int row=board.length;
        int col=board[0].length;

        if(row*col<word.length()){
            return false;
        }

        int index=0;
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(board[i][j]==word.charAt(0)){
                    boolean[][] visited=new boolean[row][col];
                    boolean ans=dfs1(board,word,visited,0,i,j);
                    if(ans==true){
                        return true;
                    }
                }
            }
        }
        return false;
    }
   public boolean dfs1(char[][] board,String word,boolean[][] visited,int index,int m,int n){
        if(index==word.length()){
            return true;
        }
        if(m<0||m>=board.length||n<0||n>=board[0].length||visited[m][n]==true){
            return false;
        }
        if(board[m][n]==word.charAt(index)){
            visited[m][n]=true;
            boolean ans=(dfs1(board,word,visited,index+1,m+1,n)
                    || dfs1(board,word,visited,index+1,m-1,n)
                    || dfs1(board,word,visited,index+1,m,n+1)
                    || dfs1(board,word,visited,index+1,m,n-1));
            if(ans==true){
                return true;
            }else{
                visited[m][n]=false;
            }
        }
        return false;
    }

红白蓝排序

/**
     * 给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
     *
     * 我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
     *
     * 必须在不使用库的sort函数的情况下解决这个问题。
     *
     * 作者：力扣 (LeetCode)
     * 链接：https://leetcode.cn/leetbook/read/top-interview-questions-medium/xvg25c/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * @param
     */
    public void sortColors(int[] nums) {
       int left=0;
       int right=nums.length-1;
       int index=0;
       while(index<=right){
           if(nums[index]==0){
               swap(nums,index,left);
               index++;
               left++;
           }else if(nums[index]==2){
               swap(nums,index,right);
               right--;
           }else{
               index++;
           }
       }
    }
    public void swap(int[] nums,int index1,int index2){
        if(index1<nums.length&&index2<nums.length) {
            int copy = nums[index1];
            nums[index1]=nums[index2];
            nums[index2]=copy;
        }
    }

合并区间

 /**
     * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
     *
     * 作者：力扣 (LeetCode)
     * 链接：https://leetcode.cn/leetbook/read/top-interview-questions-medium/xv11yj/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
     * 输出：[[1,6],[8,10],[15,18]]
     * 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
     *
     * 作者：力扣 (LeetCode)
     * 链接：https://leetcode.cn/leetbook/read/top-interview-questions-medium/xv11yj/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * @param
     */
public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][2];
        }
        //自定义排序规则
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[0] - interval2[0];
            }
        });
        List<int[]> merged = new ArrayList<int[]>();
        for (int i = 0; i < intervals.length; ++i) {
            int L = intervals[i][0], R = intervals[i][1];
            if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
                merged.add(new int[]{L, R});
            } else {
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }

搜索二维矩阵

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

作者：力扣 (LeetCode)
链接：https://leetcode.cn/leetbook/read/top-interview-questions-medium/xvc64r/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
//自己写的。。。笨死了，没写完就放弃了，因为太复杂了
public boolean searchMatrix(int[][] matrix, int target) {
        int rowCount=matrix.length;
        int colCount=matrix[0].length;
        int maxBorder=Math.min(rowCount,colCount);
        int border=0;

        for(int i=0;i<maxBorder;i++,border++){
           if(target<=matrix[i][i]){
              break;
           }
        }
        if(border==maxBorder){
            if(colCount>=rowCount){
                for(int i=border;i<colCount;i++){
                    if(matrix[border-1][i]==target){
                        return true;
                    }else if(matrix[border-1][i]>target){
                        return false;
                    }
                }
            }else{
                
            }
        }
        for(int i=border-1;i>=0;i--){
            for(int j=i;j<colCount||j<rowCount;j++){
                if(j<colCount&&matrix[i][j]==target){
                    return true;
                }
                if(j<rowCount&&matrix[j][i]==target){
                    return true;
                }
            }
        }
        return false;
    }
    
//标答
 public boolean searchMatrix(int[][] matrix, int target) {
        int p = 0;
        int q = matrix[0].length - 1;
        while (p < matrix.length && q >= 0) {
        	if(matrix[p][q]>target) q--;
        	else if(matrix[p][q]<target) p++;
        	else return true;
        } 
        return false;
    }

搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

作者：力扣 (LeetCode)
链接：https://leetcode.cn/leetbook/read/top-interview-questions-medium/xvyz1t/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
其实如果明白了二分查找的本质——根据有序元素段判断元素位置以不断收缩边界选择搜索空间，这道题也可以很轻松的想出来解法。比如，对于一个有序数组[1，2，3，4，5，6，7]。mid = 4，如果我们要查找元素6会很自然的去他的右端寻找[mid+1, left]。因为我们知道mid左侧的元素有序，故这些元素都比mid 4小，自然也就比6小了。
那么对于[4,5,6,7,0,1,2]，可以想象，无论mid落到哪，在其两端都至少有一个局部有序段。假如mid为元素6，那么左侧456有序。若果mid为元素0，那么元素012有序。我们就可以利用有序段和当前target元素的比较，去排除一部分元素从而收缩边界继续寻找

 public int search(int[] nums, int target) {
        int low=0;
        int high=nums.length-1;
        int mid=-1;
        while(low<=high){
            mid=(high-low)/2+low;
            if(nums[mid]==target){
                return mid;
            }
            if(nums[mid]>=nums[low]){
                //说明此时落在左端有序段中
                if(target<nums[mid]&&target>=nums[low]) {
                    //说明target在左端有序段中
                    high = mid - 1;
                }else{
                    low=mid+1;
                }
            }else{
                //说明此时落在右端有序段中
                if(target>nums[mid]&&target<=nums[high]){
                    low=mid+1;
                }else{
                    high=mid-1;
                }
            }
        }
        return -1;
    }

跳跃游戏

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。
public boolean canJump(int[] nums) {
        int canReach=nums[0];
        int index=0;
        int maxReach=nums.length-1;
        while(index<maxReach&&index<=canReach){
            if(index+nums[index]>canReach){
                canReach=index+nums[index];
            }
            index+=1;
        }
        if(canReach>=maxReach){
            return true;
        }else{
            return false;
        }
    }

不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

作者：力扣 (LeetCode)
链接：https://leetcode.cn/leetbook/read/top-interview-questions-medium/xvjigd/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
int uniquePaths(int m, int n){
    if (m == 1 || n == 1) {
        return 1; 
    }
    int i;
    int j;

    int roads[n];
    for (j = 0; j < n; j++) {
        roads[j] = 1;
    }

    for (i = 1; i < m; i++) {
        for (j = 1; j < n; j++) {
            roads[j] = roads[j - 1] + roads[j]; // 当前路径数 = 左边的路径数 + 上一行的路径数
        }
    }
    return roads[n - 1];
}

最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

将算法的时间复杂度降低到 O(n log(n))
  
//T(n)=n^2
public int lengthOfLIS(int[] nums) {
        int numLen=nums.length;
        int[] g=new int[nums.length];
        Arrays.fill(g,1);

        for(int i=1;i<numLen;i++){
            for(int j=0;j<i;j++){
                if(nums[j]<nums[i]){
                    g[i]=Math.max(g[i],g[j]+1);
                }
            }
        }
        int res=0;
        for(int i=0;i<g.length;i++){
            res=Math.max(res,g[i]);
        }
        return res;
    }

//T(n)=n*log(n)
    public int lengthOfLIS(int[] nums) {
        int tail[]=new int[nums.length];
        tail[0]=nums[0];
        int end=0;

        for(int i=1;i<nums.length;i++){
            if(nums[i]>tail[end]){
                end+=1;
                tail[end]=nums[i];
            }else{
                //找到tail中第一个大于nums[i]的元素并替换它
                int low=0;
                int high=end;
                while(low<high){
                    int mid=(high-low)/2+low;
                    if(tail[mid]<nums[i]){
                        low=mid+1;
                    }else{
                        high=mid;
                    }
                }
                tail[low]=nums[i];
            }
        }
        return end++;
    }

位运算实现加减乘除

//加法
int add(int a,int b) {
  int carry,add;
  do{
    add = a^b;
    carry = (a&b)<<1;
    a = add;
    b=carry;
  }while(carry!=0);
  return add;
}

//减法,假设a，b均大于0
//add(~b,1)得到-b的补码
int substraction(int a,int b){
  return add(a,add(~b,1));
}

//a 被乘数，b 乘数
      int multiplication(int a,int b){
          int i = 0;
          int res = 0;
          //乘数不为0
          while (b != 0){
              //处理当前位
              //当前位是1
             if ((b & 1) == 1){
                 res += (a << i);
                 b = b >> 1;
                 //记录当前是第几位
                 i++;
             }else {
                 //当前位是0
                 b = b >> 1;
                 i++;
             }
         }
         return res;
     }

//除法
//除法的意义就在于：求a可以由多少个b组成。那么由此我们可得除法的实现：求a能减去多少个b，做减法的次数就是除法的商
int division(int a,int b){
        int res;
        if(a<b){
            return 0;
        }else{
            res=division(subtraction(a, b), b)+1;
        }
        return res;
    }

任务调度器

//给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态。
    //
    //然而，两个 相同种类 的任务之间必须有长度为整数 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。
    //
    //你需要计算完成所有任务所需要的 最短时间 。
    //
    //作者：力扣 (LeetCode)
    //链接：https://leetcode.cn/leetbook/read/top-interview-questions-medium/xwvaot/
    //来源：力扣（LeetCode）
    //著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
    public int leastInterval(char[] tasks, int n) {
        HashMap<Character,Integer> map=new HashMap<>();
        for(char c:tasks){
            map.put(c,map.getOrDefault(c,0)+1);
        }

        //下次合法执行的时间
        List<Integer> nextValid=new ArrayList<>();
        //剩余执行的次数
        List<Integer> rest=new ArrayList<>();
        Set<Map.Entry<Character,Integer>> set=map.entrySet();
        for(Map.Entry<Character,Integer> entry:set){
            nextValid.add(1);
            rest.add(entry.getValue());
        }
        int time=0;
        for(int i=0;i<tasks.length;i++){
            time+=1;
            int minNextValid=Integer.MAX_VALUE;
            for(int j=0;j<map.size();j++){
                if(rest.get(j)>0) {
                    minNextValid = Math.min(nextValid.get(j), minNextValid);
                }
            }
            time=Math.max(time,minNextValid);
            int best=-1;
            for(int j=0;j<map.size();j++){
                if(nextValid.get(j)<=time&&rest.get(j)!=0){
                    if(best==-1||rest.get(j)>rest.get(best)){
                        best=j;
                    }
                }
            }
            nextValid.set(best,time+n+1);
            rest.set(best,rest.get(best)-1);
        }
        return time;
    }

多数元素

//返回数组中多数元素：在数组中出现次数大于[n/2]的元素
    //设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题
    //你可以假设数组是非空的，并且给定的数组总是存在多数元素
    //下面的方法称为摩尔投票法，核心是“对拼消耗”
    public int majorityElement(int[] nums) {
        int res=nums[0];
        int count=1;
        for(int i=1;i<nums.length;i++){
            if(nums[i]==res){
                count+=1;
            }else{
                count+=-1;
                if(count<=0){
                    res=nums[i+1];
                }
            }
        }
        return res;
    }

两数相除

public static int dividee(int dividend, int divisor) {
       // 考虑被除数为最小值的情况
       if (dividend == Integer.MIN_VALUE) {
           if (divisor == 1) {
               return Integer.MIN_VALUE;
           }
           if (divisor == -1) {
               return Integer.MAX_VALUE;
           }
       }
       // 考虑除数为最小值的情况
       if (divisor == Integer.MIN_VALUE) {
           return dividend == Integer.MIN_VALUE ? 1 : 0;
       }
       // 考虑被除数为 0 的情况
       if (dividend == 0) {
           return 0;
       }

       // 一般情况，使用二分查找
       // 将所有的正数取相反数，这样就只需要考虑一种情况
       boolean rev = false;
       if (dividend > 0) {
           dividend = -dividend;
           rev = !rev;
       }
       if (divisor > 0) {
           divisor = -divisor;
           rev = !rev;
       }

       int left = 1, right = Integer.MAX_VALUE, ans = 0;
       while (left <= right) {
           // 注意溢出，并且不能使用除法
           int mid = left + ((right - left) >> 1);
           boolean check = quickAdd(divisor, mid, dividend);
           if (check) {
               ans = mid;
               // 注意溢出
               if (mid == Integer.MAX_VALUE) {
                   break;
               }
               left = mid + 1;
           } else {
               right = mid - 1;
           }
       }

       return rev ? -ans : ans;
   }

   // 快速乘
   public static boolean quickAdd(int y, int z, int x) {
       // x 和 y 是负数，z 是正数
       // 需要判断 z * y >= x 是否成立
       int result = 0, add = y;
       while (z != 0) {
           if ((z & 1) != 0) {
               //z的最后一位是1则可以进来
               // 需要保证 result + add >= x
               if (result < x - add) {
                   return false;
               }
               result += add;
           }
           if (z != 1) {
               // 需要保证 add + add >= x
               if (add < x - add) {
                   return false;
               }
               add += add;
           }
           // 不能使用除法
           z >>= 1;
       }
       return true;
   }