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