最长上升子序列 

1

avatar

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
class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int maxans = 1;
        for (int i = 1; i < nums.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxans = Math.max(maxans, dp[i]);
        }
        return maxans;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/zui-chang-shang-sheng-zi-xu-lie-by-leetcode-soluti/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

恢复空格 

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {
    public int respace(String[] dictionary, String sentence) {
        int n = sentence.length();

        Trie root = new Trie();
        for (String word: dictionary) {
            root.insert(word);
        }

        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i <= n; ++i) {
            dp[i] = dp[i - 1] + 1;

            Trie curPos = root;
            for (int j = i; j >= 1; --j) {
                int t = sentence.charAt(j - 1) - 'a';
                if (curPos.next[t] == null) {
                    break;
                } else if (curPos.next[t].isEnd) {
                    dp[i] = Math.min(dp[i], dp[j - 1]);
                }
                if (dp[i] == 0) {
                    break;
                }
                curPos = curPos.next[t];
            }
        }
        return dp[n];
    }
}

class Trie {
    public Trie[] next;
    public boolean isEnd;
    
    public Trie() {
        next = new Trie[26];
        isEnd = false;
    }

    public void insert(String s) {
        Trie curPos = this;

        for (int i = s.length() - 1; i >= 0; --i) {
            int t = s.charAt(i) - 'a';
            if (curPos.next[t] == null) {
                curPos.next[t] = new Trie();
            }
            curPos = curPos.next[t];
        }
        curPos.isEnd = true;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/re-space-lcci/solution/hui-fu-kong-ge-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

最长单词 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
给定一组单词words，编写一个程序，找出其中的最长单词，且该单词由这组单词中的其他单词组合而成。若有多个长度相同的结果，返回其中字典序最小的一项，若没有符合要求的单词则返回空字符串。

示例：

输入： ["cat","banana","dog","nana","walk","walker","dogwalker"]
输出： "dogwalker"
解释： "dogwalker"可由"dog"和"walker"组成。
提示：

0 <= len(words) <= 200
1 <= len(words[i]) <= 100
通过次数3,239提交次数8,452

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-word-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
class Solution {                                                                //树结点
    class TreeNode {
        private boolean isEnd;
        private TreeNode[] next;
        TreeNode() {
            this.isEnd = false;
            this.next = new TreeNode[26];
        }
    }

    class Tree {                                                                 //字典树类
        private TreeNode root;
        
        Tree() {
            this.root = new TreeNode();
        }

        public void insert(String word) {
            TreeNode curr = root;
            for (int i = 0; i < word.length(); i++) {
                int node = word.charAt(i) - 'a';
                if (curr.next[node] == null) curr.next[node] = new TreeNode();
                curr = curr.next[node];
            }
            curr.isEnd = true;                                                  //标记尾结点
        }

        public TreeNode getRoot() {
            return root;
        }
    }
    private Tree tree;
    boolean flag = false;                                                       //出现过别的单词
    boolean finish = false;                                                     //是否完成搜索
    public String longestWord(String[] words) {
        this.tree = new Tree();
        Arrays.sort(words, (o1, o2) -> {                                        //对每隔单词按照长度和字典序排序（长度相同时按照字典序）
            if (o1.length() == o2.length())
                return o1.compareTo(o2);
            else {
                return Integer.compare(o2.length(), o1.length());
            }
        });

        for (String x : words) {                                                //构造字典树
            tree.insert(x);
        }

        for (int i = 0; i < words.length; i++) {
            flag = false;                                                       //对每个单词进行搜索
            if (words[i].length() == 0) continue;
            dfs(0, words[i], tree.getRoot());                                   //传入当前字符索引，需要开始搜索的结点
            if (finish) return words[i];
        }
        return "";
    }

    private void dfs(int index, String word, TreeNode root) {
        if (index >= word.length()) return;

        int i = word.charAt(index) - 'a';
        root = root.next[i];

        if (root == null) return;
        if (index == word.length() - 1) {
            if (flag && root.isEnd) finish = true;                              //如果字符是单词并且前一部分由单词构成
        }
        if (root.isEnd && !flag) {                                              //当前结点是单词，但是之前不是单词构成的
            flag = true;
            dfs(index + 1, word, tree.getRoot());                               //从下一个字符开始，从头结点开始搜索是否可有新的单词构成
            if (finish) return;
            flag = false;
        } else if (root.isEnd && flag) {                                        //当前是单词并且已经有单词构成
            dfs(index + 1, word, tree.getRoot());
            if (finish) return;
        }
        dfs(index + 1, word, root);                                             //一般情况
        if (finish) return;
    }
}


作者：ppppjcute
链接：https://leetcode-cn.com/problems/longest-word-lcci/solution/java-shi-yong-zi-dian-shu-jin-xing-qian-zhui-cha-x/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

婴儿名字 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
每年，政府都会公布一万个最常见的婴儿名字和它们出现的频率，也就是同名婴儿的数量。有些名字有多种拼法，例如，John 和 Jon 本质上是相同的名字，但被当成了两个名字公布出来。给定两个列表，一个是名字及对应的频率，另一个是本质相同的名字对。设计一个算法打印出每个真实名字的实际频率。注意，如果 John 和 Jon 是相同的，并且 Jon 和 Johnny 相同，则 John 与 Johnny 也相同，即它们有传递和对称性。

在结果列表中，选择字典序最小的名字作为真实名字。

示例：

输入：names = ["John(15)","Jon(12)","Chris(13)","Kris(4)","Christopher(19)"], synonyms = ["(Jon,John)","(John,Johnny)","(Chris,Kris)","(Chris,Christopher)"]
输出：["John(27)","Chris(36)"]
提示：

names.length <= 100000
通过次数4,955提交次数12,076

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/baby-names-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
class Solution {
    public String[] trulyMostPopular(String[] names, String[] synonyms) {
        int n = names.length;
        int[] parent = new int[n];
        int[] freq = new int[n];
        Map<String,Integer> map = new HashMap<>();
        Map<Integer,String> map2 = new HashMap<>();

        //初始化
        int sign =0;
        for(String tname:names){
            int index = tname.indexOf("(");
            String name = tname.substring(0,index);                         // 获取名字
            String count = tname.substring(index+1,tname.length()-1);       // 获取数量

            map.put(name,sign);
            map2.put(sign,name);

            parent[sign] = sign;
            freq[sign] = Integer.valueOf(count);

            sign++;
        }

        //合并
        for(String synonym:synonyms){
            String temp = synonym.substring(1,synonym.length()-1);
            String[] arr = temp.split(",");

            Integer preIndex = map.get(arr[0]);                             // 获取名字对应的sign
            Integer aftIndex = map.get(arr[1]);                             // 获取名字对应的sign

            if(preIndex == null || aftIndex == null){
                continue;
            }

            while(preIndex != parent[preIndex]){                            // find              
                preIndex = parent[preIndex];
            }

            while(aftIndex != parent[aftIndex]){                            // find
                aftIndex = parent[aftIndex];
            }

            if(aftIndex.equals(preIndex)){                                  // 两个节点的祖先相同
                continue;
            }

            if(map2.get(preIndex).compareTo(map2.get(aftIndex)) >0){        // 字典序
                parent[preIndex] = aftIndex;                                // 合并，将parent[preIndex]合并到afterIndex
                freq[aftIndex] += freq[preIndex];                           // 计数整合
            }else{
                parent[aftIndex] = preIndex;                                // 合并，将parent[afterIndex]合并到preIndex
                freq[preIndex] += freq[aftIndex];
            }
        }

        //找根节点
        StringBuffer ans = new StringBuffer();
        for(int i=0;i<n;i++){
            if(parent[i] == i){
               String re = map2.get(i) + "("+freq[i]+")";
               ans.append(re);
               ans.append(",");
            }
        }

        return ans.toString().split(",");
    }
}

作者：jiu-wei-eh
链接：https://leetcode-cn.com/problems/baby-names-lcci/solution/6ci-acwei-guo-zui-hou-fa-xian-shi-fu-qin-42aq/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

解码方法 

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
36
37
38
39
40
41
42
43
一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：

'A' -> 1
'B' -> 2
...
'Z' -> 26
要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"111" 可以将 "1" 中的每个 "1" 映射为 "A" ，从而得到 "AAA" ，或者可以将 "11" 和 "1"（分别为 "K" 和 "A" ）映射为 "KA" 。注意，"06" 不能映射为 "F" ，因为 "6" 和 "06" 不同。

给你一个只含数字的 非空 字符串 num ，请计算并返回 解码 方法的 总数 。

题目数据保证答案肯定是一个 32 位 的整数。


示例 1：

输入：s = "12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）。
示例 2：

输入：s = "226"
输出：3
解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
示例 3：

输入：s = "0"
输出：0
解释：没有字符映射到以 0 开头的数字。含有 0 的有效映射是 'J' -> "10" 和 'T'-> "20" 。由于没有字符，因此没有有效的方法对此进行解码，因为所有数字都需要映射。
示例 4：

输入：s = "1"
输出：1
 

提示：

1 <= s.length <= 100
s 只包含数字，并且可能包含前导零。
通过次数80,634提交次数319,606

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/decode-ways
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

动态规划

类似于青蛙跳台阶，一次可以跳一步或者两步

dp[i-1]代表由一个元素转移而来

dp[i-2]代表由两个元素转移而来

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
class Solution {
    public int numDecodings(String s) {
        if (s.startsWith("0")) return 0;
        if (s.length() == 9) return 0;
        int[] dp = new int[s.length() + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= s.length(); i++) {
            String temp = s.substring(i - 2, i);
            if (temp.endsWith("0")) {                                           // 如果以0结尾，那么只能由两个元素转移而来
                if (temp.startsWith("1") || temp.startsWith("2")) {
                    dp[i] = dp[i - 2];
                } else {                                                        // 如果以0结尾，并且前面没有非0元素，无法组成
                    return 0;
                }
            } else {                                                       
                if (temp.compareTo("11") >= 0 && temp.compareTo("26") <= 0)     // 其中不包含20，由两个元素转移而来
                    dp[i] = dp[i - 1] + dp[i - 2];
                else                                                            // 由一个元素转移而来
                    dp[i] = dp[i - 1];
            }
        }
        return dp[s.length()];
    }
}

展开全文 >>

汉诺塔 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
(1) 每次只能移动一个盘子;
(2) 盘子只能从柱子顶端滑出移到下一根柱子;
(3) 盘子只能叠在比它大的盘子上。

请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。

你需要原地修改栈。

示例1:

 输入：A = [2, 1, 0], B = [], C = []
 输出：C = [2, 1, 0]
示例2:

 输入：A = [1, 0], B = [], C = []
 输出：C = [1, 0]
提示:

A中盘子的数目不大于14个。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/hanota-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
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
class Solution {
    /**
     * 将 A 上的所有盘子，借助 B，移动到C 上
     * @param A 原柱子
     * @param B 辅助柱子
     * @param C 目标柱子
     */
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        move(A.size(), A, B, C);
    }

    private void move(int num, List<Integer> A, List<Integer> B, List<Integer> C) {
        if (num == 1) {                                                             // 只剩一个盘子时，直接移动即可
            C.add(A.remove(A.size() - 1));
            return;
        }

        move(num - 1, A, C, B);                                                     // 将 size-1 个盘子，从 A 移动到 B// 把A的n-1块挪到B
        C.add(A.remove(A.size() - 1));                                              // 将 第size个盘子，从 A 移动到 C// 把A的最后一块挪到C
        move(num - 1, B, A, C);                                                     // 将 size-1 个盘子，从 B 移动到 C// 再把B的n-1块挪到C，完成
    }
}

作者：leetcoder-youzg
链接：https://leetcode-cn.com/problems/hanota-lcci/solution/java-di-gui-jie-jue-lao-sheng-chang-tan-de-yi-nuo-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

魔术索引 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
魔术索引。 在数组A[0...n-1]中，有所谓的魔术索引，满足条件A[i] = i。给定一个有序整数数组，编写一种方法找出魔术索引，若有的话，在数组A中找出一个魔术索引，如果没有，则返回-1。若有多个魔术索引，返回索引值最小的一个。

示例1:

 输入：nums = [0, 2, 3, 4, 5]
 输出：0
 说明: 0下标的元素为0
示例2:

 输入：nums = [1, 1, 1]
 输出：1
说明:

nums长度在[1, 1000000]之间
此题为原书中的 Follow-up，即数组中可能包含重复元素的版本
通过次数44,194提交次数64,805

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/magic-index-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

为了用算法而用算法，分治意义不大，还没有暴力遍历节省资源

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int findMagicIndex(int[] nums) {
        if (nums == null || nums.length == 0) return -1;
        return getValEqIndex(nums, 0, nums.length - 1);
    }

    public int getValEqIndex(int[] nums, int left, int right) {
        if (left > right) return -1;
        int mid = left + (right - left) / 2;
        int res = getValEqIndex(nums, left, mid - 1);
        if (res != -1) return res;
        if (nums[mid] == mid) {
            return nums[mid];
        }
        return getValEqIndex(nums, mid + 1, right);
    }
}

展开全文 >>

整数转换 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
整数转换。编写一个函数，确定需要改变几个位才能将整数A转成整数B。

示例1:

 输入：A = 29 （或者0b11101）, B = 15（或者0b01111）
 输出：2
示例2:

 输入：A = 1，B = 2
 输出：2
提示:

A，B范围在[-2147483648, 2147483647]之间

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/convert-integer-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int convertInteger(int A, int B) {
        int[] binA = new int[32];
        int[] binB = new int[32];
        int bit = 1, count = 0;
        for (int i = 0; i < 32; i++) {
            if ((A & bit) != 0) binA[i] = 1;
            else binA[i] = 0;
            if ((B & bit) != 0) binB[i] = 1;
            else binB[i] = 0;
            if (binA[i] != binB[i]) count++;
            bit <<= 1;
        }
        return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int convertInteger(int A, int B) {
        int count = 0;
        for (int i = 0; i < 32; i++) {
            if (((A & 1) ^ (B & 1)) != 0) count++;
            A >>>= 1;
            B >>>= 1;
        }
        return count;
    }
}

展开全文 >>

反转数位 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
给定一个32位整数 num，你可以将一个数位从0变为1。请编写一个程序，找出你能够获得的最长的一串1的长度。

示例 1：

输入: num = 1775(110111011112)
输出: 8
示例 2：

输入: num = 7(01112)
输出: 4
通过次数5,796提交次数13,702

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-bits-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
    public int reverseBits(int num) {
        String s = "";
        if (num > 0) s = "0" + Integer.toBinaryString(num);
        else s = Integer.toBinaryString(num);
        char[] arr = s.toCharArray();
        int len = arr.length;
        int[] dp = new int[arr.length];
        dp[0] = arr[0] == '1' ? 1 : 0;

        boolean flag = false;

        for (int i = 1; i < len; i++) {                     //正向计数
            if (arr[i] == '1') {
                dp[i] = dp[i - 1] + 1;
            } else {
                flag = true;
                dp[i] = 0;
            }
        }

        if (!flag) return arr.length;                       //如果没有0，直接返回二进制的长度

        int max = 0;

        for (int i = len - 2; i >= 0; i--) {                //反向计数
            if (arr[i + 1] == '1' && arr[i] == '1') {
                dp[i] = dp[i + 1];
            }
        }


        for (int i = 0; i < dp.length; i++) {               //碰到一个0，看左边的数量和右边的数量之和
            if (dp[i] == 0) {
                if (i + 1 < len && dp[i + 1] != 0) {        //只有右边
                    max = Math.max(max, dp[i + 1]);
                }
                if (i - 1 >= 0 && dp[i - 1] != 0) {         //只有左边
                    max = Math.max(max, dp[i - 1]);
                }

                if (i > 0 && i + 1 < len && dp[i - 1] != 0 && dp[i + 1] != 0) {
                    max = Math.max(max, dp[i - 1] + dp[i + 1]);
                }
            }
        }
        return max + 1;
    }
}

更优雅的写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int reverseBits(int num) {
        String s = Integer.toBinaryString(num);
        String[] arr = s.split("0");
        if(arr.length<1) {
            return arr.length+1;
        }
        int max = arr[0].length();
        int res = max+1;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i - 1].length() + arr[i].length() > max) {
                max = arr[i - 1].length() + arr[i].length();
                res = max + 1;
            }
        }
        return Math.min(res,32);                                //全是1时保证是正确的
    }
}

作者：286029651
链接：https://leetcode-cn.com/problems/reverse-bits-lcci/solution/chao-jian-dan-fang-fa-by-286029651/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

我是一只<br>又水又笨又菜的<br>菜狗子<br>希望有一天被领走