數(shù)組中的第K個最大元素
題目
在未排序的數(shù)組中找到第 k 個最大的元素。請注意埂陆，你需要找的是數(shù)組排序后的第 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
解題思路
- 利用快排的思想，當(dāng)排序到
k后囊咏，停止排序，輸出結(jié)果
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);
}
三數(shù)之和
頭條重點(diǎn)
題目
給定一個包含 n 個整數(shù)的數(shù)組 nums ，判斷 nums 中是否存在三個元素 a点弯，b，c 矿咕，使得 a + b + c = 0 抢肛？找出所有滿足條件且不重復(fù)的三元組。
注意：答案中不可以包含重復(fù)的三元組碳柱。
例如, 給定數(shù)組 nums = [-1, 0, 1, 2, -1, -4]捡絮，
滿足要求的三元組集合為：
[
[-1, 0, 1],
[-1, -1, 2]
]
解題思路
- 將數(shù)組排序
- 固定一位數(shù)，然后通過兩個指針對撞莲镣，尋找總和為 0 的三個數(shù)
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);
}
環(huán)形鏈表 II
題目
給定一個鏈表福稳，返回鏈表開始入環(huán)的第一個節(jié)點(diǎn)。 如果鏈表無環(huán)剥悟，則返回 null灵寺。
為了表示給定鏈表中的環(huán)，我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）区岗。 如果 pos 是 -1略板，則在該鏈表中沒有環(huán)。
解題思路
- 首先通過快慢指針確定鏈表是否有環(huán)
- 再使用一個指針從頭節(jié)點(diǎn)與快慢指針相遇節(jié)點(diǎn)同步長前進(jìn)慈缔，最終找到環(huán)的入口
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;
}
兩數(shù)相加
頭條重點(diǎn)
題目
給出兩個 非空 的鏈表用來表示兩個非負(fù)的整數(shù)叮称。其中，它們各自的位數(shù)是按照 逆序 的方式存儲的藐鹤，并且它們的每個節(jié)點(diǎn)只能存儲 一位 數(shù)字瓤檐。
如果，我們將這兩個數(shù)相加起來娱节，則會返回一個新的鏈表來表示它們的和挠蛉。
您可以假設(shè)除了數(shù)字 0 之外，這兩個數(shù)都不會以 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;
}
反轉(zhuǎn)鏈表
頭條重點(diǎn)
題目
反轉(zhuǎn)一個單鏈表谴古。
示例:
輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL
解題思路
- 三個指針進(jìn)行反轉(zhuǎn)
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;
}
合并兩個有序鏈表
題目
將兩個有序鏈表合并為一個新的有序鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點(diǎn)組成的稠歉。
示例：
輸入：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;
}
相交鏈表
題目
編寫一個程序掰担，找到兩個單鏈表相交的起始節(jié)點(diǎn)。
解題思路
- 首先將兩個鏈表中長的一個向前遍歷怒炸，直到兩個鏈表長度一致
- 兩個鏈表同時向前遍歷带饱，便可找到交點(diǎn)
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個排序鏈表
頭條重點(diǎn)
題目
合并 k 個排序鏈表，返回合并后的排序鏈表阅羹。請分析和描述算法的復(fù)雜度勺疼。
示例:
輸入:
[
1->4->5,
1->3->4,
2->6
]
輸出: 1->1->2->3->4->4->5->6
解題思路
- 通過小根堆，將所有元素放入小根堆
- 從小根堆依次取出數(shù)據(jù)
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;
}
翻轉(zhuǎn)字符串里的單詞
題目
給定一個字符串捏鱼，逐個翻轉(zhuǎn)字符串中的每個單詞恢口。
示例 1：
輸入: "the sky is blue"
輸出: "blue is sky the"
說明：
- 無空格字符構(gòu)成一個單詞。
- 輸入字符串可以在前面或者后面包含多余的空格穷躁，但是反轉(zhuǎn)后的字符不能包括耕肩。
- 如果兩個單詞間有多余的空格，將反轉(zhuǎn)后單詞間的空格減少到只含一個问潭。
解題思路
- 按空格拆分字符串為字符串?dāng)?shù)組
t - 逆序遍歷字符串?dāng)?shù)組
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();
}
無重復(fù)字符的最長子串
頭條重點(diǎn)
題目
給定一個字符串，請你找出其中不含有重復(fù)字符的 最長子串 的長度狡忙。
輸入: "abcabcbb"
輸出: 3
解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "abc"梳虽，所以其長度為 3。
解題思路
- 用 Map 記錄字符所在位置灾茁，當(dāng)遇到重復(fù)字符時窜觉，移動
start指針 - 替換 Map 中下標(biāo)谷炸，并計(jì)算子串長度
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;
}
排序鏈表
頭條重點(diǎn)
題目
在 O(n log n) 時間復(fù)雜度和常數(shù)級空間復(fù)雜度下，對鏈表進(jìn)行排序禀挫。
示例 1:
輸入: 4->2->1->3
輸出: 1->2->3->4
示例 2:
輸入: -1->5->3->4->0
輸出: -1->0->3->4->5
解題思路
- 通過快慢指針將鏈表拆分
- 遞歸進(jìn)行拆分旬陡，再通過合并兩個排序鏈表的方式進(jìn)行合并
- 類似于歸并排序
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;
}
