每週限時賽（內測版） 第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