赞
踩
线段树(Segment Tree)是一种用于处理区间查询和更新问题的数据结构,特别是在需要对连续区间进行操作时非常有效。线段树可以快速地对区间求和、求最小值/最大值、判断某个值的存在性等问题进行响应。
class SegmentTree { private int[] tree; private int n; public SegmentTree(int[] nums) { if (nums.length > 0) { n = nums.length; tree = new int[n * 4]; build(nums, 0, 0, n - 1); } } private void build(int[] nums, int treeIndex, int left, int right) { if (left == right) { tree[treeIndex] = nums[left]; return; } int mid = left + (right - left) / 2; build(nums, 2 * treeIndex + 1, left, mid); build(nums, 2 * treeIndex + 2, mid + 1, right); tree[treeIndex] = tree[2 * treeIndex + 1] + tree[2 * treeIndex + 2]; } public int query(int left, int right) { return query(0, 0, n - 1, left, right); } private int query(int treeIndex, int start, int end, int left, int right) { if (left > end || start > end) { return 0; } if (start >= left && end <= right) { return tree[treeIndex]; } int mid = start + (end - start) / 2; return query(2 * treeIndex + 1, start, mid, left, right) + query(2 * treeIndex + 2, mid + 1, end, left, right); } public void update(int index, int val) { update(0, 0, n - 1, index, val); } private void update(int treeIndex, int start, int end, int index, int val) { if (start == end) { tree[treeIndex] = val; return; } int mid = start + (end - start) / 2; if (index <= mid) { update(2 * treeIndex + 1, start, mid, index, val); } else { update(2 * treeIndex + 2, mid + 1, end, index, val); } tree[treeIndex] = tree[2 * treeIndex + 1] + tree[2 * treeIndex + 2]; } }
区间求和:
描述:给定一个整数数组和一个区间列表,对于每个区间,计算其内所有元素的和。
示例:
输入: nums = [1, 3, 5, 7, 9, 11], intervals = [[1, 3], [2, 5], [1, 1]]
输出: [16, 15, 3]
区间最小值:
描述:给定一个整数数组和一个区间列表,对于每个区间,找到其中的最小值。
示例:
输入: nums = [3, 4, 5, 1, 6, 2], intervals = [[2, 3], [1, 3], [0, 5]]
输出: [5, 1, 2]
区间更新:
描述:给定一个整数数组和一个更新操作列表,对于每个更新操作,将其应用到数组的指定区间。
示例:
输入: nums = [1, 3, 5, 7, 9, 11], updates = [[1, 2, 10], [3, 4, 20], [5, 5, 30]]
输出: [10, 13, 15, 30, 9, 11]
这些题目和源码展示了线段树在解决实际问题中的应用。在面试中,能够根据问题的特点选择合适的算法并实现其解决方案是非常重要的。希望这些示例能够帮助你更好地准备面试!线段树是一种高效的数据结构,特别适合处理区间查询和更新问题。以下是三道可能出现在大厂面试中的与线段树相关的编程题目,以及相应的Java源码实现。
描述:
给定一个整数数组和一个区间列表,对于每个区间,计算其内所有元素的和。
示例:
输入: nums = [1, 3, 5, 7, 9, 11], intervals = [[1, 3], [2, 5], [1, 1]]
输出: [16, 15, 3]
Java 源码:
public class IntervalSumQuery { private int[] tree; private int n; public IntervalSumQuery(int[] nums) { n = nums.length; tree = new int[n * 4]; buildTree(nums, 0, 0, n - 1); } private void buildTree(int[] nums, int treeIndex, int start, int end) { if (start == end) { tree[treeIndex] = nums[start]; return; } int mid = start + (end - start) / 2; buildTree(nums, 2 * treeIndex + 1, start, mid); buildTree(nums, 2 * treeIndex + 2, mid + 1, end); tree[treeIndex] = tree[2 * treeIndex + 1] + tree[2 * treeIndex + 2]; } public int query(int start, int end) { return query(0, 0, n - 1, start, end); } private int query(int treeIndex, int start, int end, int qStart, int qEnd) { if (qStart > qEnd || start > qEnd || end < qStart) { return 0; } if (start >= qStart && end <= qEnd) { return tree[treeIndex]; } int mid = start + (end - start) / 2; int left = query(2 * treeIndex + 1, start, mid, qStart, qEnd); int right = query(2 * treeIndex + 2, mid + 1, end, qStart, qEnd); return left + right; } public static void main(String[] args) { IntervalSumQuery query = new IntervalSumQuery(new int[]{1, 3, 5, 7, 9, 11}); int[] intervals = {{1, 3}, {2, 5}, {1, 1}}; int[] results = new int[intervals.length]; for (int i = 0; i < intervals.length; i++) { results[i] = query.intervalSumQuery(intervals[i][0], intervals[i][1]); System.out.println("Sum of interval " + Arrays.toString(intervals[i]) + ": " + results[i]); } } }
描述:
给定一个整数数组和一个区间列表,找到每个区间内的最小值。
示例:
输入: nums = [3, 4, 5, 1, 6, 2], intervals = [[2, 3], [1, 3], [0, 5]]
输出: [5, 1, 2]
Java 源码:
public class IntervalMinQuery { private int[] tree; private int n; public IntervalMinQuery(int[] nums) { n = nums.length; tree = new int[n * 4]; buildTree(nums, 0, 0, n - 1); } private void buildTree(int[] nums, int treeIndex, int start, int end) { if (start == end) { tree[treeIndex] = nums[start]; return; } int mid = start + (end - start) / 2; buildTree(nums, 2 * treeIndex + 1, start, mid); buildTree(nums, 2 * treeIndex + 2, mid + 1, end); tree[treeIndex] = Math.min(tree[2 * treeIndex + 1], tree[2 * treeIndex + 2]); } public int query(int start, int end) { return query(0, 0, n - 1, start, end); } private int query(int treeIndex, int start, int end, int qStart, int qEnd) { if (qStart > qEnd || start > qEnd || end < qStart) { return Integer.MAX_VALUE; } if (start >= qStart && end <= qEnd) { return tree[treeIndex]; } int mid = start + (end - start) / 2; int left = query(2 * treeIndex + 1, start, mid, qStart, qEnd); int right = query(2 * treeIndex + 2, mid + 1, end, qStart, qEnd); return Math.min(left, right); } public static void main(String[] args) { IntervalMinQuery query = new IntervalMinQuery(new int[]{3, 4, 5, 1, 6, 2}); int[] intervals = {{2, 3}, {1, 3}, {0, 5}}; int[] results = new int[intervals.length]; for (int i = 0; i < intervals.length; i++) { results[i] = query.intervalMinQuery(intervals[i][0], intervals[i][1]); System.out.println("Minimum of interval " + Arrays.toString(intervals[i]) + ": " + results[i]); } } }
描述:
给定一个整数数组和一个更新操作列表,对于每个更新操作,将其应用到数组的指定区间。
示例:
输入: nums = [1, 3, 5, 7, 9, 11], updates = [[1, 2, 10], [3, 4, 20], [5, 5, 30]]
输出: [10, 13, 15, 30, 9, 11]
Java 源码:
public class IntervalUpdate { private int[] tree; private int n; public IntervalUpdate(int[] nums) { n = nums.length; tree = new int[n * 4]; buildTree(nums, 0, 0, n - 1); } private void buildTree(int[] nums, int treeIndex, int start, int end) { if (start == end) { tree[treeIndex] = nums[start]; return; } int mid = start + (end - start) / 2; buildTree(nums, 2 * treeIndex + 1, start, mid); buildTree(nums, 2 * treeIndex + 2, mid + 1, end); tree[treeIndex] = tree[2 * treeIndex + 1] + tree[2 * treeIndex + 2]; } public void update(int start, int end, int val) { update(0, 0, n - 1, start, end, val); } private void update(int treeIndex, int start, int end, int qStart, int qEnd, int val) { if (qStart > qEnd || start > qEnd || end < qStart) { return; } if (start >= qStart && end <= qEnd) { tree[treeIndex] = val; return; } int mid = start + (end - start) / 2; update(2 * treeIndex + 1, start, mid, qStart, qEnd, val); update(2 * treeIndex + 2, mid + 1, end, qStart, qEnd, val); tree[treeIndex] = tree[2 * treeIndex + 1] + tree[2 * treeIndex + 2]; } public static void main(String[] args) { IntervalUpdate update = new IntervalUpdate(new int[]{1, 3, 5, 7, 9, 11}); int[][] updates = {{1, 2, 10}, {3, 4, 20}, {5, 5, 30}}; for (int[] update : updates) { update.update(update[0], update[1], update[2]); System.out.println("Array after update " + Arrays.toString(update) + ": " + Arrays.toString(update.getArray())); } } }
这些题目和源码展示了线段树在解决实际问题中的应用。在面试中,能够根据问题的特点选择合适的算法并实现其解决方案是非常重要的。希望这些示例能够帮助你更好地准备面试!
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。