leecode算法(java版)1-33

浅浅的花香味﹌ 2022-12-09 01:54 45阅读 0赞

**目录**

1.两数之和

2.两数相加

3.无重复字符的最长子串

4. 整数翻转

5.判断一个整数是否是回文数

6.罗马数字转整数

7.最长公共前缀

8.二叉数的最大深度

9.翻转链表

10.二叉数的锯齿形层序遍历

11.柱形图中最大面积

12.二叉树的前序遍历

13.二叉树的中序遍历

14.二叉树的后序遍历

15.二叉树的层序遍历

16.只出现了一次的数字

17.有效的括号

18.合并两个有序链表

19.删除排序数组中的重复项

20.移除元素

21.实现strStr()

22.搜索插入位置

23.最大子序和

24.最后一个单词的长度

25.加一

26.二进制求和

27.x的平方根

28.爬楼梯

29.删除排序链表中的重复元素

30.合并两个有序数组

31.相同的树

32.对称二叉树

33.二叉树的层次遍历II

--------------------

### 1.两数之和 ###

//给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

// // 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

// // // // 示例: // // 给定 nums = \[2, 7, 11, 15\], target = 9 // //因为 nums\[0\] + nums\[1\] = 2 + 7 = 9 //所以返回 \[0, 1\]

// // Related Topics 数组 哈希表

class Solution {
      public int[] twoSum(int[] nums, int target) {
        /**新建一个map存储数据**/
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
          /**根据结果target 得到另一个结果**/
          int complement = target - nums[i];
          /**判断map中是否包括另一个结果**/
          if (map.containsKey(complement)) {
            return new int[] { map.get(complement), i };
          }
          /**将遍历的数据放到map里**/
          map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
      }
    }

### 2.两数相加 ###

//给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。 
    //
    // 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。 
    //
    // 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。 
    //
    // 示例： 
    //
    // 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
    //输出：7 -> 0 -> 8
    //原因：342 + 465 = 807
    // 
    // Related Topics 链表 数

class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            ListNode pre = new ListNode(0);
            ListNode cur = pre;
            int carry = 0;
            while(l1 != null || l2 != null) {
                int x = l1 == null ? 0 : l1.val;
                int y = l2 == null ? 0 : l2.val;
                int sum = x + y + carry;
                
                carry = sum / 10;
                sum = sum % 10;
                cur.next = new ListNode(sum);
    
                cur = cur.next;
                if(l1 != null)
                    l1 = l1.next;
                if(l2 != null)
                    l2 = l2.next;
            }
            if(carry == 1) {
                cur.next = new ListNode(carry);
            }
            return pre.next;
        }
    }

### 3.无重复字符的最长子串 ###

//给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。 
    //
    // 示例 1: 
    //
    // 输入: "abcabcbb"
    //输出: 3 
    //解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
    // 
    //
    // 示例 2: 
    //
    // 输入: "bbbbb"
    //输出: 1
    //解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
    // 
    //
    // 示例 3: 
    //
    // 输入: "pwwkew"
    //输出: 3
    //解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
    //     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
    // 
    // Related Topics 哈希表 双指针 字符串 Sliding Window

class Solution {
        public int lengthOfLongestSubstring(String s) {
            // 记录字符上一次出现的位置
            int[] last = new int[128];
            for(int i = 0; i < 128; i++) {
                last[i] = -1;
            }
            int n = s.length();
    
            int res = 0;
            int start = 0; // 窗口开始位置
            for(int i = 0; i < n; i++) {
                int index = s.charAt(i);
                start = Math.max(start, last[index] + 1);
                res   = Math.max(res, i - start + 1);
                last[index] = i;
            }
    
            return res;
        }
    }

### 4. 整数翻转 ###

//给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。 
    //
    // 示例 1: 
    //
    // 输入: 123
    //输出: 321
    // 
    //
    // 示例 2: 
    //
    // 输入: -123
    //输出: -321
    // 
    //
    // 示例 3: 
    //
    // 输入: 120
    //输出: 21
    // 
    //
    // 注意: 
    //
    // 假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231, 231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。 
    // Related Topics 数学

class Solution {
        public int reverse(int x) {
            long result = 0;
            while (x != 0){
                result = result * 10 + x % 10;
                x = x / 10;
            }
            if (result > Integer.MAX_VALUE || result < Integer.MIN_VALUE){
                return 0;
            }
            return (int)result;
        }
        
    
    }

### 5.判断一个整数是否是回文数 ###

//判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。 
    //
    // 示例 1: 
    //
    // 输入: 121
    //输出: true
    // 
    //
    // 示例 2: 
    //
    // 输入: -121
    //输出: false
    //解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
    // 
    //
    // 示例 3: 
    //
    // 输入: 10
    //输出: false
    //解释: 从右向左读, 为 01 。因此它不是一个回文数。
    // 
    //
    // 进阶: 
    //
    // 你能不将整数转为字符串来解决这个问题吗？ 
    // Related Topics 数学

class Solution {
      public boolean isPalindrome(int x) {
        if(x<0) return false;
        List list=new ArrayList();
        while(x/10!=0){
          list.add(x%10);
          x=x/10;
        }
        list.add(x);
        for(int i=0;i<list.size()/2;i++)
        {
          if(list.get(i)!=list.get(list.size()-i-1)) return false;
        }
        return true;
      }
    }

### 6.罗马数字转整数 ###

//罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。 
    //
    // 字符          数值
    //I             1
    //V             5
    //X             10
    //L             50
    //C             100
    //D             500
    //M             1000 
    //
    // 例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + I
    //I 。 
    //
    // 通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5
    // 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况： 
    //
    // 
    // I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。 
    // X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 
    // C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。 
    // 
    //
    // 给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。 
    //
    // 
    //
    // 示例 1: 
    //
    // 输入: "III"
    //输出: 3 
    //
    // 示例 2: 
    //
    // 输入: "IV"
    //输出: 4 
    //
    // 示例 3: 
    //
    // 输入: "IX"
    //输出: 9 
    //
    // 示例 4: 
    //
    // 输入: "LVIII"
    //输出: 58
    //解释: L = 50, V= 5, III = 3.
    // 
    //
    // 示例 5: 
    //
    // 输入: "MCMXCIV"
    //输出: 1994
    //解释: M = 1000, CM = 900, XC = 90, IV = 4. 
    //
    // 
    //
    // 提示： 
    //
    // 
    // 题目所给测试用例皆符合罗马数字书写规则，不会出现跨位等情况。 
    // IC 和 IM 这样的例子并不符合题目要求，49 应该写作 XLIX，999 应该写作 CMXCIX 。 
    // 关于罗马数字的详尽书写规则，可以参考 罗马数字 - Mathematics 。 
    // 
    // Related Topics 数学 字符串

class Solution {
      public int romanToInt(String s) {
        int n = s.length();
        int roman_int = 0;
        for(int i=0;i<n;i++)
        {
          switch(s.charAt(i))
          {
            case 'I' : roman_int = roman_int + 1;break;
            case 'V' : roman_int = roman_int + 5;break;
            case 'X' : roman_int = roman_int + 10;break;
            case 'L' : roman_int = roman_int + 50;break;
            case 'C' : roman_int = roman_int + 100;break;
            case 'D' : roman_int = roman_int + 500;break;
            case 'M' : roman_int = roman_int + 1000;break;
            default: System.out.println("default");break;
          }
    
          if(i!=0)
          {
            if(((s.charAt(i)=='V')||(s.charAt(i)=='X'))&&(s.charAt(i-1)=='I'))
              roman_int = roman_int-1*2;
            if(((s.charAt(i)=='L')||(s.charAt(i)=='C'))&&(s.charAt(i-1)=='X'))
              roman_int = roman_int-10*2;
            if(((s.charAt(i)=='D')||(s.charAt(i)=='M'))&&(s.charAt(i-1)=='C'))
              roman_int = roman_int-100*2;
          }
        }
        return roman_int;
      }
    }

### 7.最长公共前缀 ###

//编写一个函数来查找字符串数组中的最长公共前缀。 
    //
    // 如果不存在公共前缀，返回空字符串 ""。 
    //
    // 示例 1: 
    //
    // 输入: ["flower","flow","flight"]
    //输出: "fl"
    // 
    //
    // 示例 2: 
    //
    // 输入: ["dog","racecar","car"]
    //输出: ""
    //解释: 输入不存在公共前缀。
    // 
    //
    // 说明: 
    //
    // 所有输入只包含小写字母 a-z 。 
    // Related Topics 字符串

class Solution {
    
      public static String longestCommonPrefix (String[] strs) {
        int count = strs.length;
        String prefix = "";
        if (count != 0) {
          prefix = strs[0];
        }
        for (int i = 0; i < count; i++) {
          //关键代码，不断的从后往前截取字符串，然后与之相比，直到startsWith()返回true
          while (!strs[i].startsWith(prefix)) {
            prefix = prefix.substring(0, prefix.length() - 1);
          }
        }
        return prefix;
      }
    }

### 8.二叉数的最大深度 ###

//给定一个二叉树，找出其最大深度。 
    //
    // 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 
    //
    // 说明: 叶子节点是指没有子节点的节点。 
    //
    // 示例： 
    //给定二叉树 [3,9,20,null,null,15,7]， 
    //
    //     3
    //   / \
    //  9  20
    //    /  \
    //   15   7 
    //
    // 返回它的最大深度 3 。 
    // Related Topics 树 深度优先搜索
    
    
    //leetcode submit region begin(Prohibit modification and deletion)

class Solution {
        public int maxDepth(TreeNode root) {
          if (root == null) {
            return 0;
          }
          // 计算左子树的深度
          int left = maxDepth(root.left);
          // 计算右子树的深度
          int right = maxDepth(root.right);
          // 树root的深度=路径最长的子树深度 + 1
          return left >= right ? (left + 1) : (right + 1);
        }
    }

### 9.翻转链表 ###

//反转一个单链表。 
    //
    // 示例: 
    //
    // 输入: 1->2->3->4->5->NULL
    //输出: 5->4->3->2->1->NULL 
    //
    // 进阶: 
    //你可以迭代或递归地反转链表。你能否用两种方法解决这道题？ 
    // Related Topics 链表

class Solution {
        public ListNode reverseList(ListNode head) {
            if(head==null||head.next==null) return head;
             ListNode newHead=reverseList(head.next);
             ListNode temp=head.next;
             head.next=null;
             temp.next=head;
             return newHead;
        }
    }

### 10.二叉数的锯齿形层序遍历 ###

//给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。 
    //
    // 例如： 
    //给定二叉树 [3,9,20,null,null,15,7], 
    //
    //     3
    //   / \
    //  9  20
    //    /  \
    //   15   7
    // 
    //
    // 返回锯齿形层次遍历如下： 
    //
    // [
    //  [3],
    //  [20,9],
    //  [15,7]
    //]
    // 
    // Related Topics 栈 树 广度优先搜索

class Solution {
      public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if (root == null) {
          return new ArrayList<>();
        }
        List<List<Integer>> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);   //初始化：将根节点放入队列中
        boolean isOrder = true;  //二叉树层序遍历 的 偶数行 需要反转
    
        while (!queue.isEmpty()) {
          int size = queue.size();
          List<Integer> level = new ArrayList<Integer>();
    
          for (int i = 0; i < size; i++) {
            TreeNode cur = queue.poll();
            level.add(cur.val);
            if (cur.left != null) {
              queue.offer(cur.left);
            }
            if (cur.right != null) {
              queue.offer(cur.right);
            }
          }
    
          if (isOrder) {
            result.add(level);
          } else {
            Collections.reverse(level);
            result.add(level);
          }
          isOrder = !isOrder;
        }
    
        return result;
      }
      }

### 11.柱形图中最大面积 ###

//给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 
    //
    // 求在该柱状图中，能够勾勒出来的矩形的最大面积。 
    //
    // 
    //
    // 
    //
    // 以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。 
    //
    // 
    //
    // 
    //
    // 图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。 
    //
    // 
    //
    // 示例: 
    //
    // 输入: [2,1,5,6,2,3]
    //输出: 10 
    // Related Topics 栈 数组

public class Solution {
      public int largestRectangleArea(int[] heights) {
        Stack < Integer > stack = new Stack < > ();
        stack.push(-1);
        int maxarea = 0;
        for (int i = 0; i < heights.length; ++i) {
          while (stack.peek() != -1 && heights[stack.peek()] >= heights[i])   //i-1 >i
            maxarea = Math.max(maxarea, heights[stack.pop()] * (i - stack.peek() - 1));//height(i-1)*i        //找高度
          stack.push(i);
        }
        while (stack.peek() != -1)
          maxarea = Math.max(maxarea, heights[stack.pop()] * (heights.length - stack.peek() -1));
        return maxarea;
      }
    }

### 12.二叉树的前序遍历 ###

//给定一个二叉树，返回它的 前序 遍历。 
    //
    // 示例: 
    //
    // 输入: [1,null,2,3]  
    //   1
    //    \
    //     2
    //    /
    //   3 
    //
    //输出: [1,2,3]
    // 
    //
    // 进阶: 递归算法很简单，你可以通过迭代算法完成吗？ 
    // Related Topics 栈 树

class Solution {
        public List<Integer> preorderTraversal(TreeNode root) {
          List<Integer> lists = new ArrayList<>();
          if(root==null) return  lists;
          Stack<TreeNode> stack=new Stack<TreeNode>();
          stack.push(root);
          while(!stack.isEmpty()){
            TreeNode temp=stack.pop();
            lists.add(temp.val);
            if(temp.right!=null){
              stack.push(temp.right);
            }
            if(temp.left!=null){
              stack.push(temp.left);
            }
          }
          return lists;
        }
    }

### 13.二叉树的中序遍历 ###

//给定一个二叉树，返回它的中序 遍历。 
    //
    // 示例: 
    //
    // 输入: [1,null,2,3]
    //   1
    //    \
    //     2
    //    /
    //   3
    //
    //输出: [1,3,2] 
    //
    // 进阶: 递归算法很简单，你可以通过迭代算法完成吗？ 
    // Related Topics 栈 树 哈希表

class Solution {
        public List<Integer> inorderTraversal(TreeNode root) {
          if(root==null) return new ArrayList<>();
          Stack<TreeNode> stack=new Stack<TreeNode>();
          TreeNode node=root,temp=null;
          List<Integer> lists=new ArrayList<Integer>();
          while(!stack.isEmpty()||node!=null){
            while(node!=null){
              stack.add(node);
              node=node.left;
            }
            if(!stack.isEmpty()){
               temp=stack.pop();
               lists.add(temp.val);
               node=temp.right;
            }
          }
           return  lists;
        }
    
    }

### 14.二叉树的后序遍历 ###

//给定一个二叉树，返回它的 后序 遍历。 
    //
    // 示例: 
    //
    // 输入: [1,null,2,3]  
    //   1
    //    \
    //     2
    //    /
    //   3 
    //
    //输出: [3,2,1] 
    //
    // 进阶: 递归算法很简单，你可以通过迭代算法完成吗？ 
    // Related Topics 栈 树

class Solution {
        public List<Integer> postorderTraversal(TreeNode root) {
          LinkedList<Integer> list=new LinkedList<>();
          if(root==null) return list;
          Stack<TreeNode> stack=new Stack<TreeNode>();
          stack.push(root);
          while(!stack.isEmpty()){
            TreeNode temp=stack.pop();
            list.addFirst(temp.val);
            if(temp.left!=null){
              stack.push(temp.left);
            }
            if(temp.right!=null){
              stack.push(temp.right);
            }
          }
            return list;
        }
    }

### 15.二叉树的层序遍历 ###

//给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。 
    //
    // 
    //
    // 示例： 
    //二叉树：[3,9,20,null,null,15,7], 
    //
    //     3
    //   / \
    //  9  20
    //    /  \
    //   15   7
    // 
    //
    // 返回其层次遍历结果： 
    //
    // [
    //  [3],
    //  [9,20],
    //  [15,7]
    //]

class Solution {
        public List<List<Integer>> levelOrder(TreeNode root) {
          if(root==null) return new ArrayList<>();
          List<List<Integer>> listList=new ArrayList<>();
          List<Integer> arrays=new ArrayList<>();
          Queue<TreeNode> queue= new LinkedList<>();
          queue.add(root);
          while(!queue.isEmpty()){
            int n=queue.size();
            for(int i=0;i<n;i++){
              TreeNode temp=queue.poll();
              arrays.add(temp.val);
              if(temp.left!=null){
                queue.add(temp.left);
              }
              if(temp.right!=null){
                queue.add(temp.right);
              }
            }
            listList.add(new ArrayList<>(arrays));
            arrays.clear();
          }
          return listList;
        }
    }

### 16.只出现了一次的数字 ###

//给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。 
    //
    // 说明： 
    //
    // 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？ 
    //
    // 示例 1: 
    //
    // 输入: [2,2,1]
    //输出: 1
    // 
    //
    // 示例 2: 
    //
    // 输入: [4,1,2,1,2]
    //输出: 4 
    // Related Topics 位运算 哈希表

class Solution {
      public static int singleNumber(int[] nums) {
        if(nums.length < 1) return 0;
        int result = nums[0];
        for (int i = 1; i < nums.length; i++) {
          result = result ^ nums[i];
        }
        return result;
      }
    }

### 17.有效的括号 ###

//给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。 
    //
    // 有效字符串需满足： 
    //
    // 
    // 左括号必须用相同类型的右括号闭合。 
    // 左括号必须以正确的顺序闭合。 
    // 
    //
    // 注意空字符串可被认为是有效字符串。 
    //
    // 示例 1: 
    //
    // 输入: "()"
    //输出: true
    // 
    //
    // 示例 2: 
    //
    // 输入: "()[]{}"
    //输出: true
    // 
    //
    // 示例 3: 
    //
    // 输入: "(]"
    //输出: false
    // 
    //
    // 示例 4: 
    //
    // 输入: "([)]"
    //输出: false
    // 
    //
    // 示例 5: 
    //
    // 输入: "{[]}"
    //输出: true

class Solution {
      public boolean isValid(String s) {
    
        Stack<Character> stack = new Stack<>();
    
        for (int i = 0; i < s.length(); i++){
          char ch = s.charAt(i);
          if(ch == '(' || ch == '[' || ch == '{'){
            stack.push(ch);
          }else{
            if(stack.isEmpty()){
              return false;
            }
            char topChar = stack.pop();
            if(ch == ')' && topChar != '('){
              return false;
            }else if(ch == ']' && topChar != '['){
              return false;
            }else if(ch == '}' && topChar != '{'){
              return false;
            }
          }
        }
    
        return stack.isEmpty();
      }
    }

### 18.合并两个有序链表 ###

//将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
    //
    // 
    //
    // 示例： 
    //
    // 输入：1->2->4, 1->3->4
    //输出：1->1->2->3->4->4
    // 
    // Related Topics 链表

class Solution {
      /**
       *Definition for singly-linked list
       */
      public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
    
        ListNode head = null;
        if (l1.val <= l2.val){
          head = l1;
          head.next = mergeTwoLists(l1.next, l2);
        } else {
          head = l2;
          head.next = mergeTwoLists(l1, l2.next);
        }
        return head;
      }
    }

### 19.删除排序数组中的重复项 ###

//给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。 
    //
    // 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。 
    //
    // 
    //
    // 示例 1: 
    //
    // 给定数组 nums = [1,1,2], 
    //
    //函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 
    //
    //你不需要考虑数组中超出新长度后面的元素。 
    //
    // 示例 2: 
    //
    // 给定 nums = [0,0,1,1,1,2,2,3,3,4],
    //
    //函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
    //
    //你不需要考虑数组中超出新长度后面的元素。
    // 
    //
    // 
    //
    // 说明: 
    //
    // 为什么返回数值是整数，但输出的答案是数组呢? 
    //
    // 请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。 
    //
    // 你可以想象内部操作如下: 
    //
    // // nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
    //int len = removeDuplicates(nums);
    //
     在函数里修改输入数组对于调用者是可见的。
     根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
    //for (int i = 0; i < len; i++) {
    //    print(nums[i]);
    //}
    // 
    // Related Topics 数组 双指针

class Solution {
      public int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0) {
          return 0;
        }
        int back = 0;
        for (int front = 1; front < nums.length; front++) {
          if (nums[back] != nums[front]) {
            back++;
            nums[back] = nums[front];
          }
        }
        return back + 1;
      }
    }

### 20.移除元素 ###

/给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。 
    //
    // 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。 
    //
    // 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。 
    //
    // 
    //
    // 示例 1: 
    //
    // 给定 nums = [3,2,2,3], val = 3,
    //
    //函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
    //
    //你不需要考虑数组中超出新长度后面的元素。
    // 
    //
    // 示例 2: 
    //
    // 给定 nums = [0,1,2,2,3,0,4,2], val = 2,
    //
    //函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
    //
    //注意这五个元素可为任意顺序。
    //
    //你不需要考虑数组中超出新长度后面的元素。
    // 
    //
    // 
    //
    // 说明: 
    //
    // 为什么返回数值是整数，但输出的答案是数组呢? 
    //
    // 请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。 
    //
    // 你可以想象内部操作如下: 
    //
    // // nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
    //int len = removeElement(nums, val);
    //
     在函数里修改输入数组对于调用者是可见的。
     根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
    //for (int i = 0; i < len; i++) {
    //    print(nums[i]);
    //}
    // 
    // Related Topics 数组 双指针

class Solution {
        public int removeElement(int[] nums, int val) {
          int back=0;
         for(int front=0;front<nums.length;front++){
           if(nums[front]!=val){
             nums[back]=nums[front];
             back++;
           }
         }
         return back;
        }
    }

### 21.实现strStr() ###

//实现 strStr() 函数。 
    //
    // 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如
    //果不存在，则返回 -1。 
    //
    // 示例 1: 
    //
    // 输入: haystack = "hello", needle = "ll"
    //输出: 2
    // 
    //
    // 示例 2: 
    //
    // 输入: haystack = "aaaaa", needle = "bba"
    //输出: -1
    // 
    //
    // 说明: 
    //
    // 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。 
    //
    // 对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。 
    // Related Topics 双指针 字符串

class Solution {
        public int strStr(String haystack, String needle) {
          if(haystack==null||haystack=="") return 0;
          if(needle==null||needle=="") return 0;
          return haystack.indexOf(needle);
        }
    }

### 22.搜索插入位置 ###

//给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。 
    //
    // 你可以假设数组中无重复元素。 
    //
    // 示例 1: 
    //
    // 输入: [1,3,5,6], 5
    //输出: 2
    // 
    //
    // 示例 2: 
    //
    // 输入: [1,3,5,6], 2
    //输出: 1
    // 
    //
    // 示例 3: 
    //
    // 输入: [1,3,5,6], 7
    //输出: 4
    // 
    //
    // 示例 4: 
    //
    // 输入: [1,3,5,6], 0
    //输出: 0

class Solution {
        public int searchInsert(int[] nums, int target) {
          int start=0;
          int end=nums.length-1;
          while(start<=end){
            int middle=(start+end)/2;
            if(nums[middle]>target){
              end=middle-1;
            }else if(nums[middle]<target){
              start=middle+1;
            }else{
              return middle;
            }
          }
          return start;
        }
    }

### 23.最大子序和 ###

//给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 
    //
    // 示例: 
    //
    // 输入: [-2,1,-3,4,-1,2,1,-5,4]
    //输出: 6
    //解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
    // 
    //
    // 进阶: 
    //
    // 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。 
    // Related Topics 数组 分治算法 动态规划

class Solution {
      public int maxSubArray(int[] nums) {
        if(nums == null || nums.length == 0){
          return 0;
        }
        int local = nums[0];
        int global = nums[0];
        for(int i=1; i<nums.length; i++){
          local = Math.max(nums[i], local+nums[i]);
          global = Math.max(local, global);
        }
        return global;
      }
    }

### 24.最后一个单词的长度 ###

//给定一个仅包含大小写字母和空格 ' ' 的字符串 s，返回其最后一个单词的长度。如果字符串从左向右滚动显示，那么最后一个单词就是最后出现的单词。 
    //
    // 如果不存在最后一个单词，请返回 0 。 
    //
    // 说明：一个单词是指仅由字母组成、不包含任何空格字符的 最大子字符串。 
    //
    // 
    //
    // 示例: 
    //
    // 输入: "Hello World"
    //输出: 5
    // 
    // Related Topics 字符串

class Solution {
        public int lengthOfLastWord(String s) {
         if(s==null||s.equals("")){
           return 0;
         }
          if(s.trim().length()==0)
            return 0;
         String arr[]=s.split(" ");
         return arr[arr.length-1].length();
        }
    }

### 25.加一 ###

//给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。 
    //
    // 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。 
    //
    // 你可以假设除了整数 0 之外，这个整数不会以零开头。 
    //
    // 示例 1: 
    //
    // 输入: [1,2,3]
    //输出: [1,2,4]
    //解释: 输入数组表示数字 123。
    // 
    //
    // 示例 2: 
    //
    // 输入: [4,3,2,1]
    //输出: [4,3,2,2]
    //解释: 输入数组表示数字 4321。

class Solution {
      public int[] plusOne(int[] digits) {
        for(int i=digits.length-1;i>=0;i--){
          digits[i]++;
          digits[i] %= 10;
          if(digits[i]!=0)//判断该位数字加1后对10取余数是否为0，实质上就是判断是否需要进位
            return digits;
        }
            /*数组大小扩容一位，99、999等全部需要进位加一的情况下会执行以下代码，也就是上面所说在极
              端情况下的数组扩容并且手动进位，极端情况下全部数字都经过 加1置零，数组元素全部变成0，
              所以不妨数组长度加1初始化（Java中int类型数组默认初始值为0）*/
        digits = new int[digits.length+1];
        digits[0]=1;
        return digits;
      }
    }

### 26.二进制求和 ###

//给你两个二进制字符串，返回它们的和（用二进制表示）。 
    //
    // 输入为 非空 字符串且只包含数字 1 和 0。 
    //
    // 
    //
    // 示例 1: 
    //
    // 输入: a = "11", b = "1"
    //输出: "100" 
    //
    // 示例 2: 
    //
    // 输入: a = "1010", b = "1011"
    //输出: "10101" 
    //
    // 
    //
    // 提示： 
    //
    // 
    // 每个字符串仅由字符 '0' 或 '1' 组成。 
    // 1 <= a.length, b.length <= 10^4 
    // 字符串如果不是 "0" ，就都不含前导零。 
    // 
    // Related Topics 数学 字符串

class Solution {
      public String addBinary(String a, String b) {
        StringBuilder ans = new StringBuilder();
        int ca = 0;
        for(int i = a.length() - 1, j = b.length() - 1;i >= 0 || j >= 0; i--, j--) {
          int sum = ca;
          sum += i >= 0 ? a.charAt(i) - '0' : 0;//长度不够补零
          sum += j >= 0 ? b.charAt(j) - '0' : 0;//长度不够补零
          ans.append(sum % 2);//取余
          ca = sum / 2;//进位
        }
        ans.append(ca == 1 ? ca : "");//进位
        return ans.reverse().toString();
      }
    }

### 27.x的平方根 ###

//实现 int sqrt(int x) 函数。 
    //
    // 计算并返回 x 的平方根，其中 x 是非负整数。 
    //
    // 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。 
    //
    // 示例 1: 
    //
    // 输入: 4
    //输出: 2
    // 
    //
    // 示例 2: 
    //
    // 输入: 8
    //输出: 2
    //说明: 8 的平方根是 2.82842..., 
    //     由于返回类型是整数，小数部分将被舍去。
    // 
    // Related Topics 数学 二分查找

public class Solution {
    
      public int mySqrt(int x) {
        int left = 0;
        int right = x;
        while (left <= right) {
          long mid = (left + right) / 2;
          if (mid * mid == x)
            return (int) mid;
          else if (mid * mid < x)
            left = (int) (mid + 1);
          else
            right = (int) (mid - 1);
        }
        return right;
      }
    
    }

### 28.爬楼梯 ###

//假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 
    //
    // 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 
    //
    // 注意：给定 n 是一个正整数。 
    //
    // 示例 1： 
    //
    // 输入： 2
    //输出： 2
    //解释： 有两种方法可以爬到楼顶。
    //1.  1 阶 + 1 阶
    //2.  2 阶 
    //
    // 示例 2： 
    //
    // 输入： 3
    //输出： 3
    //解释： 有三种方法可以爬到楼顶。
    //1.  1 阶 + 1 阶 + 1 阶
    //2.  1 阶 + 2 阶
    //3.  2 阶 + 1 阶
    // 
    // Related Topics 动态规划 找规律

class Solution {
        public int climbStairs(int n) {
            if ( n<1 ) return 0;
            if (n == 1)return 1;
            if (n == 2)return 2;
            int a = 1;
            int b = 2;
            int temp =0;
            for(int i = 3;i <= n ;i++){
              temp = b + a;
              a = b;
              b = temp;
            }
            return temp;
        }
    
    }

### 29.删除排序链表中的重复元素 ###

//给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。 
    //
    // 示例 1: 
    //
    // 输入: 1->1->2
    //输出: 1->2
    // 
    //
    // 示例 2: 
    //
    // 输入: 1->1->2->3->3
    //输出: 1->2->3 
    // Related Topics 链表

class Solution {
      public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null){
          return head;
        }
        head.next = deleteDuplicates(head.next);
        if(head.val == head.next.val) head = head.next;
        return head;
      }
    }

### 30.合并两个有序数组 ###

//给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。 
    //
    // 
    //
    // 说明: 
    //
    // 
    // 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。 
    // 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。 
    // 
    //
    // 
    //
    // 示例: 
    //
    // 输入:
    //nums1 = [1,2,3,0,0,0], m = 3
    //nums2 = [2,5,6],       n = 3
    //
    //输出: [1,2,2,3,5,6] 
    // Related Topics 数组 双指针

/*class Solution {
      public void merge(int[] nums1, int m, int[] nums2, int n) {
        for(int i=0,j=m;i<n;i++,j++) {
          nums1[j]=nums2[i];
        }
        Arrays.sort(nums1);
      }
    }*/
    class Solution {
      public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i=m-1;
        int j=n-1;
        int k=m+n-1;
        while(i>=0&&j>=0) {
          if(nums1[i]>nums2[j]) {
            nums1[k--]=nums1[i];
            i--;
          }else {
            nums1[k--]=nums2[j];
            j--;
          }
        }
        while(j>=0) {
          nums1[j]=nums2[j];
          j--;
        }
      }
    }

### 31.相同的树 ###

//给定两个二叉树，编写一个函数来检验它们是否相同。 
    //
    // 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。 
    //
    // 示例 1: 
    //
    // 输入:       1         1
    //          / \       / \
    //         2   3     2   3
    //
    //        [1,2,3],   [1,2,3]
    //
    //输出: true 
    //
    // 示例 2: 
    //
    // 输入:      1          1
    //          /           \
    //         2             2
    //
    //        [1,2],     [1,null,2]
    //
    //输出: false
    // 
    //
    // 示例 3: 
    //
    // 输入:       1         1
    //          / \       / \
    //         2   1     1   2
    //
    //        [1,2,1],   [1,1,2]
    //
    //输出: false
    // 
    // Related Topics 树 深度优先搜索

class Solution {
      public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null)
          return true;
        if(p == null || q == null)
          return false;
        if(p.val != q.val)
          return false;
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
      }
    }

### 32.对称二叉树 ###

//给定一个二叉树，检查它是否是镜像对称的。 
    //
    // 
    //
    // 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。 
    //
    //     1
    //   / \
    //  2   2
    // / \ / \
    //3  4 4  3
    // 
    //
    // 
    //
    // 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的: 
    //
    //     1
    //   / \
    //  2   2
    //   \   \
    //   3    3
    // 
    //
    // 
    //
    // 进阶： 
    //
    // 你可以运用递归和迭代两种方法解决这个问题吗？ 
    // Related Topics 树 深度优先搜索 广度优先搜索

class Solution {
      public boolean isSymmetric(TreeNode root) {
        if(root==null || (root.left==null && root.right==null)) {
          return true;
        }
        //用队列保存节点
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        //将根节点的左右孩子放到队列中
        queue.add(root.left);
        queue.add(root.right);
        while(queue.size()>0) {
          //从队列中取出两个节点，再比较这两个节点
          TreeNode left = queue.removeFirst();
          TreeNode right = queue.removeFirst();
          //如果两个节点都为空就继续循环，两者有一个为空就返回false
          if(left==null && right==null) {
            continue;
          }
          if(left==null || right==null) {
            return false;
          }
          if(left.val!=right.val) {
            return false;
          }
          //将左节点的左孩子， 右节点的右孩子放入队列
          queue.add(left.left);
          queue.add(right.right);
          //将左节点的右孩子，右节点的左孩子放入队列
          queue.add(left.right);
          queue.add(right.left);
        }
    
        return true;
      }
    }

### 33.二叉树的层次遍历II ###

//给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历） 
    //
    // 例如： 
    //给定二叉树 [3,9,20,null,null,15,7], 
    //
    //     3
    //   / \
    //  9  20
    //    /  \
    //   15   7
    // 
    //
    // 返回其自底向上的层次遍历为： 
    //
    // [
    //  [15,7],
    //  [9,20],
    //  [3]
    //]
    // 
    // Related Topics 树 广度优先搜索

class Solution {
        public List<List<Integer>> levelOrderBottom(TreeNode root) {
          List<List<Integer>> lists=new ArrayList<>();
          if(root==null) return lists;
          Queue<TreeNode> queue=new LinkedList<>();
          List<Integer> array=new ArrayList<>();
          queue.add(root);
          while(!queue.isEmpty()){
            int n=queue.size();
            for(int i=0;i<n;i++){
              TreeNode temp=queue.poll();
              array.add(temp.val);
              if(temp.left!=null){
                queue.add(temp.left);
              }
              if(temp.right!=null){
                queue.add(temp.right);
              }
            }
            lists.add(new ArrayList<>(array));
            array.clear();
          }
          Collections.reverse(lists);
          return lists;
        }
    }