• 每个整数都在范围 [0, 2n - 1] 内（含 0 和 2n - 1）
• 第一个整数是 0
• 一个整数在序列中出现 不超过一次
• 每对 相邻 整数的二进制表示 恰好一位不同 ，且
• 第一个 和 最后一个 整数的二进制表示 恰好一位不同

给你一个整数 n ，返回任一有效的 n 位格雷码序列 。

示例 1：

输入：n = 2
输出：[0,1,3,2]
解释：
[0,1,3,2] 的二进制表示是 [00,01,11,10] 。
- 00 和 01 有一位不同
- 01 和 11 有一位不同
- 11 和 10 有一位不同
- 10 和 00 有一位不同
[0,2,3,1] 也是一个有效的格雷码序列，其二进制表示是 [00,10,11,01] 。
- 00 和 10 有一位不同
- 10 和 11 有一位不同
- 11 和 01 有一位不同
- 01 和 00 有一位不同

示例 2：

输入：n = 1
输出：[0,1]

提示：

• 1 <= n <= 16

找规律想方法，找到对称关系

试着先从头开始写几行数据看下吧

   0
   0    1
  00   01   11   10
 000  001  011  010  110  111  101  100
0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000

1. 只有0的时候，不明显，继续往下看，只有第二行也一样
2. 第三行，我们先把数字都扩充到2位，之前的变成00, 01，那么剩下的只有11, 10 了此时只有 00 01 11 10这个顺序了，其他的组合情况暂不考虑
3. 第三行依旧扩充到3位000 001 011 010 ，下一个数字要和010只有一位不同的话只能选择110了，再下一位依旧只能111，这样 101 100
4. 开始总结规律，可以看到后半部分都是1xx这样的数据了，且如果户管最高位的话，和前面的内容是对称的，即，下标i和下标n - i对应，且下标i的值加1xx(二进制数)等于下标n - i 的值，那么我们基本就总结出规律了
5. 看第四行，原本前8位数字整体原封不动的保留，同时对应后面对称位置的值为当前位置的值加1000(二进制数)

稍微总结下

这个怎么来理解关系呢？我们来缕下 假设数组长度为 2n，（n不等于0，指实际位置从1开始，不是指从0开始的下标）

1. 从对称的最中间两位开始看，也就是第 n和n+1位，这两个数字后面部分是完全一样的，只有头部第一位一个是1 一个是0的区别，相差一位
2. 再看n-1 和n+2这两个对称位置，拿上面的第四行数据中间部分来说明
   0101 0100 1100 1101
   对应数字为0101和 1101, 因为0101和后面一位0100相差一位，所以同样对称部分的1100和1101如果忽略头部的1的话和这边其实是一致的也是相差一位，而又因为这两者头部都是加的1是相同的，所以这两者是必然相差一位的即n+1与n+2相差的一位是和n-1与n相差的一位是一样的
3. 再往后更多的对称部分和这一步也一样可以推断出是相差一位的

代码

class Solution {
    public List<Integer> grayCode(int n) {
        int i = 0;
        int[] list1 = new int[1];
        int[] list2 = new int[2];
        while (++i <=n){
            list2 = new int[1<<i];
            int lastIdx = list1.length * 2 - 1;
            int plus = 1 << (i-1);
            for (int idx = 0; idx < list1.length; idx++) {
                list2[idx] = list1[idx];
                list2[lastIdx - idx] =  list1[idx] | plus ;
            }
            list1 = list2;
        }
        List<Integer> r = new ArrayList<>();
        for (int i1 : list2) {
            r.add(i1);
        }
        return r;
    }
}

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

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

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

输入：s = ""
输出：0

栈模拟，java

class Solution {
    public int longestValidParentheses(String s) {
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int idx = -1;
        int ans = 0;
        while (++idx < s.length()) {
            //表示上一个未被匹配的左括号'('
            if (s.charAt(idx) == '(') {
                stack.push(idx);
            } else {
                //这里是右括号‘)’
                stack.pop();
                if (!stack.isEmpty()) {
                    ans = Math.max(ans, idx - stack.peek());
                }else{
                    stack.push(idx);
                }
            }
        }
        return ans;
    }
}

1. 栈底元素是有效区间的起始位置
2. 之后栈内只插入左括号（的位置
3. 每遇到一个右括号，则从栈顶弹出一个元素
4. 如果弹出的是左括号，那么就能知道当前的有效区间的长度
5. 如果弹出的右括号，此时栈内为空，之前的有效区间不存在了，后面再能遇到的是新的有效区间，需要从当前位置重新开始表示，那么就把当前值插入到栈底部
6. 在每次得到有效区间的时候，依次比较取较大值

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。

示例 1:

输入：root = [4,2,7,1,3], val = 2
输出：[2,1,3]

Example 2:

输入：root = [4,2,7,1,3], val = 5
输出：[]

提示：

• 数中节点数在 [1, 5000] 范围内
• 1 <= Node.val <= 107
• root 是二叉搜索树
• 1 <= val <= 107

根据二叉搜索树的左小右大的特性【递归&遍历树】

递归

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null){
            return null;
        }
        if (root.val == val){
            return root;
        }
        return root.val > val ? searchBST(root.left, val) : searchBST(root.right, val);
    }
}

应该没啥特殊的，二叉搜索树的特性

左子节点  <   根节点   <  右子节点

所以照着这个写就行了

也可以改递归为遍历的写法，毕竟 递归和遍历循环是可以相互转化的

遍历

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        while (root !=null){
            if (root.val == val) return root;
            root = root.val > val? root.left : root.right;
        }
        return root;
    }
}

给定一个较长字符串big和一个包含较短字符串的数组smalls，设计一个方法，根据smalls中的每一个较短字符串，对big进行搜索。输出smalls中的字符串在big里出现的所有位置positions，其中positions[i]为smalls[i]出现的所有位置。

示例：

输入：
big = "mississippi"
smalls = ["is","ppi","hi","sis","i","ssippi"]
输出： [[1,4],[8],[],[3],[1,4,7,10],[5]]

提示：

• 0 <= len(big) <= 1000
• 0 <= len(smalls[i]) <= 1000
• smalls的总字符数不会超过 100000。
• 你可以认为smalls中没有重复字符串。
• 所有出现的字符均为英文小写字母。

smalls数组构建字典树

1. 把smalls数组构建字典树
2. 把big数组从第i位开始到结尾的子序列拿到字典树上匹配，i从0开始分别求解，直到结束
3. 因为匹配的时候需要知道当前字典树上字符串结束节点是哪个字符的，所以字典树的节点需要额外记录下各自归属与smalls数组中对应字符串的下标
4. 在树上匹配的过程中，但凡匹配到了一个结束字符，就在结果数组的对应这个字符串下标的子数组中插入一个当前匹配的big字符串子序列的开始下标

代码

class Solution {
    public int[][] multiSearch(String big, String[] smalls) {
        Trie trie = new Trie();
        trie.smallsCount = smalls.length;
        trie.insert(smalls);
        return trie.search(big);
    }


    public class Trie{

        Node tree;
        int smallsCount = 0;

        public Trie(){
            tree = new Node();
        }

        void insert(String[] strArr){
            for (int idx = 0; idx < strArr.length; idx++) {
                Node cur = tree;
                String str = strArr[idx];
                int i = -1;
                while (++i < str.length()){
                    int child = str.charAt(i)-'a';
                    if (cur.children[child] == null){
                        cur.children[child] = new Node();
                    }
                    cur = cur.children[child];
                }
                cur.flag = true;
                cur.smallIndex = idx;
            }
        }

        int[][] search(String str){
            int[][] res = new int[smallsCount][];
            List<List<Integer>> list = new ArrayList<>();
            for (int i = 0; i < smallsCount; i++) {
                list.add(new ArrayList<>());
            }

            for (int i = 0; i < str.length(); i++) {
                String subStr = str.substring(i);
                Node cur = tree;
                int idx = -1;
                while (cur != null && ++idx < subStr.length()){
                    char c = subStr.charAt(idx);
                    if (cur.children[c-'a'] != null){
                        cur = cur.children[c-'a'];
                        if (cur.flag){
                            list.get(cur.smallIndex).add(i);
                        }
                    }else{
                        break;
                    }
                }
            }
            for (int i = 0; i < list.size(); i++) {
                res[i] = list.get(i).stream().mapToInt(Integer::intValue).toArray();
            }
            return res;
        }




        class Node{
            boolean flag = false;
            Node[] children;
            int smallIndex = -1;
            public Node(){
                children = new Node[26];
            }
        }
    }
}

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

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

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

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

判题标准:

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

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：

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

示例 2：

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

提示：

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

简单题简单做，双指针，后值往前覆盖

拿示例数据比划比划，其实这题还是比较有意思的

1. A、B两个指针，A在前B在后
2. 由于数组本身的有序递增性，所以B指针的指向必然是大于等于A的此时，所以需要移动B指针往后，找到比A指针指向的值大的数值，不能等于
3. 接下来把找到的大于A指针指向的值赋值到A指针的下一个位置，A指针移动到这个新的位置，即往后移动一位
4. 接下来继续这个循环比较A、B指针所指向的值
5. 终止条件：B指针已经走到了数组结尾
6. 返回结果：此时A指针所指向的值为所需结果的结尾指针，那么长度就是A指针的数值+1
7. 特殊情况: 当数组长度小于2的时候，可能是0，也可能是1，数组不用修改，直接返回数组长度即可（0或者1）

代码

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length < 2){
            return nums.length;
        }
        int cur1 = 0;
        int cur2 = 1;
        while (cur2 < nums.length){
            if (nums[cur1] >= nums[cur2]){
                cur2++;
                continue;
            }
            cur1++;
            nums[cur1] = nums[cur2];
        }
        return cur1 + 1;
    }
}

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

示例:

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

限制：

0 <= 节点个数 <= 5000

注意：本题与主站 206 题相同：https://leetcode-cn.com/problems/reverse-linked-list/

遍历修改指针

修改指针

操作简单

1. 把当前节点的next指向之前遍历的节点pre，这是核心
2. 因为进行了上一步操作之后下一个节点就找不到了，所以需要一个变量暂存一下修改之前的next指向
3. 同时pre指向跟随遍历窗口移动到当前节点
4. 同时需要把当前移动到原链表的下一个节点，也就是步骤(2)中记下的那个
5. 到结束时遍历到原链表的结尾null节点，此时pre指向为原链表的结尾非空那个节点，也就是翻转后的头结点

代码

class Solution {
    public ListNode reverseList(ListNode head) {
        if (null == head || head.next == null){
            return head;
        }
        ListNode pre = null;
        ListNode cur = head;
        while (cur!=null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

从若干副扑克牌中随机抽 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] .

简单统计遍历替代处理

简单、思路比较清晰

1. 建一个int[] arr = new int[14];统计次数
2. 遍历arr数组，从下标arr[1]开始，arr[0]作为特殊情况暂时留着后面有用
3. 先遍历找到统计次数不是1的下标，表示顺子可能开始的地方，当然也可能不是从这开始的，后面会说，并开始记录连续区间的长度count
4. 遇到的最基本的情况当前数字统计出现了1次，连续区间长度count加1
5. 如果某个数字出现了超过1次，必然不能组成长度为5的顺子，发牌员总共就给了5张牌
6. 如果遇到了某个数字出现次数为0，表示顺子断开了，从原来的arr[0]位置，拿一张通配牌王来顶一下
7. 如果王不够了,已经无计可施了，则直接判断此时的连续区间长度是否达到了5
8. 如果已经遍历结束了，看下已经统计到的连续区间的长度count是否为5，如果不为5的话再看看有没有多余的通配牌王，可以拿来放在当前连续区间的前面，也就是上面的第3条说的，连续区间的开始位置可能不是匹配到的位置，可能在这个位置之前拿王来抵用
9. 当然你也可能摸了5张王，而连续区间长度count为0，而arr[0] = 5,那你就是天选之人 （邱森旺） 了
10. 综上最终判断其实是(count + arr[0]) == 5

代码

class Solution {
    public boolean isStraight(int[] nums) {
        int[] arr = new int[14];
        for (int num : nums) {
            arr[num]++;
        }
        int idx = 0;
        //从1开始 可匹配任意的 0 先不管
        while (++idx < arr.length && arr[idx]==0){}
        idx--;
        int count = 0;
        while (++idx < arr.length){
            if (arr[idx]>1){
                //如果有一个数字出现的次数大于1了，则必然不能
                return false;
            }
            if (arr[idx]==0){
                if (arr[0]>0){
                    //拿 通配牌  `王` 来顶一个
                    count++;
                    arr[0]--;
                }else{
                    // `王` 也不够顶了
                    return count==5;
                }
            }else{
                //这里是等于1的情况
                count++;
            }
        }
        //可能有剩余的`王` + 已知的连续个数合起来看看能不能凑齐五个
        return (count+arr[0]) == 5;
    }
}