每周限时赛(内测版) 第3场 题解
格式化字符串
算法:模拟
算法思路
- 设置一个起始位置的指针
st
,每次将起始指针右侧两个串交换顺序加入到答案尾部,并将起始位置右移两个串的长度
复杂度分析
- 时间复杂度:
O(str.length())
// This solution is powered by @lintcode.com
class Solution {
public:
/**
* @param str: the original string
* @param sublen: an integer array
* @return: the new string
*/
string reformatString(string &str, vector<int> &sublen) {
// write your code here
string ans;
for (int i=1;i<=)
int n = sublen.size();
int st = 0;
for (int i = 1; i < n; i += 2) {
//交换st右侧两个串顺序加入到答案尾部
ans = ans + str.substr(st + sublen[i - 1], sublen[i]) + str.substr(st, sublen[i - 1]);
//将起始位置右移两个串的长度
st += sublen[i - 1] + sublen[i];
}
if (n % 2) {
ans = ans + str.substr(st, sublen[n - 1]);
}
return ans;
}
};
# This solution is powered by @lintcode.com
class Solution:
"""
@param str: the original string
@param sublen: an integer array
@return: the new string
"""
def reformatString(self, str, sublen):
# write your code here
ans=""
n = len(sublen)
st = 0
for i in range(1, n, 2):
#交换st右侧两个串顺序加入到答案尾部
ans = ans + str[st + sublen[i - 1] : st + sublen[i - 1] + sublen[i] ] + str[st : st + sublen[i - 1] ]
#将起始位置右移两个串的长度
st += sublen[i - 1] + sublen[i]
if n % 2:
ans = ans + str[st : st + sublen[n - 1] ]
return ans
Java题解详见 九章算法solution
写作业
算法:前缀和、二分查找
算法思路
因为作业要求顺序完成,我们只需要先进行前缀和以后,每个人从头查找val[i]
即可。
复杂度分析
- 时间复杂度:
O(len(val) * log(len(cost)) + len(cost))
- 空间复杂度:
O(len(cost))
// This solution is powered by @lintcode.com
class Solution {
public:
/**
* @param cost: the cost
* @param val: the val
* @return: the all cost
*/
long long sum[105000];
long long doingHomework(vector<int> &cost, vector<int> &val) {
// Write your code here.
int i, k;
memset(sum, 0, sizeof(sum));
int n = cost.size();
sum[0] =(long long) cost[0];
for (i = 1; i < n; i++) sum[i] = sum[i - 1] +(long long) (cost[i]);
long long ans = 0;
int m = val.size();
for (i = 0; i < m; i++) {
k = upper_bound(sum, sum + n, (long long )val[i]) - sum;
k--;
if (k >= 0) ans +=(long long) sum[k];
}
return ans;
}
};
Java题解详见 九章算法solution
def串
算法:数学
算法思路:
我们首先可以得到数学公式,即长度为n
的,符合题目def串的个数为3 * (2 ^ (n - 1))
。
我们只需要根据数字大小关系一点点计算即可。
复杂度分析
- 时间复杂度:
O(n)
# This solution is powered by @lintcode.com
class Solution:
"""
@param n: the length of the string.
@param k: the kth Lexicographically smallest that result should be.
@return: return the kth Lexicographically smallest string.
"""
def kthString(self, n, k):
# 判断 k 是否超出不同字符串的个数
# 长为 n 的字符串长度应等于 3 * (2 ^ (n - 1))
# n 控制在 62 以内是因为计算 2 的幂可能会溢出和时间超限
if n <= 62 and 3 * (2 ** (n - 1)) < k:
return ""
result = ""
# 计算第一个字符
if n >= 62:
result += 'a'
elif k <= 2 ** (n - 1):
result += 'a'
elif k <= 2 * (2 ** (n - 1)):
result += 'b'
k -= 2 ** (n - 1)
else:
result += 'c'
k -= 2 * (2 ** (n - 1))
# 计算后续字符
for i in range(1, n):
# position = 0代表这个位置填较小的字符,1的话填较大的
position = 0
exponent = n - i
if exponent < 62 and k > 2 ** (exponent - 1):
position = 1
k -= 2 ** (exponent - 1)
temp = "abc"
temp = temp.replace(result[i - 1], '', 1)
result += temp[position]
return result
// This solution is powered by @lintcode.com
class Solution {
public:
/**
* @param n: the length of the string.
* @param k: the kth Lexicographically smallest that result should be.
* @return: return the kth Lexicographically smallest string.
*/
string kthString(int n, long long k) {
// 判断 k 是否超出不同字符串的个数
// 长为 n 的字符串长度应等于 3 * (2 ^ (n - 1))
// n 控制在 62 以内是因为计算 2 的幂可能会溢出
if (n <= 62 and 3 * (1ll << (n - 1)) < k) {
return "";
}
string result;
// 计算第一个字符
// n 足够大时,第一个字符一定是 'a'
if (n >= 62) {
result += 'a';
}
else {
if (k <= (1ll << (n - 1))) {
result += 'a';
}
else if (k <= 2 * (1ll << (n - 1))) {
result += 'b';
k -= (1ll << (n - 1));
}
else {
result += 'c';
k -= 2 * (1ll << (n - 1));
}
}
// 计算后续的字符
for (int i = 1; i < n; i++) {
// positon = 0代表这个位置填较小的字符,1 的话填较大的
int position = 0;
int exponent = n - i;
if (exponent < 62 and k > (1ll << (exponent - 1))) {
position = 1;
k -= (1ll << (exponent - 1));
}
string temp = "abc";
temp.erase(temp.find(result[i - 1]), 1);
result += temp[position];
}
return result;
}
};
Java题解详见 九章算法solution
移动的圆
算法:数学
算法思路
其实这个问题做法有很多,在此仅提供一种思路。
这里可以将连线轨迹形成一个矩形,判断矩形和B是否相交。然后在起点和终点特殊判断。
# This solution is powered by @lintcode.com
class Solution:
"""
@param position: the position of circle A,B and point P.
@return: if two circle intersect return 1, otherwise -1.
"""
#叉积AB×AC
def xmult(self, B, C, A):
return (B[0] - A[0])*(C[1] - A[1]) - (C[0] - A[0])*(B[1] - A[1])
#两点间距离
def distance(self, A, B):
return math.sqrt((A[0] - B[0])*(A[0] - B[0]) + (A[1] - B[1])*(A[1] - B[1]))
#点A到直线BC距离
def dis_ptoline(self, A, B, C):
return abs(self.xmult(A,B,C))/self.distance(B,C)
def IfIntersect(self, position):
A = [position[0], position[1]]
ra = position[2]
B = [position[3], position[4]]
rb = position[5]
P = [position[6], position[7]]
#过点B作直线AP的垂线,M为该垂线上一点(A和P不重合时M点不与B重合)
M = [B[0] - (P[1] - A[1]), B[1] + (P[0] - A[0])]
dmin = 0.0
dmax = 0.0
#若圆A移动过程中会经过B点到直线AP垂线的交点
if self.xmult(A, B, M) * self.xmult(B, P, M) > 0 :
dmin = self.dis_ptoline(B, A, P)
else :
dmin = min(self.distance(A, B), self.distance(P, B))
dmax = max(self.distance(A, B), self.distance(P, B))
if dmin > ra + rb or dmax < abs(ra - rb):
return -1
return 1
// This solution is powered by @lintcode.com
class Solution {
public:
/**
* @param position: the position of circle A,B and point P.
* @return: if two circle intersect return 1, otherwise -1.
*/
typedef struct point {
double x, y;
}point;
//叉积AB×AC
double xmult(point B, point C, point A) {
return (B.x - A.x)*(C.y - A.y) - (C.x - A.x)*(B.y - A.y);
}
//两点间距离
double distance(point A, point B) {
return sqrt((A.x - B.x)*(A.x - B.x) + (A.y - B.y)*(A.y - B.y));
}
//点A到直线BC距离
double dis_ptoline(point A, point B, point C) {
return fabs(xmult(A,B,C))/distance(B,C);
}
int IfIntersect(vector<double> &position) {
point A, B, P, M;
double ra, rb;
double dmin, dmax;
A.x = position[0], A.y = position[1];
ra = position[2];
B.x = position[3], B.y = position[4];
rb = position[5];
P.x = position[6], P.y = position[7];
//过点B作直线AP的垂线,M为该垂线上一点(A和P不重合时M点不与B重合)
M.x = B.x - (P.y - A.y), M.y = B.y + (P.x - A.x);
//若圆A移动过程中会经过B点到直线AP垂线的交点
if (xmult(A, B, M) * xmult(B, P, M) >= 0) {
if(A.x == P.x && A.y == P.y) {
dmin = distance(B,A);
}
else {
dmin = dis_ptoline(B, A, P);
}
}
else {
dmin = min(distance(A, B), distance(P, B));
}
dmax = max(distance(A, B), distance(P, B));
if (dmin > ra + rb || dmax < fabs(ra - rb))
return -1;
return 1;
}
};
Java题解详见 九章算法solution