Leetcode刷题记录（日更）

Leetcode
  • 最近开始慢慢刷Leetcode题目了，为了督促自己，挖个坑记录下，顺便分享一下答案及思路。

“对于程序员而言，刷了Leetcode不一定能拿offer，但是不刷肯定拿不到offer。”

Lusion鲁迅

Lusion

Update：2018年11月13日16:29:32

读前须知：

  • 由于是按tag刷的，由简单->困难，故不是按照题号刷的。如果有需要查找题目，请直接Command-F或Ctrl+F搜索对应题号或关键字即可。
  • 解法并不唯一。本篇只是个人的拙见，也并不意味着这是最优解 (ಥ﹏ಥ)
  • 如果有更好的想法欢迎向我的Github砸Pull requests！感激不尽 (๑˙―˙๑)
  • 想联系我请戳邮箱，谢绝广告和培训机构，蟹蟹 (ง •̀_•́)ง
724. 寻找数组的中心索引 Find Pivot Indexex724.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int pivotIndex(int[] nums) {
    int sum = 0;
    for (int num : nums)
        sum += num;
    int left = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i > 0)
            left += nums[i - 1];
        int right = sum - nums[i] - left;
        if (left == right) {
            return i;
        }
    }
    return -1;
}
050. Pow(x, n)ex050.java
1
2
3
4
5
6
7
8
public double myPow(double x, int n) {
    double result = 1.0;
    for (int i = n; i != 0; i /= 2) {
        if (i % 2 != 0) result *= x;
        x *= x;
    }
    return n < 0 ? 1 / result : result;
}
035. 搜索插入位置 Search Insert Positionex035.java
1
2
3
4
5
6
7
8
9
10
public int searchInsert(int[] nums, int target) {
    int lo = 0, hi = nums.length - 1;
    while (lo <= hi) {
        int mid = (lo + hi) >>> 1;
        if (nums[mid] > target) hi = mid - 1;
        else if (nums[mid] < target) lo = mid + 1;
        else return mid;
    }
    return lo;
}
744. 寻找比目标字母大的最小字母 Find Smallest Letter Greater Than Targetex744.java
1
2
3
4
5
6
7
8
9
10
public char nextGreatestLetter(char[] letters, char target) {
    int lo = 0, hi = letters.length - 1;
    if (target >= letters[hi]) return letters[0];
    while (lo < hi) {
        int mid = (lo + hi) >>> 1;
        if (letters[mid] <= target) lo = mid + 1;
        else hi = mid;
    }
    return letters[lo];
}
852. 山脉数组的峰顶索引 Peak Index in a Mountain Arrayex852.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int peakIndexInMountainArray(int[] A) {
    int lo = 1, hi = A.length - 2;
    while (lo <= hi) {
        int mid = (lo + hi) >>> 1;
        if (A[mid] <= A[mid - 1]) hi = mid - 1;
        else if (A[mid] <= A[mid + 1]) lo = mid + 1;
        else return mid;
    }
    return -1;
}

public int peakIndexInMountainArray2(int[] A) {
    for (int i = 1; i < A.length; i++)
        if (A[i - 1] > A[i])
            return i - 1;
    return -1;
}
029. 两数相除 Divide Two Integersex029.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//如果被除数大于或等于除数，则进行如下循环，定义变量t等于除数，定义计数p
//当t的两倍小于等于被除数时，进行如下循环，t扩大一倍，p扩大一倍，然后更新res和m
public int divide(int dividend, int divisor) {
    if (divisor == 0 || (dividend == Integer.MIN_VALUE && divisor == -1))
        return Integer.MAX_VALUE;
    long m = Math.abs(dividend), n = Math.abs(divisor), res = 0;
    int sign = (dividend < 0) ^ (divisor < 0) ? -1 : 1;
    if (n == 1) return (int) (sign > 0 ? m : -m);
    while (m >= n) {
        long t = n, p = 1;
        while (m >= (t << 1)) {
            t <<= 1;
            p <<= 1;
        }
        res += p;
        m -= t;
    }
    return (int) (sign > 0 ? res : -res);
}
658. 找到K个最接近的元素 Find K Closest Elementsex658.java
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
public List<Integer> findClosestElements(int[] arr, int k, int x) {
    List<Integer> list = new ArrayList<>(k);
    int lo = 0, hi = arr.length - k - 1;
    while (lo <= hi) {
        int mid = (lo + hi) >>> 1;
        if (Math.abs(x - arr[mid]) > Math.abs(x - arr[mid + k]))
            lo = mid + 1;
        else hi = mid - 1;
    }
    for (int i = 0; i < k; i++)
        list.add(arr[lo + i]);
    return list;
}

//非二分法，采用首尾逼近
public List<Integer> findClosestElements2(int[] arr, int k, int x) {
    List<Integer> list = new ArrayList<>(k);
    for (int i : arr) list.add(i);
    while (list.size() > k) {
        if (x - list.get(0) <= list.get(list.size() - 1) - x)
            list.remove(list.size() - 1);
        else list.remove(list.get(0));
    }
    return list;
}
034. 在排序数组中查找元素的第一个和最后一个位置 Find First and Last Position of Element in Sorted Array Arrayex034.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int[] searchRange(int[] nums, int target) {
    int[] range = new int[]{-1, -1};
    if (nums.length < 1) return range;
    int lo = 0, hi = nums.length - 1;
    while (lo < hi) {
        int mid = (lo + hi) >>> 1;
        if (nums[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    if (nums[hi] != target) return range;
    range[0] = hi;
    hi = nums.length - 1;
    while (lo <= hi) {
        int mid = (lo + hi) >>> 1;
        if (nums[mid] > target) hi = mid - 1;
        else lo = mid + 1;
    }
    range[1] = lo - 1;
    return range;
}
153. 寻找旋转排序数组中的最小值 Find Minimum in Rotated Sorted Arrayex153.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int findMin(int[] nums) {
    for (int i = 1; i < nums.length; i++)
        if (nums[i] < nums[i - 1]) return nums[i];
    return nums[0];
}

public int findMin2(int[] nums) {
    int lo = 0, hi = nums.length - 1;
    if (nums[lo] <= nums[hi]) return nums[lo];
    while (lo != hi - 1) {
        int mid = (lo + hi) >>> 1;
        if (nums[mid] > nums[lo]) lo = mid;
        else hi = mid;
    }
    return nums[lo] < nums[hi] ? nums[lo] : nums[hi];
}
162. 寻找峰值 Find Peak Elementex162.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int findPeakElement(int[] nums) {
    int lo = 0, hi = nums.length - 1;
    while (lo < hi) {
        int mid = (lo + hi) >>> 1;
        if (nums[mid] < nums[mid + 1]) lo = mid + 1;
        else hi = mid;
    }
    return hi;
}

public int findPeakElement2(int[] nums) {
    for (int i = 1; i < nums.length; i++)
        if (nums[i] < nums[i - 1]) return i - 1;
    return nums.length - 1;
}
278. 第一个错误的版本 First Bad Versionex278.java
1
2
3
4
5
6
7
8
9
public int firstBadVersion(int n) {
    int lo = 1, hi = n;
    while (lo < hi) {
        int mid = (lo + hi) >>> 1;
        if (isBadVersion(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}
033. 搜索旋转排序数组 Search in Rotated Sorted Arrayex033.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int search(int[] nums, int target) {
    int lo = 0, hi = nums.length - 1;
    while (lo <= hi) {
        int mid = (lo + hi) >>> 1;
        if (nums[mid] == target) return mid;
        else if (nums[mid] > nums[lo]) {
            //左边有序 lo...mid
            if (nums[mid] > target && target >= nums[lo]) hi = mid - 1;
            else lo = mid + 1;
        } else if (nums[mid] < nums[hi]) {
            //右边有序 mid...hi
            if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return -1;
}
374. 猜数字大小 Guess Number Higher or Lowerex374.java
1
2
3
4
5
6
7
8
9
10
11
public int guessNumber(int n) {
    int lo = 0, hi = n;
    while (lo <= hi) {
        int mid = (lo + hi) >>> 1;
        int result = guess(mid);
        if (result == 0) return mid;
        else if (result < 0) hi = mid - 1;
        else lo = mid + 1;
    }
    return -1;
}
069. x 的平方根 Sqrt(x)ex069.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int mySqrt(int x) {
    if (x <= 1) return x;
    //right = x
    int left = 0, right = x / 2 + 1;
    while (left < right) {
        int mid = (left + right) >>> 1;
        if (x / mid >= mid) left = mid + 1;
        else right = mid;
    }
    return right - 1;
}

//牛顿逼近法
public int mySqrt2(int x) {
    if (x == 0) return 0;
    double last = 0;
    double res = 1;
    while (last != res) {
        last = res;
        res = (res + x / res) / 2;
    }
    return (int) res;
}
430. 扁平化多级双向链表 Flatten a Multilevel Doubly Linked Listex430.java
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
//递归1，一层一层递归
public Node flatten(Node head) {
    if (head == null) return null;
    Node curr = head;
    while (curr != null) {
        if (curr.child != null) {
            Node next = curr.next;
            Node nextLayer = flatten(curr.child);
            curr.next = nextLayer;
            nextLayer.prev = curr;
            curr.child = null;
            while (nextLayer.next != null) nextLayer = nextLayer.next;
            nextLayer.next = next;
            if (next != null) next.prev = nextLayer;
        }
        curr = curr.next;
    }
    return head;
}

//递归2，一个一个递归
public Node flatten2(Node head) {
    if (head == null) return null;
    if (head.child == null) head.next = flatten2(head.next);
    else {
        Node next = flatten2(head.next);
        Node nextLayer = flatten2(head.child);
        nextLayer.prev = head;
        head.next = nextLayer;
        head.child = null;
        while (nextLayer.next != null) nextLayer = nextLayer.next;
        nextLayer.next = next;
        if (next != null) next.prev = nextLayer;
    }
    return head;
}

//迭代解决
public Node flatten3(Node head) {
    for (Node curr = head; curr != null; curr = curr.next) {
        Node next = curr.next;
        if (curr.child != null) {
            curr.next = curr.child;
            curr.child.prev = curr;
            curr.child = null;
            Node temp = curr.next;
            while (temp.next != null) temp = temp.next;
            temp.next = next;
            if (next != null) next.prev = temp;
        }
    }
    return head;
}

class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;

    public Node() {
    }

    public Node(int _val, Node _prev, Node _next, Node _child) {
        val = _val;
        prev = _prev;
        next = _next;
        child = _child;
    }
}
061. 旋转链表 Rotate Listex061.java
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
public ListNode rotateRight(ListNode head, int k) {
    if (head == null || head.next == null) return head;
    ListNode curr = head;
    int sum = 1;
    while (curr.next != null) {
        sum++;
        curr = curr.next;
    }
    curr.next = head;
    sum = sum - k % sum;
    for (int i = 0; i < sum; i++)
        curr = curr.next;
    head = curr.next;
    curr.next = null;
    return head;
}

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}
138. 复制带随机指针的链表 Copy List with Random Pointerex138.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public RandomListNode copyRandomList(RandomListNode head) {
    RandomListNode node = new RandomListNode(-1);
    node.next = head;
    RandomListNode curr = node;
    while (head != null) {
        curr.next = new RandomListNode(head.label);
        curr.next.random = head.random == null ? null : new RandomListNode(head.random.label);
        curr = curr.next;
        head = head.next;
    }
    return node.next;
}

class RandomListNode {
    int label;
    RandomListNode next, random;

    RandomListNode(int x) {
        this.label = x;
    }
}
025. k个一组翻转链表 Reverse Nodes in k-Groupex025.java
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
//迭代解决
public ListNode reverseKGroup(ListNode head, int k) {
    ListNode dummyHead = new ListNode(0);
    dummyHead.next = head;
    ListNode pre = dummyHead;
    ListNode curr = head;
    int sum = 0;
    while (curr != null) {
        sum++;
        curr = curr.next;
    }
    while (sum >= k) {
        curr = pre.next;
        for (int i = 1; i < k; i++) {
            ListNode node = curr.next;
            curr.next = node.next;
            node.next = pre.next;
            pre.next = node;
        }
        pre = curr;
        sum -= k;
    }
    return dummyHead.next;
}

//递归解决
public ListNode reverseKGroup2(ListNode head, int k) {
    ListNode nextFirst = head;
    for (int i = 0; i < k; i++) {
        if (nextFirst == null) return head;
        nextFirst = nextFirst.next;
    }
    ListNode first = reverseList(head, nextFirst);
    head.next = reverseKGroup2(nextFirst, k);
    return first;
}

private ListNode reverseList(ListNode first, ListNode nextFirst) {
    ListNode pre = nextFirst;
    while (first != nextFirst) {
        ListNode temp = first.next;
        first.next = pre;
        pre = first;
        first = temp;
    }
    return pre;
}
019. 删除链表的倒数第N个节点 Remove Nth Node From End of Listex019.java
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
public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode slow = head;
    ListNode fast = head;
    for (int i = 0; i < n; i++)
        fast = fast.next;
    if (fast == null) return head.next;//删除第一个结点
    while (fast.next != null) {
        fast = fast.next;
        slow = slow.next;
    }
    slow.next = slow.next.next;
    return head;
}

public ListNode removeNthFromEnd2(ListNode head, int n) {
    ListNode dummyHead = new ListNode(-1);
    dummyHead.next = head;
    ListNode slow = dummyHead;
    ListNode fast = head;
    for (int i = 0; i < n; i++)
        fast = fast.next;
    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }
    slow.next = slow.next.next;
    return dummyHead.next;
}

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}
142. 环形链表 II Linked List Cycle IIex142.java
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
public ListNode detectCycle(ListNode head) {
    if (head == null || head.next == null || head.next.next == null) return null;
    ListNode slow = head.next, fast = head.next.next;
    while (slow != fast) {
        if (fast == null || fast.next == null)
            //检测到无环
            return null;
        slow = slow.next;
        fast = fast.next.next;
    }
    // 检测到有环，a指head到环起点的距离，b指环起点到相交点距离，b+c为环的周长
    // 2(a+b)=a+b+n(b+c);a=(n-1)b+nc=(n-1)(b+c)+c;
    // 意味着从起点出发走a，必然与环内循环的点相交于环的起点。
    slow = head;
    while (fast != slow) {
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}

public ListNode detectCycle2(ListNode head) {
    ListNode slow = head, fast = slow;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) break;
    }
    if (fast == null || fast.next == null) return null;
    slow = head;
    while (fast != slow) {
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}
082. 删除排序链表中的重复元素 II Remove Duplicates from Sorted List IIex082.java
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
//递归实现
public ListNode deleteDuplicates(ListNode head) {
    if (head == null || head.next == null) return head;
    if (head.val == head.next.val) {
        //如果当前结点是重复结点，则找到第一个与当前结点不同的开始递归。
        ListNode node = head.next;
        while (node != null && node.val == head.val) {
            node = node.next;
        }
        return deleteDuplicates(node);
    } else {
        //如果当前结点不是重复结点，保留当前结点，从下个结点开始递归。
        head.next = deleteDuplicates(head.next);
        return head;
    }
}

//迭代实现
public ListNode deleteDuplicates2(ListNode head) {
    ListNode dummyHead = new ListNode(-1);
    dummyHead.next = head;
    ListNode pre = dummyHead;
    ListNode curr = head;
    while (curr != null && curr.next != null) {
        if (curr.val == curr.next.val) {
            //出现重复
            while (curr.next != null && curr.val == curr.next.val)
                curr = curr.next;
            pre.next = curr.next;
            curr.next = null;
            curr = pre.next;
            continue;
        }
        curr = curr.next;
        pre = pre.next;
    }
    return dummyHead.next;
}

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}
086. 分隔链表 Partition Listex086.java
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
//不生成新链表，变化顺序为：
//1 -> 4 -> 3 -> 2 -> 5 -> 2
//1 -> 2 -> 4 -> 3 -> 5 -> 2
//1 -> 2 -> 2 -> 4 -> 3 -> 5
public ListNode partition(ListNode head, int x) {
    ListNode dummyHead = new ListNode(-1);
    dummyHead.next = head;
    ListNode pre = dummyHead;
    while (pre.next != null && pre.next.val < x) {
        pre = pre.next;
    }
    ListNode large = pre.next;
    while (large != null && large.next != null) {
        if (large.next.val >= x) {
            large = large.next;
            continue;
        }
        ListNode small = large.next;
        large.next = small.next;
        small.next = pre.next;
        pre.next = small;
        pre = pre.next;
    }
    return dummyHead.next;
}

//生成新链表（比x小的创建新链表），变化顺序为：
//Original: 1 -> 4 -> 3 -> 2 -> 5 -> 2
//New:
//Original: 4 -> 3 -> 2 -> 5 -> 2
//New:      1
//Original: 4 -> 3 -> 5 -> 2
//New:      1 -> 2
//Original: 4 -> 3 -> 5
//New:      1 -> 2 -> 2
//Original:
//New:      1 -> 2 -> 2 -> 4 -> 3 -> 5
public ListNode partition2(ListNode head, int x) {
    ListNode dummyHead = new ListNode(-1);
    dummyHead.next = head;
    ListNode newHead = new ListNode(-1);
    ListNode large = dummyHead, small = newHead;
    while (large.next != null) {
        if (large.next.val < x) {
            small.next = large.next;
            small = small.next;
            large.next = large.next.next;
        } else {
            large = large.next;
        }
    }
    //连接小链表和大链表
    small.next = dummyHead.next;
    return newHead.next;
}

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}
092. 反转链表 II Reverse Linked List IIex092.java
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
public ListNode reverseBetween(ListNode head, int m, int n) {
    ListNode dummyHead = new ListNode(0);
    dummyHead.next = head;
    ListNode first = dummyHead;
    for (int i = 0; i < m - 1; i++) {
        first = first.next;
    }
    ListNode curr = first.next;
    for (int i = 0; i < n - m; i++) {
        ListNode node = curr.next;
        curr.next = node.next;
        node.next = first.next;
        first.next = node;
    }
    return dummyHead.next;
}

//解决的不好，不易理解，纯靠画图完成
public ListNode reverseBetween2(ListNode head, int m, int n) {
    if (head == null || head.next == null) return head;
    ListNode pre = null, s = head, t = head, curr = head;
    //构造结构
    //  1   ->  2   ->  3   ->  4   ->  5   ->  null, m=2, n=4
    //pre      preS     s               t
    for (int i = 1; (i <= n) && curr != null; i++) {
        if (i < m) pre = curr;
        curr = curr.next;
        t = curr;
    }
    ListNode preS;
    if (pre != null)
        preS = pre.next;
    else
        preS = head;
    s = preS.next;
    //把从s到t的前一个逆序
    //  1   ->  2  <-> 3   <-  4        5   ->  null, m=2, n=4
    //pre    preNext           preS     st
    ListNode preNext = preS;
    while (s != t && s != null) {
        ListNode temp = s.next;
        s.next = preS;
        preS = s;
        s = temp;
    }
    //最后整理链表顺序
    preNext.next = t;
    if (pre != null)
        pre.next = preS;
    else head = preS;
    return head;
}

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}
445. 两数相加 II Add Two Numbers IIex445.java
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
//不反转链表通过Stack存储数据并弹出，然后模仿Stack在头部添加新结点
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    Stack<Integer> stack1 = new Stack<>();
    Stack<Integer> stack2 = new Stack<>();
    ListNode p = l1, q = l2;
    while (p != null) {
        stack1.push(p.val);
        p = p.next;
    }
    while (q != null) {
        stack2.push(q.val);
        q = q.next;
    }
    int carry = 0;
    ListNode first = null;
    while (!stack1.isEmpty() || !stack2.isEmpty()) {
        int x = stack1.isEmpty() ? 0 : stack1.pop();
        int y = stack2.isEmpty() ? 0 : stack2.pop();
        int sum = x + y + carry;
        carry = sum / 10;
        ListNode temp = first;
        first = new ListNode(sum % 10);
        first.next = temp;
    }
    if (carry > 0) {
        ListNode temp = first;
        first = new ListNode(carry);
        first.next = temp;
    }
    return first;
}

//反转链表
public ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
    ListNode rl1 = reverse(l1);
    ListNode rl2 = reverse(l2);

    int carry = 0;
    ListNode dummyHead = new ListNode(0);
    ListNode curr = dummyHead;
    ListNode p = rl1, q = rl2;
    while (p != null || q != null) {
        int x = p != null ? p.val : 0;
        int y = q != null ? q.val : 0;
        int sum = x + y + carry;
        carry = sum / 10;
        curr.next = new ListNode(sum % 10);
        curr = curr.next;
        if (p != null) p = p.next;
        if (q != null) q = q.next;
    }
    if (carry > 0) curr.next = new ListNode(carry);
    return reverse(dummyHead.next);
}

private ListNode reverse(ListNode head) {
    ListNode pre = null;
    while (head != null) {
        ListNode temp = head.next;
        head.next = pre;
        pre = head;
        head = temp;
    }
    return pre;
}

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}
725. 分隔链表 Split Linked List in Partsex725.java
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
public ListNode[] splitListToParts(ListNode root, int k) {
    //总数
    int sum = 0;
    ListNode curr = root;
    while (curr != null) {
        sum++;
        curr = curr.next;
    }
    curr = root;
    //每个部分的基础大小
    int per = sum < k ? 1 : sum / k;
    //额外分配多1的结点数(extra<per)
    int extra = sum < k ? 0 : sum % k;

    ListNode[] result = new ListNode[k];
    ListNode pre = null;
    for (int i = 0; i < k; i++, --extra) {
        result[i] = curr;
        for (int j = 0; (j < per + (extra > 0 ? 1 : 0)) && curr != null; j++) {
            pre = curr;
            curr = curr.next;
        }
        if (pre != null) pre.next = null;
    }
    return result;
}

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}
143. 重排链表 Reorder Listex143.java
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
public void reorderList(ListNode head) {
    ListNode fast = head, slow = head, curr = head;
    ListNode reverse = null;
    //寻找中间结点slow
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    //将后半部分链表翻转
    while (slow != null) {
        ListNode temp = slow.next;
        slow.next = reverse;
        reverse = slow;
        slow = temp;
    }
    //合并两个链表C-R-C-R-C-R···
    //末尾结点两种情况：
    //1.C和R为同一个，以R!=null为循环结束判断条件:···-C/R-null
    //2.R为最后一个，以R.next!=null为循环结束判断条件:···-C-R-null
    while (reverse != null && reverse.next != null) {
        ListNode temp = curr.next;
        ListNode tempR = reverse.next;
        curr.next = reverse;
        reverse.next = temp;
        curr = temp;
        reverse = tempR;
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}
817. Linked List Componentsex817.java
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
public int numComponents(ListNode head, int[] G) {
    Set<Integer> g = new HashSet<>();
    int num = 0;
    for (int i : G) g.add(i);
    while (head != null) {
        if (g.contains(head.val)) {
            if (head.next == null || !g.contains(head.next.val))
                num++;
        }
        head = head.next;
    }
    return num;
}

public int numComponents2(ListNode head, int[] G) {
    Set<Integer> g = new HashSet<>();
    for (int i : G) g.add(i);
    int nums = 0;
    while (head != null) {
        if (g.contains(head.val)) {
            ++nums;
            ListNode next = head.next;
            while (next != null && g.contains(next.val)) {
                next = next.next;
            }
            head = next;
            continue;
        }
        head = head.next;
    }
    return nums;
}

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}
328. 奇偶链表 Odd Even Linked Listex328.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public ListNode oddEvenList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode odd = head;
    ListNode even = head.next;
    ListNode evenHead = even;
    while (even != null && even.next != null) {
        odd.next = even.next;
        odd = odd.next;
        even.next = odd.next;
        even = even.next;
    }
    odd.next = evenHead;
    return head;
}

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}
024. 两两交换链表中的节点 Swap Nodes in Pairsex024.java
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
public ListNode swapPairs(ListNode head) {
    ListNode curr = head;
    ListNode pre = null;
    if (head != null && head.next != null)
        head = head.next;
    while (curr != null && curr.next != null) {
        if (pre != null)
            pre.next = curr.next;
        ListNode temp = curr.next;
        curr.next = temp.next;
        temp.next = curr;
        pre = curr;
        curr = curr.next;
    }
    return head;
}

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}
707. 设计链表 Design Linked Listex707.java
1
代码略长……直接去github看吧 三三三c⌒っﾟДﾟ)っ
160. 相交链表 Intersection of Two Linked Listsex160.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    //A + B = B + A;
    //(a+intersection)+(b+intersection)=(b+intersection)+(a+intersection)
    //遍历A+B 和 B+A，若相交,则最后必然会有相交点。
    ListNode p = headA, q = headB;
    while (p != q) {
        p = p != null ? p.next : headB;
        q = q != null ? q.next : headA;
    }
    return p;
}

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}
234. 回文链表 Palindrome Linked Listex234.java
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
public boolean isPalindrome(ListNode head) {
    //空链表或是单结点链表为true
    if (head == null || head.next == null) return true;
    //判断是否为奇数个数的链表
    boolean single = false;
    ListNode slow = head, fast = head;
    ListNode pre = null;
    //遍历链表slow至中序，并将pre作为前段逆序，若总结点数为count，则sum -> Node(i <= count/2)
    //i属于0 ~ count-1
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        if (fast != null)
            single = fast.next == null;
        ListNode temp = slow.next;
        slow.next = pre;
        pre = slow;
        slow = temp;
    }

    //如果为奇数链表，slow需要下移一位
    //1 2 1
    //P S ? F
    if (single) slow = slow.next;
    while (slow != null) {
        if (pre == null) return false;
        if (pre.val != slow.val) return false;
        slow = slow.next;
        pre = pre.next;
    }
    return true;
}

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}
002. 两数相加 Add Two Numbersex002.java
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
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummyHead = new ListNode(0);
    ListNode p = l1, q = l2, curr = dummyHead;
    int carry = 0;
    while (p != null || q != null) {
        int x = p != null ? p.val : 0;
        int y = q != null ? q.val : 0;
        int sum = x + y + carry;
        carry = sum / 10;
        curr.next = new ListNode(sum % 10);
        curr = curr.next;
        if (p != null) {
            p = p.next;
        }
        if (q != null) {
            q = q.next;
        }
    }
    if (carry > 0) {
        curr.next = new ListNode(carry);
    }
    return dummyHead.next;
}

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}
876. 链表的中间结点 Middle of the Linked Listex876.java
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
public ListNode middleNode(ListNode head) {
    int total = 0;
    ListNode curr = head;
    while (curr != null) {
        total++;
        curr = curr.next;
    }
    curr = head;
    for (int i = 0; i < total / 2; i++) {
        curr = curr.next;
    }
    return curr;
}

public ListNode middleNode2(ListNode head) {
    ListNode curr = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        curr = curr.next;
    }
    return curr;
}

public class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}
206. 反转链表 Reverse Linked Listex206.java
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
//递归解决
public ListNode reverseList(ListNode head) {
    if (head != null && head.next != null) {
        ListNode reverseHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return reverseHead;
    } else
        return head;
}

//迭代解决
public ListNode reverseList2(ListNode head) {
    ListNode pre = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode temp = curr.next;
        curr.next = pre;
        pre = curr;
        curr = temp;
    }
    return pre;
}

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}
237. 删除链表中的节点 Delete Node in a Linked Listex237.java
1
2
3
4
5
6
7
8
9
10
11
12
13
public void deleteNode(ListNode node) {
    node.val = node.next.val;
    node.next = node.next.next;
}

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}
001. 两数之和 Two Sumex001.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int[] twoSum(int[] nums, int target) {
    int[] temp = new int[2];
    if (null == nums || nums.length < 2) {
        return temp;
    }

    HashMap<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        if (map.containsKey(target - nums[i])) {
            temp[0] = map.get(target - nums[i]);
            temp[1] = i;
            break;
        } else {
            map.put(nums[i], i);
        }
    }
    return temp;
}
704. 二分查找 Binary Searchex704.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int search(int[] nums, int target) {
    int lo = 0;
    int hi = nums.length - 1;
    if (lo == hi) {
        if (target == nums[lo]) return lo;
        else return -1;
    }
    int mid;
    while (nums[lo] < nums[hi]) {
        mid = (lo + hi) / 2;
        if (lo == mid || hi == mid) {
            if (target == nums[lo]) return lo;
            else if (target == nums[hi]) return hi;
            else return -1;
        }
        if (target < nums[mid]) hi = mid;
        else if (target > nums[mid]) lo = mid;
        else return mid;
    }
    return -1;
}
083. 删除排序链表中的重复元素 Remove Duplicates from Sorted Listex083.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public ListNode deleteDuplicates(ListNode head) {
    ListNode curr = head;
    while (curr != null && curr.next != null) {
        if (curr.val == curr.next.val) {
            curr.next = curr.next.next;
        } else {
            curr = curr.next;
        }
    }
    return head;
}

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}
203. 删除链表中的节点 Remove Linked List Elementsex203.java
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
public ListNode removeElements(ListNode head, int val) {
    while (head != null && head.val == val) {
        head = head.next;
    }
    ListNode curr = head;
    while (curr != null && curr.next != null) {
        if (curr.next.val == val) {
            curr.next = curr.next.next;
        } else {
            curr = curr.next;
        }
    }
    return head;
}

public ListNode removeElements2(ListNode head, int val) {
    if (head == null) return null;
    head.next = removeElements2(head.next, val);
    return head.val == val ? head.next : head;
}

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}
021. 合并两个有序链表 Merge Two Sorted Listsex021.java
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
//在数组中可以使用归并排序-merge
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode curr = new ListNode(-1);
    ListNode head;
    head = curr;
    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            curr.next = new ListNode(l1.val);
            l1 = l1.next;
        } else {
            curr.next = new ListNode(l2.val);
            l2 = l2.next;
        }
        curr = curr.next;
    }
    if (l1 == null) {
        curr.next = l2;
    } else {
        curr.next = l1;
    }
    return head.next;
}

public ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
    if (l1 == null) return l2;
    if (l2 == null) return l1;
    ListNode head = null;
    if (l1.val < l2.val) {
        head = l1;
        head.next = mergeTwoLists2(l1.next, l2);
    } else {
        head = l2;
        head.next = mergeTwoLists2(l1, l2.next);
    }
    return head;
}

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}
141. 环形链表 Linked List Cycleex141.java
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
public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null)
        return false;
    ListNode slow = head;
    ListNode fast = head.next;
    while (slow != fast) {
        if (fast == null || fast.next == null)
            return false;
        slow = slow.next;
        fast = fast.next.next;
    }
    return true;
}

public boolean hasCycle2(ListNode head) {
    while (head != null) {
        if (head.val == 0x7fffffff) return true;
        head.val = 0x7fffffff;
        head = head.next;
    }
    return false;
}

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

本文标题:Leetcode刷题记录（日更）

文章作者:

发布时间:2018-08-22, 00:26:25

最后更新:2020-09-12, 16:12:15

原始链接:http://yif-hong.github.io/2018/08/22/LeetcodeExercise/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
|