7.6 头条算法习题
7.6.1 字符串
- 无重复字符的最长子串 (给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。示例 1:
输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。, 示例 2:输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。), 示例 3:输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
class Solution {
public int lengthOfLongestSubstring(String s) {
Set<Character> set = new HashSet<>();
int lengthOfLongest = 0;
int i = 0, j = 0;
int n = s.length();
while(i < n && j < n) {
if(!set.contains(s.charAt(j))) {
set.add(s.charAt(j++));
lengthOfLongest = Math.max(lengthOfLongest, j - i);
} else {
set.remove(s.charAt(i++));
}
}
return lengthOfLongest;
}
}
- 最长公共前缀 (编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ““。示例 1:
输入: ["flower","flow","flight"] 输出: "fl", 示例 2:输入: ["dog","racecar","car"] 输出: "" 解释: 输入不存在公共前缀。)
class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
}
String prefix = "";
int length = strs[0].length();
int prefixIndex = 1;
String currentPrefix = null;
while (prefixIndex <= length) {
currentPrefix = strs[0].substring(0, prefixIndex);
for (int i = 1; i < strs.length; i++) {
if (!strs[i].startsWith(currentPrefix)) {
return prefix;
}
}
prefix = currentPrefix;
prefixIndex++;
}
return prefix;
}
}
- 字符串的排列 (给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。换句话说，第一个字符串的排列之一是第二个字符串的子串。示例1:
输入: s1 = "ab" s2 = "eidbaooo" 输出: True 解释: s2 包含 s1 的排列之一 ("ba")., 示例2:输入: s1= "ab" s2 = "eidboaoo" 输出: False)
class Solution {
public boolean checkInclusion(String s1, String s2) {
if (s1 == null || s2 == null) {
return false;
}
int left = 0;
int k = s1.length();
int count = k;
boolean isInclusion = false;
int stringMap[] = new int[26];
for (int i = 0; i < s1.length(); i++) {
stringMap[s1.charAt(i) - 'a']++;
}
for (int right = 0; right < s2.length(); right++) {
if (--stringMap[s2.charAt(right) - 'a'] >= 0) {
count--;
}
if (count == 0) {
isInclusion = true;
break;
}
if (right - left + 1 == k) {
if (++stringMap[s2.charAt(left) - 'a'] > 0){
count++;
}
left++;
}
}
return isInclusion;
}
}
- 字符串相乘 (给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。示例 1:
输入: num1 = "2", num2 = "3" 输出: "6", 示例 2:输入: num1 = "123", num2 = "456" 输出: "56088")
class Solution {
public String multiply(String num1, String num2) {
if (num1 == null || num2 == null) {
return null;
}
int m = num1.length();
int n = num2.length();
int sum[] = new int [m + n];
for (int i = m - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
int p1 = i + j;
int p2 = i + j + 1;
mul += sum[p2];
sum[p1] += mul / 10;
sum[p2] = mul % 10;
}
}
StringBuilder sb = new StringBuilder();
for (int p : sum) {
if (!(sb.length() == 0 && p == 0)) {
sb.append(p);
}
}
return sb.length() == 0 ? "0" : sb.toString();
}
}
- 翻转字符串里的单词 (给定一个字符串，逐个翻转字符串中的每个单词。示例 1：
输入: "the sky is blue" 输出: "blue is sky the", 示例 2：输入: " hello world! " 输出: "world! hello" 解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。, 示例 3：输入: "a good example" 输出: "example good a" 解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。)
class Solution {
public String reverseWords(String s) {
List<String> resultList = new ArrayList();
for (String item : s.split(" ")) {
if (item.length() > 0) {
resultList.add(0, item);
}
}
return String.join(" ", resultList);
}
}
- 简化路径 (以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。更多信息请参阅：Linux / Unix中的绝对路径 vs 相对路径 请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示绝对路径的最短字符串。示例1:
输入："/home/" 输出："/home" 解释：注意，最后一个目录名后面没有斜杠。, 示例5:输入："/a/../../b/../c//.//" 输出："/c")
class Solution {
public String simplifyPath(String path) {
List<String> res = new ArrayList<>();
res.add("/");
int start = 1, end = 1, len = path.length();
while (end < len) {
while (end < len && path.charAt(end) != '/')
end++;
String subPath = path.substring(start, end);
if ("..".equals(subPath)) {
if (res.size() != 1) {
res.remove(res.size() - 1);
}
} else if (!(".".equals(subPath)) && !("/".equals(subPath)) && !("".equals(subPath))) {
System.out.println(subPath);
res.add(subPath);
}
while (end < len && path.charAt(end) == '/')
end++;
start = end;
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < res.size(); i++) {
if (i == 0 || i == res.size() - 1) {
sb.append(res.get(i));
} else {
sb.append(res.get(i)).append("/");
}
}
return sb.toString();
}
}
- 复原IP地址 (给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。示例:
输入: "25525511135" 输出: ["255.255.11.135", "255.255.111.35"])
class Solution {
public List<String> restoreIpAddresses(String s) {
int gap = s.length() / 4;
List<String> restoreIps = new ArrayList<>();
_restoreIpAddresses(s, 0, "", restoreIps);
return restoreIps;
}
public void _restoreIpAddresses(String s, int n, String out, List<String> resultList) {
if (n == 4) {
if (s.isEmpty()) {
resultList.add(out);
}
return ;
}
System.out.println(out);
for (int i = 1; i < 4; i++) {
if (s.length() < i) {
break;
}
int value = Integer.parseInt(s.substring(0, i));
if (value > 255 || i != String.valueOf(value).length()) {
continue;
}
_restoreIpAddresses(s.substring(i), n+1, out + s.substring(0, i) + (n==3 ? "" : "."), resultList);
}
}
}
7.6.2 数组与排序
- 三数之和 (给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。示例:
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，满足要求的三元组集合为： [[-1, 0, 1],[-1, -1, 2]])
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> resultList = new ArrayList<>();
if (nums.length == 0) return resultList;
Arrays.sort(nums);
boolean hasZero = false;
for (int i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
int left = i + 1;
int right = nums.length - 1;
int sum = 0 - nums[i];
while (left < right) {
if (nums[left] + nums[right] == sum) {
resultList.add(Arrays.asList(nums[i], nums[left], nums[right]));
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
} else if (nums[left] + nums[right] < sum) {
while (left < right && nums[left] == nums[left + 1]) left++;
left++;
} else {
while (left < right && nums[right] == nums[right - 1]) right--;
right--;
}
}
}
return resultList;
}
}
- 搜索旋转排序数组(假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。你可以假设数组中不存在重复的元素。你的算法时间复杂度必须是 O(log n) 级别。示例:
输入: nums = [4,5,6,7,0,1,2], target = 0 输出: 4; 输入: nums = [4,5,6,7,0,1,2], target = 3 输出: -1)
class Solution {
public int search(int[] nums, int target) {
return search(nums, 0, nums.length - 1, target);
}
private int search(int[] nums, int low, int high, int target) {
if (low > high) {
return -1;
}
int mid = (low + high) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[mid] < nums[high]) {
if (nums[mid] < target && target <= nums[high]) {
return search(nums, mid + 1, high, target);
} else {
return search(nums, low, mid - 1, target);
}
} else {
if (nums[low] <= target && target <nums[mid]) {
return search(nums, low, mid - 1, target);
} else {
return search(nums, mid + 1, high, target);
}
}
}
}
- 最长连续递增序列(给定一个未经排序的整数数组，找到最长且连续的的递增序列。示例:
输入: [1,3,5,4,7] 输出: 3 解释: 最长连续递增序列是 [1,3,5], 长度为3。尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为5和7在原数组里被4隔开。输入: [2,2,2,2,2] 输出: 1 解释: 最长连续递增序列是 [2], 长度为1。)
class Solution {
public int findLengthOfLCIS(int[] nums) {
int previousValue = -1;
int previousLengthOfLCIS = 0;
int lengthOfLCIS = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] > previousValue) {
lengthOfLCIS++;
} else {
if (lengthOfLCIS > previousLengthOfLCIS) {
previousLengthOfLCIS = lengthOfLCIS;
}
lengthOfLCIS = 1;
}
previousValue = nums[i];
}
if (previousLengthOfLCIS > lengthOfLCIS) {
lengthOfLCIS = previousLengthOfLCIS;
}
return lengthOfLCIS;
}
}
- 数组中的第K个最大元素(在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。示例:
输入: [3,2,1,5,6,4] 和 k = 2 输出: 5; 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4)
class Solution {
public int findKthLargest(int[] nums, int k) {
heapSort(nums);
return nums[nums.length - k];
}
public void heapSort(int[] nums) {
int len = nums.length;
for (int i = len / 2 - 1; i >= 0; i--) {
maxHeap(nums, i, len);
}
for (int i = len - 1; i > 0; i--) {
swap(nums, 0, i);
maxHeap(nums, 0, i);
}
}
public void maxHeap(int[] nums, int index, int length) {
int temp = nums[index];
for (int i = index * 2 + 1; i < length; i = index * 2 + 1) {
if (i+1 < length && nums[i] < nums[i+1]) {
i++;
}
if (nums[i] > temp) {
nums[index] = nums[i];
index = i;
} else {
break;
}
}
nums[index] = temp;
}
public void swap(int[] nums, int left, int right) {
int tmp = nums[left];
nums[left] = nums[right];
nums[right] = tmp;
}
}
- 最长连续序列(给定一个未排序的整数数组，找出最长连续序列的长度。要求算法的时间复杂度为 O(n)。示例:
输入: [100, 4, 200, 1, 3, 2] 输出: 4 解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。)
class Solution {
public int longestConsecutive(int[] nums) {
HashSet<Integer> numsSet = new HashSet<>();
int longestCount = 0;
for (int i = 0; i < nums.length; i++) {
numsSet.add(nums[i]);
}
for (int i = 0; i < nums.length; i++) {
int num = nums[i];
int tmpLongestCount = 0;
while (numsSet.contains(num++) && tmpLongestCount < nums.length) {
tmpLongestCount++;
}
if (tmpLongestCount > longestCount) {
longestCount = tmpLongestCount;
}
}
return longestCount;
}
}
- 第k个排列(给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。示例:
输入: n = 3, k = 3 输出: "213"; 输入: n = 4, k = 9 输出: "2314")
class Solution {
public String getPermutation(int n, int k) {
List<Integer> nums = new ArrayList<>();
int factorial[] = new int[n + 1];
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
nums.add(i + 1);
}
int sum = 1;
factorial[0] = 1;
for (int i = 1; i <= n; i++) {
sum *= i;
factorial[i] = sum;
}
k--;
for (int i = 1; i <= n; i++) {
int index = k / factorial[n - i];
sb.append(nums.get(index));
nums.remove(index);
k -= index * factorial[n - i];
}
return sb.toString();
}
}
- 朋友圈(班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。示例:
输入: [[1,1,0],[1,1,0],[0,0,1]] 输出: 2 说明：已知学生0和学生1互为朋友，他们在一个朋友圈。第2个学生自己在一个朋友圈。所以返回2。输入: [[1,1,0],[1,1,1],[0,1,1]] 输出: 1 说明：已知学生0和学生1互为朋友，学生1和学生2互为朋友，所以学生0和学生2也是朋友，所以他们三个在一个朋友圈，返回1。)
class Solution {
public int findCircleNum(int[][] M) {
int count = 0;
int len = M[0].length;
int visited[] = new int[len];
for (int i = 0; i < M[0].length; i++) {
if (visited[i] == 0) {
dfs(M, visited, i);
count++;
}
}
return count;
}
public void dfs(int[][]M, int visited[], int i) {
for (int j = 0; j < M[0].length; j++) {
if (M[i][j] == 1 && visited[j] == 0) {
visited[j] = 1;
dfs(M, visited, j);
}
}
}
}
- 合并区间(给出一个区间的集合，请合并所有重叠的区间。示例:
输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]] 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]. 输入: [[1,4],[4,5]] 输出: [[1,5]] 解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。)
class Solution {
private class IntervalComparator implements Comparator<Interval> {
public int compare(Interval a, Interval b) {
return a.start < b.start ? -1 : a.start == b.start ? 0 : 1;
}
}
public int[][] merge(int[][] intervals) {
List<Interval> intervalList = new ArrayList<>();
for (int i = 0; i < intervals.length; i++) {
Interval interval = new Interval();
interval.start = intervals[i][0];
interval.end = intervals[i][1];
intervalList.add(interval);
}
Collections.sort(intervalList, new IntervalComparator());
LinkedList<Interval> merged = new LinkedList<Interval>();
for (Interval interval : intervalList) {
if (merged.isEmpty() || merged.getLast().end < interval.start) {
merged.add(interval);
} else {
merged.getLast().end = Math.max(merged.getLast().end, interval.end);
}
}
int [][] mergeArray = new int[merged.size()][2];
int i = 0;
for (Interval interval : merged) {
mergeArray[i][0] = interval.start;
mergeArray[i][1] = interval.end;
i++;
}
return mergeArray;
}
class Interval {
int start;
int end;
}
}
- 接雨水(给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1] 输出: 6)
class Solution {
public int trap(int[] height) {
int left = 0, right = height.length - 1;
int ans = 0;
int leftMax = 0, rightMax = 0;
while (left < right) {
if (height[left] < height[right]) {
if (height[left] >= leftMax) {
leftMax = height[left];
} else {
ans += (leftMax - height[left]);
}
++left;
} else {
if (height[right] >= rightMax) {
rightMax = height[right];
} else {
ans += (rightMax - height[right]);
}
--right;
}
}
return ans;
}
}
7.6.3 链表和树
- 合并两个有序链表(将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例:
输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null && l2 == null) {
return null;
}
ListNode top = new ListNode(0);
ListNode currsor = top;
while (l1 != null || l2 != null) {
if(l1 == null) {
currsor.next = new ListNode(l2.val);
l2 = l2.next;
} else if (l2 == null) {
currsor.next = new ListNode(l1.val);
l1 = l1.next;
} else {
int left = l1.val;
int right = l2.val;
if(left > right) {
currsor.next = new ListNode(right);
l2 = l2.next;
} else {
currsor.next = new ListNode(left);
l1 = l1.next;
}
}
currsor = currsor.next;
System.out.println(currsor.val);
}
return top.next;
}
}
- 反转链表(反转一个单链表。示例:
输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode tail = null;
while (head != null) {
ListNode next = head.next;
head.next = tail;
tail = head;
head = next;
}
return tail;
}
}
- 两数相加(给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外，这两个数都不会以 0 开头。示例:
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode sumListNode = null;
ListNode nextNode = null;
int tenNum = 0;
while(l1 != null || l2 != null) {
int l1Val = 0;
if(l1 != null) {
l1Val = l1.val;
}
int l2Val = 0;
if(l2 != null) {
l2Val = l2.val;
}
int sum = l1Val + l2Val + tenNum;
int unitNum = sum % 10;
tenNum = sum / 10;
if(nextNode == null) {
nextNode = new ListNode(unitNum);
sumListNode = nextNode;
} else {
nextNode.next = new ListNode(unitNum);
nextNode = nextNode.next;
}
if(l1 != null) {
l1 = l1.next;
}
if(l2 != null) {
l2 = l2.next;
}
}
if(tenNum != 0) {
nextNode.next = new ListNode(tenNum);
nextNode = nextNode.next;
}
return sumListNode;
}
}
- 排序链表(在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。示例:
输入: 4->2->1->3 输出: 1->2->3->4; 输入: -1->5->3->4->0 输出: -1->0->3->4->5)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode prev = null;
ListNode fast = head, slow = head;
while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
prev.next = null;
ListNode left = sortList(head);
ListNode right = sortList(slow);
return merge(left, right);
}
private ListNode merge(ListNode left, ListNode right) {
ListNode p = new ListNode(0);
ListNode result = p;
while (left != null && right != null) {
if (left.val < right.val) {
result.next = left;
left = left.next;
} else {
result.next = right;
right = right.next;
}
result = result.next;
}
if (left != null) {
result.next = left;
}
if (right != null) {
result.next = right;
}
return p.next;
}
}
- 环形链表 II(给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。示例:
输入：head = [3,2,0,-4], pos = 1 输出：tail connects to node index 1 解释：链表中有一个环，其尾部连接到第二个节点。输入：head = [1,2], pos = 0 输出：tail connects to node index 0 解释：链表中有一个环，其尾部连接到第一个节点。)
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode cursor = head;
ListNode prev = null;
Set<ListNode> visited = new HashSet<ListNode>();
while (cursor != null) {
if (visited.contains(cursor)) {
prev = cursor;
break;
}
visited.add(cursor);
cursor = cursor.next;
}
return prev;
}
}
/**
* 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 null;
ListNode a = headA;
ListNode b = headB;
while (a != b) {
a = a == null ? headB : a.next;
b = b == null ? headA : b.next;
}
return a;
}
}
- 合并K个排序链表(合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。示例:
输入: [1->4->5,1->3->4,2->6]输出: 1->1->2->3->4->4->5->6)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) {
return null;
} else if (lists.length == 1) {
return lists[0];
} else if (lists.length == 2) {
return merge2Lists(lists[0], lists[1]);
}
int mid = lists.length/2;
ListNode[] l1 = new ListNode[mid];
for(int i = 0; i < mid; i++){
l1[i] = lists[i];
}
ListNode[] l2 = new ListNode[lists.length-mid];
for(int i = mid,j=0; i < lists.length; i++,j++){
l2[j] = lists[i];
}
return merge2Lists(mergeKLists(l1),mergeKLists(l2));
}
public ListNode merge2Lists(ListNode leftList, ListNode rightList) {
ListNode p = new ListNode(0);
ListNode cursor = p;
while (leftList != null && rightList != null) {
if (leftList.val < rightList.val) {
cursor.next = leftList;
leftList = leftList.next;
} else {
cursor.next = rightList;
rightList = rightList.next;
}
cursor = cursor.next;
}
if (leftList != null) {
cursor.next = leftList;
}
if (rightList != null) {
cursor.next = rightList;
}
return p.next;
}
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
TreeNode node = null;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left == null) {
return right;
} else if (right == null) {
return left;
} else {
return root;
}
}
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
List<List<Integer>> orderList = new ArrayList<>();
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
if (root == null) return orderList;
zigzagLevelOrder(root, 0);
return orderList;
}
public void zigzagLevelOrder(TreeNode root, int level) {
if (orderList.size() == level) {
List<Integer> orders = new ArrayList<>();
orderList.add(orders);
}
if (level % 2 == 0) {
orderList.get(level).add(root.val);
} else {
orderList.get(level).add(0, root.val);
}
if (root.left != null) {
zigzagLevelOrder(root.left, level + 1);
}
if (root.right != null) {
zigzagLevelOrder(root.right, level + 1);
}
}
}
7.6.4 动态或贪心
class Solution {
public int maxProfit(int[] prices) {
if (prices.length <= 1) return 0;
int length = prices.length;
int diff[] = new int[length - 1];
for (int i = 0; i < length - 1; i++) {
diff[i] = prices[i + 1] - prices[i];
}
int dp[] = new int [length];
dp[0] = 0;
int maxProfit = 0;
for (int i = 1; i < length; i++) {
if (dp[i - 1] + diff[i - 1] < diff[i - 1]) {
dp[i] = diff[i - 1];
} else {
dp[i] = dp[i - 1] + diff[i - 1];
}
maxProfit = Math.max(maxProfit, dp[i]);
}
return maxProfit;
}
}
- 最大子序和(给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例:
输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。)
class Solution {
public int maxSubArray(int[] nums) {
if (nums == null || nums.length == 0) return -1;
int length = nums.length;
int[] dp = new int[length];
dp[0] = nums[0];
int maxSum = dp[0];
for (int i = 1; i < length; i++) {
if (dp[i - 1] + nums[i] < nums[i]) {
dp[i] = nums[i];
} else {
dp[i] = nums[i] + dp[i - 1];
}
maxSum = Math.max(maxSum, dp[i]);
}
return maxSum;
}
}
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int dp[] = new int[triangle.size() + 1];
for (int i = triangle.size() - 1;i >= 0;i--) {
for (int j = 0; j < triangle.get(i).size(); j++) {
dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);
}
}
return dp[0];
}
}