赞
踩
给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
示例:
public static int maxSubArray(int[] nums) { if (nums == null || nums.length == 0) { throw new IllegalArgumentException("Array is empty"); } int n = nums.length; int[] dp = new int[n]; dp[0] = nums[0]; int maxSum = dp[0]; for (int i = 1; i < n; i++) { dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]); maxSum = Math.max(maxSum, dp[i]); } return maxSum; }
以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。
示例:
public static int[][] merge(int[][] intervals) { if (intervals == null || intervals.length == 0) { return new int[0][0]; } // Sort intervals by starting time Arrays.sort(intervals, Comparator.comparingInt(a -> a[0])); List<int[]> merged = new LinkedList<>(); int[] currentInterval = intervals[0]; merged.add(currentInterval); for (int i = 1; i < intervals.length; i++) { int[] interval = intervals[i]; // If the current interval overlaps with the new interval if (currentInterval[1] >= interval[0]) { // Merge the current interval with the new interval currentInterval[1] = Math.max(currentInterval[1], interval[1]); } else { // If no overlap, add the current interval to the result // and start a new interval currentInterval = interval; merged.add(currentInterval); } } return merged.toArray(new int[merged.size()][]); }
给定一个整数数组 nums,将数组中的元素向右轮转 k 个位置,其中 k 是非负数。
示例:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]
public class ArrayRotation { // 向右轮转数组 public static void rotate(int[] nums, int k) { int n = nums.length; if (n == 0 || k % n == 0) { return; // 如果数组为空或 k 是数组长度的倍数,则不需要旋转 } k = k % n; // 处理 k 大于数组长度的情况 reverse(nums, 0, n - 1); // 反转整个数组 reverse(nums, 0, k - 1); // 反转前 k 个元素 reverse(nums, k, n - 1); // 反转后 n - k 个元素 } // 反转数组的部分 private static void reverse(int[] nums, int start, int end) { while (start < end) { int temp = nums[start]; nums[start] = nums[end]; nums[end] = temp; start++; end--; } } }
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法,且在 O(n) 时间复杂度内完成此题。
示例:
public class ProductArray { // 计算除自身以外的数组乘积 public static int[] productExceptSelf(int[] nums) { int n = nums.length; int[] leftProducts = new int[n]; int[] rightProducts = new int[n]; int[] result = new int[n]; // 计算左侧乘积 leftProducts[0] = 1; for (int i = 1; i < n; i++) { leftProducts[i] = leftProducts[i - 1] * nums[i - 1]; } // 计算右侧乘积 rightProducts[n - 1] = 1; for (int i = n - 2; i >= 0; i--) { rightProducts[i] = rightProducts[i + 1] * nums[i + 1]; } // 计算结果数组 for (int i = 0; i < n; i++) { result[i] = leftProducts[i] * rightProducts[i]; } return result; } }
给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。
示例:
public static int firstMissingPositive(int[] nums) { int n = nums.length; // 标记所有小于等于 0 或大于 n 的数为 n + 1 for (int i = 0; i < n; i++) { if (nums[i] <= 0 || nums[i] > n) { nums[i] = n + 1; } } // 将每个正整数映射到对应的索引位置 for (int i = 0; i < n; i++) { int num = Math.abs(nums[i]); if (num <= n) { nums[num - 1] = -Math.abs(nums[num - 1]); } } // 查找第一个未出现的正整数 for (int i = 0; i < n; i++) { if (nums[i] > 0) { return i + 1; } } // 如果所有 1 到 n 的正整数都出现了,则返回 n + 1 return n + 1; }
给定一个 m x n 的矩阵,如果一个元素为 0 ,则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
示例:
public class MatrixZeroes { public static void setZeroes(int[][] matrix) { if (matrix == null || matrix.length == 0) { return; } int m = matrix.length; int n = matrix[0].length; boolean firstRowZero = false; boolean firstColZero = false; // Check if the first row needs to be zeroed for (int j = 0; j < n; j++) { if (matrix[0][j] == 0) { firstRowZero = true; break; } } // Check if the first column needs to be zeroed for (int i = 0; i < m; i++) { if (matrix[i][0] == 0) { firstColZero = true; break; } } // Use the first row and first column as markers for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (matrix[i][j] == 0) { matrix[i][0] = 0; // Mark the row matrix[0][j] = 0; // Mark the column } } } // Zero out cells based on markers in the first row and first column for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (matrix[i][0] == 0 || matrix[0][j] == 0) { matrix[i][j] = 0; } } } // Zero out the first row if needed if (firstRowZero) { for (int j = 0; j < n; j++) { matrix[0][j] = 0; } } // Zero out the first column if needed if (firstColZero) { for (int i = 0; i < m; i++) { matrix[i][0] = 0; } } } }
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像,这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
示例:
public void rotate(int[][] matrix) { int n = matrix.length; // Step 1: 转置矩阵 for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { // 交换 matrix[i][j] 和 matrix[j][i] int temp = matrix[i][j]; matrix[i][j] = matrix[j][i]; matrix[j][i] = temp; } } // Step 2: 反转每一行 for (int i = 0; i < n; i++) { for (int j = 0; j < n / 2; j++) { // 交换 matrix[i][j] 和 matrix[i][n-1-j] int temp = matrix[i][j]; matrix[i][j] = matrix[i][n - 1 - j]; matrix[i][n - 1 - j] = temp; } } }
整数数组 nums 按升序排列,数组中的值 互不相同 。
在传递给函数之前,nums 在预先未知的某个下标 k(0 <= k < nums.length)上进行了 旋转,使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]](下标 从 0 开始 计数)。例如, [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ,如果 nums 中存在这个目标值 target ,则返回它的下标,否则返回 -1 。
示例:
class Solution { public int search(int[] nums, int target) { int left = 0; int right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; // 找到目标值 if (nums[mid] == target) { return mid; } // 判断哪一部分是有序的 if (nums[left] <= nums[mid]) { // 左侧有序 if (nums[left] <= target && target < nums[mid]) { right = mid - 1; // 目标在左侧 } else { left = mid + 1; // 目标在右侧 } } else { // 右侧有序 if (nums[mid] < target && target <= nums[right]) { left = mid + 1; // 目标在右侧 } else { right = mid - 1; // 目标在左侧 } } } return -1; // 未找到目标值 } }
已知一个长度为 n 的数组,预先按照升序排列,经由 1 到 n 次 旋转 后,得到输入数组。例如,原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到:
若旋转 4 次,则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次,则可以得到 [0,1,2,4,5,6,7]
注意,数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ,它原来是一个升序排列的数组,并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例:
class Solution { public int findMin(int[] nums) { int left = 0; int right = nums.length - 1; while (left < right) { int mid = left + (right - left) / 2; // 比较中间值与右边界值 if (nums[mid] > nums[right]) { // 最小值在 mid 右侧 left = mid + 1; } else { // 最小值在 mid 左侧或 mid 即为最小值 right = mid; } } // 最终 left == right,即为最小值 return nums[left]; } }
给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target,返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例:
class Solution { private static int findFirstPosition(int[] nums, int target) { int left = 0; int right = nums.length - 1; int result = -1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { result = mid; right = mid - 1; // 继续向左查找 } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return result; } // 查找目标值在数组中的结束位置 private static int findLastPosition(int[] nums, int target) { int left = 0; int right = nums.length - 1; int result = -1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { result = mid; left = mid + 1; // 继续向右查找 } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return result; } // 主方法,返回目标值的开始位置和结束位置 public static int[] searchRange(int[] nums, int target) { int[] result = new int[2]; result[0] = findFirstPosition(nums, target); result[1] = findLastPosition(nums, target); return result; } }
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例:
class Solution { public int searchInsert(int[] nums, int target) { int left = 0; int right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return left; } }
已知一个长度为 n 的数组,预先按照升序排列,经由 1 到 n 次 旋转 后,得到输入数组。例如,原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到:
若旋转 4 次,则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次,则可以得到 [0,1,2,4,5,6,7]
示例:
class Solution { public int findMin(int[] nums) { int left = 0; int right = nums.length - 1; while (left < right) { int mid = left + (right - left) / 2; // 比较中间元素和右端元素 if (nums[mid] > nums[right]) { // 最小值在右半部分 left = mid + 1; } else { // 最小值在左半部分或者是 mid right = mid; } } // 最小值在 left 或 right 位置 return nums[left]; } }
给你一个 m 行 n 列的矩阵 matrix ,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。
示例:
public static List<Integer> spiralOrder(int[][] matrix) { List<Integer> result = new ArrayList<>(); if (matrix == null || matrix.length == 0) { return result; } int m = matrix.length; int n = matrix[0].length; int left = 0, right = n - 1, top = 0, bottom = m - 1; while (left <= right && top <= bottom) { // 从左到右遍历上边界 for (int i = left; i <= right; i++) { result.add(matrix[top][i]); } top++; // 上边界下移 // 从上到下遍历右边界 for (int i = top; i <= bottom; i++) { result.add(matrix[i][right]); } right--; // 右边界左移 // 确保还有下边界要遍历 if (top <= bottom) { // 从右到左遍历下边界 for (int i = right; i >= left; i--) { result.add(matrix[bottom][i]); } bottom--; // 下边界上移 } // 确保还有左边界要遍历 if (left <= right) { // 从下到上遍历左边界 for (int i = bottom; i >= top; i--) { result.add(matrix[i][left]); } left++; // 左边界右移 } } return result; }
给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
示例 1:
class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } public class Solution { public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode curr = head; while (curr != null) { ListNode temp = curr.next; // 保存下一个节点 curr.next = prev; // 当前节点的next指向前一个节点 prev = curr; // 前一个节点移到当前节点 curr = temp; // 当前节点移到下一个节点 } return prev; } }
给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。
示例:
public ListNode swapPairs(ListNode head) { // 1. 创建一个哑节点,简化边界情况处理 ListNode dummy = new ListNode(0); dummy.next = head; ListNode prev = dummy; while (prev.next != null && prev.next.next != null) { // 2. 标记要交换的两个节点 ListNode first = prev.next; ListNode second = prev.next.next; // 3. 交换节点 first.next = second.next; second.next = first; prev.next = second; // 4. 移动到下一个节点对 prev = first; } return dummy.next; }
给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。
示例:
public ListNode removeNthFromEnd(ListNode head, int n) { // 1. 创建一个哑节点,简化边界情况处理 ListNode dummy = new ListNode(0); dummy.next = head; ListNode first = dummy; ListNode second = dummy; // 2. 让 first 指针先移动 n+1 步 for (int i = 0; i < n + 1; i++) { first = first.next; } // 3. 同时移动 first 和 second 指针,直到 first 到达链表末尾 while (first != null) { first = first.next; second = second.next; } // 4. 删除倒数第 n 个节点 second.next = second.next.next; // 返回链表的头节点 return dummy.next; }
给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。
请你将两个数相加,并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例1:
public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummyHead = new ListNode(0); ListNode p = l1, q = l2, current = 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 = carry + x + y; carry = sum / 10; current.next = new ListNode(sum % 10); current = current.next; if (p != null) p = p.next; if (q != null) q = q.next; } if (carry > 0) { current.next = new ListNode(carry); } return dummyHead.next; }
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例1:
public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0); ListNode current = dummy; while (l1 != null && l2 != null) { if (l1.val < l2.val) { current.next = l1; l1 = l1.next; } else { current.next = l2; l2 = l2.next; } current = current.next; } if (l1 != null) { current.next = l1; } else { current.next = l2; } return dummy.next; }
给你一个链表数组,每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中,返回合并后的链表。
示例1:
示例2:
输入:lists = [[]]
输出:[]
public ListNode mergeKLists(ListNode[] lists) { PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val); // 初始化优先队列,将每个链表的第一个节点放入队列 for (ListNode list : lists) { if (list != null) { pq.add(list); } } ListNode dummy = new ListNode(0); ListNode current = dummy; // 处理优先队列中的节点 while (!pq.isEmpty()) { ListNode node = pq.poll(); current.next = node; current = current.next; if (node.next != null) { pq.add(node.next); } } return dummy.next; }
给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。
示例1:
public ListNode sortList(ListNode head) { // 基本情况:如果链表为空或只有一个节点 if (head == null || head.next == null) { return head; } // 找到链表的中点 ListNode mid = getMid(head); ListNode left = head; ListNode right = mid.next; mid.next = null; // 将链表分为两个部分 // 递归地对两个子链表进行排序 left = sortList(left); right = sortList(right); // 合并排序后的子链表 return merge(left, right); } private ListNode getMid(ListNode head) { ListNode slow = head; ListNode fast = head.next; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } return slow; } private ListNode merge(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0); ListNode current = dummy; while (l1 != null && l2 != null) { if (l1.val < l2.val) { current.next = l1; l1 = l1.next; } else { current.next = l2; l2 = l2.next; } current = current.next; } if (l1 != null) { current.next = l1; } else { current.next = l2; } return dummy.next; }
给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。
题目数据 保证 整个链式结构中不存在环。
示例1:
输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出:Intersected at ‘8’
public ListNode getIntersectionNode(ListNode headA, ListNode headB) { // Step 1: Calculate lengths of both lists int lenA = getLength(headA); int lenB = getLength(headB); // Step 2: Adjust starting points so that they start at the same distance from end while (lenA > lenB) { headA = headA.next; lenA--; } while (lenB > lenA) { headB = headB.next; lenB--; } // Step 3: Compare nodes until intersection or end while (headA != headB) { headA = headA.next; headB = headB.next; } // Either headA or headB is the intersection node, or null if no intersection return headA; } // Helper method to calculate length of a linked list private int getLength(ListNode node) { int length = 0; while (node != null) { length++; node = node.next; } return length; }
给你一个链表的头节点 head ,判断链表中是否有环,如果链表中存在环 ,则返回 true 。 否则,返回 false 。
示例1:
示例2:
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; }
给定一个链表的头节点 head ,返回链表开始入环的第一个节点。
如果链表无环,则返回 null。
示例1:
输入:head = [3,2,0,-4], pos = 1
输出:返回索引为 1 的链表节点
解释:链表中有一个环,其尾部连接到第二个节点。
示例2:
public ListNode detectCycle(ListNode head) { if (head == null || head.next == null) { return null; } ListNode slow = head; ListNode fast = head; boolean hasCycle = false; // Step 1: Determine if there is a cycle while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { hasCycle = true; break; } } // Step 2: If there is a cycle, find the start of the cycle if (hasCycle) { slow = head; while (slow != fast) { slow = slow.next; fast = fast.next; } return slow; // Both pointers meet at the start of the cycle } return null; // No cycle found }
给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false 。
示例1:
public boolean isPalindrome(ListNode head) { if (head == null || head.next == null) { return true; } // Step 1: Find the middle of the linked list ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } // Step 2: Reverse the second half of the list ListNode secondHalfStart = reverseList(slow); // Step 3: Compare the first half and the reversed second half ListNode firstHalfStart = head; ListNode secondHalfCopy = secondHalfStart; while (secondHalfStart != null) { if (firstHalfStart.val != secondHalfStart.val) { return false; } firstHalfStart = firstHalfStart.next; secondHalfStart = secondHalfStart.next; } // Optional Step 4: Restore the list reverseList(secondHalfCopy); return true; } private ListNode reverseList(ListNode head) { ListNode prev = null; while (head != null) { ListNode next = head.next; head.next = prev; prev = head; head = next; } return prev; }
给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。
请你将两个数相加,并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例1:
示例2:
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 = carry + x + y; 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; }
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例1:
示例2:
public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummyHead = new ListNode(0); ListNode curr = dummyHead; while (l1 != null && l2 != null) { if (l1.val <= l2.val) { curr.next = l1; l1 = l1.next; } else { curr.next = l2; l2 = l2.next; } curr = curr.next; } // If either l1 or l2 still has remaining elements if (l1 != null) { curr.next = l1; } else { curr.next = l2; } return dummyHead.next; }
给你链表的头节点 head ,每 k 个节点一组进行翻转,请你返回修改后的链表。
k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。
示例1:
class Solution { private static ListNode reverseList(ListNode head, int k) { ListNode prev = null; ListNode curr = head; ListNode next = null; while (k > 0) { next = curr.next; curr.next = prev; prev = curr; curr = next; k--; } return prev; } // 计算链表的长度 private static int getLength(ListNode head) { int length = 0; ListNode current = head; while (current != null) { length++; current = current.next; } return length; } // 主函数,K 个一组翻转链表 public static ListNode reverseKGroup(ListNode head, int k) { if (head == null || k <= 1) { return head; } int length = getLength(head); ListNode dummy = new ListNode(0); dummy.next = head; ListNode prevGroupEnd = dummy; while (length >= k) { ListNode groupStart = prevGroupEnd.next; ListNode groupEnd = groupStart; for (int i = 1; i < k; i++) { groupEnd = groupEnd.next; } ListNode nextGroupStart = groupEnd.next; // 反转当前组 groupEnd.next = null; prevGroupEnd.next = reverseList(groupStart, k); groupStart.next = nextGroupStart; // 移动 prevGroupEnd prevGroupEnd = groupStart; length -= k; } return dummy.next; } }
给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。
示例:
class Solution { // 复制链表 public Node copyRandomList(Node head) { if (head == null) { return null; } // 第一遍遍历:为每个节点创建一个新节点,并将新节点插入到原节点之后 Node current = head; while (current != null) { Node newNode = new Node(current.val); newNode.next = current.next; current.next = newNode; current = newNode.next; } // 第二遍遍历:设置新节点的 random 指针 current = head; while (current != null) { Node newNode = current.next; newNode.random = (current.random != null) ? current.random.next : null; current = newNode.next; } // 第三遍遍历:分离原链表和复制链表 Node oldHead = head; Node newHead = head.next; Node newCurrent = newHead; while (oldHead != null) { oldHead.next = newCurrent.next; oldHead = oldHead.next; if (oldHead != null) { newCurrent.next = oldHead.next; newCurrent = newCurrent.next; } } return newHead; } }
给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。
示例1:
public List<Integer> inorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); TreeNode current = root; while (current != null || !stack.isEmpty()) { // Reach the left most TreeNode while (current != null) { stack.push(current); current = current.left; } // Current must be null at this point current = stack.pop(); result.add(current.val); // Add the node value to the result current = current.right; // Visit the right subtree } return result; }
给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。
示例1:
public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if (root == null) return result; Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { int levelSize = queue.size(); List<Integer> currentLevel = new ArrayList<>(); for (int i = 0; i < levelSize; i++) { TreeNode currentNode = queue.poll(); currentLevel.add(currentNode.val); if (currentNode.left != null) { queue.add(currentNode.left); } if (currentNode.right != null) { queue.add(currentNode.right); } } result.add(currentLevel); } return result; }
给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。
示例1:
public boolean isValidBST(TreeNode root) { if (root == null) return true; Stack<TreeNode> stack = new Stack<>(); TreeNode prev = null; while (root != null || !stack.isEmpty()) { while (root != null) { stack.push(root); root = root.left; } root = stack.pop(); // Check current node's value with previous node if (prev != null && root.val <= prev.val) { return false; } prev = root; root = root.right; } return true; }
给你一个二叉树的根节点 root , 检查它是否轴对称。
示例1:
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
return isMirror(root.left, root.right);
}
private boolean isMirror(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) return true;
if (t1 == null || t2 == null) return false;
return (t1.val == t2.val)
&& isMirror(t1.right, t2.left)
&& isMirror(t1.left, t2.right);
}
给你一个二叉树的根节点 root ,返回其 最大路径和 。
路径和 是路径中各节点值的总和。
示例1:
int maxSum = Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { maxPathSumRecursive(root); return maxSum; } private int maxPathSumRecursive(TreeNode node) { if (node == null) return 0; // 计算左右子树的最大路径和,如果小于0则置0 int leftSum = Math.max(maxPathSumRecursive(node.left), 0); int rightSum = Math.max(maxPathSumRecursive(node.right), 0); // 当前节点作为根节点的最大路径和 int currentMax = node.val + leftSum + rightSum; // 更新全局最大路径和 maxSum = Math.max(maxSum, currentMax); // 返回以当前节点为根节点的最大路径和(只能选左子树或右子树的一条路径) return node.val + Math.max(leftSum, rightSum); }
给你一棵二叉树的根节点 root ,翻转这棵二叉树,并返回其根节点。
示例1:
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
// 递归翻转左右子树
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
// 交换左右子节点
root.left = right;
root.right = left;
return root;
}
给你二叉树的根结点 root ,请你将它展开为一个单链表:
示例1:
public void flatten(TreeNode root) { if (root == null) { return; } // 递归展开左子树和右子树 flatten(root.left); flatten(root.right); // 保存右子树 TreeNode rightSubtree = root.right; // 将左子树移到右子树位置 root.right = root.left; root.left = null; // 找到新的右子树的末端 TreeNode current = root; while (current.right != null) { current = current.right; } // 将保存的右子树接到末端 current.right = rightSubtree; }
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。
示例:
class Solution { public void sortColors(int[] nums) { int low = 0, mid = 0, high = nums.length - 1; while (mid <= high) { if (nums[mid] == 0) { // Swap nums[low] and nums[mid] int temp = nums[low]; nums[low] = nums[mid]; nums[mid] = temp; low++; mid++; } else if (nums[mid] == 1) { mid++; } else { // Swap nums[mid] and nums[high] int temp = nums[mid]; nums[mid] = nums[high]; nums[high] = temp; high--; } } } }
给定一个大小为 n 的数组 nums ,返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
示例:
class Solution { public int majorityElement(int[] nums) { int candidate = findCandidate(nums); return candidate; } private int findCandidate(int[] nums) { int candidate = nums[0]; int count = 1; for (int i = 1; i < nums.length; i++) { if (nums[i] == candidate) { count++; } else { count--; if (count == 0) { candidate = nums[i]; count = 1; } } } return candidate; } }
给定两个字符串 text1 和 text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0 。
例如,“ace” 是 “abcde” 的子序列,但 “aec” 不是 “abcde” 的子序列。
示例:
class Solution { public int longestCommonSubsequence(String text1, String text2) { int m = text1.length(); int n = text2.length(); // 创建动态规划表 int[][] dp = new int[m + 1][n + 1]; // 填充动态规划表 for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (text1.charAt(i - 1) == text2.charAt(j - 1)) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); } } } // 返回最长公共子序列的长度 return dp[m][n]; } }
给你一个整数 n ,返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1、4、9 和 16 都是完全平方数,而 3 和 11 不是。
示例:
public class PerfectSquares { // 计算和为 n 的完全平方数的最少数量 public static int numSquares(int n) { if (n <= 0) { return 0; } // 初始化动态规划数组 int[] dp = new int[n + 1]; // 填充 dp 数组,初始值为最大值 n + 1 for (int i = 1; i <= n; i++) { dp[i] = Integer.MAX_VALUE; } // 计算 dp[i] 的值 for (int i = 1; i <= n; i++) { for (int j = 1; j * j <= i; j++) { dp[i] = Math.min(dp[i], dp[i - j * j] + 1); } } return dp[n]; } }
给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。
示例:
public class CoinChange { // 计算组成金额 amount 的最少硬币数量 public static int coinChange(int[] coins, int amount) { // 动态规划数组 int[] dp = new int[amount + 1]; // 初始化动态规划数组,初始值为最大值 amount + 1 for (int i = 1; i <= amount; i++) { dp[i] = amount + 1; } dp[0] = 0; // 组成金额 0 不需要硬币 // 填充动态规划数组 for (int i = 1; i <= amount; i++) { for (int coin : coins) { if (i - coin >= 0) { dp[i] = Math.min(dp[i], dp[i - coin] + 1); } } } // 返回结果 return dp[amount] > amount ? -1 : dp[amount]; } }
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。
示例:
public class WordBreak { // 判断字符串 s 是否可以由字典中的单词拼接而成 public static boolean wordBreak(String s, Set<String> wordDict) { int n = s.length(); // 动态规划数组 boolean[] dp = new boolean[n + 1]; dp[0] = true; // 空字符串可以被认为是由字典中的单词拼接而成 // 填充动态规划数组 for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) { if (dp[j] && wordDict.contains(s.substring(j, i))) { dp[i] = true; break; // 找到一个有效的拆分后就可以停止 } } } // 返回结果 return dp[n]; } }
给你一个整数数组 nums ,请你找出数组中乘积最大的非空连续
子数组
(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。
示例:
class Solution { // 找出数组中乘积最大的非空连续子数组 public int maxProduct(int[] nums) { if (nums.length == 0) return 0; // 初始化动态规划变量 int maxEndingHere = nums[0]; int minEndingHere = nums[0]; int globalMax = nums[0]; // 遍历数组更新动态规划变量 for (int i = 1; i < nums.length; i++) { int num = nums[i]; // 计算当前元素可能的最大乘积和最小乘积 int tempMax = Math.max(num, Math.max(num * maxEndingHere, num * minEndingHere)); minEndingHere = Math.min(num, Math.min(num * maxEndingHere, num * minEndingHere)); maxEndingHere = tempMax; // 更新全局最大乘积 globalMax = Math.max(globalMax, maxEndingHere); } return globalMax; } }
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
问总共有多少条不同的路径?
示例:
class Solution { public int uniquePaths(int m, int n) { // 创建一个动态规划数组 int[][] dp = new int[m][n]; // 初始化第一行和第一列 for (int i = 0; i < m; i++) { dp[i][0] = 1; // 第一列只有一种路径,即一直向下 } for (int j = 0; j < n; j++) { dp[0][j] = 1; // 第一行只有一种路径,即一直向右 } // 填充动态规划数组 for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } // 返回右下角的路径数量 return dp[m - 1][n - 1]; } }
给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
说明:每次只能向下或者向右移动一步。
示例:
输入:grid = [[1,3,1],[1,5,1],[4,2,1]]
输出:7
解释:因为路径 1→3→1→1→1 的总和最小。
class Solution { // 计算从左上角到右下角的最小路径和 public int minPathSum(int[][] grid) { if (grid == null || grid.length == 0 || grid[0].length == 0) { return 0; } int m = grid.length; int n = grid[0].length; // 创建一个动态规划数组 int[][] dp = new int[m][n]; // 初始化动态规划数组 dp[0][0] = grid[0][0]; // 初始化第一行 for (int j = 1; j < n; j++) { dp[0][j] = dp[0][j - 1] + grid[0][j]; } // 初始化第一列 for (int i = 1; i < m; i++) { dp[i][0] = dp[i - 1][0] + grid[i][0]; } // 填充动态规划数组 for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]); } } // 返回右下角的最小路径和 return dp[m - 1][n - 1]; } }
给你一个字符串 s,找到 s 中最长的 回文子串。
示例:
class Solution { // 找到字符串中的最长回文子串 public static String longestPalindrome(String s) { if (s == null || s.length() == 0) { return ""; } int start = 0; // 最长回文子串的起始索引 int maxLength = 1; // 最长回文子串的长度 for (int i = 0; i < s.length(); i++) { // 以 s[i] 为中心的回文子串 String pal1 = expandAroundCenter(s, i, i); // 以 s[i] 和 s[i+1] 之间的间隙为中心的回文子串 String pal2 = expandAroundCenter(s, i, i + 1); // 选择更长的回文子串 String longerPal = pal1.length() > pal2.length() ? pal1 : pal2; if (longerPal.length() > maxLength) { maxLength = longerPal.length(); start = s.indexOf(longerPal); } } return s.substring(start, start + maxLength); } // 扩展回文中心 private static String expandAroundCenter(String s, int left, int right) { while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) { left--; right++; } return s.substring(left + 1, right); } }
给你两个单词 word1 和 word2, 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作:
插入一个字符
删除一个字符
替换一个字符
示例:
class Solution { public static int minDistance(String word1, String word2) { int m = word1.length(); int n = word2.length(); // 创建动态规划数组 int[][] dp = new int[m + 1][n + 1]; // 初始化 dp 数组 for (int i = 0; i <= m; i++) { dp[i][0] = i; // 删除操作 } for (int j = 0; j <= n; j++) { dp[0][j] = j; // 插入操作 } // 填充动态规划数组 for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (word1.charAt(i - 1) == word2.charAt(j - 1)) { dp[i][j] = dp[i - 1][j - 1]; // 字符相同,不需要额外操作 } else { dp[i][j] = Math.min(Math.min(dp[i - 1][j] + 1, // 删除操作 dp[i][j - 1] + 1), // 插入操作 dp[i - 1][j - 1] + 1); // 替换操作 } } } // 返回将 word1 转换成 word2 的最小操作数 return dp[m][n]; } }
给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例:
class Solution { public int[] topKFrequent(int[] nums, int k) { // 统计每个元素的频率 Map<Integer, Integer> frequencyMap = new HashMap<>(); for (int num : nums) { frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1); } // 使用优先队列(最小堆)来维护前 k 个频率最高的元素 PriorityQueue<Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<>( (a, b) -> a.getValue() - b.getValue() ); for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) { minHeap.add(entry); if (minHeap.size() > k) { minHeap.poll(); // 移除频率最低的元素 } } // 将优先队列中的元素取出并放入结果数组 int[] result = new int[k]; for (int i = 0; i < k; i++) { result[i] = minHeap.poll().getKey(); } return result; } }
给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。
请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例:
class Solution { private static final Random rand = new Random(); public static int findKthLargest(int[] nums, int k) { int n = nums.length; return quickSelect(nums, 0, n - 1, n - k); } private static int quickSelect(int[] nums, int left, int right, int index) { if (left == right) { return nums[left]; } int pivotIndex = partition(nums, left, right); if (pivotIndex == index) { return nums[pivotIndex]; } else if (pivotIndex < index) { return quickSelect(nums, pivotIndex + 1, right, index); } else { return quickSelect(nums, left, pivotIndex - 1, index); } } private static int partition(int[] nums, int left, int right) { int pivotIndex = left + rand.nextInt(right - left + 1); int pivotValue = nums[pivotIndex]; swap(nums, pivotIndex, right); int storeIndex = left; for (int i = left; i < right; i++) { if (nums[i] < pivotValue) { swap(nums, storeIndex, i); storeIndex++; } } swap(nums, storeIndex, right); return storeIndex; } private static void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } }
给定一个整数数组 temperatures ,表示每天的温度,返回一个数组 answer ,其中 answer[i] 是指对于第 i 天,下一个更高温度出现在几天后。如果气温在这之后都不会升高,请在该位置用 0 来代替。
示例:
class Solution { public int[] dailyTemperatures(int[] temperatures) { int n = temperatures.length; int[] answer = new int[n]; Stack<Integer> stack = new Stack<>(); for (int i = 0; i < n; i++) { while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) { int index = stack.pop(); answer[index] = i - index; } stack.push(i); } return answer; } }
设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
示例:
输入:
[“MinStack”,“push”,“push”,“push”,“getMin”,“pop”,“top”,“getMin”]
[[],[-2],[0],[-3],[],[],[],[]]
输出:
[null,null,null,null,-3,null,0,-2]
class MinStack { private Stack<Integer> stack; private Stack<Integer> minStack; public MinStack() { stack = new Stack<>(); minStack = new Stack<>(); } public void push(int val) { stack.push(val); if (minStack.isEmpty() || val <= minStack.peek()) { minStack.push(val); } else { minStack.push(minStack.peek()); } } public void pop() { stack.pop(); minStack.pop(); } public int top() { return stack.peek(); } public int getMin() { return minStack.peek(); } }
给定一个只包括 ‘(’,‘)’,‘{’,‘}’,‘[’,‘]’ 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
示例:
class Solution { public boolean isValid(String s) { // 使用栈来存放左括号 Stack<Character> stack = new Stack<>(); // 遍历字符串中的每个字符 for (char c : s.toCharArray()) { // 如果是左括号,压入栈中 if (c == '(' || c == '{' || c == '[') { stack.push(c); } // 如果是右括号,检查栈顶是否是对应的左括号 else if (c == ')' && !stack.isEmpty() && stack.peek() == '(') { stack.pop(); } else if (c == '}' && !stack.isEmpty() && stack.peek() == '{') { stack.pop(); } else if (c == ']' && !stack.isEmpty() && stack.peek() == '[') { stack.pop(); } else { // 如果不匹配或者栈为空,则字符串无效 return false; } } // 如果栈为空,则字符串有效 return stack.isEmpty(); } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。