阿祁的部落格

LeetCode 2147 - Number of Ways to Divide a Long Corridor 解題心得( 題目 )

解題概念:數學組合

解題方法:我們可以先處理特例，如果出現奇數一定無解，再來解法是把兩個兩個椅子之間形成區間，討論區間與區間之間空格數，相乘就是方法數。

Java參考程式碼(有更好解法可在下方留言，謝謝!):

//Date:2022/1/28

//Author:En Chi Tsung(欉恩祁)

class Solution {

    int cnt;

    final int mod=(int)Math.pow(10,9)+7;

    long ans=1;

    ArrayList<Seg> segment=new ArrayList<>();

     public int numberOfWays(String corridor) {

        for(int i=0;i<corridor.length();i++) {

            if(corridor.charAt(i)=='S') {

                cnt++;

                if(cnt%2==0) {

                    segment.get(segment.size()-1).r=i;

                }

                else {

                    segment.add(new Seg(i));

                }

            }

        }

        if(cnt%2!=0||cnt==0)return 0;

        cnt/=2;

        cnt--;

        for(int i=0;i<cnt;i++) {

            ans*=(segment.get(i+1).l-segment.get(i).r);

            ans%=mod;

        }

        return (int)ans;

    }

}



class Seg{

    int l,r;

    Seg(int a){

        l=a;

    }

}