力扣刷题记录（Java）（三）

括号生成

题目链接：括号生成

个人版本一（暴力全排列和筛选）

class Solution {
    public List<String> generateParenthesis(int n) {
        int len = 2*n;
        List<String> list = new ArrayList<>();
        Stack<String> stack = new Stack<>();
        boolean[] used = new boolean[len];
        List<String> arr = new ArrayList<>();
        for(int i=0 ; i<n ; i++) {
            arr.add("(");
        }
        for(int i=0 ; i<n ; i++) {
            arr.add(")");
        }
        dfs(arr, 0, len, stack, list, used, 0);

        return new ArrayList<>(list);
    }
    // 全排列基础上去除括号不匹配情况以及重复的情况
    public void dfs(List<String> arr, int depth, int len, Stack<String> stack, List<String> list, boolean[] used, int count){
        if(depth == len){
            list.add(String.join("", stack));
        }
        String nowStr = "";
        for(int i=0 ; i<len ; i++){
            // 当前元素已经被使用
            if(used[i]) continue;
            // 首次进入记录符号
            if(i == depth && "".equals(nowStr)){
                nowStr = arr.get(i);
            }else{
                 /**
                 *  这里主要是处理重复，对于上述产生的固定组合：(())
                 *  产生重复的主要原因是，某一层的元素，从一个元素到下一个元素的时候，这
                 *  两个元素相等，而移动前的位置又会被它的下一层填补，移动前和移动后的位置
                 *  上的元素都是相同的，这样按层数组合字符串的时候会出现重复，因为如果将这两层的元素
                 *  固定，其他层的变化可以是相同的
                  */
                if(nowStr.equals(arr.get(i))){
                    continue;
                }else{
                    nowStr = arr.get(i);
                }
            }
//            if (i > depth  && arr.get(i).equals(arr.get(i-1))) continue;

            String ele = arr.get(i);
            // 通过count统计是否匹配，如果是匹配的情况下，count是大于等于0
            if(ele.equals("(")){
                count++;
            }else{
                count--;
            }
            if(count < 0) continue;
            // 向栈中添加要组合的元素
            stack.push(ele);
            used[i]  = true;
            dfs(arr, depth+1, len, stack, list, used, count);
            // 弹出元素，让下一个元素进行组合
            ele = stack.pop();
            if(ele.equals("(")){
                count--;
            }else{
                count++;
            }
            used[i] = false;
        }
    }
}
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

官方版本一（暴力法）

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> combinations = new ArrayList<String>();
        generateAll(new char[2 * n], 0, combinations);
        return combinations;
    }

    public void generateAll(char[] current, int pos, List<String> result) {
        if (pos == current.length) {
            if (valid(current)) {
                result.add(new String(current));
            }
        } else {
            current[pos] = '(';
            generateAll(current, pos + 1, result);
            current[pos] = ')';
            generateAll(current, pos + 1, result);
        }
    }

    public boolean valid(char[] current) {
        int balance = 0;
        for (char c: current) {
            if (c == '(') {
                ++balance;
            } else {
                --balance;
            }
            if (balance < 0) {
                return false;
            }
        }
        return balance == 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
36

官方版本二（回溯法）

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<String>();
        backtrack(ans, new StringBuilder(), 0, 0, n);
        return ans;
    }

    public void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max) {
        if (cur.length() == max * 2) {
            ans.add(cur.toString());
            return;
        }
        if (open < max) {
            cur.append('(');
            backtrack(ans, cur, open + 1, close, max);
            cur.deleteCharAt(cur.length() - 1);
        }
        if (close < open) {
            cur.append(')');
            backtrack(ans, cur, open, close + 1, max);
            cur.deleteCharAt(cur.length() - 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
25

官方版本三（按括号序列的长度递归）

class Solution {
    ArrayList[] cache = new ArrayList[100];

    public List<String> generate(int n) {
        if (cache[n] != null) {
            return cache[n];
        }
        ArrayList<String> ans = new ArrayList<String>();
        if (n == 0) {
            ans.add("");
        } else {
            for (int c = 0; c < n; ++c) {
                for (String left: generate(c)) {
                    for (String right: generate(n - 1 - c)) {
                        ans.add("(" + left + ")" + right);
                    }
                }
            }
        }
        cache[n] = ans;
        return ans;
    }

    public List<String> generateParenthesis(int n) {
        return generate(n);
    }
}

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

其他版本一（按括号数量匹配回溯）

// 在匹配过程中，有如下规律：左括号数量总是小于等于右括号数量
class Solution {
        List<String> res = new ArrayList<>();
        public List<String> generateParenthesis(int n) {
            if(n <= 0){
                return res;
            }
            getParenthesis("",n,n);
            return res;
        }

        private void getParenthesis(String str,int left, int right) {
            if(left == 0 && right == 0 ){
                res.add(str);
                return;
            }
            if(left == right){
                //剩余左右括号数相等，下一个只能用左括号
                getParenthesis(str+"(",left-1,right);
            }else if(left < right){
                //剩余左括号小于右括号，下一个可以用左括号也可以用右括号
                if(left > 0){
                    getParenthesis(str+"(",left-1,right);
                }
                getParenthesis(str+")",left,right-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
25
26
27
28

其他版本二（整体拼接）

class Solution {
    public static List<String> generateParenthesis(int n){
        /**
         * 
         * 将()进行组装，n=3是,()()()、 (())()、()(())这三个
         * 实际可以看做()在()()不同位置拼接而来，例如在前边拼接就是()()()
         * 起始位置继续往后移动异步就是(())()，然后再移动异步就是()(())
         * 最后在移动又变成()()()，所以需要去重
         */
        if (n == 1){
            return Arrays.asList("()");
        }
        HashSet<String> set = new HashSet<>();
        for (String str : generateParenthesis(n - 1)){
            for (int i = 0; i <= str.length()/2; i++) {
                set.add(str.substring(0,i) + "()" + str.substring(i,str.length()));
            }
        }
        return new ArrayList<>(set);

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

合并K个升序链表

题目链接：合并K个升序链表

个人版本一（顺序合并）

/**
 * 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 mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length == 0) {
            return null;
        }
        if(lists.length == 1){
            return lists[0];
        }
        int len = lists.length;
        ListNode listNode = lists[0];
        for(int i=1 ; i < len ; i++){
            listNode = mergeTwoLists(listNode, lists[i]);
        }
        return listNode;
    }
    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode l1 = list1, l2 = list2, tmpNode;
        ListNode head = new ListNode(), tail = head;
        while (l1 != null && l2 != null){
            if(l1.val <= l2.val){
                tmpNode = new ListNode(l1.val);
                tail.next = tmpNode;
                l1 = l1.next;
            }else if(l1.val > l2.val){
                tmpNode = new ListNode(l2.val);
                tail.next = tmpNode;
                l2 = l2.next;
            }
            tail = tail.next;
        }
        if(l1 != null){
            tail.next = l1;
        }
        if(l2 != null){
            tail.next = l2;
        }
        return head.next;
    }
}
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 ListNode mergeKLists(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }

    public ListNode merge(ListNode[] lists, int l, int r) {
        if (l == r) {
            return lists[l];
        }
        if (l > r) {
            return null;
        }
        int mid = (l + r) >> 1; // 这里就是除以2
        // 切分结果类似于归并排序，将元素切分成2个2个组合，组合排序结束，递归回到上层就变成4个4个之间组合，以此类推
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }
        public  ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode l1 = list1, l2 = list2, tmpNode;
        ListNode head = new ListNode(), tail = head;
        while (l1 != null && l2 != null){
            if(l1.val <= l2.val){
                tmpNode = new ListNode(l1.val);
                tail.next = tmpNode;
                l1 = l1.next;
            }else if(l1.val > l2.val){
                tmpNode = new ListNode(l2.val);
                tail.next = tmpNode;
                l2 = l2.next;
            }
            tail = tail.next;
        }
        if(l1 != null){
            tail.next = l1;
        }
        if(l2 != null){
            tail.next = l2;
        }
        return head.next;
    }

}


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

官方版本二（优先队列合并）

class Solution {
	// 实现Comparable类用以后续多个Status的合并
	// 算法是将维护每个链表中没有被合并的最前边的元素
    class Status implements Comparable<Status> {
        int val;
        ListNode ptr;

        Status(int val, ListNode ptr) {
            this.val = val;
            this.ptr = ptr;
        }
        
        public int compareTo(Status status2) {
            return this.val - status2.val;
        }
    }

    PriorityQueue<Status> queue = new PriorityQueue<Status>();

    public ListNode mergeKLists(ListNode[] lists) {
    // 开始的时候，每个链表中没有被合并的就是头结点
        for (ListNode node: lists) {
            if (node != null) {
            // 添加节点到优先队列中，优先队列会自动调用status的比较方法，在后续获取队列元素时总是返回节点上数值最小的节点相关的类
                queue.offer(new Status(node.val, node));
            }
        }
        ListNode head = new ListNode(0);
        ListNode tail = head;
        while (!queue.isEmpty()) {
        // 拿到队列中值最小的类
            Status f = queue.poll();
            tail.next = f.ptr;
            tail = tail.next;
            if (f.ptr.next != null) {
                queue.offer(new Status(f.ptr.next.val, f.ptr.next));
            }
        }
        return head.next;
    }
}
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

两两交换链表中的节点

题目链接：两两交换链表中的节点

个人版本一

/**
 * 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 swapPairs(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        // 总共维护三个结点，前一个几点，前前个节点，下一个节点，其中下一个节点就是要被调到前边来的
        int count = 1;
        ListNode preNode = head, tail = head.next, nextNode = tail, newHead, prepreNode;
        preNode.next = tail.next;
        nextNode.next = preNode;
        newHead = nextNode;
        tail = preNode.next;
        prepreNode = preNode;
        while (tail != null && tail.next != null){
            if(count == 1){
                preNode = tail;
                nextNode = tail.next;
            }else{
                preNode.next = nextNode.next;
                nextNode.next = preNode;
                prepreNode.next = nextNode;
                prepreNode = preNode;
                tail = preNode.next;
            }
            count = (++count)%2;
        }
        return newHead;
    }
}

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

官方版本一（递归）

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;
    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13

官方版本二（迭代）

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

K 个一组翻转链表

题目链接：K 个一组翻转链表

个人版本一

/**
 * 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 reverseKGroup(ListNode head, int k) {
        ListNode listNode = head;
        int count = 0, i=0;
        ListNode[] listNodes = new ListNode[5000];
        if(head.next == null){
            return head;
        }
        while (listNode != null){
            listNodes[i] = listNode;
            listNode = listNode.next;
            listNodes[i].next = null;
            i++;
            count++;
        }
        i = k-1;
        ListNode h = new ListNode(), t = h;
        while (true){
            int j = i;
            while (j > i-k){
                t.next = listNodes[j];
                j--;
                t = t.next;
            }
            if(count-i-1 < k) {
                i++;
                while (i<count){
                    t.next = listNodes[i];
                    t = t.next;
                    i++;
                }
                break;
            };
            i += k;
        }
        return h.next;
    }

}
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

个人版本二（递归）

/**
 * 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 {
    ListNode headNode = null;
    ListNode h = null;
    public ListNode reverseKGroup(ListNode head, int k) {
        int len = 0;
        if(head.next == null||k == 1){
            return head;
        }
        ListNode tmpNode = head;
        while (tmpNode != null){
            len++;
            tmpNode = tmpNode.next;
        }
        ListNode tail = null;
        // 从0开始以每k个元素为一组开始
        for( int i=0 ; i<len/k ; i++){
            // 返回该分组的最后一个元素
            tmpNode = reverseList(head, k, 0);
            head = tmpNode.next;
            if(tail != null){
                // tail是上一个分组的末尾,h是下一个分组的开始，二者需要关联
                tail.next = h;
            }
            tail = tmpNode;
        }
        return headNode;
    }
    public ListNode reverseList(ListNode head, int k, int count){
        count++;
        // 当count是k的倍数，说明已经到最后一个了
        if(count%k == 0){
            return head;
        }
        ListNode nextNode = head.next;
        // 开始递归，递归的基本子集是两个节点的交换，再回到上层是两个整体的交换，以此类推
        // 递归是1个元素和一个集合这整体的交换，例如[1,2,3] k=3，
        // 递归到最后一层是2和3节点的交换，交换完毕以后返回上层是1和(3,2)交换
        // 所以递归返回的是集合的最后一个节点，例如(3,2)集合结果返回2节点，这样1就能连接到2后边实现交换
        ListNode tmpNode = reverseList(nextNode, k, count);
        head.next = tmpNode.next;
        tmpNode.next = head;
        if(count == k-1) {
            if(headNode == null){
                // 记录头部节点用于返回
                headNode = tmpNode;
            }
            // 记录每个组的开始节点，用于与上一个组进行连接
            h = tmpNode;
        };
        return head;
    }

}
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

官方版本一（模拟）

/**
 * 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 reverseKGroup(ListNode head, int k) {
        ListNode hair = new ListNode(0);
        hair.next = head;
        ListNode pre = hair;

        while (head != null) {
            ListNode tail = pre;
            // 查看剩余部分长度是否大于等于 k
            for (int i = 0; i < k; ++i) {
                tail = tail.next;
                if (tail == null) {
                    return hair.next;
                }
            }
            ListNode nex = tail.next;
            ListNode[] reverse = myReverse(head, tail);
            head = reverse[0];
            tail = reverse[1];
            // 把子链表重新接回原链表
            pre.next = head;
            tail.next = nex;
            pre = tail;
            head = tail.next;
        }

        return hair.next;
    }

    public ListNode[] myReverse(ListNode head, ListNode tail) {
        ListNode prev = tail.next;
        ListNode p = head;
        while (prev != tail) {
            ListNode nex = p.next;
            p.next = prev;
            prev = p;
            p = nex;
        }
        return new ListNode[]{tail, head};
    }
}


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

其他版本一

/**
 * 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 static ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(-1, head), prev = dummy;
        while (true) {
            // 检查剩余节点是否有k个，不足则返回
            ListNode last = prev;
            for (int i = 0; i < k; i++) {
                last = last.next;
                if (last == null) {
                    return dummy.next;
                }
            }

            // 翻转k个节点,需要翻转k-1次
            ListNode curr = prev.next, next;
            for (int i = 0; i < k - 1; i++) {
                next = curr.next;
                curr.next = next.next;
                next.next = prev.next;
                prev.next = next;
            }
            prev = curr;
        }
    }
}


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

删除有序数组中的重复项

删除有序数组中的重复项

个人版本一（模拟）

class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums.length == 1){
            return 1;
        }
        int len = nums.length;
        int i=0, start = 0;
        while (start < len-1){
            while (i < len-1 && nums[i] == nums[i+1]){
                i++;
            }
            // 移动的距离
            int count = i-start;
            if(count == 0){
                start++;
                i++;
                continue;
            };
            for(int j=i+1 ; j<len ; j++){
                nums[j-count] = nums[j];
            }
            // 删除重复元素
            len -= count;
            start = start+1;
            i = start;
        }
        return len;
    }
}
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

个人版本二

class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums.length == 1){
            return 1;
        }
        int len = nums.length;
        int i = 1, start = 0;
        while (i < len){
            while (i < len && nums[i] == nums[i-1]){
                i++;
            }
            if(i == len){
                break;
            }
            // 无重复
            if(i-start == 1){
                start++;
                i++;
                continue;
            };
            start++;
            nums[start] = nums[i];
            i++;
        }
        return start+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
25
26
27

个人版本三（版本二再优化)

class Solution {
public int removeDuplicates(int[] nums) {
    if(nums == null || nums.length == 0) return 0;
    int p = 0;
    int q = 1;
    while(q < nums.length){
        if(nums[p] != nums[q]){
            if(q - p > 1){
                nums[p + 1] = nums[q];
            }
            p++;
        }
        q++;
    }
    return p + 1;
}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

官方版本一（双指针）

class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int fast = 1, slow = 1;
        while (fast < n) {
            if (nums[fast] != nums[fast - 1]) {
                nums[slow] = nums[fast];
                ++slow;
            }
            ++fast;
        }
        return slow;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

移除元素

题目链接：移除元素

个人版本一（双指针）

class Solution {
    public int removeElement(int[] nums, int val) {
        int len = nums.length;
        int next = 0, start = 0;
        while (next < len){
            if(nums[next] != val){
                nums[start] = nums[next];
                start++;
            }
            next++;
        }
        return start;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

个人版本二（再优化）

class Solution {
    public int removeElement(int[] nums, int val) {
        int len = nums.length;
        int left = 0;
        for (int i= 0; i< len; i++) {
            if (nums[i] != val) {
                nums[left] = nums[i];
                left++;
            }
        }
        return left;
    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

官方版本一（个人版本二再优化）

// 上述两个版本中，例如对[1,2,3,4] val=1时，都会让后续的元素往回赋值，也就是移动
// 实际上对于题目要去是不按顺序，那么这里就可以在左边等于val时，把最后的元素移动到前边，除此以外只需要指针移动
// 例如上述例子,第一个就是1，那么这个时候4移动到1位置，也就是[4,2,3]
class Solution {
    public int removeElement(int[] nums, int val) {
        int left = 0;
        int right = nums.length;
        while (left < right) {
            if (nums[left] == val) {
                nums[left] = nums[right - 1];
                right--;
            } else {
                left++;
            }
        }
        return left;
    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

实现 strStr()

题目链接： 实现 strStr()

个人版本一

class Solution {
    public int strStr(String haystack, String needle) {
        int hLen = haystack.length(), nLen = needle.length();
        int start = -1, i = 0;
        while (i < hLen && hLen-i >= nLen){
            if(haystack.charAt(i) == needle.charAt(0)){
                String tmpStr = haystack.substring(i, i+nLen);
                if(tmpStr.equals(needle)){
                    start = i;
                    break;
                }
            }
            i++;
        }
        return start;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

官方版本一（暴力匹配）

class Solution {
    public int strStr(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        for (int i = 0; i + m <= n; i++) {
            boolean flag = true;
            for (int j = 0; j < m; j++) {
                if (haystack.charAt(i + j) != needle.charAt(j)) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                return i;
            }
        }
        return -1;
    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

官方版本二（Knuth-Morris-Pratt 算法）

class Solution {
    public int strStr(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        if (m == 0) {
            return 0;
        }
        int[] pi = new int[m];
        for (int i = 1, j = 0; i < m; i++) {
            while (j > 0 && needle.charAt(i) != needle.charAt(j)) {
                j = pi[j - 1];
            }
            if (needle.charAt(i) == needle.charAt(j)) {
                j++;
            }
            pi[i] = j;
        }
        for (int i = 0, j = 0; i < n; i++) {
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = pi[j - 1];
            }
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            if (j == m) {
                return i - m + 1;
            }
        }
        return -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
25
26
27
28
29
30
31
32

其他版本一（基于窗口滑动的算法）

class Solution {
    /**
     * 基于窗口滑动的算法
     * 

     * 时间复杂度：O(m*n)
     * 空间复杂度：O(1)
     * 注：n为haystack的长度，m为needle的长度
     */
    public int strStr(String haystack, String needle) {
        int m = needle.length();
        // 当 needle 是空字符串时我们应当返回 0
        if (m == 0) {
            return 0;
        }
        int n = haystack.length();
        if (n < m) {
            return -1;
        }
        int i = 0;
        int j = 0;
        while (i < n - m + 1) {
            // 找到首字母相等
            while (i < n && haystack.charAt(i) != needle.charAt(j)) {
                i++;
            }
            if (i == n) {// 没有首字母相等的
                return -1;
            }
            // 遍历后续字符，判断是否相等
            i++;
            j++;
            while (i < n && j < m && haystack.charAt(i) == needle.charAt(j)) {
                i++;
                j++;
            }
            if (j == m) {// 找到
                return i - j;
            } else {// 未找到
                i -= j - 1;
                j = 0;
            }
        }
        return -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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

其他版本二（Knuth-Morris-Pratt 算法）

详细解析

// 方法一
class Solution {
    public void getNext(int[] next, String s){
        int j = -1;
        next[0] = j;
        // 前缀表都是统一减1的，因为下边的逻辑，都是使用j+1的位置去处理的，所以j直接回到上一个位置
        // 那么j+1就能拿到想要比较的位置
        // 例如haystack = aabaabaaf   needle = aabaaf
        // 当haystack中的b和needle中的f不匹配的时候，j就根据next[j]，在neddle中拿到了下标为1的位置，也就是第二个a
        // 那么比较的时候，j+1就拿到needle的b，该b跟haystack中第二个b比较（haystack上次就是比较到这里.
        //发现b和f不相等），而不是每次从头开始比较，就是当b和f不相等，下一次比较又从neddle第一个字母开始
        for (int i = 1; i<s.length(); i++){
            while(j>=0 && s.charAt(i) != s.charAt(j+1)){
                j=next[j];
            }

            if(s.charAt(i)==s.charAt(j+1)){
                j++;
            }
            next[i] = j;
        }
    }
    public int strStr(String haystack, String needle) {
        if(needle.length()==0){
            return 0;
        }

        int[] next = new int[needle.length()];
        getNext(next, needle);
        int j = -1;
        for(int i = 0; i<haystack.length();i++){
            while(j>=0 && haystack.charAt(i) != needle.charAt(j+1)){
                j = next[j];
            }
            if(haystack.charAt(i)==needle.charAt(j+1)){
                j++;
            }
            if(j==needle.length()-1){
                return (i-needle.length()+1);
            }
        }

        return -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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45