leetcode第149週試合

leetcode第149週試合

試合感想

1154. 1年目の日付

テーマ大意

解題構想

関連コード

1155. サイコロを投げるN種の方法

テーマ大意

解題構想

関連コード

1156. 単一文字繰り返しサブ列の最大長

テーマ大意

解題構想

関連コード

1157. サブ配列のほとんどを占める要素

テーマ大意

解題構想

関連コード

試合の感想
3問出てきて、最後の問題pythonクエリーはO(n)の方法でタイムアウトして、O(n)より小さい方法をずっと考えていて、それからggですが、他の人がc++で書いたO(n)の方法も巧みで、勉強しました.またpythonはcollectionsを使います.Counterで済むので、このライブラリの最適化はいいでしょう.
1154.一年の何日目
テーマの大意
YYYY-MM-DD形式で日付を表す文字列dateをあげます.その日付がその年の数日目であることを計算して返してください.
通常、1月1日は毎年の1日目、1月2日は毎年の2日目と考えられています.毎月の日数は現行の紀元紀年法(グリコ暦)と一致している.
問題を解く構想.
簡単な問題ですが、各月に何日あるか、閏年の2月に29日(閏年は400の倍数または4の倍数で100の倍数ではありません)、現在の日付の日数は(MM-1)ヶ月の日数の合計+DDです.
関連コード

class Solution:
    def ordinalOfDate(self, date: str) -> int:
    	#          ，         
        month_days = []
        for i in range(12):
            if i == 1:
                month_days.append(28)
            elif i % 2 == 0:
                if i <= 6:
                    month_days.append(31)
                else:
                    month_days.append(30)
            elif i % 2 == 1:
                if i <= 6:
                    month_days.append(30)
                else:
                    month_days.append(31)

        year = int(date[0:4])
        month = int(date[5:7])
        day = int(date[8:])
        ans = 0
        for i in range(1, month):
            ans += month_days[i - 1]
            if i == 2 and (year % 400 == 0 or (year % 4 == 0 and year % 100 != 0)):
                ans += 1
        ans += day
        return ans

1155.サイコロを投げるN種類の方法
テーマの大意
ここにはd個の同じサイコロがあり、各サイコロにはf個の面があり、それぞれ1,2,...,fと表記されている.
私たちはサイコロを投げる総点数を各サイコロが上を向いている数字の総和とすることを約束した.
投げた総点数がtargetである必要がある場合は、どのような異なる組み合わせ(すべての組み合わせにf^d種類がある)があるかを計算し、型10^9+7を返します.
問題を解く構想.
ダイナミックプランニングは,ans[i][j]でi個のサイコロを用いてjを投げた組合せの総数を表す.ans[0][0]=1,ans[i][j]=ans[i-1][j-1]+ans[i-1][j-2]+...+ans[i-1][j-f],最後にans[d][target]を出力すればよい.各層は上の層のみに関係するため、少し空間最適化を加えることができ、ans[j]=ans[j-1]+...+ans[j-f],jの状態は大きいから小さいまで遍歴すればよく、最後にans[target]を出力し、型で割ることを覚えておいてください.
関連コード

class Solution:
    def numRollsToTarget(self, d: int, f: int, target: int) -> int:
        ans = [0 for j in range(target + 1)]
        ans[0] = 1
        for i in range(d):
            for j in range(target , -1, -1):
                ans[j] = 0
                for k in range(1, f + 1):
                    if j - k >= 0 and ans[j - k] != 0:
                        ans[j] = (ans[j] + ans[j - k]) % (10**9 + 7)
        return ans[target]

1156.単一文字重複サブストリングの最大長
テーマの大意
文字列のすべての文字が同じである場合、この文字列は単一文字で繰り返される文字列です.
文字列textを1つあげます.2つの文字を一度に交換するか、何もしないで、単一の文字が重複するサブストリングを得るしかありません.最も長いサブストリングの長さを返します.
問題を解く構想.
この問題の意味ははっきりしていて、1つの文字しか交換できないか、交換しないかのどちらかなので、私たちは毎回3段、上段同じ、上段同じ、現在同じ段を記録します.上段の内容が現在のセグメントの内容と一致し、上段の文字が1つしかない場合は、上段を交換して、上段と現在のセグメントをつなぎ合わせることができます.他の場所に現在のセグメントの文字がある場合は、他の場所の文字で置き換えることができます.ない場合は、上段の一番左側または現在のセグメントの一番右側でしか上段を置き換えることができません.
関連コード

class Solution:
    def maxRepOpt1(self, text: str) -> int:
        alphabet_map = {'':0}
        #            
        for each in text:
            if each not in alphabet_map:
                alphabet_map[each] = 1
            else:
                alphabet_map[each] += 1
        #            
        last_last_alp = ''
        last_last_sum = 0
        #    
        last_alp = ''
        last_sum = 0
        #    
        now_alp = ''
        now_sum = 0
        ans = 0
        
        for each in text:
            if each == now_alp:
                now_sum += 1
            else:
                if last_sum == 1 and now_alp == last_last_alp:
                    if alphabet_map[now_alp] > last_last_sum + now_sum:
                        ans = max(ans, last_last_sum + now_sum + 1)
                    else:
                        ans = max(ans, last_last_sum + now_sum)
                else:
                    if alphabet_map[now_alp] > now_sum:
                        ans = max(ans, now_sum + 1)
                    else:
                        ans = max(ans, now_sum)
                        
                last_last_sum = last_sum
                last_last_alp = last_alp
                last_sum = now_sum
                last_alp = now_alp
                now_alp = each
                now_sum = 1
		#               
        if last_sum == 1 and now_alp == last_last_alp:
            if alphabet_map[now_alp] > last_last_sum + now_sum:
                ans = max(ans, last_last_sum + now_sum + 1)
            else:
                ans = max(ans, last_last_sum + now_sum)
        else:
            if alphabet_map[now_alp] > now_sum:
                ans = max(ans, now_sum + 1)
            else:
                ans = max(ans, now_sum)
                
        return ans

1157.サブ配列のほとんどを占める要素
テーマの大意
MajorityCheckerのクラスを実装します.以下のAPIをいくつか持つ必要があります.

MajorityChecker(int[]arr)は、与えられた配列arrを使用してMajorityCheckerのインスタンスを構築します.

int query(int left,int right,int threshold)には、次のパラメータがあります.

0<=left<=right

2*threshold>right-left+1、すなわちバルブ値thresholdは常にサブシーケンスの長さの半分よりも大きい.

クエリーquery(...)のたびにarr[left],arr[left+1],...,arr[right]に少なくともバルブ値回数thresholdが現れる要素が返され,このような要素が存在しない場合は−1が返される.
問題を解く構想.
一般的なアイデアqueryは範囲内の数を統計し、補助的な空間が必要であり、効率的には相対的に遅い可能性があります.問題に条件が与えられているため、thresholdはクエリ範囲の半分よりも長いに違いありません.答えは存在しないか、1つの答えしかありません.では、クエリーの範囲を2つのabに分けることを考えることができます.もしaセグメントに半分を超えた数がなければ、bセグメントにも半分を超えた数がなければ、存在しないに違いありません.したがって、それを可能にするには、aセグメントの半分を超えず、bセグメントの半分を超えなければならない(数学の反証法に似ている).では、最初から遍歴を始め、最初の数を基準にn番目の数を検索すると、基準の数と基準ではない数がちょうど半分で、aセグメントの半分を超えていない数を満たしているので、bセグメントを直接見て、基準をbセグメントの最初の数に割り当てて、遍歴が終わるまでします.最後に得られた基準は、クエリー範囲の最大数ではなく、クエリー範囲の長さの半分以上になる可能性がある数であることに注意してください.
関連コード
c++コード

class MajorityChecker {
public:
    vector<int> my_arr;
    
    MajorityChecker(vector<int>& arr) {
        my_arr = arr;
    }
    
    int query(int left, int right, int threshold) {
    	//          number
        int number = my_arr[left];
        int count = 1;
        for (int i = left + 1; i <= right; ++i)
        {
            if (my_arr[i] == number)
            {
                ++count;
            }   
            else if (count > 0)
            {
                --count;
            }
            else
            {
                count = 1;
                number = my_arr[i];
            }
        }
        //   
        count = 0;
        for (int i = left; i <= right; ++i)
            if (my_arr[i] == number)
                ++count;
        if (count >= threshold)
        {
            return number;   
        }
        
        return -1;     
    }
};

python 3コード

class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.arr = arr

    def query(self, left: int, right: int, threshold: int) -> int:
        temp = self.arr[left:right+1]
        dic = collections.Counter(temp)
        for key, val in dic.items():
            if val >= threshold:
                return key
        return -1