数组中的第K个最大元素

题目

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

解题思路

1. 利用快排的思想，当排序到 k 后，停止排序，输出结果

public static int findKthLargest(int[] nums, int k) {
    fastSort(nums, 0, nums.length - 1);
    return nums[nums.length - k];
}

public static void fastSort(int[] nums, int start, int end) {
    if (nums.length <= 1) {
        return;
    }

    if (start > end) {
        return;
    }

    if (end < 0 || start < 0 || end > nums.length - 1 || start > nums.length - 1) {
        return;
    }

    int left = start, right = end;
    int keyIndex = (left + right) / 2;

    while (left < right) {
        while (right > keyIndex && nums[right] > nums[keyIndex]) {
            right--;
        }

        if (right > keyIndex) {
            swap(nums, keyIndex, right);
            keyIndex = right;
        }

        while (left < keyIndex && nums[left] < nums[keyIndex]) {
            left++;
        }

        if (left < keyIndex) {
            swap(nums, left, keyIndex);
            keyIndex = left;
        }
        left++;
    }

    fastSort(nums, keyIndex + 1, end);
    fastSort(nums, start, keyIndex - 1);

}

三数之和

头条重点

题目

给定一个包含 n 个整数的数组 nums ，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

解题思路

1. 将数组排序
2. 固定一位数，然后通过两个指针对撞，寻找总和为 0 的三个数

public static List<List<Integer>> threeSum(int[] nums) {
    if (nums.length < 3) {
        return Collections.emptyList();
    }

    Set<List<Integer>> res = new HashSet<>();
    Arrays.sort(nums);

    int zCount = 0;
    for (int num : nums) {
        if (num == 0) {
            zCount++;
        }
    }

    for (int i = 0; i < nums.length && nums[i] < 0; i++) {
        int first = nums[I];
        int j = i + 1;
        int k = nums.length - 1;
        while (j < k) {
            int t = nums[j] + nums[k] + first;
            if (t == 0) {
                List<Integer> list = new ArrayList<>();
                list.add(first);
                list.add(nums[j]);
                list.add(nums[k]);

                res.add(list);
                j++;
                k--;
            } else if (t > 0) {
                k--;
            } else {
                j++;
            }
        }

    }

    if (zCount >= 3) {
        List<Integer> list = new ArrayList<>();
        list.add(0);
        list.add(0);
        list.add(0);
        res.add(list);
    }
    return new ArrayList<>(res);
}

环形链表 II

题目

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

解题思路

1. 首先通过快慢指针确定链表是否有环
2. 再使用一个指针从头节点与快慢指针相遇节点同步长前进，最终找到环的入口

public ListNode detectCycle(ListNode head) {
    ListNode fast = head, slow = head;

    ListNode meetNode = null;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;

        if (fast == slow) {
            meetNode = fast;
            break;
        }
    }

    if (meetNode == null) {
        return meetNode;
    }

    while (head != meetNode) {
        head = head.next;
        if (head == meetNode) {
            break;
        }

        meetNode = meetNode.next;
    }

    return meetNode;
}

两数相加

头条重点

题目

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

解题思路

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    if (l1 == null || l2 == null) {
        return null;
    }

    StringBuilder builder1 = new StringBuilder();
    while (l1 != null) {
        builder1.append(l1.val);
        l1 = l1.next;
    }

    StringBuilder builder2 = new StringBuilder();
    while (l2 != null) {
        builder2.append(l2.val);
        l2 = l2.next;
    }

    BigDecimal bigDecimal1 = new BigDecimal(builder1.reverse().toString());
    BigDecimal bigDecimal2 = new BigDecimal(builder2.reverse().toString());

    String resStr = bigDecimal1.add(bigDecimal2).toPlainString();

    ListNode head = new ListNode(Integer.parseInt(String.valueOf(resStr.charAt(resStr.length() - 1))));
    ListNode cur = head;
    for (int i = resStr.length() - 2; i >= 0; i--) {
        cur.next = new ListNode(Integer.parseInt(String.valueOf(resStr.charAt(i))));
        cur = cur.next;
    }

    return head;
}

反转链表

头条重点

题目

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

解题思路

1. 三个指针进行反转

public ListNode reverseList(ListNode head) {
    if (head == null) {
        return head;
    }

    if (head.next == null) {
        return head;
    }

    ListNode pre = head;
    ListNode cur = head.next;

    while (cur != null) {
        ListNode next = cur.next;
        cur.next = pre;

        pre = cur;
        cur = next;
    }

    head.next = null;

    return pre;
}

合并两个有序链表

题目

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

解题思路

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1 == null && l2 == null) {
        return null;
    }

    if (l1 == null) {
        return l2;
    }

    if (l2 == null) {
        return l1;
    }

    ListNode head;

    if (l1.val > l2.val) {
        head = l2;
        l2 = l2.next;
    } else {
        head = l1;
        l1 = l1.next;
    }

    ListNode res = head;
    while (true) {
        ListNode cur;
        if (l1 == null && l2 == null) {
            break;
        }

        if (l1 == null) {
            cur = l2;
            l2 = l2.next;
        } else if (l2 == null) {
            cur = l1;
            l1 = l1.next;
        } else if (l1.val > l2.val) {
            cur = l2;
            l2 = l2.next;
        } else {
            cur = l1;
            l1 = l1.next;
        }

        head.next = cur;
        head = head.next;
    }

    return res;
}

相交链表

题目

编写一个程序，找到两个单链表相交的起始节点。

解题思路

1. 首先将两个链表中长的一个向前遍历，直到两个链表长度一致
2. 两个链表同时向前遍历，便可找到交点

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) {
        return null;
    }

    if (headA == headB) {
        return headA;
    }

    int lenA = 1;
    int lenB = 1;
    ListNode temp = headA;
    while (temp.next != null) {
        temp = temp.next;
        lenA++;
    }

    ListNode tailA = temp;

    temp = headB;
    while (temp.next != null) {
        temp = temp.next;
        lenB++;
    }

    ListNode tailB = temp;
    if (tailB != tailA) {
        return null;
    }

    if (lenA > lenB) {
        for (int i = 0; i < lenA - lenB && headA != null; i++) {
            headA = headA.next;
        }

    } else if (lenA < lenB) {
        for (int i = 0; i < lenB - lenA && headB != null; i++) {
            headB = headB.next;
        }
    }

    while (!headA.equals(headB)) {
        headA = headA.next;
        headB = headB.next;
    }

    return headA;
}

合并K个排序链表

头条重点

题目

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

解题思路

1. 通过小根堆，将所有元素放入小根堆
2. 从小根堆依次取出数据

public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null) {
        return null;
    }

    Queue<ListNode> set = new PriorityQueue<>(Comparator.comparingInt(o -> o.val));

    for (ListNode node : lists) {
        while (node != null) {
            set.add(node);
            node = node.next;
        }
    }

    ListNode head = new ListNode(-1);
    ListNode res = head;
    ListNode cur;
    while ((cur = set.poll()) != null) {
        head.next = cur;
        head = head.next;
    }

    head.next = null;
    return res.next;
}

翻转字符串里的单词

题目

给定一个字符串，逐个翻转字符串中的每个单词。

示例 1：

输入: "the sky is blue"
输出: "blue is sky the"

说明：

• 无空格字符构成一个单词。
• 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
• 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

解题思路

1. 按空格拆分字符串为字符串数组 t
2. 逆序遍历字符串数组 t，并组成新的字符串

public String reverseWords(String s) {
    String trimed = s.trim();

    String[] split = trimed.split(" ");

    StringBuilder builder = new StringBuilder();
    for (int i = split.length - 1; i >= 0; i--) {
        String t = split[I];
        if (t.trim().isEmpty()) {
            continue;
        }

        builder.append(t).append(" ");
    }

    return builder.toString().trim();
}

无重复字符的最长子串

头条重点

题目

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

解题思路

1. 用 Map 记录字符所在位置，当遇到重复字符时，移动 start 指针
2. 替换 Map 中下标，并计算子串长度

public int lengthOfLongestSubstring(String str) {
    if (str == null || str.length() == 0) return 0;

    HashMap<Character, Integer> temp = new HashMap<>();
    char[] chars = str.toCharArray();

    int res = 0, start = 0;
    for (int i = 0; i < chars.length; i++) {
        if (temp.containsKey(chars[i])) {
            start = Math.max(temp.put(chars[i], i) + 1, start);
        }

        temp.put(chars[i], i);
        res = Math.max(res, i - start + 1);

    }

    return res;
}

排序链表

头条重点

题目

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

输入: 4->2->1->3
输出: 1->2->3->4
示例 2:

输入: -1->5->3->4->0
输出: -1->0->3->4->5

解题思路

1. 通过快慢指针将链表拆分
2. 递归进行拆分，再通过合并两个排序链表的方式进行合并
3. 类似于归并排序

public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }

    ListNode slow = head, fast = head;
    while (fast.next != null && fast.next.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }

    ListNode mid = slow.next;
    slow.next = null;

    ListNode l1 = sortList(head);
    ListNode l2 = sortList(mid);

    return merge(l1, l2);
}

private ListNode merge(ListNode l1, ListNode l2) {
    if (l1 == null) {
        return l2;
    }

    if (l2 == null) {
        return l1;
    }

    ListNode head,res;
    if (l1.val > l2.val) {
        head = l2;
        l2 = l2.next;
    } else {
        head = l1;
        l1 = l1.next;
    }
    res = head;
//        head.next = null;

    while (l1 != null || l2 != null) {
        if (l1 == null) {
            head.next = l2;
            l2 = l2.next;
        } else if (l2 == null) {
            head.next = l1;
            l1 = l1.next;
        } else {
            if (l1.val > l2.val) {
                head.next = l2;
                l2 = l2.next;
            } else {
                head.next = l1;
                l1 = l1.next;
            }
        }
        head = head.next;
    }

    return res;
}