freeswitch 发update sip消息_LeetCode LCP 05——发 LeetCoin
生活随笔
收集整理的這篇文章主要介紹了
freeswitch 发update sip消息_LeetCode LCP 05——发 LeetCoin
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
關鍵字：線段樹
歸航return：(Trivial)LeetCode 1354——多次求和構造目標數(shù)組?zhuanlan.zhihu.com歸航return：(Trivial) LeetCode 84—柱狀圖中最大的矩形?zhuanlan.zhihu.comProblem
力扣決定給一個刷題團隊發(fā) LeetCoin 作為獎勵。同時，為了監(jiān)控給大家發(fā)了多少 LeetCoin，力扣有時候也會進行查詢。
該刷題團隊的管理模式可以用一棵樹表示：
力扣想進行的操作有以下三種：
輸入：
operations[i][0] = 1: 代表第一種操作，operations[i][1] 代表成員的編號，operations[i][2] 代表 LeetCoin 的數(shù)量；
operations[i][0] = 2: 代表第二種操作，operations[i][1]代表成員的編號，operations[i][2] 代表 LeetCoin 的數(shù)量；
operations[i][0] = 3: 代表第三種操作，operations[i][1] 代表成員的編號；
輸出：
返回一個數(shù)組，數(shù)組里是每次查詢的返回值（發(fā) LeetCoin 的操作不需要任何返回值）。由于發(fā)的 LeetCoin 很多，請把每次查詢的結果模 1e9+7 (1000000007)。
示例 1：
輸入：N = 6, leadership = [[1, 2], [1, 6], [2, 3], [2, 5], [1, 4]], operations = [[1, 1, 500], [2, 2, 50], [3, 1], [2, 6, 15], [3, 1]] 輸出：[650, 665] 解釋：團隊的管理關系見下圖。 第一次查詢時，每個成員得到的LeetCoin的數(shù)量分別為（按編號順序）：500, 50, 50, 0, 50, 0; 第二次查詢時，每個成員得到的LeetCoin的數(shù)量分別為（按編號順序）：500, 50, 50, 0, 50, 15.限制：
Solution
這里的問題就是區(qū)間修改，單點查詢，區(qū)間查詢，這類問題的正確解答，就是線段樹。但是我們還需要正確地確定一個節(jié)點和其后續(xù)的所有節(jié)點的正確編號，保證節(jié)點和其后代在線段樹的下標都是連續(xù)的。這個問題的解決方案就是利用樹的遍歷的先序遍歷來進行求解。為此，我們需要維護一個 dfs 時間戳，當我們第一次訪問到這個節(jié)點的時候，就對應的是節(jié)點的開始時間，完成先序遍歷的遞歸算法完畢返回之后的時間戳，就剛好是節(jié)點的對應時間。這種算法稱作 DFS 序。
C++ 風格的偽代碼如下：
void dfs(int idx, int& timeStamp){from[idx] = timeStamp;for (int next : adj[idx]){++timeStamp;dfs(next, timeStamp);}to[idx] = timeStamp; }當然，這里需要考慮下標問題，因此實際的實現(xiàn)中，我是將所有的坐標都減去 1，這樣就可以映射到
中，使用一個大小為 n 的數(shù)組即可。在這么處理之后，操作 1 對應的就是在 [from[people], from[people]] 單點修改，2 對應的就是 [from[people], to[people]] 上區(qū)間修改，操作 3 對應的就是在 [from[people], to[people]] 上區(qū)間查詢。起始時間點設定為 0，這樣可以方便處理后續(xù)線段樹的代碼問題。上述 test case 中，from 和 to 數(shù)組就是：
from: [0,1,2,5,3,4] 和 to: [5,3,2,5,3,4]
這么做之前，我們還需要維護一個臨接表，用于這個 dfs 操作：
vector<vector<int>> generateAdj(const vector<vector<int>>& leadership, int n){vector<vector<int>> adj(n);for (const auto & x : leadership){int src = x[0] - 1;int dst = x[1] - 1;adj[src].emplace_back(dst);}return adj; }注意，線段樹的底層原理我并不是很懂，所以不會詳細解釋線段樹的代碼原理，而是當作黑箱子直接使用。代碼如下：
class Solution {private int[] from;private int[] to;private List<Integer>[] adj;private int cnt;private static final int mod = (int)(1e9 + 7);public int[] bonus(int n, int[][] leadership, int[][] operations) {from = new int[n];to = new int[n];adj = new List[n];cnt = 0;int people = 0;int money = 0;for (int i = 0; i < n; ++i){adj[i] = new ArrayList<>();}for (int[] x : leadership){int src = x[0] - 1;int dst = x[1] - 1;adj[src].add(dst);}dfs(0);List<Integer> ans = new ArrayList<>();SegmentTree segmentTree = new SegmentTree(n);for (int[] operation : operations){switch (operation[0]){case (1):{people = operation[1] - 1;money = operation[2];segmentTree.update(from[people], from[people], money);break;}case (2):{people = operation[1] - 1;money = operation[2];segmentTree.update(from[people], to[people], money);break;}case (3):{people = operation[1] - 1;ans.add((int)(segmentTree.query(from[people], to[people]) % mod));break;}}}return ans.stream().mapToInt(i -> i).toArray();}private void dfs(int idx){from[idx] = cnt;for (int next : adj[idx]){++cnt;dfs(next);}to[idx] = cnt;} } class SegmentTree{private static class SegmentTreeSupport{private SegmentTreeSupport(){}public static int getLeftSon(int x){return x << 1;}public static int getRightSon(int x){return (x << 1) + 1;}public static int getFather(int x){if (x == 0){throw new IllegalArgumentException();}return x >> 1;}public final static int SEGMENT_TREE_FACTOR = 4;}private long[] tree, lazy;private final int length;private void rangeCheck(int index){if (index < 0 || index >= length){throw new IndexOutOfBoundsException(index);}}public SegmentTree(final int[] arr){if (arr == null || arr.length == 0){throw new IllegalArgumentException();}length = arr.length;tree = new long[SegmentTreeSupport.SEGMENT_TREE_FACTOR * length];lazy = new long[SegmentTreeSupport.SEGMENT_TREE_FACTOR * length];buildTree(arr, 0, length - 1, 1);}public SegmentTree(int n){this(new int[n]);}private void buildTree(final int[] arr, int fromIndex, int toIndex, int treeIndex){if (fromIndex == toIndex){tree[treeIndex] = arr[fromIndex];return;}int midIndex = (fromIndex + toIndex) >>> 1;buildTree(arr, fromIndex, midIndex, SegmentTreeSupport.getLeftSon(treeIndex));buildTree(arr, midIndex + 1, toIndex, SegmentTreeSupport.getRightSon(treeIndex));collectSubMsgTo(treeIndex);}private void collectSubMsgTo(int treeIndex){//this line should be replaced by the function we want to maintain//that is: tree[treeIndex] = f(tree[leftIndex], tree[rightIndex])//if we want to maintain the range sumtree[treeIndex] = tree[SegmentTreeSupport.getLeftSon(treeIndex)] + tree[SegmentTreeSupport.getRightSon(treeIndex)];//if we want to maintain the minimum value // tree[treeIndex] = Math.min(tree[SegmentTreeSupport.getLeftSon(treeIndex)], tree[SegmentTreeSupport.getRightSon(treeIndex)]);//if we want to maintain the maximum value // tree[treeIndex] = Math.max(tree[SegmentTreeSupport.getLeftSon(treeIndex)], tree[SegmentTreeSupport.getRightSon(treeIndex)]);}private void getLazyStatus(int fromIndex, int toIndex, int treeIndex, long diff){//this line should be replaced by the function we want to maintain//now, we set the value to diff // lazy[treeIndex] = diff; // tree[treeIndex] = (long)(toIndex - fromIndex + 1) * diff;//if we want to add the value by diff, then code is:tree[treeIndex] += diff * (toIndex - fromIndex + 1);lazy[treeIndex] += diff;//if we want to set the value and maintain the minimum/maximum value // tree[treeIndex] = diff; // lazy[treeIndex] = diff;//if we want to add the value and maintain the minimum/maximum value // tree[treeIndex] += diff; // lazy[treeIndex] += diff;}private void push_down(int fromIndex, int toIndex, int treeIndex){int midIndex = (fromIndex + toIndex) >>> 1;getLazyStatus(fromIndex, midIndex, SegmentTreeSupport.getLeftSon(treeIndex), lazy[treeIndex]);getLazyStatus(midIndex + 1, toIndex, SegmentTreeSupport.getRightSon(treeIndex), lazy[treeIndex]);lazy[treeIndex] = 0;}public void update(int updateFromIndex, int updateToIndex, long diff){rangeCheck(updateFromIndex);rangeCheck(updateToIndex);update(updateFromIndex, updateToIndex, 0, length - 1, 1, diff);}private void update(int updateFromIndex, int updateToIndex, int fromIndex, int toIndex, int treeIndex, long diff){if (updateFromIndex <= fromIndex && toIndex <= updateToIndex){getLazyStatus(fromIndex, toIndex, treeIndex, diff);return;}if (lazy[treeIndex] != 0){push_down(fromIndex, toIndex, treeIndex);}int midIndex = (fromIndex + toIndex) >>> 1;if (updateFromIndex <= midIndex){update(updateFromIndex, updateToIndex, fromIndex, midIndex, SegmentTreeSupport.getLeftSon(treeIndex), diff);}if (updateToIndex >= midIndex + 1){update(updateFromIndex, updateToIndex, midIndex + 1, toIndex, SegmentTreeSupport.getRightSon(treeIndex), diff);}collectSubMsgTo(treeIndex);}public long query(int queryFromIndex, int queryToIndex){rangeCheck(queryFromIndex);rangeCheck(queryToIndex);if (queryFromIndex > queryToIndex){throw new IllegalArgumentException();}return query(queryFromIndex, queryToIndex, 0, length - 1, 1);}private long query(int queryFromIndex, int queryToIndex, int fromIndex, int toIndex, int treeIndex){if (queryFromIndex <= fromIndex && toIndex <= queryToIndex){return tree[treeIndex];}int midIndex = (fromIndex + toIndex) >>> 1;if (lazy[treeIndex] != 0){push_down(fromIndex, toIndex, treeIndex);}//if we want to maintain the range sumreturn (queryFromIndex <= midIndex ?query(queryFromIndex, queryToIndex, fromIndex, midIndex, SegmentTreeSupport.getLeftSon(treeIndex)): 0)+ (queryToIndex >= midIndex + 1? query(queryFromIndex, queryToIndex, midIndex + 1, toIndex, SegmentTreeSupport.getRightSon(treeIndex)) :0);//if we want to maintain the minimum value // return Math.min( // (queryFromIndex <= midIndex ? query(queryFromIndex, queryToIndex, fromIndex, midIndex, SegmentTreeSupport.getLeftSon(treeIndex)) : Long.MAX_VALUE), // (queryToIndex >= midIndex + 1 ? query(queryFromIndex, queryToIndex, midIndex + 1, toIndex, SegmentTreeSupport.getRightSon(treeIndex)) : Long.MAX_VALUE) // );//if we want to maintain the maximum value // return Math.max( // (queryFromIndex <= midIndex ? query(queryFromIndex, queryToIndex, fromIndex, midIndex, SegmentTreeSupport.getLeftSon(treeIndex)) : Long.MIN_VALUE), // (queryToIndex >= midIndex + 1 ? query(queryFromIndex, queryToIndex, midIndex + 1, toIndex, SegmentTreeSupport.getRightSon(treeIndex)) : Long.MIN_VALUE) // );}@Overridepublic String toString() {return "SegmentTreen" +"tree = " + Arrays.toString(tree) +", lazy = " + Arrays.toString(lazy);} }時間復雜度上，建立線段樹和 DFS 的過程：
，每次查詢的時間復雜度： ，總共有 次查詢，因此總的時間復雜度是： 。空間復雜度上，線段樹加上 lazy 標記需要 8 倍的空間，from 和 to 是 1 倍的空間，因此是
。EOF。
總結
以上是生活随笔為你收集整理的freeswitch 发update sip消息_LeetCode LCP 05——发 LeetCoin的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： java水果超市mysql_Java基础
- 下一篇： 华为手机怎么使用读卡器_华为手机使用小窍