1. 从头到尾

算法思路

暴力模拟

我们只要从头到尾的施加法术，然后看看在n次之类能否一样即可，其中n是字符串长度。

代码

• Java

// This solution is powered by @lintcode.com
public class Solution {
    /**
     * @param s1: the string 1
     * @param s2: the string 2
     * @return: judge can s1 change to s2
     */
    public boolean judge(String s1, String s2) {
        s1 += s1;
        return s1.indexOf(s2) != -1 && s1.length() / 2 == s2.length();
    }
}

• Python

# This solution is powered by @lintcode.com
class Solution:
    """
    @param s1: the string 1
    @param s2: the string 2
    @return: judge can s1 change to s2
    """
    def judge(self, s1, s2):
        # write your code here
        n = len(s1)
        m = len(s2)
        if n != m:
            return False 
        for i in range(n):
            s3 = s1[i:n] + s1[0:i]
            if s3 == s2:
                print(s1[0:i])
                print(s2[i:n])
                print(i)
                return True 
            
        return False

C++题解详见：九章solution

2. 闰年

算法思路

暴力枚举y1和y2是平年还是闰年，然后判断公式的合法性即可。根据题目的要求来输出答案。

代码

• Java

// This solution is powered by @lintcode.com
public class Solution {
    /**
     * @param inputQueries: input Queries, means [[m1, d1, m2, d2, x], [m1, d1, m2, d2, x],...]
     * @return: guess whether y1 is leep year
     */
    
    int[] days = {0,31,28,31,30,31,30,31,31,30,31,30,31};
    boolean rui(int year)
    {
        if(year%100==0)
        {
            return year%400==0;
        }
        return year%4==0;
    }
    int getDays(int y1,int m1,int d1,int y2,int m2,int d2)
    {
        int ans=0;
        for(int i=y1;i<=y2;i++)ans+=365+(rui(i)?1:0);
        for(int i=1;i<m1;i++)
        {
            ans-=days[i];
            if(i==2&&rui(y1))ans--;
        }
        ans-=d1-1;
        ans-=days[m2]-d2;
        if(m2==2&&rui(y2))ans--;
        for(int i=m2+1;i<=12;i++)
        {
            ans-=days[i];
            if(i==2&&rui(y2))ans--;
        }
        return ans-1;
    }
    
    char checkQueries(int m1,int d1,int m2,int d2,int x)
    {
        if(m1==2&&d1==29)return 'R';
        if(m2==2&&d2==29)
        {
            if(m1<=2)return 'R';
            else return 'P';
        }
        int flag1=0,flag2=0;
        if(getDays(0,m1,d1,0,m2,d2)==x)flag1=1;
        if(getDays(0,m1,d1,1,m2,d2)==x)flag1=1;
        if(getDays(1,m1,d1,1,m2,d2)==x)flag2=1;
        if(getDays(1,m1,d1,2,m2,d2)==x)flag2=1;
        if(getDays(3,m1,d1,4,m2,d2)==x)flag2=1;
        if(flag1==1&&flag2==1)return '?';
        else if(flag1==1)return 'R';
        else return 'P';
    }
     
    public String guessYear(int[][] inputQueries) {
        String ans="";
        for(int i=0;i<inputQueries.length;i++)
        {
            ans+=checkQueries(inputQueries[i][0],inputQueries[i][1],inputQueries[i][2],inputQueries[i][3],inputQueries[i][4]);
        }
        return ans;
    }
    
}

• Python

# This solution is powered by @lintcode.com
from datetime import date, timedelta

class Solution:
    """
    @param inputQueries: input Queries, means [[m1, d1, m2, d2, x], [m1, d1, m2, d2, x],...]
    @return: guess whether y1 is leep year
    """
    def guessYear(self, inputQueries):
        res = ""
        for q in inputQueries:
            res += self.f(q)
        return res
    
    def f(self, q):
        m1, d1 = q[0], q[1]
        m2, d2 = q[2], q[3]
        x = q[4]
        
        def _try(y):
            if m1 == 2 and d1 == 29:
                return y == 2020
            date1 = date(y, m1, d1)
            date1 += timedelta(x)
            return date1.month == m2 and date1.day == d2
        
        leagl1 = _try(2018)
        leagl2 = _try(2019)
        leagl3 = _try(2020)
        
        if not leagl3 and (leagl1 or leagl2):
            return 'P'
        if leagl3 and not leagl1 and not leagl2:
            return 'R'
        return '?'

C++题解详见：九章solution

3. 抽奖

算法思路

二分答案

由于概率一定是在0.01到100当中的，而且具有单调的性质，因此我们可以二分答案，找到符合要求的位置，从而计算出结果。

代码

• Java

// This solution is powered by @lintcode.com
public class Solution {
    /**
     * @param b: 
     * @param c: 
     * @param p: 
     * @return: return the a
     */
     
    double getAns(double a,int b,int c)
    {
        double pp=a/100.0;
        double pre=1;
        int times=0;
        double E=0;
        while(pp+0.0001<=1.0)
        {
            times++;
            if(times>=b)pp=Math.min(1.0,pp+0.01*c);
            E+=pp*pre*times;
            pre*=1-pp;
        }
        return E;
    }
    
    public double lotteryDraw(int b, int c, int p) {
        double ans=0.000,cha=1e9;
        for(double a=0.00;a<=100.00;a+=0.01)
        {
            double wucha=Math.abs(getAns(a,b,c)-100.0/p);
            if(wucha<cha){ans=a;cha=wucha;}
        }
        return ans;
    }

}

• Python

# This solution is powered by @lintcode.com
class Solution:
    """
    @param b: 
    @param c: 
    @param p: 
    @return: return the a
    """
    def lotteryDraw(self, b, c, p):
        # write your code here
        left = 0.01
        right = 100
        while right - left >= 0.00001:
            mid = (left + right) / 2 
            if self.calc(mid, b, c) <= p:
                left = mid
            else:
                right = mid 
            
            
        return left 
    
    def calc(self, a, b, c):
        ex = 0 
        pnow = 1 
        for i in range(1, b):
            ex += i *  pnow * a / 100
            pnow *= (1 - a / 100)
            # print(ex)
        
        times = b 
        while a < 100:
            a = min(a + c, 100)
            # a = a + c
            ex += times * pnow * a / 100
            pnow *= (1 - a / 100)
            times += 1
        
        return 100/ex

C++题解详见：九章solution

4. 十字绣

算法思路

dfs+剪枝

但是普通的剪枝并不够，需要提前预处理每一行每一列的情况，固定一些格子以后再剪枝

注意这里只要唯一解即可，所以不需要考虑回溯的问题。

代码

• Java

// This solution is powered by @lintcode.com
public class Solution {
    /**
     * @param rowInfo: row information
     * @param colInfo: col information
     * @return: return the printed picture
     */
    public String[] crossStitch(int[][] rowInfo, int[][] colInfo) {
        // write your code here
        int n = rowInfo.length;
        int m = colInfo.length;
        int[][] a = new int[30][30];
        int[][] b = new int[30][30];
        int[][] col = new int[30][30];
        int[][] cgd = new int[30][30];
        int[] now = new int[30];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < rowInfo[i].length; j++) {
                a[i + 1][j + 1] = rowInfo[i][j];
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < colInfo[i].length; j++) {
                b[i + 1][j + 1] = colInfo[i][j];
            }
        }
        String[] ans = new String[n];
        dfs(1, 1, 0, n, m, a, b, col, now, cgd, ans);
        return ans;
    }
    public boolean Set(int x, int y, int n, int m, int[][] a, int[][] b, int[][] col, int[] now, int[][] cgd, String[] ans) {
        now[y]++;
        int i;
        if (b[y][now[y]] == 0) {
            now[y]--;
            return false;
        }
        if (x + b[y][now[y]] - 1 > n) {
            now[y]--;
            return false;
        }
        col[x][y] = 2;
        for (i = 1; i < b[y][now[y]] && i + x <= n; i++) {
            col[x + i][y] = 2;
            cgd[x + i][y] = 1;
        }
        if (x + i <= n) {
            col[x + i][y] = 1;
            cgd[x + i][y] = 1;
        }
        return true;
    }
    public void restore(int x, int y, int n, int m, int[][] a, int[][] b, int[][] col, int[] now, int[][] cgd, String[] ans) {
        col[x][y] = 0;
        int i;
        for (i = 1; i < b[y][now[y]] && i + x <= n; i++) {
            col[x + i][y] = 0;
            cgd[x + i][y] = 0;
        }
        if (x + i <= n) {
            col[x + i][y] = 0;
            cgd[x + i][y] = 0;
        }
        now[y]--;
    }
    public void dfs(int i, int j, int now, int n, int m, int[][] a, int[][] b, int[][] col, int[] nowp, int[][] cgd, String[] ans) {
        if (ans[0] != null)
            return;
        if (i > n) {
            for (int x = 1; x <= n; x++) {
                String tmp = "";
                for (int y = 1; y <= m; y++) {
                    if (col[x][y] < 2)
                        tmp += ".";
                    else
                        tmp += "*";
                }
                ans[x - 1] = tmp;
            }
            return;
        }
        if (j > m) {
            if (a[i][now + 1] == 0)
                dfs(i + 1, 1, 0, n, m, a, b, col, nowp, cgd, ans);
            return;
        }
        if (col[i][j] == 0 || col[i][j] == 1) {
            col[i][j] = 1;
            dfs(i, j + 1, now, n, m, a, b, col, nowp, cgd, ans);
            if (cgd[i][j] == 0)
                col[i][j] = 0;
        }
        int k;
        if (a[i][now + 1] > 0) {
            for (k = 0; k < a[i][now + 1] && j + k <= m; k++)
                if (col[i][j + k] == 1)
                    break;
            if (k < a[i][now + 1] || (j + a[i][now + 1] <= m && col[i][j + a[i][now + 1]] == 2))
                return;
            for (k = 0; k < a[i][now + 1]; k++)
                if (cgd[i][j + k] == 0)
                    if (!Set(i, j + k, n, m, a, b, col, nowp, cgd, ans))
                        break;
            if (k >= a[i][now + 1])
                dfs(i, j + a[i][now + 1] + 1, now + 1, n, m, a, b, col, nowp, cgd, ans);
            for (k--; k >= 0; k--)
                if (cgd[i][j + k] == 0)
                    restore(i, j + k, n, m, a, b, col, nowp, cgd, ans);
        }
    }
}

• Python

# This solution is powered by @lintcode.com
class Solution:
    """
    @param rowInfo: row information
    @param colInfo: col information
    @return: return the printed picture
    """
    def crossStitch(self, rowInfo, colInfo):
        # write your code here
        ans = []
        n = len(rowInfo)
        m = len(colInfo)
        a = [[0] * 30 for _ in range(30)]
        b = [[0] * 30 for _ in range(30)]
        col = [[0] * 30 for _ in range(30)]
        cgd = [[0] * 30 for _ in range(30)]
        now = [0] * 30
        for i in range(n):
            for j in range(len(rowInfo[i])):
                a[i + 1][j + 1] = rowInfo[i][j]
        for i in range(m):
            for j in range(len(colInfo[i])):
                b[i + 1][j + 1] = colInfo[i][j]
        self.dfs(1, 1, 0, n, m, a, b, col, now, cgd, ans)
        return ans
    def dfs(self, i, j, now, n, m, a, b, col, nowp, cgd, ans):
        if (len(ans) != 0):
            return
        if (i > n):
            for i in range(1, n + 1):
                tmp = ""
                for j in range(1, m + 1):
                    if col[i][j] < 2:
                        tmp += "."
                    else:
                        tmp += "*"
                ans.append(tmp)
            return
        if (j > m):
            if (a[i][now + 1] == 0):
                self.dfs(i + 1, 1, 0, n, m, a, b, col, nowp, cgd, ans)
            return
        if (col[i][j] == 0 or col[i][j] == 1):
            col[i][j] = 1
            self.dfs(i, j + 1, now, n, m, a, b, col, nowp, cgd, ans)
            if (cgd[i][j] == 0):
                col[i][j] = 0
        if (a[i][now + 1] != 0):
            k = 0
            while (k < a[i][now + 1] and j + k <= m):
                if (col[i][j + k] == 1):
                    break
                k += 1
            if (k<a[i][now+1] or (j+a[i][now+1]<=m and col[i][j+a[i][now+1]]==2)):
                return
            k = 0
            while k < a[i][now + 1]:
                if cgd[i][j + k] == 0:
                    if (not self.Set(i, j + k, n, m, a, b, col, nowp, cgd, ans)):
                        break
                k += 1
            if k >= a[i][now + 1]:
                self.dfs(i, j + a[i][now + 1] + 1, now + 1, n, m, a, b, col, nowp, cgd, ans)
            k -= 1
            while (k >= 0):
                if (cgd[i][j + k] == 0):
                    self.restore(i, j + k, n, m, a, b, col, nowp, cgd, ans)
                k -= 1
    def Set(self, x, y, n, m, a, b, col, now, cgd, ans):
        now[y] += 1
        if (b[y][now[y]] == 0):
            now[y] -= 1
            return False
        if x + b[y][now[y]] - 1 > n:
            now[y] -= 1
            return False
        col[x][y] = 2
        i = 1
        while i < b[y][now[y]] and i + x <= n:
            col[x + i][y] = 2
            cgd[x + i][y] = 1
            i += 1
        if x + i <= n:
            col[x + i][y] = 1
            cgd[x + i][y] = 1
        return True
    def restore(self, x, y, n, m, a, b, col, now, cgd, ans):
        col[x][y] = 0
        i = 1
        while i < b[y][now[y]] and i + x <= n:
            col[x + i][y] = 0
            cgd[x + i][y] = 0
            i += 1
        if x + i <= n:
            col[x + i][y] = 0
            cgd[x + i][y] = 0
        now[y] -= 1

C++题解详见：九章solution