每周限时赛（内测版） 第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