链表相交 

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
给定两个（单向）链表，判定它们是否相交并返回交点。请注意相交的定义基于节点的引用，而不是基于节点的值。换句话说，如果一个链表的第k个节点与另一个链表的第j个节点是同一节点（引用完全相同），则这两个链表相交。


示例 1：

输入：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：

输入：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：

输入：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) 内存。
通过次数23,312提交次数33,949

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists-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
/**
 * 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) {
        if (headA == null && headB == null) return headA;
        if (headA == null || headB == null) return null;

        ListNode la = headA;
        ListNode lb = headB;

        while (la != lb) {
            la = la == null ? headB : la.next;
            lb = lb == null ? headA : lb.next;
        }
        return la;
    }
}

参考文献

集合，双指针等3种解决方式，后两种击败了100%的用户

淡淡的扯淡的评论

展开全文 >>

删除中间节点

实现一种算法，删除单向链表中间的某个节点 (即不是第一个或最后一个节点)，假定你只能访问该节点。

示例：

1
2
3
4
5
6
7
输入：单向链表a->b->c->d->e->f中的节点c
结果：不返回任何数据，但该链表变为a->b->d->e->f
通过次数43,038提交次数50,461

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/delete-middle-node-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

展开全文 >>

返回倒数第k个节点 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。

注意：本题相对原题稍作改动

示例：

输入： 1->2->3->4->5 和 k = 2
输出： 4
说明：

给定的 k 保证是有效的。

通过次数41,066提交次数52,575

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/kth-node-from-end-of-list-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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int kthToLast(ListNode head, int k) {
        if (head == null) return -1;
        ListNode slow = head;
        ListNode fast = head;

        int count = 0;
        while (fast != null) {
            fast = fast.next;
            if (count - k >= 0) {
                slow = slow.next;
            }
            count++;
        }

        return k <= count ? slow.val : -1;
    }
}

展开全文 >>

移除重复节点 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。

示例1:

 输入：[1, 2, 3, 3, 2, 1]
 输出：[1, 2, 3]
示例2:

 输入：[1, 1, 1, 1, 2]
 输出：[1, 2]
提示：

链表长度在[0, 20000]范围内。
链表元素在[0, 20000]范围内。
进阶：

如果不得使用临时缓冲区，该怎么解决？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-duplicate-node-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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeDuplicateNodes(ListNode head) {
        if (head == null) return head;

        Set<Integer> set = new HashSet<>();
        ListNode cur = head;
        ListNode pre = head;
        while (cur != null) {

            if (set.contains(cur.val)) {
                pre.next = cur.next;
                cur = pre.next;
            } else {
                pre = cur;
                set.add(cur.val);
                cur = cur.next;
            }
        }
        return head;
    }
}

进阶只能暴力O(N*N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public ListNode removeDuplicateNodes(ListNode head) {
        ListNode ob = head;
        while (ob != null) {
            ListNode oc = ob;
            while (oc.next != null) {
                if (oc.next.val == ob.val) {
                    oc.next = oc.next.next;
                } else {
                    oc = oc.next;
                }
            }
            ob = ob.next;
        }
        return head;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/remove-duplicate-node-lcci/solution/yi-chu-zhong-fu-jie-dian-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

字符串轮转 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
字符串轮转。给定两个字符串s1和s2，请编写代码检查s2是否为s1旋转而成（比如，waterbottle是erbottlewat旋转后的字符串）。

示例1:

 输入：s1 = "waterbottle", s2 = "erbottlewat"
 输出：True
示例2:

 输入：s1 = "aa", s2 = "aba"
 输出：False
提示：

字符串长度在[0, 100000]范围内。
说明:

你能只调用一次检查子串的方法吗？
通过次数18,834提交次数34,434

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/string-rotation-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean isFlipedString(String s1, String s2) {
        if (s1 == null && s2 == null) return true;
        if (s1 == null || s2 == null || s1.length() != s2.length()) return false;
        if (s1.equals(s2)) return true;
        int s1Len = s1.length();

        for (int i = 0; i < s1.length(); i++) {
            if (s1.charAt(i) == s2.charAt(0)) {                                 //找到入口点
                int index = i;
                for (int j = 0; j < s2.length(); j++) {                         //从入口点向后找
                    if (s2.charAt(j) == s1.charAt(index % s1Len)) {             //利用循环链表的方法超过坐标从0开始
                        index++;                                                //每匹配一个就将index后移一个
                    }
                }
                if (index - i == s1Len) return true;                            //如果完全匹配走过的路应该是s1的字符串长度
            }
        }
        return false;
    }
}

先判断长度是否相同，不相同返回false，其次拼接两个s2，则如果是由s1旋转而成，则拼接后的s一定包含s1.

1
2
3
4
5
6
7
8
9
class Solution {
    public boolean isFlipedString(String s1, String s2) {
            if(s1.length() != s2.length()) {
            return false;
        }
        String s = s2 + s2;
        return s.contains(s1);
    }
}

参考文献

作者：bobby996 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

字符串压缩 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短，则返回原先的字符串。你可以假设字符串中只包含大小写英文字母（a至z）。

示例1:

 输入："aabcccccaaa"
 输出："a2b1c5a3"
示例2:

 输入："abbccd"
 输出："abbccd"
 解释："abbccd"压缩后为"a1b2c2d1"，比原字符串长度更长。
提示：

字符串长度在[0, 50000]范围内。
通过次数50,601提交次数106,734

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/compress-string-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 {
    public String compressString(String S) {
        if (S == null || S.length() == 0) return S;

        char[] arr = S.toCharArray();
        StringBuilder bd = new StringBuilder();

        int count = 1;
        char last = arr[0];

        bd.append(last);

        for (int i = 1; i < arr.length; i++) {
            if (arr[i] == last) {
                count++;
            } else {
                bd.append(count);
                last = arr[i];
                bd.append(last);
                count = 1;
            }
        }
        bd.append(count);                       //最后一个字符的数字没有添加上

        return bd.length() >= arr.length ? S : bd.toString();
    }
}

展开全文 >>

回文排列 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
给定一个字符串，编写一个函数判定其是否为某个回文串的排列之一。

回文串是指正反两个方向都一样的单词或短语。排列是指字母的重新排列。

回文串不一定是字典当中的单词。


示例1：

输入："tactcoa"
输出：true（排列有"tacocat"、"atcocta"，等等）
 

通过次数23,286提交次数42,670

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

回文串可以是中间一个字母的数量只有一个或者每个字母的数量至少有两个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean canPermutePalindrome(String s) {
        if (s == null || s.length() == 0) return true;
        Map<Character, Integer> map = new HashMap<>();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        int count = 0;
        for (Map.Entry entry : map.entrySet()) {
            if (((Integer) entry.getValue() & 1) == 1) count++;
        }

        return count <= 1;
    }
}

展开全文 >>

URL化 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
URL化。编写一种方法，将字符串中的空格全部替换为%20。假定该字符串尾部有足够的空间存放新增字符，并且知道字符串的“真实”长度。（注：用Java实现的话，请使用字符数组实现，以便直接在数组上操作。）

示例 1：

输入："Mr John Smith    ", 13
输出："Mr%20John%20Smith"
示例 2：

输入："               ", 5
输出："%20%20%20%20%20"
 
提示：

字符串长度在 [0, 500000] 范围内。
通过次数24,678提交次数42,113

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/string-to-url-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public String replaceSpaces(String S, int length) {
        if (S == null) return "";
        char[] arr = S.toCharArray();

        int index = arr.length - 1;
        for (int i = length - 1; i >= 0; i--) {
            if (arr[i] != ' ') {
                arr[index--] = arr[i];
            } else {
                arr[index--] = '0';
                arr[index--] = '2';
                arr[index--] = '%';
            }
        }
        index++;
        String s = new String(arr);
        return s.substring(index, s.length());
    }
}

展开全文 >>

验证括号是否匹配

验证括号是否匹配

1
2
3
4
5
6
7
8
9
10
11
class Solution{
    public boolean isValid(String thesis) {
        int count = 0;
        for (int i = 0; i < thesis.length(); i++) {
            if (thesis.charAt(i) == '(') count++;
            else count--;
            if (count < 0) return false;
        }
        return count == 0;
    }
}

展开全文 >>

括号 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
括号。设计一种算法，打印n对括号的所有合法的（例如，开闭一一对应）组合。

说明：解集不能包含重复的子集。

例如，给出 n = 3，生成结果为：

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]
通过次数12,382提交次数15,243

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

回溯

  1. 如果左括号的数量小于n，可以继续添加左括号
  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
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public List<String> generateParenthesis(int n) {
        if (n == 0) return new ArrayList<>();
        Set<String> set = new HashSet<>();

        backtrack(n * 2, new StringBuilder(), set, 0, 0);

        return new ArrayList<>(set);
    }

    public void backtrack(int n, StringBuilder bd, Set<String> set, int leftNum, int rightNum) {
        if (bd.length() == n) {
            String thesis = bd.toString();
            if (isValid(thesis)) set.add(thesis);
            return;
        }
        if (leftNum < n / 2) {
            bd.append("(");
            backtrack(n, bd, set, leftNum + 1, rightNum);
            bd.deleteCharAt(bd.length() - 1);
        }
        if (rightNum < leftNum) {
            bd.append(")");
            backtrack(n, bd, set, leftNum, rightNum + 1);
            bd.deleteCharAt(bd.length() - 1);
        }
    }
    public boolean isValid(String thesis) {
        int count = 0;
        for (int i = 0; i < thesis.length(); i++) {
            if (thesis.charAt(i) == '(') count++;
            else count--;
            if (count < 0) return false;
        }
        return count == 0;
    }
}

展开全文 >>

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>希望有一天被领走