# leetcode

**Repository Path**: wudibinge/leetcode

## Basic Information

- **Project Name**: leetcode
- **Description**: 用简短的语言描述一下吧
- **Primary Language**: Java
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2022-06-19
- **Last Updated**: 2024-10-13

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# **LeetCode练习**

## 15.三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

```java
示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

示例 2：

输入：nums = []
输出：[]

示例 3：

输入：nums = [0]
输出：[]

提示：

0 <= nums.length <= 3000
-105 <= nums[i] <= 105


```

**基本思想：双指针**

采用三重循环去遍历数组时判断nums[i]+nums[j]+nums[k]==0，如果先对数组进行排序，那么第一层循环不变，a+b+c的值随着b的增加而增加，如果a+b+c>0要想使其为0，b'>b,c'<c。所以第二层循环和第三层循环可以合并

```java
for (int j = i + 1; j < nums.length - 1; j++){
                    if(j>i+1&&nums[j]==nums[j-1])
                        continue;
                    while (j < k && nums[i] + nums[j]+nums[k]>0) {
                        k--;
                    }
}
```


如果j==k，说明没有找到，如果值不等于0可以跳过。如果此时值为0可以添加到列表中。

                    if(j==k)break;
                    if(nums[i]+nums[j]+nums[k]==0){
                        tmp=new ArrayList<>();
                        tmp.add(nums[i]);
                        tmp.add(nums[j]);
                        tmp.add(nums[k]);
                        result.add(tmp);
                    }

- 源代码：

```java
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>>result=new ArrayList<>();
            List<Integer>tmp;
            if(nums.length<3)return result;
            Arrays.sort(nums);
            int k;
            for(int i=0;i<nums.length-2;i++) {
                if(i>0&&nums[i]==nums[i-1])
                    continue;
                k=nums.length-1;
                for (int j = i + 1; j < nums.length - 1; j++){
                    if(j>i+1&&nums[j]==nums[j-1])
                        continue;
                    while (j < k && nums[i] + nums[j]+nums[k]>0) {
                        k--;
                    }
                    if(j==k)break;
                    if(nums[i]+nums[j]+nums[k]==0){
                        tmp=new ArrayList<>();
                        tmp.add(nums[i]);
                        tmp.add(nums[j]);
                        tmp.add(nums[k]);
                        result.add(tmp);
                    }
                }

            }
     
            return result;
    }

}

```

## [17. 电话号码的字母组合 - 力扣（LeetCode）](https://leetcode.cn/problems/letter-combinations-of-a-phone-number/)

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/11/09/200px-telephone-keypad2svg.png)

 

示例 1：

```java
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
```

示例 2：

```java
输入：digits = ""
输出：[]
```

示例 3：

```java
输入：digits = "2"
输出：["a","b","c"]
```




提示：

- 0 <= digits.length <= 4
- digits[i] 是范围 ['2', '9'] 的一个数字。

**基本思想：回溯**

采用回溯法，对于每个按下的数字，选择一个它对应的字母中的一个，然后去选择下一个按下数字的数字对应的字母，知道选择完，然后开始回溯到上一步，讲每个字母都进行一次选择。

源代码：

```java
class Solution {
        public List<String> letterCombinations(String digits) {
            List<String>result=new ArrayList<>();
            Map<Integer,String>maps=new HashMap<>();
            maps.put(2,"abc");
            maps.put(3,"def");
            maps.put(4,"ghi");
            maps.put(5,"jkl");
            maps.put(6,"mno");
            maps.put(7,"pqrs");
            maps.put(8,"tuv");
            maps.put(9,"wxyz");
            if(digits.length()==0)return result;
            backtrace(result,maps,digits,0,new StringBuffer());
            return result;
        }
        //经典回溯
        public static void backtrace(List<String> result,Map<Integer,String>maps,String digits,int index,StringBuffer s){
            if(index==digits.length()){
                result.add(s.toString());
                return;
            }
            else{
                int x=digits.charAt(index)-48;
//                System.out.println("x="+x+"digits="+digits);
                for(int i=0;i<maps.get(x).length();i++){
                    s.append(maps.get(x).charAt(i));
                    backtrace(result,maps,digits,index+1,s);
                    s.deleteCharAt(index);
                }
            }
        }

    }
```



## [18. 四数之和 - 力扣（LeetCode）](https://leetcode.cn/problems/4sum/)

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

- 0 <= a, b, c, d < n
- a、b、c 和 d 互不相同
- nums[a] + nums[b] + nums[c] + nums[d] == target
- 你可以按 任意顺序 返回答案 。

 ```java
示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]
 ```


提示：

- 1 <= nums.length <= 200
- -109 <= nums[i] <= 109
- -109 <= target <= 109

**基本思想：双指针**

是三数之和的变形，在三数之和的基础上增加了第四个数和target，所以现在可以把它转化成三数之和的形式，然后再采用三数之和的解法进行解题。  

a+b+c+d=target，这个等式可以换成b+c+d=target-a=newTarget的形式，第一层循环index选出一个数与target做减法得到新的target，第二层循环i从index+1开始作为b，第三层与第四层利用双指针合在一起，如果加和小与新的target并且j<k那么k--;如果j==k，说明无解，否则如果相等就加入到list。     

源代码：

```java
class Solution {
        public List<List<Integer>> fourSum(int[] nums, int target) {
            List<List<Integer>>result=new ArrayList<>();
            if(nums.length<4)return result;
            Arrays.sort(nums);
            for(int index=0;index<nums.length;index++) {
                if(index>0&&nums[index]==nums[index-1])
                    continue;
                int temp = target - nums[index];
                for (int i = index + 1; i < nums.length-2; i++) {
                    if(i>index+1&&nums[i]==nums[i-1])continue;

                    int k = nums.length - 1;
                    for (int j = i + 1; j < nums.length-1; j++) {
                        if(j>i+1&&nums[j]==nums[j-1])continue;
                        if (j<k&&nums[i] + nums[j] + nums[k]>temp){
                            while(j<k&&nums[i] + nums[j] + nums[k]>temp)
                                k--;
                        }
                        if(j==k)break;
                        if (nums[i] + nums[j] + nums[k] == temp) {
                            List<Integer> sum = new ArrayList<>();
                            sum.add(nums[index]);
                            sum.add(nums[i]);
                            sum.add(nums[j]);
                            sum.add(nums[k]);
                            result.add(sum);
                        }
                    }

                }
            }
            return result;
        }
```



## [19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）](https://leetcode.cn/problems/remove-nth-node-from-end-of-list/)

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

 

示例 1：

![img](https://assets.leetcode.com/uploads/2020/10/03/remove_ex1.jpg)

```java
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
```

示例 2：

```java
输入：head = [1], n = 1
输出：[]
```

示例 3：

```java
输入：head = [1,2], n = 1
输出：[1]
```


提示：

- 链表中结点的数目为 sz
- 1 <= sz <= 30
- 0 <= Node.val <= 100
- 1 <= n <= sz

**基本思想：两次扫描**

两次扫描链表，第一次得到链表的长度，第二次定位到要删除的节点进行删除，可以添加一个头结点，这样在删除头结点的时候就不用进行判断。

源代码：

```java
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
       ListNode yum=new ListNode(0,head);
            ListNode p=yum;
            int length=0;
            while(p.next!=null){
                length++;
                p=p.next;
            }
            p=yum;
            for(int i=0;i<length-n;i++){
                p=p.next;
            }
            p.next=p.next.next;
            return yum.next;
    }
}
```

## [20. 有效的括号 - 力扣（LeetCode）](https://leetcode.cn/problems/valid-parentheses/submissions/)

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。


示例 1：

```java
输入：s = "()"
输出：true
```

示例 2：

```java
输入：s = "()[]{}"
输出：true
```

示例 3：

```java
输入：s = "(]"
输出：false
```

示例 4：

```java
输入：s = "([)]"
输出：false
```

示例 5：

```java
输入：s = "{[]}"
输出：true
```


提示：

- 1 <= s.length <= 104
- s 仅由括号 '()[]{}' 组成

**基本思想：栈，符号匹配**

如果是左边的符号直接入栈，如果是右边的符号则与栈顶符号匹配，成功就继续否则匹配失败。如果右边符号匹配时栈为空则匹配失败，如果匹配完成后栈不空，匹配失败。

源代码：

```java
class Solution {
    public boolean isValid(String s) {
        Stack<Character>judge=new Stack<>();
            for(int i=0;i<s.length();i++){
                char tmp=s.charAt(i);
                if(tmp=='('||tmp=='{'||tmp=='['){
                    judge.push(tmp);
                }
                else{
                    if(judge.empty())return false;
                    char c= judge.pop();
                    if(tmp==']'&&c!='[')return false;
                    if(tmp==')'&&c!='(')return false;
                    if(tmp=='}'&&c!='{')return false;
                }
                
            }
            
             if(!judge.empty())return false;
            return true;
    }
}
```

## [21. 合并两个有序链表 - 力扣（LeetCode）](https://leetcode.cn/problems/merge-two-sorted-lists/)

将两个升序链表合并为一个新的 **升序** 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例 1：

![img](https://assets.leetcode.com/uploads/2020/10/03/merge_ex1.jpg)

```java
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
```

示例 2：

```java
输入：l1 = [], l2 = []
输出：[]
```

示例 3：

```java
输入：l1 = [], l2 = [0]
输出：[0]
```


提示：

- 两个链表的节点数目范围是 [0, 50]
- -100 <= Node.val <= 100
- l1 和 l2 均按 非递减顺序 排列

**方法一：直接遍历**

定义一个带头结点的新链表头，p1和p2都没有遍历完时就进行比较小的那一个加到新链表中，然后继续遍历比较。当有一个链表空了把不空的加入到后边。

源代码：

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode p1=list1,p2=list2,head=new ListNode(0,null),p=head;
            while(p1!=null&&p2!=null){//如果都不空，比较添加
                if(p1.val<=p2.val){
                    p.next=p1;
                    p=p.next;
                    p1=p1.next;
                }
                else {
                    p.next=p2;
                    p=p.next;
                    p2=p2.next;
                }
            }
        	//将剩余的链表追加
            if(p1!=null){
                p.next=p1;
            }
            if(p2!=null){
                p.next=p2;
            }
            return head.next;
    }
}
```

**方法二：递归**

我们可以如下递归地定义两个链表里的 merge 操作（忽略边界情况，比如空链表等）：

$$
\begin{cases}
list1[0]+merge(list1[1:],list2)&list1[0]<list2[0]\\
list2[0]+merge(list1,list2[1:])&otherwise
\end{cases}
$$


也就是说，两个链表头部值较小的一个节点与剩下元素的 merge 操作结果合并。

```java
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}
```

## [22. 括号生成 - 力扣（LeetCode）](https://leetcode.cn/problems/generate-parentheses/)

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

```java
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
```


示例 2：

```java
输入：n = 1
输出：["()"]
```


提示：

1 <= n <= 8

基本思想：动态规划

```tex
假设dp[i]表示有i个括号时的所有组合，那么dp[i+1]="("+dp[i][j]+")"+dp[i][i-1-j],其中j=0,1...i-1
所有的括号组合最左边一定是"("，最右边一定是")"，那么第n个括号组合可以看做由第n-1个括号组合推导而来，即在"("和")"之间的和在")"的括号加起来的组合
```

源代码：

```java
class Solution {
    public List<String> generateParenthesis(int n) {
        Map<Integer,List<String>>listMap=new HashMap<>();
            List<String>tmp=new ArrayList<>();
            tmp.add("");
            listMap.put(0,tmp);
            tmp=new ArrayList<>();//这里不要使用tmp.clear()，否则map中的list会被覆盖
            tmp.add("()");
            listMap.put(1,tmp);
            if(n==1)return listMap.get(1);
            for(int i=2;i<=n;i++){
                tmp=new ArrayList<>();
                for(int j=0;j<=i-1;j++){
                    for(int k=0;k<listMap.get(j).size();k++) {
                        for (int l = 0; l < listMap.get(i - 1 - j).size(); l++) {
                            tmp.add("(" + listMap.get(j).get(k) + ")" + listMap.get(i - 1 - j).get(l));
                        }
                    }
                }
                listMap.put(i,tmp);
            }

            return listMap.get(n);
    }
}
```

## [23. 合并K个升序链表 - 力扣（LeetCode）](https://leetcode.cn/problems/merge-k-sorted-lists/)

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

 

示例 1：

```java
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
```


示例 2：

```java
输入：lists = []
输出：[]
示例 3：

输入：lists = [[]]
输出：[]
```


提示：

- k == lists.length
- 0 <= k <= 10^4
- 0 <= lists[i].length <= 500
- -10^4 <= lists[i][j] <= 10^4
- lists[i] 按 升序 排列
- lists[i].length 的总和不超过 10^4

链表结构：

```java
 public  class ListNode {
          int val;
          ListNode next;
          ListNode() {}
          ListNode(int val) { this.val = val; }
          ListNode(int val, ListNode next) { this.val = val; this.next = next; }
      }
```



基本思想：1.顺序合并 2.分治法

- 顺序合并：在之前有一个两个链表的合并，我们利用一个虚结点作为头结点，然后遍历合并两个链表，得到一个有序的链表，返回头结点的next，这是基本的两个链表的合并。对于一个链表数组，我们可以首先用一个空链表与其中一个链表合并，得到的结果再与剩余的两两合并，合并n次，返回一个结果，比较耗时100ms

源代码：

```java
//暴力合并，两两合并
class Solution {
            public ListNode mergeKLists(ListNode[] lists) {
                if(lists.length==0)return null;
                if(lists.length==1)return lists[0];
                ListNode head=null;
                for(int i=0;i< lists.length;i++)
                    head=merge(head,lists[i]);
                return head;
            }
            public ListNode merge(ListNode l1,ListNode l2){
                ListNode head=new ListNode(0,null),h=head;
                if(l1==null) return l2;
                if(l2==null) return l1;
                ListNode p1=l1,p2=l2;
                while(p1!=null&&p2!=null){
                    if(p1.val<=p2.val){
                        h.next=p1;
                        p1=p1.next;
                    }
                    else {
                        h.next=p2;
                        p2=p2.next;
                    }
                    h=h.next;
                }
                if(p1!=null)h.next=p1;
                if(p2!=null)h.next=p2;

                return head.next;
            }
      }
```

- 分治法：将链表数组中的链表两两合并，得到的结果继续两两合并，最终得到一个链表；

源代码：

```java
//分治
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
            ListNode head=divide(lists,0, lists.length-1);
            return head;
        }
        public ListNode divide(ListNode[] lists,int l,int r){
            if(l==r)return lists[l];
            if(l>r)return null;
            int mid=(l+r)>>1;
            return merge(divide(lists,l,mid),divide(lists,mid+1,r));
        }

        public ListNode merge(ListNode l1,ListNode l2){
            ListNode head=new ListNode(0,null),h=head;
            if(l1==null) return l2;
            if(l2==null) return l1;
            ListNode p1=l1,p2=l2;
            while(p1!=null&&p2!=null){
                if(p1.val<=p2.val){
                    h.next=p1;
                    p1=p1.next;
                }
                else {
                    h.next=p2;
                    p2=p2.next;
                }
                h=h.next;
            }
            if(p1!=null)h.next=p1;
            if(p2!=null)h.next=p2;

            return head.next;
        }
    
}
```

## [24. 两两交换链表中的节点 - 力扣（LeetCode）](https://leetcode.cn/problems/swap-nodes-in-pairs/)

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

![img](https://assets.leetcode.com/uploads/2020/10/03/swap_ex1.jpg)

```java
输入：head = [1,2,3,4]
输出：[2,1,4,3]
```


示例 2：

```java
输入：head = []
输出：[]
```

示例 3：

```java
输入：head = [1]
输出：[1]
```


提示：

- 链表中节点的数目在范围 [0, 100] 内
- 0 <= Node.val <= 100

链表结构：

```java
 public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
```



基本思想：1.逆序链表 2.递归（官方）3.迭代（官方）

- 逆序链表：首先将链表逆序并且获得长度，然后按照局部逆序的块数再进行逆序获得结果

源代码：

```java
class Solution {
        public ListNode swapPairs(ListNode head) {
            if(head==null)return head; 
            ListNode h=new ListNode(1,null);
            int length=0;
            ListNode p=head,q,m;
            while(p!=null){
                length++;
                q=p.next;
                p.next=h;
                h=p;
                p=q;
            }
            if(length<2)return head;
            head=new ListNode(0,null);
            p=h;
            int mod=length%2,x=0;
            if(mod!=0){
                q=p;
                for(;x<mod-1;x++){
                    q=q.next;
                }
                m=q.next;
                q.next=head;
                head=p;
                p=m;
            }
            while(p.next!=null){
                q=p;
                for(x=0;x<2-1;x++){
                    q=q.next;
                }
                m=q.next;
                q.next=head;
                head=p;
                p=m;
            }
            p=head;
            while(p.next.next!=null)p=p.next;
            p.next=null;
            return head;
        }
```

- 递归：递归进行交换，例如1->2->3->4，我们每次交换前两个节点，后面的节点进行递归，具体是让2->1->递归(3->4)

源代码：

```java
class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = head.next;
        head.next = swapPairs(newHead.next);
        newHead.next = head;
        return newHead;
    }
}
```

- 迭代：创建一个虚节点，然后两两交换，返回结果

源代码：

```java
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode temp = dummyHead;
        while (temp.next != null && temp.next.next != null) {
            ListNode node1 = temp.next;
            ListNode node2 = temp.next.next;
            temp.next = node2;
            node1.next = node2.next;
            node2.next = node1;
            temp = node1;
        }
        return dummyHead.next;
    }
}
```

## [25. K 个一组翻转链表 - 力扣（LeetCode）](https://leetcode.cn/problems/reverse-nodes-in-k-group/)

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例 1：

![img](https://assets.leetcode.com/uploads/2020/10/03/reverse_ex1.jpg)

```java
输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]
```

示例 2：

![img](https://assets.leetcode.com/uploads/2020/10/03/reverse_ex2.jpg)

```java
输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]
```

提示：

- 链表中的节点数目为 n
- 1 <= k <= n <= 5000
- 0 <= Node.val <= 1000

链表结构：

```java
public static class ListNode {
         int val;
         ListNode next;
         ListNode() {}
         ListNode(int val) { this.val = val; }
         ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
```

基本思想：递归

在此之前，我们已经做过了两两交换链表的节点，那么我们可以沿用递归的思路，首先从头找到一组长度为k的链表，将它逆序，然后后半部分递归实现，如果长度不够那么直接返回。

源代码：

```java
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
            int length=0;
            if(k==1)return head;
            ListNode p=head,q=head;
            while(q!=null){
                length++;
                if(length==k){
                    ListNode s=p.next,m;
                    p.next=reverseKGroup(q.next,k);
                    while(s!=q){
                        m=s.next;
                        s.next=p;
                        p=s;
                        s=m;
                    }
                    s.next=p;
                    head=q;
                }
                q=q.next;
            }
            return head;
        }
}
```

## [26. 删除有序数组中的重复项 - 力扣（LeetCode）](https://leetcode.cn/problems/remove-duplicates-from-sorted-array/)

给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。

由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。

将最终结果插入 nums 的前 k 个位置后返回 k 。

不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

判题标准:

系统会用下面的代码来测试你的题解:

```java
int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案

int k = removeDuplicates(nums); // 调用

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}
```


如果所有断言都通过，那么您的题解将被 通过。

示例 1：

```java
输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
```

示例 2：

```java
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
```


提示：

- 0 <= nums.length <= 3 * 104
- -104 <= nums[i] <= 104
- nums 已按 升序 排列

基本思想：双指针

i作为遍历指针，j作为基指针，从1开始，如果nums[i]==nums[i-1]那么丢弃，否则nums[j++]=nums[i]，返回长度j；

源代码：

```java
class Solution {
    public int removeDuplicates(int[] nums) {
            if(nums.length<=1)return nums.length;
            int i=1,j=1;
            for(;i<nums.length;i++){
                if(nums[i]==nums[i-1])
                    continue;
                else{
                    nums[j++]=nums[i];
                }
                
            }
            return j;
        }
}
```

## [27. 移除元素 - 力扣（LeetCode）](https://leetcode.cn/problems/remove-element/)

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

 

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

```java
// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}
```


示例 1：

```java
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
```

示例 2：

```java
输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
```


提示：

- 0 <= nums.length <= 100
- 0 <= nums[i] <= 50
- 0 <= val <= 100

基本思想：双指针

i作为遍历指针，j作为基指针，从1开始，如果nums[i]==val那么丢弃，否则nums[j++]=nums[i]，返回长度j；

源代码：

```java
class Solution {
   public int removeElement(int[] nums, int val) {
            int i=0,j=0;
            for(;i<nums.length;i++){
                if(nums[i]==val){
                    continue;
                }
                else {
                    nums[j++]=nums[i];
                }
            }
            return j;
        }
}
```

## [28. 实现 strStr() - 力扣（LeetCode）](https://leetcode.cn/problems/implement-strstr/)

实现 strStr() 函数。

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回  -1 。

说明：

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。

示例 1：

```java
输入：haystack = "hello", needle = "ll"
输出：2
```

示例 2：

```java
输入：haystack = "aaaaa", needle = "bba"
输出：-1
```


提示：

- 1 <= haystack.length, needle.length <= 104
- haystack 和 needle 仅由小写英文字符组成

基本思想：KMP算法

首先求得next数组，然后进行匹配，如果匹配那么继续，如果不匹配就回退，外层永远不回退，回退内层，j=next[j]；

源代码：

```java
class Solution {
    public int strStr(String haystack, String needle) {
            int[] next=new int[needle.length()];
            getKMP(next,needle);
            for(int i=0,j=0;i<haystack.length();i++) {
                while (j>0&&haystack.charAt(i)!=needle.charAt(j)) {
                    j=next[j];
                }
                if(haystack.charAt(i)==needle.charAt(j)){
                    j++;
                }
                if(j==needle.length()){
                    return i-j+1;
                }
            }
            return -1;

        }
        void getKMP(int[] next,String str){
            int j=0,k=-1;
            next[j]=k;
            while(j<str.length()-1){
                if(k==-1||str.charAt(j)==str.charAt(k)){
                    j++;
                    k++;
                    next[j]=k;
                }
                else {
                    k=next[k];
                }
            }

        }
}
```

## [29. 两数相除 - 力扣（LeetCode）](https://leetcode.cn/problems/divide-two-integers/)

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

 

示例 1:

```java
输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = truncate(3.33333..) = truncate(3) = 3
```

示例 2:

```java
输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = truncate(-2.33333..) = -2
```


提示：

- 被除数和除数均为 32 位有符号整数。
- 除数不为 0。
  假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231,  231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。

基本思想：位运算

本题要求不能使用除、取余运算，那么使用位运算，注意边界，符号问题可以使用异或运算^来解决，从i=31开始，dividend>>i，如果大于除数divisor，那么说明找到了最大的位运算位数，result+=1<<i，dividen-=divisor<<i；继续运算，知道循环结束

源代码：

```java
class Solution {
   public int divide(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==0)return 0;
            boolean flag=(dividend^divisor)<0;
            int result=0;
            long a=dividend,b=divisor;
            if(dividend<0)a=Math.abs((long)dividend);
            if(divisor<0)b=Math.abs((long)divisor);
            for(int i=31;i>=0;i--){
                if(a>>i >= b)
                {
                    result+=1<<i;
                    a-=b<<i;
                }
            }
            return flag?-result:result;

        }
}
```

## [30. 串联所有单词的子串 - 力扣（LeetCode）](https://leetcode.cn/problems/substring-with-concatenation-of-all-words/)

给定一个字符串 s 和一些 长度相同 的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配，中间不能有其他字符 ，但不需要考虑 words 中单词串联的顺序。

 

示例 1：

```java
输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。
```

示例 2：

```java
输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出：[]
```

示例 3：

```java
输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出：[6,9,12]
```


提示：

- 1 <= s.length <= 104
- s 由小写英文字母组成
- 1 <= words.length <= 5000
- 1 <= words[i].length <= 30
- words[i] 由小写英文字母组成

**基本思想：首先用map统计words中的单词的出现次数，然后在根据子串的长度遍历s，每次取子串，分割成与words中的单词长度相等的单词，如果在map中没有就舍弃子串，如果存在数量对应相等那么保存index**

源代码：

```java
class Solution {
  public List<Integer>findSubstring(String s,String words[]){
            List<Integer>result=new ArrayList<>();
            HashMap<String,Integer>map1=new HashMap<>();
            int len=words[0].length(),tmplen=len* words.length;

            for(int i=0;i<words.length;i++){
                if (map1.get(words[i]) == null) {
                    map1.put(words[i], 1);
                } else {
                    int y = map1.get(words[i]);
                    map1.put(words[i], ++y);
                }
            }
            int num=0;
            Map<String,Integer>map2;
            for(int i=0;i<s.length()- words.length*len+1;i++){
                num=0;
                String tmp = s.substring(i, i + words.length * len);
                map2 = new HashMap<>();
                while(num<tmplen) {
                    String tmp1=tmp.substring(num,num+len);
                    //System.out.println(tmp1);
                    if (map1.containsKey(tmp1)) {
                        int value = map2.getOrDefault(tmp1, 0);
                        map2.put(tmp1, ++value);
                        if (map2.get(tmp1) > map1.get(tmp1)) {
                            break;
                        }
                        num+=len;

                    } else {
                        break;
                    }

                }
                if(num==tmplen)result.add(i);
            }
            return result;

        }


}
```

## [31. 下一个排列 - 力扣（LeetCode）](https://leetcode.cn/problems/next-permutation/)

整数数组的一个 排列  就是将其所有成员以序列或线性顺序排列。

- 例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
  整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

- 例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
  类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
  而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
  给你一个整数数组 nums ，找出 nums 的下一个排列。

- 必须 原地 修改，只允许使用额外常数空间。

 

示例 1：

```java
输入：nums = [1,2,3]
输出：[1,3,2]
```

示例 2：

```java
输入：nums = [3,2,1]
输出：[1,2,3]
```

示例 3：

```java
输入：nums = [1,1,5]
输出：[1,5,1]
```

基本思想：字典排序

**字典排序：
第一步：从右至左找第一个左邻小于右邻的数，记下位置i，值list[a]
第二部：从右边往左找第一个右边大于list[a]的第一个值，记下位置j，值list[b] 
第三步：交换list[a]和list[b]的值
第四步：将i以后的元素重新按从小到大的顺序排列**

源代码：

```java
class Solution {
    public void nextPermutation(int[] nums) {
            int x=-1,y=0;
            for(int i= nums.length-1;i>0;i--){
                if(nums[i]>nums[i-1]){
                    x=i-1;
                    break;
                }
            }
            if(x==-1){
                quickSort(nums,0, nums.length-1);
                return;
            }

            for(int i=nums.length-1;i>x;i--){
                if(nums[i]>nums[x]){
                    y=i;
                    break;
                }
            }
           
            int t=nums[x];
            nums[x]=nums[y];
            nums[y]=t;
            quickSort(nums,x+1, nums.length-1);
        

            return;
        }
        //快排
        public static void quickSort(int[] a,int left,int right){
            int i,j,temp;
            if(left>right)
                return;

            temp=a[left];
            i=left;
            j=right;
            while(i<j){
                 while(a[j]>=temp&&j>i)
                    j--;
                while(a[i]<=temp&&i<j)
                    i++;
                if(i<j){
                    int t=a[j];
                    a[j]=a[i];
                    a[i]=t;
                }
            }
            a[left]=a[i];
            a[i]=temp;
            quickSort(a,left,i-1);
            quickSort(a,i+1,right);
        }
}
```

## [32. 最长有效括号 - 力扣（LeetCode）](https://leetcode.cn/problems/longest-valid-parentheses/)

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

 

示例 1：

```java
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
```

示例 2：

```java
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"
```

示例 3：

```java
输入：s = ""
输出：0
```


提示：

- 0 <= s.length <= 3 * 104
- s[i] 为 '(' 或 ')'

基本思路：1.动态规划 2.栈 3.左右计数扫描

- **动态规化**

记dp[i]为以下标i结尾的子串有效字符串的最长长度，显然，如果s[i]=='('，那么dp[i]=0。如果s[i]==')',那么对s[i-1]进行判断，

如果s[i-1]=='('，这时正好匹配，dp[i]=dp[i-2]+2；

如果s[i-1]==')'，假设c为s[i-1-dp[i-1]]那么字符串的格局是  ....c......))，如果c=='('，那么dp[i]=dp[i-1]+dp[i-2-dp[i-1]]+2。

源代码：

```java
class Solution {
    public int longestValidParentheses(String s) {
        int[] dp=new int[s.length()];
        int maxlen=0;
        for(int i=1;i<s.length();i++){
            if(s.charAt(i)==')'){
                if(s.charAt(i-1)=='('){
                    if(i>=2){
                        dp[i]=dp[i-2]+2;
                    }
                    else{
                        dp[i]=2;
                    }
                }
                if(s.charAt(i-1)==')'){
                    if(i-dp[i-1]-1>=0&&s.charAt(i-dp[i-1]-1)=='('){
                        dp[i]=dp[i-1]+(i-dp[i-1]-2>0?dp[i-dp[i-1]-2]:0)+2;
                    }
                }

            }
            if(dp[i]>maxlen)maxlen=dp[i];
        }
        return maxlen;
    }
}
```



- **栈**

符号匹配的基本方法就是使用栈，我们对符号串进行遍历，对符号进行如下处理：

如果遇到'('，那么就将它的下标压入栈

如果遇到')'，那么就弹出栈顶元素视为匹配，如果栈为空，将下标压入栈，如果栈不空，计算下标与栈顶元素的差作为最大长度

初始栈中压入-1。

源代码：

```java
class Solution {
    public int longestValidParentheses(String s) {
        int maxlen=0;
        Stack<Integer>stack=new Stack<>();
        stack.push(-1);
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='(')
                stack.push(i);
            if(s.charAt(i)==')'){
                int x=stack.pop();
                if(stack.isEmpty()){
                    stack.push(i);
                }
                else{

                    if(i-stack.peek()>maxlen)maxlen=i-stack.peek();

                }
            }

        }
        return maxlen;
    }
}
```

- 左右计数扫描

正向逆向扫描，从左到右扫描，如果是'('，那么left++，如果是')'，那么right++。

如果right>left，那么left和right都置为0，如果left==right，那么计算最大长度。

从右向左扫描，如果是'('，那么left++，如果是')'，那么right++。

如果right<left，那么left和right都置为0，如果left==right，那么计算最大长度。

源代码：

```java
class Solution {
    public int longestValidParentheses(String s) {
        int maxlen=0;
        int left=0,right=0;
        int left1=0,right1=0;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='('){
                left++;
            }
            if(s.charAt(i)==')'){
                right++;
            }
            if(right>left){
                left=0;
                right=0;
            }
            if(left==right){
                if(left+right>maxlen){
                    maxlen=left+right;
                }
            }

            if(s.charAt(s.length()-i-1)=='('){
                left1++;
            }
            if(s.charAt(s.length()-i-1)==')'){
                right1++;
            }
            if(left1>right1){
                left1=0;
                right1=0;
            }
            if(left1==right1){
                if(left1+right1>maxlen)
                    maxlen=left1+right1;
            }
        }
        return maxlen;
    }
}
```

## [33. 搜索旋转排序数组 - 力扣（LeetCode）](https://leetcode.cn/problems/search-in-rotated-sorted-array/)

整数数组 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) 的算法解决此问题。

 

示例 1：

```java
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
```

示例 2：

```java
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1
```

示例 3：

```java
输入：nums = [1], target = 0
输出：-1
```


提示：

- 1 <= nums.length <= 5000
- -104 <= nums[i] <= 104
- nums 中的每个值都 独一无二
- 题目数据保证 nums 在预先未知的某个下标上进行了旋转
- -104 <= target <= 104

基本思想：

时间复杂度为log n，那么想到就是二分查找，但是现在 不是有序的，一个最简单的思路就是用二分查找找到旋转点，一分为二再二分查找target，时间复杂度也是log n。

源代码：

```java
class Solution {
    public int search(int[] nums, int target) {

            int index=binarySearch(nums,0,nums.length-1);
            if(index==-1)return binarySearch(nums,0, nums.length-1,target);
            if(target<nums[index+1]||target>nums[index])return -1;
            if(target>nums[nums.length-1])return binarySearch(nums,0,index,target);
            return binarySearch(nums,index+1, nums.length-1,target);

        }
        public int binarySearch(int[] nums,int left,int right){
            if(left>right)return -1;
            int mid=(left+right)/2;
            if(mid== nums.length-1)return -1;
            if(nums[mid]>nums[mid+1]){
                return mid;
            }
            if(nums[mid]<nums[right]&&nums[mid]<nums[left]){
                return binarySearch(nums,left,mid-1);
            }
            return binarySearch(nums,mid+1,right);
        }

        public int binarySearch(int nums[],int left,int right,int target){
            if(left>right)return -1;
            int mid=(left+right)/2;
            if(nums[mid]==target)return mid;
            if(nums[mid]>target)return binarySearch(nums,left,mid-1,target);
            return binarySearch(nums,mid+1,right,target);
    }
}
```

还有一种思路：

将数组一分为二，其中一定有一个是有序的，另一个可能是有序，也能是部分有序。
此时有序部分用二分法查找。无序部分再一分为二，其中一个一定有序，另一个可能有序，可能无序。就这样循环. 



源代码：

```java
class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        if (n == 0) {
            return -1;
        }
        if (n == 1) {
            return nums[0] == target ? 0 : -1;
        }
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[0] <= nums[mid]) {
                if (nums[0] <= target && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[n - 1]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return -1;
    }
}
```

## [34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）](https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/)

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

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

 

示例 1：

```java
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
```

示例 2：

```java
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
```

示例 3：

```java
输入：nums = [], target = 0
输出：[-1,-1]
```


提示：

- 0 <= nums.length <= 105
- -109 <= nums[i] <= 109
- nums 是一个非递减数组
- -109 <= target <= 109

基本思想：

看到时间复杂度是log n就是二分查找，最简单的就是先二分查找，然后在找到的节点左右扩展边界，这样有点取巧，在最坏的情况下时间复杂度不是log n

源代码：

```java
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] result=new int[2];
        result[0]=binarySearch(nums,0,nums.length-1,target);
        if(result[0]==-1){

            result[1]=-1;
            return result;
        }
        int x=result[0],y=result[0];
        while(nums[x]==target&&x>0)x--;
        if(nums[0]==target)result[0]=0;
        else result[0]=x+1;
        while (nums[y]==target&&y<nums.length-1)y++;
        if(nums[nums.length-1]==target)result[1]= nums.length-1;
        else result[1]=y-1;
        return result;
    }
    public int binarySearch(int nums[],int left,int right,int target){
        if(left>right)return -1;
        int mid=(left+right)/2;
        if(nums[mid]==target)return mid;
        if(nums[mid]>target)return binarySearch(nums,left,mid-1,target);
        return binarySearch(nums,mid+1,right,target);
    }
}
```



如果不取巧，可以使用二分的思想，直接求得边界

源代码：

```java
class SolutionTwo {
    public int[] searchRange(int[] nums, int target) {
        int left=binary(nums,target,0, nums.length-1,true );
        int right=binary(nums,target,0, nums.length-1,false)-1;
        System.out.println(left+"\n"+right);
        if(left<=right&&right< nums.length&&nums[left]==target&&nums[right]==target){
            return new int[]{left,right};
        }


        return new int[]{-1,-1};
    }
    public int binary(int[] nums,int target,int left,int right,Boolean flag){
        int i=left,j=right,ans= nums.length;
        while(i<=j){
            int mid=(i+j)/2;
            if(nums[mid]>target||(flag&&nums[mid]>=target)){
                j=mid-1;
                ans=mid;
            }
            else{
                i=mid+1;
            }
        }
        return ans;
    }
}
```



## [35. 搜索插入位置 - 力扣（LeetCode）](https://leetcode.cn/problems/search-insert-position/)

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

 

示例 1:

```java
输入: nums = [1,3,5,6], target = 5
输出: 2
```

示例 2:

```java
输入: nums = [1,3,5,6], target = 2
输出: 1
```

示例 3:

```java
输入: nums = [1,3,5,6], target = 7
输出: 4
```


提示:

- 1 <= nums.length <= 104
- -104 <= nums[i] <= 104
- nums 为 无重复元素 的 升序 排列数组
- -104 <= target <= 104

基本思想：

二分查找，用二分查找经典模板即可

```java
class Solution {
     public int searchInsert(int[] nums, int target) {
            int left=0,right=nums.length-1;
            while(left<=right){
                int mid=(left+right)>>1;
                if(nums[mid]>=target){
                    right=mid-1;
                }
                else {
                    left=mid+1;
                }
            }

            return left;
        }
}
```

## [36. 有效的数独 - 力扣（LeetCode）](https://leetcode.cn/problems/valid-sudoku/)



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

1. 数字 1-9 在每一行只能出现一次。

2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）


注意：

- 一个有效的数独（部分已被填充）不一定是可解的。
- 只需要根据以上规则，验证已经填入的数字是否有效即可。
- 空白格用 '.' 表示。

示例 1：

![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/04/12/250px-sudoku-by-l2g-20050714svg.png)

```java
输入：board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：true
```

示例 2：

```java
输入：board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
```


提示：

- board.length == 9

- board[i].length == 9
- board[i][j] 是一位数字（1-9）或者 '.'

基本思想：一次遍历，我们可以用row[9] [9]数组记录每一行的1-9数字的个数，比如row[1] [8]就是第二行的9的个数，我们可以用board[i] [j]-'1'获得数字的标号，同理col[9] [9]记录每一列的数字的个数，sub[3] [3] [9]记录每一个九宫格的数字的个数，(i/3,j/3)，就是第几个九宫格的坐标。如果数字个数大于1就返回false，否则返回true。

源代码：

```java
class Solution {
    public boolean isValidSudoku(char[][] board) {
            int[][] row=new int[9][9];
            int[][] col=new int[9][9];
            int[][][] sub=new int[3][3][9];
            for(int i=0;i<9;i++){
                for(int j=0;j<9;j++){
                    if(board[i][j]!='.'){
                        int index=board[i][j]-'1';
                        row[i][index]++;
                        col[j][index]++;
                        sub[i/3][j/3][index]++;
                        if(row[i][index]>1||col[j][index]>1||sub[i/3][j/3][index]>1)return false;
                    }
                }
            }

            return true;

        }
}
```

## [37. 解数独 - 力扣（LeetCode）](https://leetcode.cn/problems/sudoku-solver/)

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

1. 数字 1-9 在每一行只能出现一次。

2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
4. 数独部分空格内已填入了数字，空白格用 '.' 表示。

 

示例 1：

![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/04/12/250px-sudoku-by-l2g-20050714svg.png)

```java
输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
```

解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/04/12/250px-sudoku-by-l2g-20050714_solutionsvg.png)


提示：

- board.length == 9

- board[i].length == 9
- board[i][j] 是一位数字或者 '.'
- 题目数据 保证 输入数独仅有一个解

基本思想：回溯

首先采用有效的数独的判断数字的有效性记录在数组中，然后不断地试探，如果没有数字填入一个有效的数字然后试探下一位，如果失败就回溯，设置一个成功标志位，如果成功，那么就不在回溯。

源代码：

```java
class Solution {
     	int[][] row=new int[9][9];
        int[][] col=new int[9][9];
        int[][][] sub=new int[3][3][9];
        boolean isSuccess=false;
        public void solveSudoku(char[][] board) {
            for(int i=0;i<9;i++){
                for(int j=0;j<9;j++){
                    if(board[i][j]!='.'){
                        int index=board[i][j]-'1';
                        row[i][index]++;
                        col[j][index]++;
                        sub[i/3][j/3][index]++;
                    }

                }
            }
            baktrace(board,0);
            for(int i=0;i<9;i++){
                System.out.println(Arrays.toString(board[i]));
            }
        }
        public void baktrace(char[][] board,int n){
            if(n==81){
                isSuccess=true;
                return;
            }
            int x=n/9,y=n%9;
            if(board[x][y]!='.')baktrace(board,n+1);
            else {
                for (int i = 0; i < 9; i++) {
                    if (row[x][i] == 0 && col[y][i] == 0 && sub[x / 3][y / 3][i] == 0) {
                        board[x][y] = (char) (i + '1');
                        row[x][i]++;
                        col[y][i]++;
                        sub[x/3][y/3][i]++;
                        baktrace(board, n + 1);
                        if(!isSuccess) {
                            board[x][y] = '.';
                            row[x][i]--;
                            col[y][i]--;
                            sub[x / 3][y / 3][i]--;
                        }
                    }
                }
            }
        }
}
```

## [38. 外观数列 - 力扣（LeetCode）](https://leetcode.cn/problems/count-and-say/)

给定一个正整数 n ，输出外观数列的第 n 项。

「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。

你可以将其视作是由递归公式定义的数字字符串序列：

- countAndSay(1) = "1"
- countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。

前五项如下：

1.     1
2.     11
3.     21
4.     1211
5.     111221

```java
第一项是数字 1 
描述前一项，这个数是 1 即 “ 一 个 1 ”，记作 "11"
描述前一项，这个数是 11 即 “ 二 个 1 ” ，记作 "21"
描述前一项，这个数是 21 即 “ 一 个 2 + 一 个 1 ” ，记作 "1211"
描述前一项，这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ，记作 "111221"
要 描述 一个数字字符串，首先要将字符串分割为 最小 数量的组，每个组都由连续的最多 相同字符 组成。然后对于每个组，先描述字符的数量，然后描述字符，形成一个描述组。要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。
```

例如，数字字符串 "3322251" 的描述如下图：

![img](https://pic.leetcode-cn.com/1629874763-TGmKUh-image.png)


示例 1：

```java
输入：n = 1
输出："1"
解释：这是一个基本样例。
```

示例 2：

```java
输入：n = 4
输出："1211"
解释：
countAndSay(1) = "1"
countAndSay(2) = 读 "1" = 一 个 1 = "11"
countAndSay(3) = 读 "11" = 二 个 1 = "21"
countAndSay(4) = 读 "21" = 一 个 2 + 一 个 1 = "12" + "11" = "1211"
```

提示：

1 <= n <= 30

基本思想：按照题意进行模拟生成

源代码：

```java
class Solution {
    public String countAndSay(int n) {
            if(n==1)return "1";
            String[] s=new String[n];
            Arrays.fill(s,"");
            s[0]="1";
            for(int i=1;i<n;i++){
                int count=1;
                char c=s[i-1].charAt(0);
                for(int j=1;j<s[i-1].length();j++){
                    if(s[i-1].charAt(j)==c){
                        count++;
                    }
                    else {
                        s[i]+=count+String.valueOf(c);
                        c=s[i-1].charAt(j);
                        count=1;
                    }
                }
                s[i]+= count +String.valueOf(c);

            }
            return s[n-1];
        }
}
```

## [39. 组合总和 - 力扣（LeetCode）](https://leetcode.cn/problems/combination-sum/)

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

 

示例 1：

```java
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。
```

示例 2：

```java
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
```

示例 3：

```java
输入: candidates = [2], target = 1
输出: []
```


提示：

- 1 <= candidates.length <= 30
- 1 <= candidates[i] <= 200
- candidate 中的每个元素都 互不相同
- 1 <= target <= 500

基本思想：回溯

由于可以取重复的，回溯经典模板递归调用时n取i，而不是i+1

源代码：

```java
class Solution {
     public List<List<Integer>> combinationSum(int[] candidates, int target) {
            List<List<Integer>> result=new ArrayList<>();
            List<Integer>list=new ArrayList<>();
            backtrace(candidates,target,0,list,result);
            return result;
        }
        public void backtrace(int[] candidates,int target,int n,List<Integer>list,List<List<Integer>>result){

            if(target==0){
                result.add(new ArrayList<>(list));
                return;
            }
            if(target<0){
                return;
            }
            if(n==candidates.length)return;
          for(int i=n;i<candidates.length;i++) {
                if (target -candidates[i]>= 0) {
                    list.add(candidates[i]);
                    backtrace(candidates, target - candidates[i], i, list, result);
                    list.remove(list.size() - 1);
                }
            }

        }
}
```

## [40. 组合总和 II - 力扣（LeetCode）](https://leetcode.cn/problems/combination-sum-ii/)

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。 

示例 1:

```java
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
```

示例 2:

```java
输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]
```


提示:

- 1 <= candidates.length <= 100
- 1 <= candidates[i] <= 50
- 1 <= target <= 30

基本思想：回溯

与组合总和1不同的是，这里不能使用重复的数字，所以回溯时要用i+1，同时要去重，去重if(i>n&&candidates[i]==candidates[i-1])continue。

源代码：

```java
class Solution {
       public List<List<Integer>> combinationSum2(int[] candidates, int target) {
            List<List<Integer>>result=new ArrayList<>();
            List<Integer>list=new ArrayList<>();
            Arrays.sort(candidates);
            backtrace(candidates,0,target,list,result);
            return result;
        }
        public void backtrace(int[] candidates,int n,int target,List<Integer>list,List<List<Integer>>result){
            if(target==0){
                List<Integer>tmp=new ArrayList<>(list);
                result.add(tmp);
                return;
            }
            if(target<0){
                return;
            }
            if(n==candidates.length)return;
            for(int i=n;i<candidates.length;i++){
                if(i>n&&candidates[i]==candidates[i-1])continue;
                list.add(candidates[i]);
                backtrace(candidates,i+1,target-candidates[i],list,result);
                list.remove(list.size()-1);
            }


        }
}
```

## [41. 缺失的第一个正数 - 力扣（LeetCode）](https://leetcode.cn/problems/first-missing-positive/)

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。


示例 1：

```java
输入：nums = [1,2,0]
输出：3
```

示例 2：

```java
输入：nums = [3,4,-1,1]
输出：2
```

示例 3：

```java
输入：nums = [7,8,9,11,12]
输出：1
```


提示：

- 1 <= nums.length <= 5 * 105
- -231 <= nums[i] <= 231 - 1

基本思想：1.哈希 2.原地哈希 3.置换

所有的方法都是基于一个条件，对于数组中的负数（以下简称条件1）以及大于数组长度的数（以下简称条件2）都是可以丢弃的，三种方法对于这个条件的处理方法不一样。

- 哈希：第一次遍历对于所有不满足条件1和条件2的数，也就是数字大小在(0,nums.length]之间的数存到map[]中，使map[nums[i]]=1。第二次遍历，从i=1开始，如果map[i]==0，返回i+1。该方法不满足空间复杂度,仅供参考

源代码：

```java
class Solution {
    public int firstMissingPositive(int[] nums) {
        int[] map=new int[nums.length+1];
        for(int i=0;i< nums.length;i++){
            if(nums[i]>0&&nums[i]<= nums.length)map[nums[i]]=1;
        }
        int i;
        for ( i=1;i<=nums.length;i++){
            if(map[i]==0){
                return i;
            }
        }
        return i;
    }
}
```

- 原地哈希：与哈希不同，没有使用额外的空间作为哈希表，而是在nums的基础上进行哈希。第一次遍历对于所有满足条件1和条件2的数，都置为nums.length+1，这样所有的数字都是正数，并且所有满足条件的数都转换成满足条件2。第二次遍历，对于所有绝对值不满足条件的数nums[i]，将nums[nums[i]-1]置为负数，nums[nums[i]-1]为负表示正整数nums[i]存在。第三次遍历，从头开始，找到第一个不为负的下标i，返回i+1。

如图：![fig1](https://assets.leetcode-cn.com/solution-static/41/41_fig1.png)



源代码：

```java
class SolutionTwo {
    public int firstMissingPositive(int[] nums) {
        for(int i=0;i< nums.length;i++){
            if(nums[i]<=0)nums[i]=nums.length+1;
        }
        for(int i=0;i< nums.length;i++){
            int x=Math.abs(nums[i]);
            if(x<=nums.length){
                nums[x-1]=-Math.abs(nums[x-1]);
            }
        }
        int i=0;
        for(;i< nums.length;i++){
            if(nums[i]>0)break;
        }
        return i+1;
    }
}
```

- 置换：第一次遍历，对于所有的nums[i]，如果不满足条件1和条件2并且nums[i]!=nums[nums[i]-1]，那么就将nums[i]和nums[nums[i]-1]置换，如果置换后继续满足置换条件就继续置换。第二次遍历，找到第一个nums[i]!=i+1的i，返回i+1;

源代码：

```java
class Solution {
   public int firstMissingPositive(int[] nums) {
            for(int i=0;i<nums.length;i++){
                while(nums[i]>0&&nums[i]<= nums.length&&nums[nums[i]-1]!=nums[i]){
                    int t=nums[nums[i]-1];
                    nums[nums[i]-1]=nums[i];
                    nums[i]=t;
                }
            }
            int i=0;
            for(;i< nums.length;i++){
                if(nums[i]!=i+1)break;
            }
            return i+1;
        }
}
```

## [42. 接雨水 - 力扣（LeetCode）](https://leetcode.cn/problems/trapping-rain-water/)

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

 

示例 1：

![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/10/22/rainwatertrap.png)

```java
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
```


示例 2：

```java
输入：height = [4,2,0,3,2,5]
输出：9
```


提示：

- n == height.length

- 1 <= n <= 2 * 104
- 0 <= height[i] <= 105

基本思想：1.暴力 2.动态规划 3.单调栈 4.双指针

- 暴力：对于每一个柱子来说，它所在的构成接水的区域中所能接水的多少是包括它在内的左边的最高柱子和包括它在内的右边的最高柱子的最小值减去它本身，双层循环暴力解决

源代码：

```java
class Solution {
   public int trap(int[] height) {
            int left = 0, right = 0, sum = 0;
            for(int i=0;i< height.length;i++){
                left=0;
                right=0;
                for(int j=i;j>=0;j--){
                    left=Math.max(height[j],left);
                }
                for(int j=i;j< height.length;j++){
                    right=Math.max(height[j],right);
                }
                sum+=Math.min(left,right)-height[i];
            }

            return sum;
   	}
}
```



- 动态规划：对于暴力方法，对于每一个柱子都要找到左边和右边的最高的柱子，如果把左边和右边最高的柱子记录下来，那么就可以不用重复求左右最大柱子。可以使用left[i]来记录下标为i的柱子左边最大的柱子，使用right[i]来记录下标为i的柱子的右边的最大柱子，那么可以得到递推公式:

$$
\begin{cases}
left[i]=height[i]&i==0\\
left[i]=max\{height[i],left[i-1]\}&i>0\&\&i<height.length
\end{cases}
$$


$$
\begin{cases}
    right[i]=height[i]&i==height.length-1\\
    right[i]=max\{height[i],right[i+1]\}&i>0\&\&i<height.length-1
    \end{cases}
$$
得到left和right之后，sum+=min{left[i],right[i]}-height[i]

源代码：

```java
class Solution {
   public int trap(int[] height) {
            int[] left=new int[height.length];
            int[] right=new int[height.length];
            int sum=0;
            left[0]=height[0];
            right[height.length-1]=height[height.length-1];
            for(int i=1;i< height.length;i++)
                left[i]=Math.max(left[i-1],height[i]);
            for (int i = height.length-2; i >=0 ; i--) {
                right[i]=Math.max(right[i+1],height[i]);
            }

            for(int i=0;i< height.length;i++){
                sum+=Math.min(left[i],right[i])-height[i];
            }
            return sum;
    }
}
```

- 单调栈：维护一个递减的单调栈，里面存放的是柱子的下标，对于每一个柱子，如果小于栈顶柱子，那么将它的下标入栈。如果大于栈顶柱子，那么如果栈里的元素只有一个就出栈并将该柱子的下标入栈，如果有两个元素，那么出栈，当前元素减去栈顶元素乘两个元素的最小值与出栈的差值就是接雨水的量。

源代码：

```java
class Solution {
    public int trap(int[] height) {
            int sum=0;
            Stack<Integer> stack=new Stack<>();
            for (int i = 0; i < height.length; i++) {
                while(!stack.empty()&&height[i]>height[stack.peek()]){
                    int x=stack.pop();
                    if(stack.empty())break;
                    int j=stack.peek();
                    int k=i-j-1;
                    sum+=(Math.min(height[i],height[j])-height[x])*k;
                }
                stack.push(i);
            }
            return sum;
        }
}
```



# 剑指offer

## [剑指 Offer 03. 数组中重复的数字 - 力扣（LeetCode）](https://leetcode.cn/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/)

找出数组中重复的数字。


在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1：

```java
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3 
```


限制：

- 2 <= n <= 100000

基本思想：1.哈希 2.原地哈希

- 哈希：题目中已经说明数字在0~n-1之间，那么新建哈希数组hash[n]，对于每一个nums[i]，hash[nums[i]]++，如果大于1，说明重复，返回即可。

源代码：

```java
class Solution {
   public int findRepeatNumber(int[] nums) {
            int[] hash=new int[nums.length];
            int i;
            for(i=0;i<nums.length;i++)
            {
                hash[nums[i]]++;
                if(hash[nums[i]]>1)break;
            }

            return nums[i];
        }
}
```

## [剑指 Offer 04. 二维数组中的查找 - 力扣（LeetCode）](https://leetcode.cn/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/)

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

 

示例:

```java
现有矩阵 matrix 如下：

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。

给定 target = 20，返回 false。
```

限制：

- 0 <= n <= 1000


- 0 <= m <= 1000


基本思想：1.二分查找 2.线性查找

- 二分查找：对于每一行进行二分查找，得到结果

源代码：

```java
class Solution {
   public boolean findNumberIn2DArray(int[][] matrix, int target) {
            boolean ans=false;
            for(int i=0;i<matrix.length;i++){
                if(binary(matrix[i],target)!=-1){
                    ans=true;
                    break;
                }
            }

            return ans;
        }

        public int binary(int nums[],int target){
            int left=0,right= nums.length-1,ans=-1;
            while(left<=right){
                int mid=(left+right)>>1;
                if(nums[mid]==target){
                    ans=mid;
                    break;
                }
                else if(nums[mid]<target){
                    left=mid+1;
                }
                else {
                    right=mid-1;
                }
            }
            return ans;
        }
}
```

- 线性查找：从右上角到左下角进行查找，如果当前元素大于目标，那么去下一行，如果小于目标去上一列，如果相等返回true。

源代码：

```java
class Solution {
   public boolean findNumberIn2DArray(int[][] matrix, int target) {
            if(matrix.length==0)return false;
            boolean ans=false;
            int i=0,j=matrix[0].length-1;
            while(i<matrix.length&&j>=0){
                if(matrix[i][j]==target){
                    ans=true;
                    break;
                }
                else if(matrix[i][j]<target){
                    i++;
                }
                else j--;
            }

            return ans;
        }
}
```

## [剑指 Offer 05. 替换空格 - 力扣（LeetCode）](https://leetcode.cn/problems/ti-huan-kong-ge-lcof/)

请实现一个函数，把字符串 s 中的每个空格替换成"%20"。

 

示例 1：

```java
输入：s = "We are happy."
输出："We%20are%20happy."
```


限制：

- 0 <= s 的长度 <= 10000

基本思想：对于结果字符串，如果原来字符串中的字符不是空格就直接追加，否则追加"%20"。

源代码：

```java
class Solution {
     public String replaceSpace(String s) {
            String result="";
            for(int i=0;i<s.length();i++)
            {
                if(s.charAt(i)!=' ')
                    result+=s.charAt(i);
                else result+="%20";
            }
            return result;
        }
}
```



## [剑指 Offer 06. 从尾到头打印链表 - 力扣（LeetCode）](https://leetcode.cn/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/)

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

 

示例 1：

```java
输入：head = [1,3,2]
输出：[2,3,1]
```


限制：

- 0 <= 链表长度 <= 10000

基本思想：1.链表逆序 2.栈

- 链表逆序：先将链表逆序，然后输出

源代码：

```java
class Solution {
    public int[] reversePrint(ListNode head) {
            ListNode p=head,h=new ListNode(0),q;
            h.next=null;
            int length=0;
            while (p!=null){
                q=p.next;
                p.next=h.next;
                h.next=p;
                p=q;
                length++;
            }
            int[] result=new int[length];
            int i=0;
            p=h.next;
            while(p!=null){
                result[i++]=p.val;
                p=p.next;
            }

            return result;
        }
}
```

- 栈：可以正序遍历，将元素存放到栈中，然后出栈即为逆序

## [剑指 Offer 07. 重建二叉树 - 力扣（LeetCode）](https://leetcode.cn/problems/zhong-jian-er-cha-shu-lcof/)

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。



示例 1:

![img](https://assets.leetcode.com/uploads/2021/02/19/tree.jpg)

```java
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
```

示例 2:

```java
Input: preorder = [-1], inorder = [-1]
Output: [-1]
```


限制：

- 0 <= 节点个数 <= 5000

基本思想：经典的构造二叉树，根据前序遍历可以确定根节点，根据中序遍历可以确定左子树和右子树的元素，递归构造。

源代码：

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
     public TreeNode buildTree(int[] preorder, int[] inorder) {
         if(preorder.length==0)return null;
            TreeNode t = new TreeNode(0);
            build(t,preorder,inorder);
            return t;
        }
        public void build(TreeNode t,int[] preorder,int[] inorder){
            
            int tmp=preorder[0],index=0;
            t.val=tmp;
            for(int i=0;i<inorder.length;i++)
            {
                if(inorder[i]==tmp){
                    index=i;
                    break;
                }
            }
            int[] left=new int[index],right=new int[inorder.length-index-1];
            for(int i=0;i<index;i++)
                left[i]=inorder[i];
            for(int i=index+1;i<inorder.length;i++)
                right[i-index-1]=inorder[i];

            int[] pleft=new int[index],pright=new int[inorder.length-index-1];
            for(int i=1;i<=index;i++)
                pleft[i-1]=preorder[i];
            for (int i = index+1; i < preorder.length; i++)
                pright[i-1-index]=preorder[i];
            if(pleft.length==0)t.left=null;
            else{
                t.left=new TreeNode(0);
                build(t.left,pleft,left);
            }
            if(pright.length==0)t.right=null;
            else {
                t.right = new TreeNode(0);
                build(t.right, pright, right);
            }
        }
}
```

## [剑指 Offer 09. 用两个栈实现队列 - 力扣（LeetCode）](https://leetcode.cn/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/)

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

 

示例 1：

```java
输入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出：[null,null,3,-1]
```

示例 2：

输入：

```java
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]
```

提示：

- 1 <= values <= 10000
- 最多会对 appendTail、deleteHead 进行 10000 次调用

基本思想：一个栈入队，一个栈出队。

源代码：

```java
class CQueue {

     	Stack<Integer>head;
        Stack<Integer>tail;
        public CQueue() {
           head=new Stack<>();
           tail=new Stack<>();
        }

        public void appendTail(int value) {
            head.push(value);
        }

        public int deleteHead() {
            if(tail.empty()){
                if(head.empty())return -1;
                while(!head.empty())tail.push(head.pop());
            }
            return tail.pop();
        }
}
```

## [剑指 Offer 10- I. 斐波那契数列 - 力扣（LeetCode）](https://leetcode.cn/problems/fei-bo-na-qi-shu-lie-lcof/submissions/)

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

 

示例 1：

```java
输入：n = 2
输出：1
```

示例 2：

```java
输入：n = 5
输出：5
```


提示：

- 0 <= n <= 100

基本思想：

F(0) = 0,   F(1) = 1，F(N) = (F(N - 1) + F(N - 2))%1000000007,N>1

源代码：

```java
class Solution {
    public int fib(int n) {
            if(n==0)return 0;
            if(n==1)return 1;
            int[] result=new int[n];
            result[0]=1;
            result[1]=1;
            for(int i=2;i<n;i++){
                result[i]=(result[i-1]+result[i-2])%1000000007;
            }
            return result[n-1];
        }
}
```

## [剑指 Offer 10- II. 青蛙跳台阶问题 - 力扣（LeetCode）](https://leetcode.cn/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/)

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

```java
输入：n = 2
输出：2
```

示例 2：

```java
输入：n = 7
输出：21
```

示例 3：

```java
输入：n = 0
输出：1
```

提示：

- 0 <= n <= 100

基本思想：F(0) = 1,   F(1) = 2，F(N) = (F(N - 1) + F(N - 2))%1000000007,N>1

源代码：

```java
class Solution {
    public int numWays(int n) {
            if(n==0)return 1;
            if(n==1)return 1;
            int[] result=new int[n];
            result[0]=1;
            result[1]=2;
            for(int i=2;i<n;i++){
                result[i]=(result[i-1]+result[i-2])%1000000007;
            }
            return result[n-1];
        }
}
```

## [剑指 Offer 11. 旋转数组的最小数字 - 力扣（LeetCode）](https://leetcode.cn/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/)

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。  

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

 

示例 1：

```java
输入：numbers = [3,4,5,1,2]
输出：1
```

示例 2：

```java
输入：numbers = [2,2,2,0,1]
输出：0
```


提示：

- n == numbers.length

- 1 <= n <= 5000
- -5000 <= numbers[i] <= 5000
- numbers 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

基本思想：二分查找

数组是局部有序的，所以如果一分为二，那么必然有一部分有序，另一部分可以继续分，所以可以进行二分查找。在 进行mid寻找的时候可以用mid=left+(right-left)>>1，这样可以防止过大溢出。

源代码：

```java
class Solution {
    public int minArray(int[] numbers) {

            int left=0,right= numbers.length-1;
            while(left<=right){
               int mid=(left+right)>>1;
               if(numbers[mid]>numbers[right]){
                   left=mid+1;
               } else if (numbers[mid] == numbers[right]) {
                   if(numbers[left]<numbers[mid]){
                       right=mid-1;
                   }
                   else  {
                       left++;
                   }
               }
               else {
                    if (mid>0&&numbers[mid]>=numbers[mid-1]) {
                        right=mid-1;
                    }
                    else {
                        return numbers[mid];
                    }
               }
            }
            return numbers[right];
    }
}

//官方版
class Solution {
    public int minArray(int[] numbers) {
        int low = 0;
        int high = numbers.length - 1;
        while (low < high) {
            int pivot = low + (high - low) / 2;
            if (numbers[pivot] < numbers[high]) {
                high = pivot;
            } else if (numbers[pivot] > numbers[high]) {
                low = pivot + 1;
            } else {
                high -= 1;
            }
        }
        return numbers[low];
    }
}
```



## [剑指 Offer 12. 矩阵中的路径 - 力扣（LeetCode）](https://leetcode.cn/problems/ju-zhen-zhong-de-lu-jing-lcof/)

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

 

例如，在下面的 3×4 的矩阵中包含单词 "ABCCED"（单词中的字母已标出）。

![img](https://assets.leetcode.com/uploads/2020/11/04/word2.jpg)

 

示例 1：

```java
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true
```

示例 2：

```java
输入：board = [["a","b"],["c","d"]], word = "abcd"
输出：false
```


提示：

- 1 <= board.length <= 200
- 1 <= board[i].length <= 200
- board 和 word 仅由大小写英文字母组成

基本思想：回溯

对于每个节点，对它的上下左右节点进行试探，如果符合就继续，如果不符合就回溯。只有第一层可以顺序移动节点，其他的只能上下左右移动。

```java
class Solution {
   boolean isSuccess=false;
        public boolean exist(char[][] board, String word) {
            boolean[][] isUse=new boolean[board.length][board[0].length];
            for(int i=0;i< isUse.length;i++)
                Arrays.fill(isUse[i],false);
            backtrace(board,word,isUse,0,0,0);
            return isSuccess;
        }
        public void backtrace(char[][] board,String word,boolean[][] isUse,int r,int l,int len){
            if(len==word.length()){
                isSuccess=true;
                return;
            }
            if (r > board.length - 1 || l > board[0].length - 1 || r < 0 || l < 0||isSuccess) return;
            for(int i=r;i< board.length;i++)
                for (int j=l;j<board[0].length;j++) {
                    if (!isUse[i][j] && word.charAt(len) == board[i][j]) {
                        isUse[i][j] = true;
                        backtrace(board, word, isUse, i, j + 1, len+1);
                        backtrace(board, word, isUse, i + 1, j, len+1);
                        backtrace(board, word, isUse, i, j - 1, len+1);
                        backtrace(board, word, isUse, i - 1, j, len+1);
                        isUse[i][j] = false;
                    }
                    if(len>0)return;//除了第一层，都只能在其上下左右进行试探
                }

        }
}
```

## [剑指 Offer 13. 机器人的运动范围 - 力扣（LeetCode）](https://leetcode.cn/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/)

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

 

示例 1：

```java
输入：m = 2, n = 3, k = 1
输出：3
```

示例 2：

```java
输入：m = 3, n = 1, k = 0
输出：1
```

提示：

- 1 <= n,m <= 100
- 0 <= k <= 20

基本思想：广度优先搜索，使用队列进行广度搜索，每次扩展节点只向右和向下扩展。

源代码：

```java
class Solution {
   public int movingCount(int m, int n, int k) {
            if(k==0)return 1;
            int sum=0;
            boolean[][] access=new boolean[m][n];
            for(int i=0;i<m;i++)
                Arrays.fill(access[i],false);
            access[0][0]=true;
            if(n>1)access[0][1]=true;
            if(m>1)access[1][0]=true;
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    if((j>0&&access[i][j-1]|| i>0&&access[i-1][j])){
                        if(add(i)+add(j)>k)continue;
                        else {
                            access[i][j] = true;
                            if(j<n-1&&!access[i][j+1]){
                                if(add(i)+add(j+1)<=k)
                                    access[i][j+1]=true;
                            }
                            if(i<m-1&&!access[i+1][j]){
                                if(add(i+1)+add(j)<=k)
                                    access[i+1][j]=true;
                            }

                        }
                    }
                }
            }
            for (boolean[] booleans : access) {
                for (boolean aBoolean : booleans) {
                    if(aBoolean)sum++;
                }
            }
            return sum;
        }
         public int add(int n){
            int sum=0;
            while(n>0){
                sum+=n%10;
                n=n/10;
            }
            return sum;
        }
}

//官方版
class Solution {
    public int movingCount(int m, int n, int k) {
        if (k == 0) {
            return 1;
        }
        Queue<int[]> queue = new LinkedList<int[]>();
        // 向右和向下的方向数组
        int[] dx = {0, 1};
        int[] dy = {1, 0};
        boolean[][] vis = new boolean[m][n];
        queue.offer(new int[]{0, 0});
        vis[0][0] = true;
        int ans = 1;
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int x = cell[0], y = cell[1];
            for (int i = 0; i < 2; ++i) {
                int tx = dx[i] + x;
                int ty = dy[i] + y;
                if (tx < 0 || tx >= m || ty < 0 || ty >= n || vis[tx][ty] || get(tx) + get(ty) > k) {
                    continue;
                }
                queue.offer(new int[]{tx, ty});
                vis[tx][ty] = true;
                ans++;
            }
        }
        return ans;
    }

    private int get(int x) {
        int res = 0;
        while (x != 0) {
            res += x % 10;
            x /= 10;
        }
        return res;
    }
}
```

## [剑指 Offer 14- I. 剪绳子 - 力扣（LeetCode）](https://leetcode.cn/problems/jian-sheng-zi-lcof/)

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

示例 1：

```java
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1
```

示例 2:

```java
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
```

提示：

- 2 <= n <= 58

基本思想：1.动态规划  2.数学方法

- 动态规划：dp[i]表示长度为n的绳子的分割m段的最大乘积，那么对于dp[i]，对于每一个长度j，可以将绳子分为（j，i-j）两段或者（j，dp[i-j]）多段，求得最大乘积即可。状态转移方程：dp[i]=max(dp[i]，j * (i-j)，j * dp[i-j])

源代码：

```java
 //动态规划
class SolutionTwo {

        public int cuttingRope(int n) {
            if(n==2)return 1;
            int[] dp=new int[n+1];
            dp[0]=0;
            dp[1]=0;
            for(int i=2;i<=n;i++){
                for(int j=1;j<i;j++) {
                    int t=Math.max(j * (i - j), j * dp[i - j]);
                    if(t>dp[i])dp[i]=t;
                }
            }
            return dp[n];
        }
    }
```

- 数学方法：
  1. 任何大于1的数都可由2和3相加组成（根据奇偶证明）
  2. 因为2*2=1*4，2*3>1*5, 所以将数字拆成2和3，能得到的积最大
  3. 因为2*2*2<3*3, 所以3越多积越大 

源代码：

```java
class Solution {
 public int cuttingRope(int n) {
            if(n==2)return 1;
            if(n==3)return 2;
            int x=n/3,y=n%3;
            if(y==0 )return (int)Math.pow(3,x);
            if(y==1)return (int)Math.pow(3,x-1)*4;
            return (int)Math.pow(3,x)*2;
        }
}
```



## [剑指 Offer 14- II. 剪绳子 II - 力扣（LeetCode）](https://leetcode.cn/problems/jian-sheng-zi-ii-lcof/)

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m - 1] 。请问 k[0]*k[1]*...*k[m - 1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

 

示例 1：

```java
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1
```

示例 2:

```java
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
```


提示：

- 2 <= n <= 1000

基本思想：和上一题一样，注意取余

源代码：

```java
class Solution {
    public int cuttingRope(int n) {
            if(n<4)return n-1;
            long result=1;
            while(n>4){
                result*=3;
                result=result%1000000007;
                n-=3;
            }
            result=result*n;
            return (int)(result%1000000007);
        }
}
```

## [剑指 Offer 15. 二进制中1的个数 - 力扣（LeetCode）](https://leetcode.cn/problems/er-jin-zhi-zhong-1de-ge-shu-lcof/)

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为 汉明重量).）。

 

提示：

- 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
- 在 Java 中，编译器使用 二进制补码 记法来表示有符号整数。因此，在上面的 示例 3 中，输入表示有符号整数 -3。


示例 1：

```java
输入：n = 11 (控制台输入 00000000000000000000000000001011)
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
```

示例 2：

```java
输入：n = 128 (控制台输入 00000000000000000000000010000000)
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
```

示例 3：

```java
输入：n = 4294967293 (控制台输入 11111111111111111111111111111101，部分语言中 n = -3）
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。
```


提示：

- 输入必须是长度为 32 的 二进制串 。

基本思想：1.转化二进制遍历 2.n与2的i次方与运算，只有是1才是1

源代码：

```java
public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
            int sum=0;
            String s=Integer.toBinaryString(n);
            for(int i=0;i<s.length();i++){

                if(s.charAt(i)=='1')sum++;
            }

            return sum;
        }
}

public class Solution {
    public int hammingWeight(int n) {
        int ret = 0;
        for (int i = 0; i < 32; i++) {
            if ((n & (1 << i)) != 0) {
                ret++;
            }
        }
        return ret;
    }
}

```

## [剑指 Offer 16. 数值的整数次方 - 力扣（LeetCode）](https://leetcode.cn/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/)

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。

 

示例 1：

```java
输入：x = 2.00000, n = 10
输出：1024.00000
```

示例 2：

```java
输入：x = 2.10000, n = 3
输出：9.26100
```

示例 3：

```java
输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25
```


提示：

- -100.0 < x < 100.0
- -231 <= n <= 231-1
- -104 <= xn <= 104

基本思想：快速幂
$$
\begin{cases}
x^n=x^{n/2}*x^{n/2}&n为偶数\\
x^n=x^{n/2}*x^{n/2}*x&n为奇数
\end{cases}
$$
源代码：

```java
class Solution {
   public double myPow(double x, int n) {
            long N=n;
            return N>=0?quick(x,N):1/quick(x,-N);

        }
        public double quick(double x,long N){
            if(N==0)return 1;
            double y=quick(x,N/2);
            return N%2==0?y*y:y*y*x;

        }
}
```

## [剑指 Offer 17. 打印从1到最大的n位数 - 力扣（LeetCode）](https://leetcode.cn/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof/)

输入数字 `n`，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

**示例 1:**

```java
输入: n = 1
输出: [1,2,3,4,5,6,7,8,9]
```

说明：

- 用返回一个整数列表来代替打印
- n 为正整数

基本思想：直接模拟

源代码：

```java
class Solution {
   public int[] printNumbers(int n) {
            int[] result=new int[(int)Math.pow(10,n)-1];
            for(int i=0;i< result.length;i++){
                result[i]=i+1;
            }
            return result;
        }
}
```

## [剑指 Offer 18. 删除链表的节点 - 力扣（LeetCode）](https://leetcode.cn/problems/shan-chu-lian-biao-de-jie-dian-lcof/)

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

**注意：**此题对比原题有改动

**示例 1:**

```
输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
```

**示例 2:**

```
输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
```

**说明：**

- 题目保证链表中节点的值互不相同
- 若使用 C 或 C++ 语言，你不需要 `free` 或 `delete` 被删除的节点

基本思想：添加一个头指针，p在后边，q在前边，如果q为目标值那么删除，p.next=q.next

源代码：

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteNode(ListNode head, int val) {
            ListNode h=new ListNode(0);//虚节点
            h.next=head;
            ListNode p=h,q=h.next;
            while(q!=null){
                if(q.val!=val){
                    q=q.next;
                    p=p.next;
                }
                else {
                    p.next=q.next;
                    break;
                }
            }
            return h.next;
        }
}
```

## [剑指 Offer 19. 正则表达式匹配 - 力扣（LeetCode）](https://leetcode.cn/problems/zheng-ze-biao-da-shi-pi-pei-lcof/)

请实现一个函数用来匹配包含`'. '`和`'*'`的正则表达式。模式中的字符`'.'`表示任意一个字符，而`'*'`表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串`"aaa"`与模式`"a.a"`和`"ab*ac*a"`匹配，但与`"aa.a"`和`"ab*a"`均不匹配。

**示例 1:**

```
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
```

**示例 2:**

```
输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
```

**示例 3:**

```
输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
```

**示例 4:**

```
输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
```

**示例 5:**

```
输入:
s = "mississippi"
p = "mis*is*p*."
输出: false
```

- `s` 可能为空，且只包含从 `a-z` 的小写字母。
- `p` 可能为空，且只包含从 `a-z` 的小写字母以及字符 `.` 和 `*`，无连续的 `'*'`。

基本思想：动态规划

flag[i] [j]表示s的前i项与p的前j项的匹配情况。flag[0] [0]=true。

- 如果p[j]是字母，那么flag[i] [j]=flag[i-1] [j-1]&&s[i]==p[j]。

- 如果p[j]是'.'那么一定匹配，flag[i] [j]=flag[i-1] [j-1]。

- 如果p[j]是'*'：
  - 如果s[i]==p[j-1]，那么flag[i] [j]=flag[i-1] [j]（这个是把匹配的最后一位扔掉向前匹配）|| flag[i] [j-2]（这个是' * '前面的字母被匹配0次）
  - 如果s[i]!=p[j-1]，那么flag[i] [j]=flag[i] [j-2]（这个是' * '前面的字母被匹配0次）

源代码：

```java
class Solution {
    public boolean isMatch(String s, String p) {
            boolean[][] flag=new boolean[s.length()+1][p.length()+1];
            flag[0][0]=true;
            for(int i=1;i<=s.length();i++)
                flag[i][0]=false;
            for(int i=0;i<=s.length();i++){
                for(int j=1;j<=p.length();j++){
                    if(i==0){
                        if(p.charAt(j-1)=='*'){
                            flag[i][j]=flag[i][j-2];
                        }
                    }
                    else {
                        if(p.charAt(j-1)=='.'){
                            flag[i][j]=flag[i-1][j-1];
                        }
                        else if(p.charAt(j-1)=='*'){
                            if(s.charAt(i-1)!=p.charAt(j-2)&&p.charAt(j-2)!='.'){
                               flag[i][j]=flag[i][j-2];
                            }
                            else flag[i][j]=flag[i-1][j]||flag[i][j-2];
                        }
                        else {

                            flag[i][j]=flag[i-1][j-1]&&s.charAt(i-1)==p.charAt(j-1);
                        }

                    }

                }
            }
            return flag[s.length()][p.length()];
        }
}
```

## [剑指 Offer 21. 调整数组顺序使奇数位于偶数前面 - 力扣（LeetCode）](https://leetcode.cn/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/)

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。

 

**示例：**

```
输入：nums = [1,2,3,4]
输出：[1,3,2,4] 
注：[3,1,2,4] 也是正确的答案之一。
```

 

**提示：**

1. `0 <= nums.length <= 50000`
2. `0 <= nums[i] <= 10000`

基本思想：双指针，类似快排，左边指针发现偶数停下，右边指针发现奇数停下，然后交换继续，知道两个指针相等。

源代码：

```java
class Solution {
   public int[] exchange(int[] nums) {
            int left=0,right= nums.length-1;
            while(left<right){
                while (nums[right]%2==0&&left<right)
                    right--;
                while(nums[left]%2!=0&&left<right)
                    left++;

                if(left<right){
                    int temp=nums[left];
                    nums[left]=nums[right];
                    nums[right]=temp;
                }

            }
            return nums;
        }
}
```

## [剑指 Offer 22. 链表中倒数第k个节点 - 力扣（LeetCode）](https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/)

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 `6` 个节点，从头节点开始，它们的值依次是 `1、2、3、4、5、6`。这个链表的倒数第 `3` 个节点是值为 `4` 的节点。

 

**示例：**

```java
给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.
```

基本思想：1.栈 2.双指针

- 栈：先入栈所有节点，然后出栈k-1节点，返回栈顶节点

源代码：

```java
class Solution {
   public ListNode getKthFromEnd(ListNode head, int k) {
            Stack<ListNode>stack=new Stack<>();
            ListNode p=head;
            while(p!=null){
                stack.push(p);
                p=p.next;
            }
            int n=0;
            while(n<k-1){
                stack.pop();
                n++;
            }
            return stack.peek();
        }
}
```

- 双指针：前面指针指向第k+1个节点，后边指针指向第一个指针，然后前后指针一起走，前面走到结尾饭后后边节点。

源代码：

```java
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fast = head;
        ListNode slow = head;

        while (fast != null && k > 0) {
            fast = fast.next;
            k--;
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        return slow;
    }
}
```

## [剑指 Offer 24. 反转链表 - 力扣（LeetCode）](https://leetcode.cn/problems/fan-zhuan-lian-biao-lcof/)

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

 

**示例:**

```
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
```



**限制：**

```
0 <= 节点个数 <= 5000
```

基本思想：迭代，改变指针指向即可

源代码：

```java
class Solution {
     public ListNode reverseList(ListNode head) {
            ListNode h=new ListNode(0),p;
            while(head!=null){
                p=head.next;
                head.next=h.next;
                h.next=head;
                head=p;
            }
            return h.next;
        }
}

//官方的递归方法
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}
```



## [剑指 Offer 25. 合并两个排序的链表 - 力扣（LeetCode）](https://leetcode.cn/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/)

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

**示例1：**

```
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
```

**限制：**

```
0 <= 链表长度 <= 1000
```



基本思想：1.迭代 2.递归

- 迭代：比较两个链表当前元素大小，选择小的进行合并，直到一个链表合并完，那么剩下的链表直接追加就行

源代码：

```java
class Solution {
   public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            ListNode h=new ListNode(0),p=h;
            while(l1!=null&&l2!=null){
                if(l1.val<l2.val){
                    p.next=l1;
                    l1=l1.next;
                }
                else {
                    p.next=l2;
                    l2=l2.next;
                }
                p=p.next;
            }
            if(l1!=null)p.next=l1;
            if(l2!=null)p.next=l2;
            return h.next;
        }
}

//官方的递归
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode(-1);

        ListNode prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev.next = l1 == null ? l2 : l1;

        return prehead.next;
    }
}
```

## [剑指 Offer 26. 树的子结构 - 力扣（LeetCode）](https://leetcode.cn/problems/shu-de-zi-jie-gou-lcof/)

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构， 即 A中有出现和B相同的结构和节点值。

例如:
给定的树 A:

`   3  / \  4  5 / \ 1  2`
给定的树 B：

`  4  / 1`
返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

**示例 1：**

```
输入：A = [1,2,3], B = [3,1]
输出：false
```

**示例 2：**

```
输入：A = [3,4,5,1,2], B = [4,1]
输出：true
```

**限制：**

```
0 <= 节点个数 <= 10000
```

基本思想：递归

对于A的每个子树都要判定是否与B相等

- 终止的条件是：
  - 如果B为空，那么返回true
  - 如果A是空的，那么匹配失败返回false
  - 如果A，B的当前节点值不相等返回false
  - 如果A，B的当前节点值相等返回左右子树匹配情况
- 对于A的每个子树都要进行上述匹配，即匹配A||A.left||A.right

源代码：

```java
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
            if(!(A!=null&&B!=null))return false;
            Queue<TreeNode>queue=new ArrayDeque<>();
            queue.add(A);
            while(!queue.isEmpty()){
                TreeNode t=queue.poll();
                if(is(t,B))return true;
                if(t.left!=null)queue.add(t.left);
                if (t.right!=null)queue.add(t.right);
            }

            return false;
        }
        public boolean is(TreeNode A,TreeNode B){
            if (A != null && B != null) {
                if(A.val==B.val)return is(A.left,B.left)&&is(A.right,B.right);
                return false;
            } else if (B==null) {
                return true;
            }
            return false;
        }
}
```

## [剑指 Offer 27. 二叉树的镜像 - 力扣（LeetCode）](https://leetcode.cn/problems/er-cha-shu-de-jing-xiang-lcof/)

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

例如输入：

`   4  /  \ 2   7 / \  / \1  3 6  9`
镜像输出：

```
   4  /  \ 7   2 / \  / \9  6 3  1
```

 

**示例 1：**

```
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
```

 

**限制：**

```
0 <= 节点个数 <= 1000
```



基本思想：递归

镜像树的左子树等于root的镜像右子树，镜像树的右子树等于root的镜像左子树

源代码：

```java
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
                if(root==null)return null;
                TreeNode t=new TreeNode(0);
                create(root,t);
                return t;
        }
        public void create(TreeNode A,TreeNode B){
            if(A!=null){
                B.val=A.val;
            }
            if(A.left!=null) {
                B.right=new TreeNode(0);
                create(A.left, B.right);
            }
            if(A.right!=null) {
                B.left=new TreeNode(0);
                create(A.right, B.left);
            }
        }
}
//官方版的简洁
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode left = mirrorTree(root.left);
        TreeNode right = mirrorTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }
}
```

## [剑指 Offer 28. 对称的二叉树 - 力扣（LeetCode）](https://leetcode.cn/problems/dui-cheng-de-er-cha-shu-lcof/)

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

例如，二叉树 [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

**示例 1：**

```
输入：root = [1,2,2,3,4,4,3]
输出：true
```

**示例 2：**

```
输入：root = [1,2,2,null,3,null,3]
输出：false
```

 

**限制：**

```
0 <= 节点个数 <= 1000
```



基本思想：1.生成镜像树，进行比较  2.直接比较

- 生成镜像树：

```java
class Solution {
    public boolean isSymmetric(TreeNode root) {
            if(root==null)return true;
            TreeNode B=new TreeNode(0);
            create(root,B);
            return eq(root,B);

        }
        public boolean eq(TreeNode A, TreeNode B){
            if(A==null&&B==null)return true;
            if(A!=null&&B!=null){
                return A.val==B.val&&eq(A.left,B.left)&&eq(A.right,B.right);
            }
            return false;

        }
        public void create(TreeNode A,TreeNode B){
            if(A!=null){
                B.val=A.val;
            }
            if(A.left!=null) {
                B.right=new TreeNode(0);
                create(A.left, B.right);
            }
            if(A.right!=null) {
                B.left=new TreeNode(0);
                create(A.right, B.left);
            }
        }
}
```

- 直接比较

```java
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return check(root, root);
    }

    public boolean check(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
    }
}
```

## [剑指 Offer 29. 顺时针打印矩阵 - 力扣（LeetCode）](https://leetcode.cn/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/)

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

 

**示例 1：**

```
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
```

**示例 2：**

```
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]
```

 

**限制：**

- `0 <= matrix.length <= 100`
- `0 <= matrix[i].length <= 100`

基本思想：模拟

我们可以使用一个数据记录是否被访问过，然后螺旋访问，访问之后进行标记，如果遇到边界或者访问过的就应该进行方向的转换

对于方向的转换可以使用两个数组来表示

int[] dx=new int[]{0,1,0,-1};
int[] dy=new int[]{1,0,-1,0};

源代码：

```java
class Solution {
    public int[] spiralOrder(int[][] matrix) {
         if(matrix.length==0)return new int[]{};
            int x=matrix.length,y=matrix[0].length;
            int[] result=new int[x*y];
            int[] dx=new int[]{0,1,0,-1};
            int[] dy=new int[]{1,0,-1,0};
            boolean[][] flag=new boolean[x][y];
            int num=0,i=0,j=0,k=0;
            while (num< result.length){
                if(i>=0&&i<x&&j>=0&&j<y&&!flag[i][j]) {
                    result[num++] = matrix[i][j];
                    flag[i][j] = true;
                    i += dx[k];
                    j += dy[k];
                }
                else {
                    i -= dx[k];
                    j -= dy[k];
                    k=(k+1)%4;
                    i += dx[k];
                    j += dy[k];
                }
            }
            return result;
    }
}
```



## [剑指 Offer 30. 包含min函数的栈 - 力扣（LeetCode）](https://leetcode.cn/problems/bao-han-minhan-shu-de-zhan-lcof/)

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

**示例:**

```
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.min();   --> 返回 -2.
```

 

**提示：**

1. 各函数的调用总次数不超过 20000 次

基本思想：可以使用一个辅助栈，用来存放当前的栈中最小值。这里采用一个结构体，里面存放当前的值和最小的值，只使用一个栈。

源代码：

```java
 class MinStack {
        class data{
            int val;
            int m;
            public data(int val,int m){
                this.val=val;
                this.m=m;
            }
        }
        Stack<data>stack;
        /** initialize your data structure here. */
        public MinStack() {
            stack=new Stack<>();
        }
     
        public void push(int x) {
            if(stack.empty()){
                stack.push(new data(x,x));
                return;
            }
            if(x<stack.peek().m)
                stack.push(new data(x,x));
            else stack.push(new data(x,stack.peek().m));
        }

        public void pop() {
            stack.pop();
        }

        public int top() {
            if(!stack.empty())return stack.peek().val;
            return -1;
        }

        public int min() {
            if(!stack.empty())return stack.peek().m;
            return -1;
        }
    }
/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.min();
 */
```

## [剑指 Offer 31. 栈的压入、弹出序列 - 力扣（LeetCode）](https://leetcode.cn/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/)

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。

 

**示例 1：**

```
输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
```

**示例 2：**

```
输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。
```

 

**提示：**

1. `0 <= pushed.length == popped.length <= 1000`
2. `0 <= pushed[i], popped[i] < 1000`
3. `pushed` 是 `popped` 的排列。



基本思想：模拟

对入栈和出栈进行模拟，对于pushed[i]和poped[j]：

- 如果相等那么向后推移并判定poped[j]和栈顶是否相等，相等就出栈，j向后推移
- 如果不相等，入栈pushed[i]，i向后推移。

结束后，如果j没有走完那么匹配失败

源代码：

```java
class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
            int i=0,j=0;
            Stack<Integer>stack=new Stack<>();
            while(i<pushed.length&&j< popped.length){
                if(pushed[i]==popped[j]){
                    i++;
                    j++;
                    while(!stack.empty()&&stack.peek()==popped[j]){
                        j++;
                        stack.pop();
                    }
                }
                else {
                    stack.push(pushed[i]);
                    i++;
                }
            }
            if(j!= popped.length)return false;
            return true;
        }
}
//一种简洁的写法
class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int i = 0;
        for(int num : pushed) {
            stack.push(num); // num 入栈
            while(!stack.isEmpty() && stack.peek() == popped[i]) { // 循环判断与出栈
                stack.pop();
                i++;
            }
        }
        return stack.isEmpty();
    }
}
```



## [剑指 Offer 32 - I. 从上到下打印二叉树 - 力扣（LeetCode）](https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/)

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

 

例如:
给定二叉树: `[3,9,20,null,null,15,7]`,

```
    3
   / \
  9  20
    /  \
   15   7
```

返回：

```
[3,9,20,15,7]
```

 

**提示：**

1. `节点总数 <= 1000`

基本思想：层次遍历，BFS，队列

访问每个非空节点入队，如果左右子节点不空入队。

源代码：

```java
class Solution {
    public int[] levelOrder(TreeNode root) {
            if(root==null)return new int[]{};
            List<Integer>result=new ArrayList<>();
            Queue<TreeNode> queue=new ArrayDeque<>();
            queue.add(root);
            while(!queue.isEmpty()){
                TreeNode tmp=queue.poll();
                result.add(tmp.val);
                if(tmp.left!=null)queue.add(tmp.left);
                if(tmp.right!=null)queue.add(tmp.right);
            }
            int[] arr=new int[result.size()];
            int i=0;
            for (Integer integer : result) {
                arr[i++]=integer;
            }
            return arr;
        }
}
```

## [剑指 Offer 32 - II. 从上到下打印二叉树 II - 力扣（LeetCode）](https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/)

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

 

例如:
给定二叉树: `[3,9,20,null,null,15,7]`,

```
    3
   / \
  9  20
    /  \
   15   7
```

返回其层次遍历结果：

```
[
  [3],
  [9,20],
  [15,7]
]
```

 

**提示：**

1. `节点总数 <= 1000`

基本思想：最简单的方法使用两个队列，每一层交替使用一个队列。

源代码：

```java
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
            List<List<Integer>>result=new ArrayList<>();
            Queue<TreeNode>q1=new ArrayDeque<>(),q2=new ArrayDeque<>();
            if(root!=null){
                q1.add(root);
            }
            while(!q1.isEmpty()||!q2.isEmpty()){
                List<Integer>tmp;
                if(!q1.isEmpty()){
                    tmp=new ArrayList<>();
                    while(!q1.isEmpty()){
                        TreeNode t=q1.poll();
                        tmp.add(t.val);
                        if(t.left!=null)q2.add(t.left);
                        if(t.right!=null)q2.add(t.right);
                    }
                    result.add(tmp);
                }
                else {
                    tmp=new ArrayList<>();
                    while (!q2.isEmpty()){
                        TreeNode t=q2.poll();
                        tmp.add(t.val);
                        if(t.left!=null)q1.add(t.left);
                        if(t.right!=null)q1.add(t.right);
                    }
                    result.add(tmp);
                }

            }
            return result;
    }
}
```

也可以使用一个队列，对于每一层的区分方法就是该层队列的长度：

源代码：

```java
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        if (root == null) {
            return ret;
        }

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<Integer>();
            int currentLevelSize = queue.size();
            for (int i = 1; i <= currentLevelSize; ++i) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            ret.add(level);
        }
        
        return ret;
    }
}
```

## [剑指 Offer 32 - III. 从上到下打印二叉树 III - 力扣（LeetCode）](https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/)

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

 

例如:
给定二叉树: `[3,9,20,null,null,15,7]`,

```
    3
   / \
  9  20
    /  \
   15   7
```

返回其层次遍历结果：

```
[
  [3],
  [20,9],
  [15,7]
]
```

 

**提示：**

1. `节点总数 <= 1000`

基本思想：与上一题一样，要加一个flag标志，为true就是正序，为false就是倒序，每一层转变flag。

源代码：

```java
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
            boolean flag=true;
            List<List<Integer>> result=new ArrayList<>();
            Queue<TreeNode> queue=new ArrayDeque<>();
            if(root!=null)queue.add(root);
            while(!queue.isEmpty()){
                int len=queue.size();
                List<Integer>list=new ArrayList<>();
                for (int i = 0; i < len; i++) {
                    TreeNode t=queue.poll();
                    if(flag)list.add(t.val);
                    else list.add(0,t.val);
                    if(t.left!=null)queue.add(t.left);
                    if(t.right!=null)queue.add(t.right);
                }
                result.add(list);
                flag=!flag;
            }
            return result;

        }
}
```

## [剑指 Offer 33. 二叉搜索树的后序遍历序列 - 力扣（LeetCode）](https://leetcode.cn/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/)

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 `true`，否则返回 `false`。假设输入的数组的任意两个数字都互不相同。

 

参考以下这颗二叉搜索树：

```
     5
    / \
   2   6
  / \
 1   3
```

**示例 1：**

```
输入: [1,6,3,2,5]
输出: false
```

**示例 2：**

```
输入: [1,3,2,6,5]
输出: true
```

 

**提示：**

1. `数组长度 <= 1000`

基本思想：1.递归 2.单调栈

- 递归：如果只是一个后序遍历我们是没有办法确定一个树的，但是现在这是一个二叉搜索树，那么对于每一个节点，它一定大于左子树的值，小于右子树的值，这样就可以确定这个树了，题目给出的是二叉树的后序遍历，那么最后一个节点一定是根节点，向左找到第一个小于根节点的值，那么从这里可以分为左右子树，如果左子树出现比根节点大的值判定失败，对于左右子树递归判断。

源代码：

```java
class Solution {
        public boolean verifyPostorder(int[] postorder) {
            if(postorder.length==0)return true;
            return is(postorder,0, postorder.length-1);
        }

        public boolean is(int[] nums,int left,int right){
            if(left==right)return true;
            int j=right;
            while(nums[j]>=nums[right]&&j>left)j--;
            for(int i=left;i<j;i++){
                if(nums[i]>nums[right])return false;
            }
            return is(nums,left,j)&&is(nums,j,right-1);
        }
}
```

- 单调栈：我们可以维护一个单调递增的栈，后序遍历的顺序是左孩子->右孩子->根节点，那么倒序就是根节点->右孩子->左孩子，初始我们可以令根节点等于无穷大，那么可以认为是一个根节点为无穷大的二叉搜索树，

  - 这个时候如果节点比根节点小就满足定义：

  - - 如果大于栈顶元素就是右子树，一直入栈，
    - 如果小于栈顶元素就出栈到比栈顶大，此时最后出栈元素就是子树的根。

源代码：

```java
class Solution {
    public boolean verifyPostorder(int[] postorder) {
        Stack<Integer> stack = new Stack<>();
        int root = Integer.MAX_VALUE;
        for(int i = postorder.length - 1; i >= 0; i--) {
            if(postorder[i] > root) return false;
            while(!stack.isEmpty() && stack.peek() > postorder[i])
            	root = stack.pop();
            stack.add(postorder[i]);
        }
        return true;
    }
}
```



## [剑指 Offer 34. 二叉树中和为某一值的路径 - 力扣（LeetCode）](https://leetcode.cn/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/)



给你二叉树的根节点 `root` 和一个整数目标和 `targetSum` ，找出所有 **从根节点到叶子节点** 路径总和等于给定目标和的路径。

**叶子节点** 是指没有子节点的节点。

 

**示例 1：**

![img](https://assets.leetcode.com/uploads/2021/01/18/pathsumii1.jpg)

```
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]
```

**示例 2：**

![img](https://assets.leetcode.com/uploads/2021/01/18/pathsum2.jpg)

```
输入：root = [1,2,3], targetSum = 5
输出：[]
```

**示例 3：**

```
输入：root = [1,2], targetSum = 0
输出：[]
```

 

**提示：**

- 树中节点总数在范围 `[0, 5000]` 内
- `-1000 <= Node.val <= 1000`
- `-1000 <= targetSum <= 1000`



基本思想：1.递归、回溯、深度优先遍历 2.广度优先遍历

- 回溯：将根节点加入，然后考察左子树、右子树。如果节点是空的那么返回，如果是叶子节点并且与target值相同，返回路径。

源代码：

```java
class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int target) {
            List<List<Integer>>result=new ArrayList<>();
            if(root==null)return result;
            List<TreeNode>node=new ArrayList<>();
            backtrace(result,root,target,node);
            return result;

        }
        public void backtrace(List<List<Integer>>result, TreeNode t, int target, List<TreeNode> nodes){
            if(t==null)return;
            nodes.add(t);
            target=target-t.val;
            if(target==0&&t.left==null&&t.right==null){
                List<Integer>tmp=new ArrayList<>();
                for (TreeNode node : nodes) {
                    tmp.add(node.val);
                }
                result.add(tmp);
                nodes.remove(t);
                return;
            }
            backtrace(result,t.left,target,nodes);
            backtrace(result,t.right,target,nodes);
            nodes.remove(t);
        }
}
```



- 广度优先遍历：我们也可以采用广度优先搜索的方式，遍历这棵树。当我们遍历到叶子节点，且此时路径和恰为目标和时，我们就找到了一条满足条件的路径。为了节省空间，我们使用哈希表记录树中的每一个节点的父节点。每次找到一个满足条件的节点，我们就从该节点出发不断向父节点迭代，即可还原出从根节点到当前节点的路径。

源代码：

```java
class Solution {
    List<List<Integer>> ret = new LinkedList<List<Integer>>();
    Map<TreeNode, TreeNode> map = new HashMap<TreeNode, TreeNode>();

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        if (root == null) {
            return ret;
        }

        Queue<TreeNode> queueNode = new LinkedList<TreeNode>();
        Queue<Integer> queueSum = new LinkedList<Integer>();
        queueNode.offer(root);
        queueSum.offer(0);

        while (!queueNode.isEmpty()) {
            TreeNode node = queueNode.poll();
            int rec = queueSum.poll() + node.val;

            if (node.left == null && node.right == null) {
                if (rec == target) {
                    getPath(node);
                }
            } else {
                if (node.left != null) {
                    map.put(node.left, node);
                    queueNode.offer(node.left);
                    queueSum.offer(rec);
                }
                if (node.right != null) {
                    map.put(node.right, node);
                    queueNode.offer(node.right);
                    queueSum.offer(rec);
                }
            }
        }

        return ret;
    }

    public void getPath(TreeNode node) {
        List<Integer> temp = new LinkedList<Integer>();
        while (node != null) {
            temp.add(node.val);
            node = map.get(node);
        }
        Collections.reverse(temp);
        ret.add(new LinkedList<Integer>(temp));
    }
}
```

## [剑指 Offer 35. 复杂链表的复制 - 力扣（LeetCode）](https://leetcode.cn/problems/fu-za-lian-biao-de-fu-zhi-lcof/)

请实现 `copyRandomList` 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 `next` 指针指向下一个节点，还有一个 `random` 指针指向链表中的任意节点或者 `null`。

 

**示例 1：**

![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/01/09/e1.png)

```
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
```

**示例 2：**

![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/01/09/e2.png)

```
输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]
```

**示例 3：**

**![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/01/09/e3.png)**

```
输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]
```

**示例 4：**

```
输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。
```

 

**提示：**

- `-10000 <= Node.val <= 10000`
- `Node.random` 为空（null）或指向链表中的节点。
- 节点数目不超过 1000 。

基本思想：1.哈希表 2.迭代

- 哈希表：一种方式是将所有节点复制起来，并且保存源节点和复制节点的一一对应关系，然后根据哈希表将random指针连接起来。

源代码：

```java
/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
   public Node copyRandomList(Node head) {
            if(head==null)return null;
            Node h=new Node(0);
            Map<Node, Node>map=new HashMap<>();
            Node p=head,n=h;
            while(p!=null){
                Node q=new Node(p.val);
                map.put(p,q);
                n.next=q;
                n=n.next;
                p=p.next;
            }
            for(Node node:map.keySet()){
                if(node.random!=null){
                    map.get(node).random=map.get(node.random);
                }
            }

            return h.next;
        }
}

//一种递归的实现方法
class Solution {
    Map<Node, Node> cachedNode = new HashMap<Node, Node>();

    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        if (!cachedNode.containsKey(head)) {
            Node headNew = new Node(head.val);
            cachedNode.put(head, headNew);
            headNew.next = copyRandomList(head.next);
            headNew.random = copyRandomList(head.random);
        }
        return cachedNode.get(head);
    }
}
```

- 迭代：我们首先将该链表中每一个节点拆分为两个相连的节点，如将A->B->C拆分成A->A'->B->B'->C->C'，然后将random进行链接，把新链表取出，原链表还原

源代码：

```java
class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        for (Node node = head; node != null; node = node.next.next) {
            Node nodeNew = new Node(node.val);
            nodeNew.next = node.next;
            node.next = nodeNew;
        }
        for (Node node = head; node != null; node = node.next.next) {
            Node nodeNew = node.next;
            nodeNew.random = (node.random != null) ? node.random.next : null;
        }
        Node headNew = head.next;
        for (Node node = head; node != null; node = node.next) {
            Node nodeNew = node.next;
            node.next = node.next.next;
            nodeNew.next = (nodeNew.next != null) ? nodeNew.next.next : null;
        }
        return headNew;
    }
}
```

## [剑指 Offer 36. 二叉搜索树与双向链表 - 力扣（LeetCode）](https://leetcode.cn/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/)

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

 

为了让您更好地理解问题，以下面的二叉搜索树为例：

 

![img](https://assets.leetcode.com/uploads/2018/10/12/bstdlloriginalbst.png)

 

我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。

下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。

 

![img](https://assets.leetcode.com/uploads/2018/10/12/bstdllreturndll.png)

 

特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

基本思想：递归

方法一：对于二叉搜索树来说，中序遍历就是从小到大的有序序列，那么可以将这个序列保存起来，这样再对节点进行修改

源代码：

```java
/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
    List<Node>list=new ArrayList<>();
        public Node treeToDoublyList(Node root) {
            if(root==null)return null;
            circle(root);
            Node head=list.get(0),tail=list.get(list.size()-1);
            for(int i=0;i<list.size();i++){
                if(i>0)list.get(i).left=list.get(i-1);
                if(i<list.size()-1)list.get(i).right=list.get(i+1);
            }
            head.left=tail;
            tail.right=head;
            return head;

        }
        public void circle(Node root){
            if(root==null){
                return;
            }
            circle(root.left);
            list.add(root);
            circle(root.right);
        }
}
```

方法二：在中序遍历的基础上就处理好所有的节点关系

用head指针表示最左边的节点，用pre指针不断地向前扩展，pre的右边是当前节点。

```java
class Solution {
    Node pre, head;
    public Node treeToDoublyList(Node root) {
        if(root == null) return null;
        dfs(root);
        head.left = pre;
        pre.right = head;
        return head;
    }
    void dfs(Node cur) {
        if(cur == null) return;
        dfs(cur.left);
        if(pre != null) pre.right = cur;
        else head = cur;
        cur.left = pre;
        pre = cur;
        dfs(cur.right);
    }
}
```

## [剑指 Offer 37. 序列化二叉树 - 力扣（LeetCode）](https://leetcode.cn/problems/xu-lie-hua-er-cha-shu-lcof/)

请实现两个函数，分别用来序列化和反序列化二叉树。

你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

**提示：**输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 [LeetCode 序列化二叉树的格式](https://support.leetcode-cn.com/hc/kb/article/1194353/)。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

 

**示例：**

![img](https://assets.leetcode.com/uploads/2020/09/15/serdeser.jpg)

```
输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]
```

基本思想：方法有很多，可以使用层次遍历序列化。

源代码：

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
     public String serialize(TreeNode root) {
            if(root==null)return null;
            String s=new String();
            TreeNode blank=new TreeNode(3000);
            Queue<TreeNode>queue=new ArrayDeque<>();
            queue.add(root);
            while(!queue.isEmpty()){
                TreeNode tmp=queue.poll();
                if(tmp==blank){
                    s+="null";
                }
                else {
                    s+=intToString(tmp.val);
                    if(tmp.left!=null){
                        queue.add(tmp.left);
                    }
                    else {
                        queue.add(blank);
                    }
                    if(tmp.right!=null) {
                        queue.add(tmp.right);
                    }
                    else {
                        queue.add(blank);
                    }
                }
            }
            int i=s.length()-4;
            while(s.startsWith("null", i)){
                s=s.substring(0,i);
                i-=4;
            }
            return s;
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if(data==null)return null;
            String[] s=new String[data.length()/4];
            for(int i=0;i<s.length;i++){
                s[i]=data.substring(i*4,i*4+4);
            
            }
            if(s[0].equals("null"))return null;
            TreeNode root=new TreeNode(stringToInt(s[0]));
            Queue<TreeNode>queue=new ArrayDeque<>();
            queue.add(root);
            int len=1;
            while(!queue.isEmpty()){
                TreeNode tmp=queue.poll();
                if(len*2-1<s.length&&!s[len*2-1].equals("null")){
                    tmp.left=new TreeNode(stringToInt(s[len*2-1]));
                    queue.add(tmp.left);
                }
                if(len*2<s.length&&!s[len*2].equals("null")){
                    tmp.right=new TreeNode(stringToInt(s[len*2]));
                    queue.add(tmp.right);
                }
                len++;
            }
            return root;
        }

        public String intToString(int val){
            if(val==1000)return "AAAA";
            if(val==-1000)return "BBBB";
            String s="";
            if(val>0){
                s+="+";
            }
            else if(val<0){
                s+="-";
                val=-val;
            }
            else {
                s+="0000";
                return s;
            }
            s+=String.format("%03d",val);

            return s;
        }
        public int stringToInt(String s){
            if(s.equals("AAAA"))return 1000;
            if(s.equals("BBBB"))return -1000;
            if(s.charAt(0)=='0'){
                return 0;
            }
            int sum=0;
            for(int i=1;i<4;i++){
                sum+=(s.charAt(i)-'0')*(int) Math.pow(10,3-i);
            }
            return s.charAt(0)=='+'?sum:-sum;

        }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));


//官方版的先序遍历序列化法
public class Codec {
    public String serialize(TreeNode root) {
        return rserialize(root, "");
    }
  
    public TreeNode deserialize(String data) {
        String[] dataArray = data.split(",");
        List<String> dataList = new LinkedList<String>(Arrays.asList(dataArray));
        return rdeserialize(dataList);
    }

    public String rserialize(TreeNode root, String str) {
        if (root == null) {
            str += "None,";
        } else {
            str += str.valueOf(root.val) + ",";
            str = rserialize(root.left, str);
            str = rserialize(root.right, str);
        }
        return str;
    }
  
    public TreeNode rdeserialize(List<String> dataList) {
        if (dataList.get(0).equals("None")) {
            dataList.remove(0);
            return null;
        }
  
        TreeNode root = new TreeNode(Integer.valueOf(dataList.get(0)));
        dataList.remove(0);
        root.left = rdeserialize(dataList);
        root.right = rdeserialize(dataList);
    
        return root;
    }
}
```



## [剑指 Offer 38. 字符串的排列 - 力扣（LeetCode）](https://leetcode.cn/problems/zi-fu-chuan-de-pai-lie-lcof/)



输入一个字符串，打印出该字符串中字符的所有排列。

 

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

 

**示例:**

```
输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]
```

 

**限制：**

```
1 <= s 的长度 <= 8
```

基本思想：全排列问题，最简单的方法就是遍历所有全排列然后进行去重。

源代码：

```java
class Solution {
    List<String>list=new ArrayList<>();
        public String[] permutation(String s) {
            backtrace(s,0);
            list=list.stream().distinct().collect(Collectors.toList());
            return list.toArray(new String[list.size()]);
        }
        public void backtrace(String s,int n){
            if(n>=s.length()){
                list.add(new String(s));
                return;
            }
            for(int i=n;i<s.length();i++){
        
                s=swap(s,i,n);
                backtrace(s,n+1);
                s=swap(s,i,n);
            }

        }
        public String swap(String s,int a,int b){
            StringBuffer sb = new StringBuffer(s);
            char temp = sb.charAt(a);
            sb.setCharAt(a,sb.charAt(b));
            sb.setCharAt(b,temp);
            return sb.toString();
        }
}
```

可以进行优化，再回溯的时候就进行去重，即不将重复的加入在内。

```java
class Solution {
    List<String> rec;
    boolean[] vis;

    public String[] permutation(String s) {
        int n = s.length();
        rec = new ArrayList<String>();
        vis = new boolean[n];
        char[] arr = s.toCharArray();
        Arrays.sort(arr);
        StringBuffer perm = new StringBuffer();
        backtrack(arr, 0, n, perm);
        int size = rec.size();
        String[] recArr = new String[size];
        for (int i = 0; i < size; i++) {
            recArr[i] = rec.get(i);
        }
        return recArr;
    }

    public void backtrack(char[] arr, int i, int n, StringBuffer perm) {
        if (i == n) {
            rec.add(perm.toString());
            return;
        }
        for (int j = 0; j < n; j++) {
            if (vis[j] || (j > 0 && !vis[j - 1] && arr[j - 1] == arr[j])) {
                continue;
            }
            vis[j] = true;
            perm.append(arr[j]);
            backtrack(arr, i + 1, n, perm);
            perm.deleteCharAt(perm.length() - 1);
            vis[j] = false;
        }
    }
}
```

还可以参考下一个排列

```java
class Solution {
    public String[] permutation(String s) {
        List<String> ret = new ArrayList<String>();
        char[] arr = s.toCharArray();
        Arrays.sort(arr);
        do {
            ret.add(new String(arr));
        } while (nextPermutation(arr));
        int size = ret.size();
        String[] retArr = new String[size];
        for (int i = 0; i < size; i++) {
            retArr[i] = ret.get(i);
        }
        return retArr;
    }

    public boolean nextPermutation(char[] arr) {
        int i = arr.length - 2;
        while (i >= 0 && arr[i] >= arr[i + 1]) {
            i--;
        }
        if (i < 0) {
            return false;
        }
        int j = arr.length - 1;
        while (j >= 0 && arr[i] >= arr[j]) {
            j--;
        }
        swap(arr, i, j);
        reverse(arr, i + 1);
        return true;
    }

    public void swap(char[] arr, int i, int j) {
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public void reverse(char[] arr, int start) {
        int left = start, right = arr.length - 1;
        while (left < right) {
            swap(arr, left, right);
            left++;
            right--;
        }
    }
}
```



## [剑指 Offer 39. 数组中出现次数超过一半的数字 - 力扣（LeetCode）](https://leetcode.cn/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/)

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

 

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

 

**示例 1:**

```
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2
```

 

**限制：**

```
1 <= 数组长度 <= 50000
```

基本思想：方法有很多1.哈希表2.排序 3.随机化4.分治 5.摩尔投票法

- 哈希表：将每个数出现的次数保存，找到过半的即可

源代码：

```java
class Solution {
    public int majorityElement(int[] nums) {
            if(nums.length<=2)return nums[0];
            int ans=nums[0];
            Map<Integer,Integer>map=new HashMap<>();
            for (int i=0;i<nums.length;i++){
                if (map.get(nums[i])==null) {
                    map.put(nums[i],1);
                }
                else {

                    map.put(nums[i],map.get(nums[i])+1);
                    if(map.get(nums[i])>nums.length/2){
                        ans=nums[i];
                        break;
                    }
                }
            }
            return ans;
        }
}
```

- 排序：因为肯定有数字数量过半，那么排序后n/2位置肯定是这个数

```java
class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
}
```

- 随机化：因为数字数量过半，那么我们随机选一个数，这个数就很有可能数目标，然后对它进行判断，如果是就返回，不是的话继续挑选。

```java
class Solution {
    private int randRange(Random rand, int min, int max) {
        return rand.nextInt(max - min) + min;
    }

    private int countOccurences(int[] nums, int num) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == num) {
                count++;
            }
        }
        return count;
    }

    public int majorityElement(int[] nums) {
        Random rand = new Random();

        int majorityCount = nums.length / 2;

        while (true) {
            int candidate = nums[randRange(rand, 0, nums.length)];
            if (countOccurences(nums, candidate) > majorityCount) {
                return candidate;
            }
        }
    }
}
```

- 分治法：把原数组分为两部分，那么目标在其中一部分必然是众数，然后返回两边较大的数

```java
class Solution {
    private int countInRange(int[] nums, int num, int lo, int hi) {
        int count = 0;
        for (int i = lo; i <= hi; i++) {
            if (nums[i] == num) {
                count++;
            }
        }
        return count;
    }

    private int majorityElementRec(int[] nums, int lo, int hi) {
        // base case; the only element in an array of size 1 is the majority
        // element.
        if (lo == hi) {
            return nums[lo];
        }

        // recurse on left and right halves of this slice.
        int mid = (hi - lo) / 2 + lo;
        int left = majorityElementRec(nums, lo, mid);
        int right = majorityElementRec(nums, mid + 1, hi);

        // if the two halves agree on the majority element, return it.
        if (left == right) {
            return left;
        }

        // otherwise, count each element and return the "winner".
        int leftCount = countInRange(nums, left, lo, hi);
        int rightCount = countInRange(nums, right, lo, hi);

        return leftCount > rightCount ? left : right;
    }

    public int majorityElement(int[] nums) {
        return majorityElementRec(nums, 0, nums.length - 1);
    }
}
```



- 摩尔排序法、擂台法：我么可以想象在一个擂台上，首先站上去一个人，如果下一个和它一样就继续一起站上去，如果不一样就是敌方需要出一个人和它一起下去（同归于尽），那么到最后一定是人数最多的站在擂台上。

```java
class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        Integer candidate = null;

        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }

        return candidate;
    }
}
```

## [剑指 Offer 41. 数据流中的中位数 - 力扣（LeetCode）](https://leetcode.cn/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/)

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

例如，

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

- void addNum(int num) - 从数据流中添加一个整数到数据结构中。
- double findMedian() - 返回目前所有元素的中位数。

**示例 1：**

```
输入：
["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]]
输出：[null,null,null,1.50000,null,2.00000]
```

**示例 2：**

```
输入：
["MedianFinder","addNum","findMedian","addNum","findMedian"]
[[],[2],[],[3],[]]
输出：[null,null,2.00000,null,2.50000]
```

 

**限制：**

- 最多会对 `addNum、findMedian` 进行 `50000` 次调用。

基本思想：1.列表 2.堆

- 列表：对于添加元素时要有序添加，这样寻找中位数时就很简单。

源代码：

```java
class MedianFinder {
        List<Integer>lists;
        /** initialize your data structure here. */
        public MedianFinder() {
            lists=new ArrayList<>();
        }

        public void addNum(int num) {
            int index=0;
            for (;index<lists.size();index++)
                if(lists.get(index)>num)break;
            lists.add(index,num);
        }

        public double findMedian() {
            int len=lists.size();
            if (len%2==0) {
                return (lists.get(len/2)+lists.get(len/2-1))*1.0/2;
            }
            return lists.get(len/2);
            
        }
    }

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */
```

- 堆：大顶堆和小顶堆，大顶堆保存较小的一半数，小顶堆保存较大的一半数，并且让两者数量保持相等，A最多只比B多一个

```java
class MedianFinder {
    Queue<Integer> A, B;
    public MedianFinder() {
        A = new PriorityQueue<>(); // 小顶堆，保存较大的一半
        B = new PriorityQueue<>((x, y) -> (y - x)); // 大顶堆，保存较小的一半
    }
    public void addNum(int num) {
        if(A.size() != B.size()) {
            A.add(num);
            B.add(A.poll());
        } else {
            B.add(num);
            A.add(B.poll());
        }
    }
    public double findMedian() {
        return A.size() != B.size() ? A.peek() : (A.peek() + B.peek()) / 2.0;
    }
}
```

## [剑指 Offer 42. 连续子数组的最大和 - 力扣（LeetCode）](https://leetcode.cn/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/)

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

 

**示例1:**

```
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
```

 

**提示：**

- `1 <= arr.length <= 10^5`
- `-100 <= arr[i] <= 100`



基本思想：动态规划

我们可以令dp[i]表示前i项的最大子段和，那么对于dp[i]来说，如果dp[i-1]>0那么dp[i]=dp[i-1]+nums[i]，否则dp[i]=nums[i]

源代码：

```java
class Solution {
    public int maxSubArray(int[] nums) {
            int sum=nums[0],tmp=nums[0];
            for (int i=1;i<nums.length;i++){
                if(tmp<0)tmp=nums[i];
                else tmp+=nums[i];
                if(tmp>sum)sum=tmp;
            }
            return sum;
        }
}
```

## [剑指 Offer 43. 1～n 整数中 1 出现的次数 - 力扣（LeetCode）](https://leetcode.cn/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/)

输入一个整数 `n` ，求1～n这n个整数的十进制表示中1出现的次数。

例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

 

**示例 1：**

```
输入：n = 12
输出：5
```

**示例 2：**

```
输入：n = 13
输出：6
```

 

**限制：**

- `1 <= n < 2^31`



基本思想：数位dp

```yaml
case 1: cur=0
     2  3   0  4
     千位和百位可以选00 01 02....22  十位可以取到1( 形如[00|01..|22]1[0-9] 都是<2304 ) 个位可以选0-9  共有 23 * 10 中排列
     当千位和百位取23,如果十位取1 那就是形如 231[0-9] > 2304,所以当千位和百位取23，十位只能能取0，个位取0-4即 2300 2301 2302 2303 2304
     但是2301不应该算进来，这个1是 单独  出现在个位的（而11，121,111这种可以被算多次）
     即 23*10
case 2: cur=1
   2  3  1  4
   千位和百位可以选00 01 02....22  十位可以取到1 个位可以选0-9  共有 23 * 10 中排列
   当千位和百位取23,十位取1，个位可以去0-4 即 2310-2314共5个
   即 23 *10 + 4 +1
case 3: cur>1 即2-9
   2  3  2  4
   千位和百位可以选00 01 02....22  十位可以取到1(形如 [00|01...|22]1[0-9] 都是<2324) 个位可以选0-9  共有 23 * 10 中排列
   当千位和百位取23,十位取1，个位可以去0-9 即 2310-2319共10个 （其中2311，被计算了两次，分别是从个位和十位分析得到的1次）
```



源代码：

```java
class Solution {
     public int countDigitOne(int n) {
            int cur=n%10,high=n/10,low=0,result=0,digit=1;
            while(high!=0||cur!=0){
                if(cur==0)result+=high*digit;
                else if(cur==1)result+=high*digit+low+1;
                else result+=(high+1)*digit;
                low+=cur*digit;
                cur=high%10;
                high/=10;
                digit*=10;
            }
            return result;
        }
}
```

附上一个求任意数字出现次数的代码：

```java
class Solution {
public:
    /**
     * @param k: An integer
     * @param n: An integer
     * @return: An integer denote the count of digit k in 1..n
     */
    int digitCounts(int k, int n) {
        long digit = 1;
        int res = 0, high = n / 10, low = 0, cur = n % 10;
        while (high || (cur && k)) {
            if (cur < k) res += high * digit;
            else if (cur == k) res += (high - (k == 0)) * digit + low + 1;
            else res += (high + (k != 0)) * digit;
            low += cur * digit;
            cur = high % 10;
            high /= 10;
            digit *= 10;
        }
        return res + (k == 0);
    }
};
```

## [剑指 Offer 44. 数字序列中某一位的数字 - 力扣（LeetCode）](https://leetcode.cn/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof/)

数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。

请写一个函数，求任意第n位对应的数字。

 

**示例 1：**

```
输入：n = 3
输出：3
```

**示例 2：**

```
输入：n = 11
输出：0
```

 

**限制：**

- `0 <= n < 2^31`

基本思想：找规律。

1~9 				一位数有9个（0排除）

10~99			两位数有90个

100~999 		三位数有900个

………………

这样我们就可以根据数字确定它所在的位置的位数，数字是多少以及在这个数字中的位置



源代码：

```java
class Solution {
    public int findNthDigit(int n) {


            int digit=1;
            long sum=1,count=sum*digit*9;
            while (n>count){
                n-=count;
                sum*=10;
                digit+=1;
                count=sum*digit*9;
            }
            long val=sum+(n-1)/digit;
            return Long.toString(val).charAt((n-1)%digit)-'0';
        }
}
```



## [剑指 Offer 45. 把数组排成最小的数 - 力扣（LeetCode）](https://leetcode.cn/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/)

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

 

**示例 1:**

```
输入: [10,2]
输出: "102"
```

**示例 2:**

```
输入: [3,30,34,5,9]
输出: "3033459"
```

 

**提示:**

- `0 < nums.length <= 100`

**说明:**

- 输出结果可能非常大，所以你需要返回一个字符串而不是整数
- 拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0

基本思想：自定义排序，字符串x和y交换的前提是，x+y >y+x。



源代码：

```java
class Solution {
    public String minNumber(int[] nums) {
            Integer[] n=new Integer[nums.length];
            for (int i = 0; i < nums.length; i++) {
                n[i]=nums[i];
            }
           
            Arrays.sort(n,new Comparator<Integer>(){
                public int compare(Integer a,Integer b) {
                    String s1 = Integer.toString(a);
                    String s2 = Integer.toString(b);
                    return (s1 + s2).compareTo(s2 + s1);
                }
            });
          
            String result="";
            for (Integer integer : n) {
                result+=integer;
            }
            return result;
        }
}
```

## [剑指 Offer 46. 把数字翻译成字符串 - 力扣（LeetCode）](https://leetcode.cn/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/)

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

 

**示例 1:**

```
输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
```

 

**提示：**
$$
0 <= num < 2^{31}
$$


基本思想：动态规划。将num转化为字符串。用一个数组dp表示组合总数，dp[i]表示下标为i的数字的组合数，对于每一个数字，如果可以和前一个组合成合法的两位数字那么dp[i]=dp[i-1]+dp[i-2]，否则的话dp[i]=dp[i-1]

源代码：

```java
class Solution {
    public int translateNum(int num) {
            String s=String.valueOf(num);
            int[] dp=new int[s.length()];
            dp[0]=1;
            for (int i = 1; i < s.length(); i++) {
                String tmp="";
                tmp+=s.charAt(i-1)-'0';
                tmp+=s.charAt(i)-'0';
                if(tmp.charAt(0)!='0'&&tmp.compareTo("25")<=0){
                    if(i>=2)dp[i]=dp[i-1]+dp[i-2];
                    else dp[i]=2;
                }
                else {
                    dp[i]=dp[i-1];
                }
            }
            return dp[s.length()-1];

        }
}
```



可以使用求余的方法来获取数的每一位从低位到高位求解，这样就可以减少空间。

```java
class Solution {
    public int translateNum(int num) {
        int a = 1, b = 1, x, y = num % 10;
        while(num != 0) {
            num /= 10;
            x = num % 10;
            int tmp = 10 * x + y;
            int c = (tmp >= 10 && tmp <= 25) ? a + b : a;
            b = a;
            a = c;
            y = x;
        }
        return a;
    }
}
```

## [剑指 Offer 47. 礼物的最大价值 - 力扣（LeetCode）](https://leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof/)

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

 

**示例 1:**

```
输入: 
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
```

 

提示：

- `0 < grid.length <= 200`
- `0 < grid[0].length <= 200`

基本思想：常规动态规划。

我们每次只能往右走或者往下走，那么我们用一个dp[i] [j]来表示下标i,j位置的最大价值，对于每一个位置，它的最大价值就是左边与右边的最大价值的最大值加上本身。

状态转移方程：
$$
dp[i][j]=
\begin{cases}
0&i=0,j=0\\
dp[i][j-1]+grid[i][j]&i=0,j>0\\
dp[i-1][j]+grid[i][j]&i>0,j=0\\
max(dp[i][j-1],dp[i-1][j])+grid[i][j]&i>0,j>0
\end{cases}
$$
源代码：

```java
class Solution {
    public int maxValue(int[][] grid) {
            int[][] dp=new int[grid.length][grid[0].length];
            dp[0][0]=grid[0][0];
            for(int i=0;i< grid.length;i++){
                for (int j = 0; j < grid[0].length; j++) {
                    if(i>0&&j>0)dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1])+grid[i][j];
                    else if(j>0)dp[i][j]=dp[i][j-1]+grid[i][j];
                    else if(i>0)dp[i][j]=dp[i-1][j]+grid[i][j];
                }
            }
            int max=dp[grid.length-1][0];
            for(int i=1;i< grid[0].length;i++)
                if(dp[grid.length-1][i]>max)max=dp[grid.length-1][i];
            return max;
        }
}
```



## [剑指 Offer 48. 最长不含重复字符的子字符串 - 力扣（LeetCode）](https://leetcode.cn/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/)

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

 

**示例 1:**

```
输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
```

**示例 2:**

```
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
```

**示例 3:**

```
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
```

 

提示：

- `s.length <= 40000`

基本思想：滑动窗口

我们可以使用left和right两个指针来表示窗口范围，在这个范围内是没有重复元素的，如果出现重复元素，left直接定位道重复元素的位置。right一直增加直到出现重复元素。

源代码：

```java
class Solution {
    public int lengthOfLongestSubstring(String s) {
            Set<Character> list=new HashSet<>();
            int ans=0,n=s.length(),left=0,right=-1;
            for (; left<n; left++) {
                if(left!=0)list.remove(s.charAt(left-1));
                while(right+1<n&&!list.contains(s.charAt(right+1))){
                    list.add(s.charAt(right+1));
                    right++;
                }
                if(right+1-left>ans)ans=right+1-left;

            }
            return ans;

        }
}
```



## [剑指 Offer 49. 丑数 - 力扣（LeetCode）](https://leetcode.cn/problems/chou-shu-lcof/)

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

 

**示例:**

```
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
```

**说明:** 

1. `1` 是丑数。
2. `n` **不超过**1690。

基本思想：可以使用极小堆，我们从1开始，对于每一个丑数x来时,2x,3x,5x，也是丑数，但是有可能会重复，可以使用set去重。所以每次取出极小堆的最小元素，将它的2,3,5倍放进极小堆（如果不重复），然后出队n次，第n次就是结果

源代码：

```java
class Solution {
   public int nthUglyNumber(int n) {
            int[] nums=new int[]{2,3,5};
            int ans=1;
            PriorityQueue<Long>queue=new PriorityQueue<>();
            Set<Long> set=new HashSet<>();
            queue.add(1L);
            set.add(1L);
            for (int i = 1; i <=n; i++) {
                long t=queue.poll();
                ans=(int) t;
                for(int j=0;j<3;j++){
                    long tmp=t*nums[j];
                    if(!set.contains(tmp)){
                        queue.add(tmp);
                        set.add(tmp);
                    }
                }
            }
            return ans;
        }
}
```



动态规划版

```java
class Solution {
    public int nthUglyNumber(int n) {
        int a = 0, b = 0, c = 0;
        int[] dp = new int[n];
        dp[0] = 1;
        for(int i = 1; i < n; i++) {
            int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5;
            dp[i] = Math.min(Math.min(n2, n3), n5);
            if(dp[i] == n2) a++;
            if(dp[i] == n3) b++;
            if(dp[i] == n5) c++;
        }
        return dp[n - 1];
    }
}

```

## [剑指 Offer 50. 第一个只出现一次的字符 - 力扣（LeetCode）](https://leetcode.cn/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof/)



在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

**示例 1:**

```
输入：s = "abaccdeff"
输出：'b'
```

**示例 2:**

```
输入：s = "" 
输出：' '
```

 

**限制：**

```
0 <= s 的长度 <= 50000
```



基本思想：哈希表

我们可以使用哈希表来存储每个字符出现的次数，然后返回第一次出现一次的字符



源代码：

```java
class Solution {
     public char firstUniqChar(String s) {
            if(s.equals(""))return ' ';
            Map<Character,Integer>map=new HashMap<>();
            for (int i = 0; i < s.length(); i++) {
                char c=s.charAt(i);
                if(map.get(c)!=null){
                    map.put(c,map.get(c)+1);
                }
                else map.put(c,1);
            }
            for (int i = 0; i < s.length(); i++) {
                if(map.get(s.charAt(i))==1)return s.charAt(i);
            }
            return ' ';
        }
}
```

可以选择使用数组代替hashmap因为字符就是数字



## [剑指 Offer 51. 数组中的逆序对 - 力扣（LeetCode）](https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/)

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

 

**示例 1:**

```
输入: [7,5,6,4]
输出: 5
```

 

**限制：**

```
0 <= 数组长度 <= 50000
```



基本思想：归并排序。

我们可以利用归并排序来获得逆序对数，我们将数组一分为二，那么两个数组之间的逆序对数不受影响，也就是将两边排序后计算两边的逆序对数，然后计算，如果左边的小于右边的直接合并左边的，如果大于右边的，那么逆序对数是mid+1-i，因为左右两边都是递增的。

源代码：

```java
class Solution {
    public int reversePairs(int[] nums) {
            return count(nums,0, nums.length-1);

        }

        public int merge(int[] a,int left,int mid,int right){
            int count=0;
            int[] tmp=new int[a.length];
            int i=left,j=mid+1;
            for(int k=left;k<=right;k++){
                if(j>right || (i<=mid&&a[i]<=a[j])){
                    tmp[k]=a[i++];
                }
                else {
                    tmp[k]=a[j++];
                    count+=mid+1-i;
                }
            }
            for (int k = left; k <=right ; k++) {
                a[k]=tmp[k];
            }
            return count;
        }
        public int count(int[] a,int left,int right){
            if(left<right){
                int mid=(left+right)>>1;
                 int l=count(a,left,mid),r=count(a,mid+1,right);
                if(a[mid]<=a[mid+1])return l+r;
                else {
                    int k=merge(a,left,mid,right);
                    return l+r+k;
                }
            }
            return 0;
        }
}
```



## [剑指 Offer 52. 两个链表的第一个公共节点 - 力扣（LeetCode）](https://leetcode.cn/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/)

输入两个链表，找出它们的第一个公共节点。

如下面的两个链表**：**

[![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/14/160_statement.png)](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/14/160_statement.png)

在节点 c1 开始相交。

 

**示例 1：**

[![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/14/160_example_1.png)](https://assets.leetcode.com/uploads/2018/12/13/160_example_1.png)

```
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
```

 

**示例 2：**

[![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/14/160_example_2.png)](https://assets.leetcode.com/uploads/2018/12/13/160_example_2.png)

```
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
```

 

**示例 3：**

[![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/14/160_example_3.png)](https://assets.leetcode.com/uploads/2018/12/13/160_example_3.png)

```
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。
```

 

**注意：**

- 如果两个链表没有交点，返回 `null`.
- 在返回结果后，两个链表仍须保持原有的结构。
- 可假定整个链表结构中没有循环。
- 程序尽量满足 O(*n*) 时间复杂度，且仅用 O(*1*) 内存。

基本思想：1.哈希表 2.双指针

首先要明确这里相交指的是指针的地址相同，不是val相同

- 哈希表:我们可以把一个链表的节点存放到哈希表中，如果另外一个链表中的节点与哈希表中的节点相同就返回，否则就返回null

源代码：

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
   public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            Set<ListNode> set=new HashSet<>();
            ListNode p=headA;
            while(p!=null){
                set.add(p);
                p=p.next;
            }
            p=headB;
            while (p!=null){
                if(set.contains(p))return p;
                p=p.next;
            }
            return null;
        }
}
```



- 双指针：
  - 如果A和B有相交：设A相交前的长度为a，B相交前的长度为b，相交的长度为c，那么A的长度为a+c，B的长度为b+c
    - A和B一起遍历，如果A遍历到头，就从B开始遍历，B遍历到头就从A开始遍历，这样遍历指针走过a+c+b次后一定会是相交的。
  - 如果A和B没有相交：设A的长度为m,B的长度为n
    - 如果m=n：那么一起遍历到null返回null
    - 如果m!=n：那么一起遍历m+n次后也是null

源代码：

```java
public class Solution {
    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;
    }
}
```



## [剑指 Offer 53 - I. 在排序数组中查找数字 I - 力扣（LeetCode）](https://leetcode.cn/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/)

统计一个数字在排序数组中出现的次数。

 

**示例 1:**

```
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
```

**示例 2:**

```
输入: nums = [5,7,7,8,8,10], target = 6
输出: 0
```

 

**提示：**

- `0 <= nums.length <= 105`
- `-109 <= nums[i] <= 109`
- `nums` 是一个非递减数组
- `-109 <= target <= 109`



基本思想：二分查找

查找到target返回mid，然后左右寻找个数。

源代码：

```java
class Solution {
     public int search(int[] nums, int target) {
            if(nums.length==0)return 0;
            int left=0,right=nums.length-1,mid=0;
            while(left<=right){
                mid=(left+right)>>1;
                if(nums[mid]==target)break;
                else if(nums[mid]<target){
                    left=mid+1;
                }
                else {
                    right=mid-1;
                }
            }
            if(nums[mid]!=target)return 0;
            int t=mid-1,count=1;
            while(t>=0&&nums[t]==target){
                count++;
                t--;
            }
            t=mid+1;
            while(t< nums.length&&nums[t]==target){
                count++;
                t++;
            }
            return count;
        }
}

//官方版，找到左右边界，然后相减
class Solution {
    public int search(int[] nums, int target) {
        int leftIdx = binarySearch(nums, target, true);
        int rightIdx = binarySearch(nums, target, false) - 1;
        if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {
            return rightIdx - leftIdx + 1;
        } 
        return 0;
    }

    public int binarySearch(int[] nums, int target, boolean lower) {
        int left = 0, right = nums.length - 1, ans = nums.length;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target || (lower && nums[mid] >= target)) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}

```

## [剑指 Offer 53 - II. 0～n-1中缺失的数字](https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/)

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。



**示例 1:**

```
输入: [0,1,3]
输出: 2
```

**示例 2:**

```
输入: [0,1,2,3,4,5,6,7,9]
输出: 8
```

 

**限制：**

```
1 <= 数组长度 <= 10000
```

基本思想：二分查找

因为0-n-1数字只有一个不在数组中，如果nums[mid]=mid那么就一定在右半部分寻找缺失的数字，否则在左边寻找。

源代码：

```java
class Solution {
    public int missingNumber(int[] nums) {
         int len=nums.length;
            if(nums[0]!=0)return 0;
            int left=1,right=len-1,mid;
            while(left<=right){
                mid=(right-left)/2+left;
                // if(nums[mid]!=mid&&nums[mid-1]==mid-1){
                //     return mid;
                // }
                if(nums[mid]==mid){
                    left=mid+1;
                }
                else {
                    right=mid-1;
                }

            }
            return left;
    }
}
```

## [剑指 Offer 54. 二叉搜索树的第k大节点](https://leetcode.cn/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/)



给定一棵二叉搜索树，请找出其中第 `k` 大的节点的值。

 

**示例 1:**

```
输入: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
输出: 4
```

**示例 2:**

```
输入: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
输出: 4
```

 

**限制：**

- 1 ≤ k ≤ 二叉搜索树元素个数

基本思想：遍历。

对于二叉搜索树来说，中序遍历（左子树、父节点、右子树）就是从小到大的顺序，那么反置顺序（右子树、父节点、左子树）就是从大到小的顺序，这样找到第k个元素就是答案；

源代码：

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int deep=0,result=0;
        public int kthLargest(TreeNode root, int k) {
            preorder(root,k);
            return result;
        }
        public void preorder(TreeNode root,int k){
            if(root==null)return;
            preorder(root.right,k);
            deep++;
            if(deep==k)result=root.val;
            preorder(root.left,k);
        }
}
```



## [剑指 Offer 55 - I. 二叉树的深度](https://leetcode.cn/problems/er-cha-shu-de-shen-du-lcof/)

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

例如：

给定二叉树 `[3,9,20,null,null,15,7]`，

```
    3
   / \
  9  20
    /  \
   15   7
```

返回它的最大深度 3 。

 

**提示：**

1. `节点总数 <= 10000`

基本思想：深度优先遍历

如果节点是空的，那么深度为0；

如果节点不空那么求出左子树的深度，求出右子树的深度，取大者加1；

源代码：

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
            if(root==null)return 0;
            return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
    }
}
```

## [剑指 Offer 55 - II. 平衡二叉树](https://leetcode.cn/problems/ping-heng-er-cha-shu-lcof/)

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

 

**示例 1:**

给定二叉树 `[3,9,20,null,null,15,7]`

```
    3
   / \
  9  20
    /  \
   15   7
```

返回 `true` 。

**示例 2:**

给定二叉树 `[1,2,2,3,3,null,null,4,4]`

```
       1
      / \
     2   2
    / \
   3   3
  / \
 4   4
```

返回 `false` 。

 

**限制：**

- `0 <= 树的结点个数 <= 10000`

基本思想：

1.从上至下递归判断：

依次判断每一个节点是否满足平衡二叉树

源代码：

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
            if(root==null)return true;
            int left=maxDepth(root.left);
            int right=maxDepth(root.right);
            if(Math.abs(left-right)>1)return false;
            return isBalanced(root.left)&&isBalanced(root.right);
        }
        public int maxDepth(TreeNode root) {
            if(root==null)return 0;
            return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
        }
}
```

2.后序遍历，自底向上判断。辅助函数recur，如果左右子树深度差值大于1，那么返回-1，如果是空，返回0，否则就返回该树的深度

源代码：

```java
class Solution {
    public boolean isBalanced(TreeNode root) {
        return recur(root) != -1;
    }

    private int recur(TreeNode root) {
        if (root == null) return 0;
        int left = recur(root.left);
        if(left == -1) return -1;
        int right = recur(root.right);
        if(right == -1) return -1;
        return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
    }
}
```





## [剑指 Offer 56 - I. 数组中数字出现的次数](https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/)



一个整型数组 `nums` 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

 

**示例 1：**

```
输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]
```

**示例 2：**

```
输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]
```

 

**限制：**

- `2 <= nums.length <= 10000`

基本思想：分组异或

如果两个相同的数异或结果为0，0与任何数异或都是本身。

所以数组中的数只有a,b出现一次，所有的数异或一遍最终得到的就是a和b异或的结果x。对于x的每一个二进制位，如果是1就表示该位a，b不同，可以根据这进行分组，这样a，b位于两个不同的组，每组异或的结果就是a，b

源代码：

```java
class Solution {
    public int[] singleNumbers(int[] nums) {
            int rec=0;
            for(int i=0;i<nums.length;i++){
                rec^=nums[i];
            }
            int div=1;
            while ((div&rec)==0){
                div=div<<1;
            }
            int a=0,b=0;
            for (int i = 0; i < nums.length; i++) {
                if((div&nums[i])==0){
                    a^=nums[i];
                }
                else {
                    b^=nums[i];
                }
            }

            return new int[]{a,b};

        }
}
```



## [剑指 Offer 56 - II. 数组中数字出现的次数 II](https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/)



在一个数组 `nums` 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

 

**示例 1：**

```
输入：nums = [3,4,3,3]
输出：4
```

**示例 2：**

```
输入：nums = [9,1,7,9,7,9,7]
输出：1
```

 

**限制：**

- `1 <= nums.length <= 10000`
- `1 <= nums[i] < 2^31`

基本思想：1.哈希表记录每个数字出现的次数找出目标

源代码：

```java
class Solution {
   public int singleNumber(int[] nums) {
            Map<Integer,Integer>map=new HashMap<>();
            for(int i=0;i<nums.length;i++){
                if(!map.containsKey(nums[i])){
                    map.put(nums[i],1);
                }
                else {
                    map.put(nums[i],map.get(nums[i])+1);
                }
            }
            int result=0;

            for(Map.Entry<Integer,Integer> k:map.entrySet()){
                if(k.getValue()==1)result=k.getKey();
            }

            return result;
        }
}
```

2.位运算。将每个数都视为二进制数，对于每一位来说，1个个数对3取余就是目标值在该位1的个数



## [剑指 Offer 57. 和为s的两个数字](https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/)

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

 

**示例 1：**

```
输入：nums = [2,7,11,15], target = 9
输出：[2,7] 或者 [7,2]
```

**示例 2：**

```
输入：nums = [10,26,30,31,47,60], target = 40
输出：[10,30] 或者 [30,10]
```

 

**限制：**

- `1 <= nums.length <= 10^5`
- `1 <= nums[i] <= 10^6`



基本思想：双指针

左边指针在数组开始元素，右指针初始为数组最右边元素，然后如果两个元素相加大于目标，右指针减小，如果小于目标，左指针增大。

源代码：

```java
class Solution {
   public int[] twoSum(int[] nums, int target) {
            int left=0,right=nums.length-1;
            while(nums[left]+nums[right]!=target){
                if(nums[left]+nums[right]<target){
                    left++;
                }
                else right--;

            }
            return new int[]{nums[left],nums[right]};

        }
}
```

## [剑指 Offer 57 - II. 和为s的连续正数序列](https://leetcode.cn/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/)

输入一个正整数 `target` ，输出所有和为 `target` 的连续正整数序列（至少含有两个数）。

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

 

**示例 1：**

```
输入：target = 9
输出：[[2,3,4],[4,5]]
```

**示例 2：**

```
输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]
```

 

**限制：**

- `1 <= target <= 10^5`

基本思想：双指针

如果当前和小于目标，右指针右移

如果当前和大于目标，左指针右移

如果当前和等于目标，保存结果

源代码：

```java
class Solution {
    public int[][] findContinuousSequence(int target) {
            List<int[]>list=new ArrayList<>();
            int left=1,right=2;
            while(left<right){
                if(right*right-left*left+left+right==2*target){
                    int[] tmp=new int[right-left+1];
                    for (int i = left; i <=right ; i++) {
                        tmp[i-left]=i;
                    }
                    list.add(tmp);
                    left++;
                }
                else if(right*right-left*left+left+right>2*target){
                    left++;
                }
                else right++;

            }

            return list.toArray(new int[list.size()][]);
        }
}
```

## [剑指 Offer 58 - I. 翻转单词顺序](https://leetcode.cn/problems/fan-zhuan-dan-ci-shun-xu-lcof/)

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. "，则输出"student. a am I"。

 

**示例 1：**

```
输入: "the sky is blue"
输出: "blue is sky the"
```

**示例 2：**

```
输入: "  hello world!  "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
```

**示例 3：**

```
输入: "a good   example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
```

 

**说明：**

- 无空格字符构成一个单词。
- 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
- 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。



基本思想：拆分组装

去掉收尾的空格，然后拆分，逆序组装

使用\ \s+匹配多个空格



源代码：

```java
class Solution {
    public String reverseWords(String s) {
            s=s.trim();
            String[] tmp=s.split(" ");
            String result="";
            for (int i = tmp.length-1; i >=0 ; i--) {
                if(!tmp[i].equals("")){
                    result+=tmp[i].trim();
                    if(i>0)result+=" ";
                }
            }
            return result;
        }
}
```





## [剑指 Offer 58 - II. 左旋转字符串](https://leetcode.cn/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/)

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

 

**示例 1：**

```
输入: s = "abcdefg", k = 2
输出: "cdefgab"
```

**示例 2：**

```
输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"
```

 

**限制：**

- `1 <= k < s.length <= 10000`

基本思想：提取子串进行拼接

源代码：

```java
class Solution {
    public String reverseLeftWords(String s, int n) {
            String s1=s.substring(0,n),s2=s.substring(n);

            return s2+s1;
        }
}
```

## [剑指 Offer 59 - I. 滑动窗口的最大值 - 力扣（LeetCode）](https://leetcode.cn/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/submissions/)

给定一个数组 `nums` 和滑动窗口的大小 `k`，请找出所有滑动窗口里的最大值。

**示例:**

```
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7] 
解释: 

  滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7
```

 

**提示：**

你可以假设 *k* 总是有效的，在输入数组 **不为空** 的情况下，`1 ≤ k ≤ nums.length`。



基本思想：单调栈

对于一个窗口来说，[i,j]，那么x[j]一定比x[i]晚出窗口，所以如果后加入的值大于窗口队尾值可以出队处理，这样队列就是一个单调递减的队列



源代码：

```java
class Solution {
     public int[] maxSlidingWindow(int[] nums, int k) {
            int[] result=new int[nums.length-k+1];
            Deque<Integer> deque=new LinkedList<>();
            for(int i=0;i<k;i++){
                while (!deque.isEmpty()&&nums[i]>deque.peekLast())
                    deque.removeLast();
                deque.addLast(nums[i]);
            }

            for (int i = 0,j=i+k-1; i < result.length-1; i++,j++) {
                result[i]=deque.peekFirst();
                while(!deque.isEmpty()&&nums[j+1]>deque.peekLast())
                    deque.removeLast();
                deque.addLast(nums[j+1]);
                if(nums[i]==deque.peekFirst())
                    deque.removeFirst();

            }
            result[result.length-1]=deque.peekFirst();
            return result;

        }
}
```

## [剑指 Offer 60. n个骰子的点数](https://leetcode.cn/problems/nge-tou-zi-de-dian-shu-lcof/)

把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。

你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。

 

**示例 1:**

```
输入: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]
```

**示例 2:**

```
输入: 2
输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]
```

 

**限制：**

```
1 <= n <= 11
```

基本思想：动态规划

对于k个筛子来说，k-1个筛子的点数方案加上1到6点就是k个筛子的某个点数方案，将这个点数的方案数加一。最后得出的方案数除以总方案数（6^n）

源代码：

```java
class Solution {
    public double[] dicesProbability(int n) {
            double[] result=new double[5*n+1];
            int[][] tmp=new int[n][6*n];
            for(int i=0;i<6;i++){
                tmp[0][i]=1;
            }
            for (int i = 1; i <n; i++) {
                for (int j = i; j <=i*6; j++) {
                    for (int k = 1; k <=6; k++) {
                        tmp[i][j+k-1]+=tmp[i-1][j-1];
                    }
                }
            }
        
            double N=Math.pow(6,n);
            for (int i = 0; i < result.length; i++) {
                result[i]=tmp[n-1][n-1+i]/N;
            }

            return result;
        }
}
```



## [剑指 Offer 61. 扑克牌中的顺子](https://leetcode.cn/problems/bu-ke-pai-zhong-de-shun-zi-lcof/)

从**若干副扑克牌**中随机抽 `5` 张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。

 

**示例 1:**

```
输入: [1,2,3,4,5]
输出: True
```

 

**示例 2:**

```
输入: [0,0,1,2,5]
输出: True
```

 

**限制：**

数组长度为 5 

数组的数取值为 [0, 13] .



基本思想：对于一个顺子需要满足的条件：

- 不存在重复的数字
- 最大值与最小值的差值小于5

（不包括大小王）

源代码：

```java
class Solution {
      public boolean isStraight(int[] nums) {
            Arrays.sort(nums);
            int con=0;
            for (int i = 0; i < nums.length-1; i++) {
                if(nums[i]==0){
                    con++;
                }
                else if(nums[i]==nums[i+1])
                    return false;
            }
            return nums[4]-nums[con]<5;

        }
}
```

## [剑指 Offer 62. 圆圈中最后剩下的数字](https://leetcode.cn/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/)

0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

 

**示例 1：**

```
输入: n = 5, m = 3
输出: 3
```

**示例 2：**

```
输入: n = 10, m = 17
输出: 2
```

 

**限制：**

- `1 <= n <= 10^5`
- `1 <= m <= 10^6`

基本思想：模拟不行超时。用动态规划

这么著名的约瑟夫环问题，是有数学解法的！
因为数据是放在数组里，所以我在数组后面加上了数组的复制，以体现是环状的。我们先忽略图片里的箭头：
【第一轮后面的数字应该是[0, 1, 2 ,3 ,4]，手误打错了。。抱歉】

![image.png](https://pic.leetcode-cn.com/9dda886441be8d249abb76e35f53f29fd6e780718d4aca2ee3c78f947fb76e75-image.png)


很明显我们每次删除的是第 mm 个数字，我都标红了。

第一轮是 [0, 1, 2, 3, 4] ，所以是 [0, 1, 2, 3, 4] 这个数组的多个复制。这一轮 2 删除了。

第二轮开始时，从 3 开始，所以是 [3, 4, 0, 1] 这个数组的多个复制。这一轮 0 删除了。

第三轮开始时，从 1 开始，所以是 [1, 3, 4] 这个数组的多个复制。这一轮 4 删除了。

第四轮开始时，还是从 1 开始，所以是 [1, 3] 这个数组的多个复制。这一轮 1 删除了。

最后剩下的数字是 3。

图中的绿色的线指的是新的一轮的开头是怎么指定的，每次都是固定地向前移位 mm 个位置。

然后我们从最后剩下的 3 倒着看，我们可以反向推出这个数字在之前每个轮次的位置。

最后剩下的 3 的下标是 0。

第四轮反推，补上 mm 个位置，然后模上当时的数组大小 22，位置是(0 + 3) % 2 = 1。

第三轮反推，补上 mm 个位置，然后模上当时的数组大小 33，位置是(1 + 3) % 3 = 1。

第二轮反推，补上 mm 个位置，然后模上当时的数组大小 44，位置是(1 + 3) % 4 = 0。

第一轮反推，补上 mm 个位置，然后模上当时的数组大小 55，位置是(0 + 3) % 5 = 3。

所以最终剩下的数字的下标就是3。因为数组是从0开始的，所以最终的答案就是3。

总结一下反推的过程，就是 (当前index + m) % 上一轮剩余数字的个数。





源代码：

```java
class Solution {
   public int lastRemaining(int n, int m) {
           int result=0;
           for (int i=2;i<n+1;i++)
                result=(result+m)%i;
           return result;
        }
}
```

## [剑指 Offer 63. 股票的最大利润](https://leetcode.cn/problems/gu-piao-de-zui-da-li-run-lcof/)

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

 

**示例 1:**

```
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
```

**示例 2:**

```
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
```

 

**限制：**

```
0 <= 数组长度 <= 10^5
```



基本思想：动态规划

我们可以使用一个辅助数组a[]，在该数组中a[i]保存截止到第i天最低价格，price[i+1]-a[i]>最大值就更新最大值

a[i]转移方程 
$$
a[i]=
\begin{cases}
a[i-1]&&a[i-1]<price[i] \\
price[i]&&a[i-1]>price[i]
\end{cases}
$$
result的更新方式
$$
result=
\begin{cases}
price[i]-a[i-1]&&price[i]-a[i-1]>result\\
result&&price[i]-a[i-1]<=result

\end{cases}
$$
源代码：

```java
class Solution {
   public int maxProfit(int[] prices) {
            int[] a=new int[prices.length];
            if(prices.length==0)return 0;
            a[0]=prices[0];
            int result=0;
            for (int i = 1; i <prices.length; i++) {
                if(prices[i]<a[i-1])
                    a[i]=prices[i];
                else a[i]=a[i-1];
                if(prices[i]-a[i-1]>result)
                    result=prices[i]-a[i-1];

            }
            return result;
        }
}
```

## [剑指 Offer 64. 求1+2+…+n](https://leetcode.cn/problems/qiu-12n-lcof/)

求 `1+2+...+n` ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

 

**示例 1：**

```
输入: n = 3
输出: 6
```

**示例 2：**

```
输入: n = 9
输出: 45
```

 

**限制：**

- `1 <= n <= 10000`



基本思想：递归

这里限制了循环和条件语句，只能选择递归来代替循环，循环终止条件不能使用if等条件语句，可以使用&&与操作，对于"条件一&&条件二"，只要条件一不成立条件二就不会执行，可以把递归放在条件二，当条件一不成立时递归就终止了，条件一为递归终止条件



源代码：

```java
class Solution {
   public int sumNums(int n) {
            boolean x=n > 1 && (n+=sumNums(n-1))>0;
            return n;
        }
}
```



## [剑指 Offer 65. 不用加减乘除做加法](https://leetcode.cn/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof/)

写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。

 

**示例:**

```
输入: a = 1, b = 1
输出: 2
```

 

**提示：**

- `a`, `b` 均可能是负数或 0
- 结果不会溢出 32 位整数

基本思想：位运算

对于两个数a、b，a和b的与运算就是进位的结果，a和b的异或运算就是相加的结果，如果进位不为0，那么结果就是进位加相加，直到没有进位

源代码：

```java
class Solution {
   public int add(int a, int b) {
            int carry=a&b;
            int sum=a^b;
            while(carry!=0){
                carry<<=1;
                return add(carry,sum);
            }
            return sum;
        }
}
```



## [剑指 Offer 66. 构建乘积数组](https://leetcode.cn/problems/gou-jian-cheng-ji-shu-zu-lcof/)

给定一个数组 `A[0,1,…,n-1]`，请构建一个数组 `B[0,1,…,n-1]`，其中 `B[i]` 的值是数组 `A` 中除了下标 `i` 以外的元素的积, 即 `B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]`。不能使用除法。

 

**示例:**

```
输入: [1,2,3,4,5]
输出: [120,60,40,30,24]
```

 

**提示：**

- 所有元素乘积之和不会溢出 32 位整数
- `a.length <= 100000`

基本思想：

- 方案一：两次遍历，第一次遍历将所有值乘起来得到一个乘积，对于结果数组每一个数用这个乘积除以对应的原数组的数即可。这里会出现0的问题，所以需要统计一下0的个数，如果超过两个那么全部的结果都是0，如果只有1个0，那么除了0位置的值不为0其余全为0

源代码：

```java
class Solution {
     public int[] constructArr(int[] a) {
            int tmp=1,count=0,index=0;
            int[] result=new int[a.length];
            for (int i = 0; i < a.length; i++) {
                if(a[i]==0) {
                    index=i;
                    count++;
                    if (count > 1) return result;
                    continue;
                }
                tmp*=a[i];
            }
            if(count==1){
                result[index]=tmp;
                return result;
            }
            for (int i = 0; i < a.length; i++) {
                result[i]=tmp/a[i];
            }
            return result;
        }
}
```

- 方案二：如图所示

![Picture1.png](https://pic.leetcode-cn.com/1624619180-vpyyqh-Picture1.png)

源代码：

```java
class Solution {
    public int[] constructArr(int[] a) {
        int len = a.length;
        if(len == 0) return new int[0];
        int[] b = new int[len];
        b[0] = 1;
        int tmp = 1;
        for(int i = 1; i < len; i++) {
            b[i] = b[i - 1] * a[i - 1];
        }
        for(int i = len - 2; i >= 0; i--) {
            tmp *= a[i + 1];
            b[i] *= tmp;
        }
        return b;
    }
}
```

## [剑指 Offer 67. 把字符串转换成整数](https://leetcode.cn/problems/ba-zi-fu-chuan-zhuan-huan-cheng-zheng-shu-lcof/)



写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。

 

首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。

当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。

该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。

注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。

在任何情况下，若函数不能进行有效的转换时，请返回 0。

**说明：**

假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回  INT_MAX (231 − 1) 或 INT_MIN (−231) 。

**示例 1:**

```
输入: "42"
输出: 42
```

**示例 2:**

```
输入: "   -42"
输出: -42
解释: 第一个非空白字符为 '-', 它是一个负号。
     我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
```

**示例 3:**

```
输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。
```

**示例 4:**

```
输入: "words and 987"
输出: 0
解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
     因此无法执行有效的转换。
```

**示例 5:**

```
输入: "-91283472332"
输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。 
     因此返回 INT_MIN (−231) 。
```



基本思想：模拟。

首先去除首部可能出现的空格，然后判断首字符是不是数字或者正负号，如果不是直接返回0，如果是正负号标记一下正负。然后开始循环转换数字，result*10+str[i]。直到出现非数字或者越界。

源代码：

```java
class Solution {
   public int strToInt(String str) {
            str=str.trim();
            if(str.length()==0)return 0;
            int index=0;
            Boolean flag=true;
            if(isNum(str.charAt(index))){

            }
            else if(str.charAt(index)=='-'){
                flag=false;
                index++;
            }
            else if(str.charAt(index)=='+'){
                index++;
            }
            else return 0;
            Long tmp= 0L;
            while(index<str.length()&&isNum(str.charAt(index))&&tmp<=Integer.MAX_VALUE&&tmp>=Integer.MIN_VALUE){
                tmp=tmp*10+str.charAt(index)-'0';
                index++;
            }
            if(!flag)tmp=-tmp;
            if(tmp>Integer.MAX_VALUE)return Integer.MAX_VALUE;
            if(tmp<Integer.MIN_VALUE)return Integer.MIN_VALUE;
            return Math.toIntExact(tmp);
        }
        public boolean isNum(char s){
            return s>='0'&&s<='9';
        }
}
```