每週限時賽（內測版） 第2場 題解
1. 粉刷天花板
算法：雙指針
算法思路
我們仔細觀察題目裡s數組生成的式子，我們可以發現s數組是遞增的，即s_i > s_{i - 1}恆成立。因此，我們要求滿足s_i * s_j <= a的(i,j)即可。
很顯然，當s_j越來越小的時候，s_i的上界就越來越大。因此，我們可以使用雙指針的做法來統計答案。右指針指向j，左指針指向i，隨著j的減小，i越來越大。
// This solution is powered by @lintcode.com
class Solution {
public:
/**
* @param s0: the number s[0]
* @param n: the number n
* @param k: the number k
* @param b: the number b
* @param m: the number m
* @param a: area
* @return: the way can paint the ceiling
*/
long long painttheCeiling(int s0, int n, int k, int b, int m, long long a) {
// write your code here
long long ans = 1;
int right = 0;
vector<int> s;
s.push_back(s0);
if (1LL * s0 * s0 > a) {
return 0;
}
int last = s0;
for (int i = 1; i < n; i++) {
last = (1LL * k * last + b) % m + 1 + last;
if (1LL * last * last <= a) {
ans += i * 2 + 1;
s.push_back(last);
right = i;
}
else {
while (right >= 0 && 1LL * s[right] * last > a) {
right--;
}
ans += 2 * (right + 1);
}
}
return ans;
}
};# This solution is powered by @lintcode.com
class Solution:
"""
@param s0: the number s[0]
@param n: the number n
@param k: the number k
@param b: the number b
@param m: the number m
@param a: area
@return: the way can paint the ceiling
"""
def painttheCeiling(self, s0, n, k, b, m, a):
# write your code here
ans = 0
right = n - 1
s = []
s.append(s0)
last = s0
for i in range(1, n):
last = (k * last + b) % m + 1 + last
s.append(last)
for i in range(n):
while (right >= 0 and s[right] * s[i] > a):
right -= 1
ans += right + 1
return ansJava題解詳見 九章算法solution
2. 第二直徑
題目算法
求樹的第一直徑
- 從任意點P出發，找離它最遠的Q，再從Q出發，找離它最遠的W，W到Q的簡單路徑便是直徑
- 證明：
- 若P在直徑上，那麼根據直徑定義，Q也在直徑上，而且Q為直徑的一個端點
-
若P不在直徑上，假設WQ不是直徑，AB是直徑
- AB與PQ有交點，因為P到Q最遠那麼PC+CQ>PC+CA，所以CQ>CA 所以CQ+CB>CA+CB 最後推出QB>AB,與AB是直徑的假設矛盾
- 若AB與PQ沒有交點，M為AB上任意一點，N為PQ上任意一點。首先還是NP+NQ>NQ+MN+MB，推出 NP>MN+MB，易知NP+MN>MB，所以NP+MN+MA>MB+MA，即NP+MN+MA>AB，與AB是直徑矛盾
- 通過上述的證明我們知道了從一個點P出發，找最遠的點Q，那麼Q一定是直徑的端點之一
求樹的第二直徑
本題要求我們求出樹的第二直徑也就是兩兩點對之間距離的次大值
那我們可以先忽略掉第一直徑的值，再求兩兩點對之間的距離的最大值便是答案
- 先求出樹的第一直徑的兩個端點，兩個端點分別遍歷整個樹，算出每個點
i到兩個端點的距離distanceOne_i,distanceTwo_i - 由上述證明的性質知道了到
i的最遠點一定是直徑端點之一 那麼maxDistance_i=max(distanceOne_i,distanceTwo_i) - 忽略掉第一直徑的值，再求兩兩點對之間的距離的最大值便是答案,那只需要我們遍歷一遍，算出
max(maxDistance_i )要求i不是第一直徑的端點，就可以找出第二直徑的答案了
複雜度分析
- 時間複雜度
令N為點數，從P出發遍歷一遍找出Q的時間複雜度O(N),從Q出發遍歷一遍找出W並計算出distanceOne的時間複雜度O(N),從W出發遍歷一遍算出distanceTwo的時間複雜度O(N)
最後遍歷一遍非直徑端點的點，統計答案，所以最終的時間複雜度是O(N)
- 空間複雜度
令N為點數，遍歷時需要distance距離數組，visited訪問數組，queuebfs的隊列，以及Edge樹的邊，所以空間複雜度O(N)
代碼
// This solution is powered by @lintcode.com
typedef struct Edge {
int to, value;
Edge (int to, int value) : to (to), value (value) {}
} Edge ;
void bfs(int begin, int n, vector<long long> &distance, vector<vector<Edge> > &pointEdge) {
//bfs隊列
queue<int>q;
//標記訪問數組
vector<bool>visited(n, false);
//將begin壓入隊列
visited[begin] = true;
q.push(begin);
distance[begin] = 0;
while(!q.empty()) {
//取出隊首
int now = q.front();
q.pop();
//枚舉和now相連的其他點
for(int i = 0; i < pointEdge[now].size(); i++) {
int toPoint = pointEdge[now][i].to;
int value = pointEdge[now][i].value;
//如果相連的點沒有訪問過，則壓入隊列
if(!visited[toPoint]) {
visited[toPoint] = true;
//計算距離
distance[toPoint] = distance[now] + value;
q.push(toPoint);
}
}
}
}
/**
*從distance數組裡找出距離最大的位置
**/
int findMaxDistanceIndex(vector<long long> &distance) {
//初始化最大距離和最大距離所在的數組下標
long long maxDistance = 0;
int index = 0;
//找出最大距離
for(int i = 0; i < distance.size(); i++) {
if(distance[i] > maxDistance) {
maxDistance = distance[i];
index = i;
}
}
return index;
}
/**
* @param edge: edge[i][0] [1] [2] start point,end point,value
* @return: return the second diameter length of the tree
*/
long long getSecondDiameter(vector<vector<int> > &edge) {
// write your code here
//邊的數量
int edgeNumber = edge.size();
//點的數量
int n = edgeNumber + 1;
//距離指定起點的距離
vector<long long>distance(n, 0);
//距離直徑第一個端點的距離
vector<long long>distanceOne(n, 0);
//距離直徑第二個端點的距離
vector<long long>distanceTwo(n, 0);
//每個點儲存有哪些邊
vector<vector<Edge> >pointEdge(n);
//加無向邊
for(int i = 0; i < edgeNumber; i++) {
pointEdge[edge[i][0]].push_back(Edge(edge[i][1], edge[i][2]));
pointEdge[edge[i][1]].push_back(Edge(edge[i][0], edge[i][2]));
}
//從指定的起點開始BFS
bfs(0, n, distance, pointEdge);
//找出距離指定起點的最遠的點 ，也就是直徑的第一個端點
int diameterFirstPointIndex = findMaxDistanceIndex(distance);
//從直徑的第一個端點再開始BFS
bfs(diameterFirstPointIndex, n, distanceOne, pointEdge);
//找出距離第一個端點最遠的點 ，也就是直徑的第二個端點
int diameterSecondPointIndex = findMaxDistanceIndex(distanceOne);
//從直徑的第二個端點再開始BFS
bfs(diameterSecondPointIndex, n, distanceTwo, pointEdge);
//第二直徑的值
long long secondDiameter = 0;
//遍歷每個點，找到每個點的最遠距離更新第二直徑
for(int i = 0; i < n; i++) {
//最長的邊是第一直徑，如果我們把第一直徑的兩個端點去掉，就可以把第一直徑給忽略了
//這樣只需要在忽略第一直徑後剩下的距離找一個最大值就是第二直徑
if(i != diameterFirstPointIndex && i != diameterSecondPointIndex) {
//到i的最遠距離的點肯定是第一直徑的兩個端點之一
secondDiameter = max(secondDiameter, max(distanceOne[i], distanceTwo[i]));
}
}
return secondDiameter;
}
};# This solution is powered by @lintcode.com
class Solution:
"""
從begin點開始bfs遍歷整個樹，並計算出begin到每個點的距離 存到distance數組裡
"""
def bfs(self, begin, n, distance, pointEdge):
# bfs隊列
deque = collections.deque()
# 標記訪問數組
visited = [False] * n
# 將begin壓入隊列
distance[begin] = 0
visited[begin] = True
deque.append(begin)
while (len(deque)):
# 取出隊首
now = deque.popleft()
# 枚舉和now相連的其他點
for i in range(len(pointEdge[now])):
to = pointEdge[now][i][0]
# print(to)
value = pointEdge[now][i][1]
# 如果相連的點沒有訪問過，則壓入隊列
if visited[to] == False:
visited[to] = True
distance[to] = distance[now] + value
deque.append(to)
"""
從distance數組裡找出距離最大的位置
"""
def findMaxDistanceIndex(self, distance):
# 初始化最大距離和最大距離所在的數組下標
maxDistance = 0
index = 0
# 找出最大距離
for i in range(len(distance)):
if distance[i] > maxDistance:
maxDistance = distance[i]
index = i
return index
"""
@param edge: edge[i][0] [1] [2] start point,end point,value
@return: return the second diameter length of the tree
"""
def getSecondDiameter(self, edge):
# write your code here
# 邊的數量
edgeNumber = len(edge)
# 點的數量
n = edgeNumber + 1
# 距離指定起點的距離
distance = [0] * n
# 距離直徑第一個端點的距離
distanceOne = [0] * n
# 距離直徑第二個端點的距離
distanceTwo = [0] * n
# 每個點儲存有哪些邊
pointEdge = [[] for i in range(n)]
# 加無向邊
for i in range(edgeNumber):
pointEdge[edge[i][0]].append((edge[i][1], edge[i][2]))
pointEdge[edge[i][1]].append((edge[i][0], edge[i][2]))
# print(pointEdge)
# //從指定的起點開始BFS
self.bfs(0, n, distance, pointEdge)
# 找出距離指定起點的最遠的點 ，也就是直徑的第一個端點
diameterFirstPointIndex = self.findMaxDistanceIndex(distance)
# 從直徑的第一個端點再開始BFS
self.bfs(diameterFirstPointIndex, n, distanceOne, pointEdge)
# 找出距離第一個端點最遠的點 ，也就是直徑的第二個端點
diameterSecondPointIndex = self.findMaxDistanceIndex(distanceOne)
# 從直徑的第二個端點再開始BFS
self.bfs(diameterSecondPointIndex, n, distanceTwo, pointEdge)
# 第二直徑的值
secondDiameter = 0
# 遍歷每個點，找到每個點的最遠距離更新第二直徑
for i in range(n):
# 最長的邊是第一直徑，如果我們把第一直徑的兩個端點去掉，就可以把第一直徑給忽略了
# 這樣只需要在忽略第一直徑後剩下的距離找一個最大值就是第二直徑
if i != diameterFirstPointIndex and i != diameterSecondPointIndex:
# 到i的最遠距離的點肯定是第一直徑的兩個端點之一
secondDiameter = max(secondDiameter, max(distanceOne[i], distanceTwo[i]))
return secondDiameter
Java題解詳見 九章算法solution
3. 最大非負子序和
解題思路
- 因為題目要求的子序和最大，並且所選元素都是非負整數，那我們一定是將所選的非負整數子數組延長到不能延長的地方（到達數組的末尾或者是到達數組元素為負數的位置）。
算法流程
我們令 maxSubArraySum[i] 表示以A[i]結尾的最大非負子序和。
- 先將
maxSubArraySum[i]初始化為-1。 - 如果
A[i]為負數，那麼maxSubArraySum[i]仍為-1，當我們在儘可能延伸子數組的時候，如果延伸到-1位置就應該停止了，因為這時候遇到了負數。 -
如果
A[i]不是負數，那麼我們可以考慮將A[i]拼接到A[i-1]所在的子數組的末尾，形成新的子數組- 如果
maxSubArraySum[i-1]為-1，表明A[i-1]為負數，這時候只能A[i]自己作為一個新的子數組的開頭，那麼maxSubArraySum[i] = A[i] - 如果
maxSubArraySum[i-1]不為-1，表明A[i-1]為非負數，這時候只能A[i]可以拼接到以A[i]結尾的子數組的末尾，使得子數組儘可能地延伸長度，那麼maxSubArraySum[i] = A[i] + maxSubArraySum[i-1]
- 如果
- 統計完
maxSubArraySum，根據maxSubArraySum的定義，以A[i]結尾的最大非負子序和。那麼我們再枚舉以誰結尾，求一個最大值，就是這個給定數組A的最大的連續非負子數組的和
算法優化
在上面算法流程中發現我們提到的maxSubArraySum數組，maxSubArraySum[i] 只與 maxSubArraySum[i-1]和A[i]有關，那麼我們可以只用一個變量lastIndexSubArraySum記錄maxSubArraySum[i-1],代表上一個位置的最大連續非負子序和，一個nowIndexSubArraySum代表當前位置的最大連續非負子序和。
通過這樣的優化，就可以只需要開兩個變量就可以完成題目，而不需要maxSubArraySum數組，從而可以優化空間
時空複雜度分析
-
時間複雜度
- 令n為給定的整數數組長度，我們只需要遍歷一遍給定的整數數組即可，那麼時間複雜度為
O(n)
- 令n為給定的整數數組長度，我們只需要遍歷一遍給定的整數數組即可，那麼時間複雜度為
-
空間複雜度
- 令n為給定的整數數組長度，如果開闢
maxSubArraySum數組，所以空間複雜度是O(n)
如果使用nowIndexSubArraySum和lastIndexSubArraySum，空間複雜度O(1)
- 令n為給定的整數數組長度，如果開闢
代碼
// This solution is powered by @lintcode.com
class Solution {
public:
/**
* @param A: an integer array
* @return: return maxium contiguous non-negative subarray sum
*/
int maxNonNegativeSubArray(vector<int> &A) {
// write your code here
//A數組長度
int n = A.size();
// maxSubArraySum[i] 表示以A[i]結尾的最大非負子序和
// 若maxSubArraySum[i]為-1 ，表示A[i] 為負值
// 因為maxSubArraySum[i]只與maxSubArraySum[i-1] A[i]有關 我們可以只使用一個變量lastIndexSubArraySum記錄maxSubArraySum[i-1]
int lastIndexSubArraySum = -1;
//初始化邊界條件
//記錄0位置的答案
if(A[0] >= 0) {
lastIndexSubArraySum = A[0];
}
//答案
int maxSubArraySumAnswer = -1;
maxSubArraySumAnswer = lastIndexSubArraySum;
for(int i = 1; i < n; i++) {
//用nowIndexSubArraySum來代替maxSubArraySum[i]
int nowIndexSubArraySum = -1;
//如果A[i]為非負整數，計算A[i]結尾的最大非負子序和
if(A[i] >= 0) {
//maxSubArraySum[i-1]為-1 表明A[i-1]為負數，我們從i位置重新開始一段新的子數組
//我們用lastIndexSubArraySum記錄maxSubArraySum[i-1]
//只用maxSubArraySum[i-1]即可判斷
if(lastIndexSubArraySum == -1) {
nowIndexSubArraySum = A[i];
}
//maxSubArraySum[i-1]不是-1 表明A[i-1]為非負整數，那我們將A[i]接在A[i-1]的子數組的後面，
//我們用lastIndexSubArraySum記錄maxSubArraySum[i-1]
//只用maxSubArraySum[i-1]即可判斷
else {
nowIndexSubArraySum = lastIndexSubArraySum + A[i]; ;
}
}
//更新答案
maxSubArraySumAnswer = max(maxSubArraySumAnswer, nowIndexSubArraySum);
//更新lastIndexSubArraySum
lastIndexSubArraySum = nowIndexSubArraySum;
}
//如果maxSubArraySumAnswer還是-1 說明整個A數組都是負數
return maxSubArraySumAnswer;
}
};
# This solution is powered by @lintcode.com
class Solution:
"""
@param A: an integer array
@return: return maxium contiguous non-negative subarray sum
"""
def maxNonNegativeSubArray(self, A):
# write your code here
# A數組長度
n = len(A)
# maxSubArraySum[i] 表示以A[i]結尾的最大非負子序和
# 若maxSubArraySum[i]為-1 ，表示A[i] 為負值
# 因為maxSubArraySum[i]只與maxSubArraySum[i-1] A[i]有關 我們可以只使用一個變量lastIndexSubArraySum記錄maxSubArraySum[i-1]
lastIndexSubArraySum = -1
# 初始化邊界條件
# 記錄0位置的答案
if A[0] >= 0:
lastIndexSubArraySum = A[0]
#答案
maxSubArraySumAnswer = -1
maxSubArraySumAnswer = lastIndexSubArraySum
for i in range(1, n):
# 用nowIndexSubArraySum來代替maxSubArraySum[i]
nowIndexSubArraySum = -1
# 如果A[i]為非負整數，計算A[i]結尾的最大非負子序和
if A[i] >= 0:
# maxSubArraySum[i-1]為-1 表明A[i-1]為負數，我們從i位置重新開始一段新的子數組
# 我們用lastIndexSubArraySum記錄maxSubArraySum[i-1]
# 只用maxSubArraySum[i-1]即可判斷
if lastIndexSubArraySum == -1:
nowIndexSubArraySum = A[i]
# maxSubArraySum[i-1]不是-1 表明A[i-1]為非負整數，那我們將A[i]接在A[i-1]的子數組的後面
# 我們用lastIndexSubArraySum記錄maxSubArraySum[i-1]
# 只用maxSubArraySum[i-1]即可判斷
else:
nowIndexSubArraySum = lastIndexSubArraySum + A[i]
# 更新答案
maxSubArraySumAnswer = max(maxSubArraySumAnswer, nowIndexSubArraySum)
# 更新lastIndexSubArraySum
lastIndexSubArraySum = nowIndexSubArraySum
# 如果maxSubArraySumAnswer還是-1 說明整個A數組都是負數
return maxSubArraySumAnswerJava題解詳見 九章算法solution
4. 排序方案
解題思路
本題考查的是樹狀數組/線段樹的應用，我們不需要模擬數組實際的插入過程。
如果使用二分查找，找到對應的位置，然後模擬插入的話，時間複雜度會退化到 O(N^2)。
對於第 i 個數的插入，我們可以認為前 i - 1 個數已經排好序了，只需考慮先將前綴取出，還是先將後綴取出。所以我們需要統計前 i - 1 個數中比當前數小的個數，以及比當前數大的個數。採取較小的方案即可。
代碼思路
樹狀數組(Binary Indexed Tree(B.I.T), Fenwick Tree)是一個查詢和修改複雜度都為log(n)的數據結構。
主要功能有修改數組某一位的值和查詢前綴和。
某個數加上它的 lowbit，即他的二進制最低位 1 的位的二次冪，可以找到它對應節點的父節點。
某個數減去它的 lowbit，可以找打計算前綴和時的下一位置，直到減到零為止。
複雜度分析
設待插入的數組長度為 N。
時間複雜度
- 樹狀數組每次插入和查詢的時間複雜度為
O(logN)。總時間複雜度為O(NlogN)。
空間複雜度
- 樹狀數組的空間複雜度為
O(N)。
源代碼
// This solution is powered by @lintcode.com
class Solution {
public:
/**
* @param nums: the array of elements to be inserted.
* @return: return the least operation number.
*/
long long sortedArrangement(vector<int> &nums) {
int n = nums.size();
// 樹狀數組
vector<int> binaryIndexTree(n + 1);
long long result = 0;
for (int i = 0; i < n; i++) {
int number = nums[i];
// 先獲取前綴中比當前數小的個數
int prefixSmallerCount = query(number - 1, binaryIndexTree);
// 計算前綴中比當前數大的個數
int prefixLargerCount = i - prefixSmallerCount;
// 計算結果，採取更小的方案
result += 2 * min(prefixSmallerCount, prefixLargerCount) + 1;
// 將當前數也加入樹狀數組中, 在number位置上+1，代表number出現過
update(number, 1, binaryIndexTree);
}
return result;
}
int lowbit(int x) {
return x & (-x);
}
// 更新position位置的值，使其加上value
void update(int position, int value, vector<int>& binaryIndexTree) {
while (position < (int)binaryIndexTree.size()) {
binaryIndexTree[position] += value;
position += lowbit(position);
}
}
// 查詢[1, position]的所有值的和
int query(int position, vector<int>& binaryIndexTree) {
int prefixSum = 0;
while (position > 0) {
prefixSum += binaryIndexTree[position];
position -= lowbit(position);
}
return prefixSum;
}
};# This solution is powered by @lintcode.com
class Solution:
"""
@param nums: the array of elements to be inserted.
@return: return the least operation number.
"""
def sortedArrangement(self, nums):
n = len(nums)
# 樹狀數組
binary_index_tree = [0] * (n + 1)
result = 0
for i, number in enumerate(nums):
# 先獲取前綴中比當前數小的個數
prefix_smaller_count = self.query(number - 1, binary_index_tree)
# 計算前綴中比當前數大的個數
prefix_larger_count = i - prefix_smaller_count
# 計算結果，採取更小的方案
result += 2 * min(prefix_smaller_count, prefix_larger_count) + 1
# 將當前數也加入樹狀數組中, 在number位置上+1，代表number出現過
self.update(number, 1, binary_index_tree)
return result
def lowbit(self, x):
return x & (-x)
# 更新position位置上的值，使其加上value
def update(self, position, value, binary_index_tree):
while position < len(binary_index_tree):
binary_index_tree[position] += value
position += self.lowbit(position)
# 查詢[1,position]所有值的和
def query(self, position, binary_index_tree):
prefix_sum = 0
while position > 0:
prefix_sum += binary_index_tree[position]
position -= self.lowbit(position)
return prefix_sumJava題解詳見 九章算法solution