给定两个字符串 s 和 t ，如果它们的编辑距离为 1 ，则返回 true ，否则返回 false 。

字符串 s 和字符串 t 之间满足编辑距离等于 1 有三种可能的情形：

• 往 s 中插入 恰好一个 字符得到 t
• 从 s 中删除 恰好一个 字符得到 t
• 在 s 中用 一个不同的字符 替换 恰好一个 字符得到 t

示例 1：

输入: s = "ab", t = "acb"
输出: true
解释: 可以将 'c' 插入字符串 s 来得到 t。

示例 2:

输入: s = "cab", t = "ad"
输出: false
解释: 无法通过 1 步操作使 s 变为 t。

提示:

• 0 <= s.length, t.length <= 104
• s 和 t 由小写字母，大写字母和数字组成

简单逐字符比较

比较简单，就挨个比较没啥太多细节，动态规划解法的话，还是有点点复杂的，不过拿来做这题有点过了

class Solution {
    public boolean isOneEditDistance(String s, String t) {
        if (s.length() - t.length() > 1 || t.length() - s.length() > 1){
            return false;
        }
        if (s.length() == t.length()){
            return checkSameLength(s,t);
        }

        if (s.length() > t.length()){
            return checkOneCharDiff(s,t);
        }else{
            return checkOneCharDiff(t,s);
        }
    }

    public boolean checkOneCharDiff(String s, String t){
        int sIdx = 0;
        int tIdx = 0;
        int sameCount = 0;
        while (tIdx<t.length() && s.charAt(sIdx) == t.charAt(tIdx)){
            sIdx++;
            tIdx++;
            sameCount++;
        }
        sIdx++;
        while (tIdx<t.length() && s.charAt(sIdx) == t.charAt(tIdx)){
            sIdx++;
            tIdx++;
            sameCount++;
        }
        return s.length()-sameCount == 1;
    }

    public boolean checkSameLength(String s, String t){
        int sIdx = 0;
        int tIdx = 0;
        int sameCount = 0;
        while (sIdx<s.length() && s.charAt(sIdx) == t.charAt(tIdx)){
            sIdx++;
            tIdx++;
            sameCount++;
        }
        sIdx++;
        tIdx++;
        while (sIdx<s.length() && s.charAt(sIdx) == t.charAt(tIdx)){
            sIdx++;
            tIdx++;
            sameCount++;
        }
        return s.length()-sameCount == 1;
    }
}

实现 strStr() 函数。

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

说明：

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

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

示例 1：

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

示例 2：

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

提示：

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

Sunday算法实现

举个栗子说明，haystack字符串

h, e, l, l, o, s, h, e, l, l, d, o, h, e, l, d, l, o, h, e, l, w, l, o, q, h, e, l, l, o, w, h, e, l, l, o
0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

needle字符串

l, o, h, e, l, w, l
0  1  2  3  4  5  6

1. 从头开始匹配，匹配失败，
2. 找到haystack第7个字符下标6位置的字符h，h字符在needle字符串l, o, h, e, l, w, l最后出现的下标为2，则从下标6位置的字符h往前找2位开始匹配，
3. 此时新开始匹配的下标为4，字符为o，依旧匹配失败，继续往后找needle字符串长度的位置在下标11位置发现字符o，此时o在needle中最后出现的位置为下标1，则往前找一位，从haystack的10下标开始匹配
4. 10下标的d不能和needle匹配，继续往后找needle长度个位置，依旧是字符o，在needle中最后出现的位置为下标1，则往前找一位从haystack的第16下标开始匹配，
5. 能完全匹配，结束，返回当前开始的下标16。

代码

class Solution {
    //Sunday算法实现
    public int strStr(String haystack, String needle) {
        int n = haystack.length();
        int m = needle.length();
        int[] lastPos = new int[256];
        for (int i = 0; i < needle.length(); i++) {
            lastPos[needle.charAt(i)] = i;
        }
        for (int i = 0; i + m <= n; i += (m - lastPos[haystack.charAt(i+m)])) {
            boolean flag = true;
            for (int j = 0; j < m; j++) {
                if (haystack.charAt(i+j) == needle.charAt(j)){
                    continue;
                }
                flag = false;
                break;
            }
            if (flag){
                return i;
            }
            if (i + m >= n) break;
        }
        return -1;
    }
}

给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。打乱后，数组的所有排列应该是 等可能 的。

实现 Solution class:

• Solution(int[] nums) 使用整数数组 nums 初始化对象
• int[] reset() 重设数组到它的初始状态并返回
• int[] shuffle() 返回数组随机打乱后的结果

示例 1：

输入
["Solution", "shuffle", "reset", "shuffle"]
[[[1, 2, 3]], [], [], []]
输出
[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]

解释
Solution solution = new Solution([1, 2, 3]);
solution.shuffle();    // 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。例如，返回 [3, 1, 2]
solution.reset();      // 重设数组到它的初始状态 [1, 2, 3] 。返回 [1, 2, 3]
solution.shuffle();    // 随机返回数组 [1, 2, 3] 打乱后的结果。例如，返回 [1, 3, 2]

提示：

• 1 <= nums.length <= 50
• -106 <= nums[i] <= 106
• nums 中的所有元素都是 唯一的
• 最多可以调用 104 次 reset 和 shuffle

随机简单，可以参考下java.util.Collections#shuffle方法

核心：和前面的随机一位数字交换

class Solution {

    int[] nums;

    int[] shuffle;

    public Solution(int[] nums) {
        this.nums = nums;
    }
    
    public int[] reset() {
        return nums;
    }

    
    public int[] shuffle() {
        shuffle = nums.clone();
        Random random = new Random();
        for (int i = 0; i < shuffle.length; i++) {
            swap(shuffle,i,random.nextInt(i+1));
        }
        return shuffle;
    }

    public void swap(int[] arr ,int x ,int y){
        int tmp = arr[x];
        arr[x] = arr[y];
        arr[y] = tmp;
    }

}

看下java.util.Collections#shuffle(java.util.List<?>, java.util.Random)方法的源码，其实思想是一样的

public static void shuffle(List<?> list, Random rnd) {
    int size = list.size();
    if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
        for (int i=size; i>1; i--)
            swap(list, i-1, rnd.nextInt(i));
    } else {
        Object arr[] = list.toArray();

        // Shuffle array
        for (int i=size; i>1; i--)
            swap(arr, i-1, rnd.nextInt(i));

        // Dump array back into list
        // instead of using a raw type here, it's possible to capture
        // the wildcard but it will require a call to a supplementary
        // private method
        ListIterator it = list.listIterator();
        for (int i=0; i<arr.length; i++) {
            it.next();
            it.set(arr[i]);
        }
    }
}

给定一个 N 叉树，找到其最大深度。

最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。

示例 1：

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

示例 2：

输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：5

提示：

• 树的深度不会超过 1000 。
• 树的节点数目位于 [0, 104] 之间。

深搜

遍历树并记录更新最大深度

class Solution {
    int deep = 0;
    public int maxDepth(Node root) {
        dfs(root,0);

        return deep;
    }

    public void dfs(Node node,int current){
        if (null == node){
            return ;
        }
        current++;
        deep = Math.max(deep,current);
        for (Node child : node.children){
            dfs(child,current);
        }
    }
}

广搜也可以，按层遍历记录最终的层数，代码比较简单不做赘述

和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。

现在，给你一个整数数组 nums ，请你在所有可能的子序列中找到最长的和谐子序列的长度。

数组的子序列是一个由数组派生出来的序列，它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。

示例 1：

输入：nums = [1,3,2,2,5,2,3,7]
输出：5
解释：最长的和谐子序列是 [3,2,2,2,3]

示例 2：

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

示例 3：

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

提示：

• 1 <= nums.length <= 2 * 104
• -109 <= nums[i] <= 109

哈希表一次遍历

1. 遍历int[] nums数组，统计每个数字出现的次数
2. 如果统计的表中有当前数字 -1 或者 +1 则可以和当前数字组成符合要求的子序列，长度为两个数字统计次数之和
3. 如果不存在-1 或者 +1 的统计结果，则表明只有当前数字，不能组成符合要求的子序列

代码

class Solution {

    public int findLHS(int[] nums) {
        int max = 0;
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num,map.getOrDefault(num,0)+1);
            int tmp = Math.max(map.getOrDefault(num-1,0),map.getOrDefault(num+1,0))+ map.get(num);
            if (tmp> map.get(num)){
                max = Math.max(max,tmp);
            }
        }
        return max;
    }
}

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例 1：

输入：strs = ["flower","flow","flight"]
输出："fl"

示例 2：

输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。

提示：

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] 仅由小写英文字母组成

字典树解法

思路

字符串搜索匹配中常用的方法之一字典树，用在这里还是很方便的

1. 遍历String[] strs构建字典树
2. 从字典树的根节点看是往下找只有一个子节点的情况，把这个自己点转化为char字符记下来
3. 不光是只有一个的子节点的情况。如果说遇到的节点是标记为了字符串结尾的话，也应当结束，因为记录下来的字符组成的字符串已经达到了某个字符串的长度了

一点思考

代码中的getSingleChild()方法是判断这个节点是否只有一个子节点的，用了个遍历26个字母的方法

如果只有一个子节点的话，会返回那个子节点对应的下标，从而可以重新转换为char字符。

不过可以再优化调整下，我们可以在Node节点中再增加一个字段标记当前节点下面有多少个不同的子节点，而需要操作就变为，当在Node的children上构建新子节点的时候，同时给这个统计字段+1，这样我们在后面遍历搜索的时候就可以直接判断了

代码

class Solution {
    public String longestCommonPrefix(String[] strs) {
        Trie trie = new Trie();

        for (String str : strs) {
            trie.insert(str);
        }


        return trie.longestCommonPrefix();
    }



    class Trie{

        Node root = new Node();

        public void insert(String str){
            if (null == str){
                return;
            }
            int idx = -1;
            Node cur = root;
            while (++idx < str.length()){
                int i = str.charAt(idx) - 'a';
                if (cur.children[i] == null){
                    cur.children[i] = new Node();
                }
                cur = cur.children[i];
            }
            cur.flag = true;
        }


        public String longestCommonPrefix(){
            StringBuffer sb = new StringBuffer();
            Node cur = root;
            int idx = getSingleChild(cur);
            while (idx != -1){
                if (cur.flag){
                    break;
                }
                //记char
                sb.append((char)('a'+idx));
                //找下一个
                cur = cur.children[idx];
                idx = getSingleChild(cur);
            }
            return sb.toString();
        }

        private int getSingleChild(Node node){
            int singleChild = -1;
            for (int i = 0; i < node.children.length; i++) {
                if (node.children[i]!=null){
                    if (singleChild!=-1){
                        return -1;
                    }
                    singleChild = i;
                }
            }
            return singleChild;
        }

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

改了一下，完全没提升

class Solution {
    public String longestCommonPrefix(String[] strs) {
        Trie trie = new Trie();
        for (String str : strs) {
            trie.insert(str);
        }
        return trie.longestCommonPrefix();
    }


    class Trie {

        Node root = new Node();

        public void insert(String str) {
            if (null == str) {
                return;
            }
            int idx = -1;
            Node cur = root;
            while (++idx < str.length()) {
                int i = str.charAt(idx) - 'a';
                if (cur.children[i] == null) {
                    cur.children[i] = new Node();
                    cur.childrenCount++;
                }
                cur = cur.children[i];
            }
            cur.flag = true;
        }


        public String longestCommonPrefix() {
            StringBuffer sb = new StringBuffer();
            Node cur = root;
            int idx = cur.getSingleChild();
            while (idx != -1) {
                if (cur.flag) {
                    break;
                }
                //记char
                sb.append((char) ('a' + idx));
                //找下一个
                cur = cur.children[idx];
                idx = cur.getSingleChild();
            }
            return sb.toString();
        }

        class Node {

            boolean flag;
            Node[] children;
            int childrenCount;

            public Node() {
                childrenCount = 0;
                flag = false;
                children = new Node[26];
            }

            public boolean isSingleChild() {
                return childrenCount == 1;
            }

            public int getSingleChild() {
                if (isSingleChild()) {
                    for (int i = 0; i < children.length; i++) {
                        if (children[i] != null) {
                            return i;
                        }
                    }
                }
                return -1;
            }
        }
    }
}

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

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

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

示例 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 被删除的节点

遍历修改引用

基本分析

1. 删除头结点的操作作为特殊情况处理，直接返回头结点的下一个节点
2. 遍历链表，找到值等于val的节点，
3. 遍历的时候还要有个变量记下前一个节点是谁，
4. 直接把前一个节点的next指向当前值为val的节点的next节点
5. 注意一些遍历的边界情况
   • 比如没有找到匹配的val的节点的话，最红对链表结尾的判定
   • 比如加入链表长度只有1，且val也没有匹配这个节点的值的话pre节点依旧为null
   • 该有比如，假如链表里值为val的节点不止一个的话怎么处理呢？本题好像没这个情况

代码

class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        if (head==null){
            return head;
        }
        if (head.val == val){
            return head.next;
        }

        ListNode cur = head;
        ListNode pre = null;
        while (val != cur.val && cur != null){
            pre = cur;
            cur = cur.next;
        }
        if (null!=pre){
            pre.next = cur.next;
        }
        return head;
    }
}