New Post

Write your content here!

LeetCode weekly524 Q3. Count Frequency Staircase Subarrays I

problem: https://leetcode.com/contest/weekly-contest-525/problems/count-frequency-staircase-subarrays-i/description/

My solution

class Solution:
    def countStaircase(self, nums: list[int]) -> int:
        stairs = []
        ans = 0
        n = len(nums)
        for i in range(n):
            timing = {}
            count = []
            completed = 0
            for j in range(i, n):
                x = nums[j]
                if x in timing and count[timing[x]] == timing[x] + 1:
                    break
                if x not in timing:
                    timing[x] = len(count)
                    count.append(0)
                count[timing[x]] += 1
                if count[timing[x]] == timing[x] + 1:
                    completed += 1
                if len(timing) == completed:
                    ans += 1
        return ans

I fixed the left endpoint and extended the right endpoint one element at a time. Each distinct value's required frequency is determined by its first-appearance order: 1 for the first distinct value, 2 for the second, and so on.

To avoid checking every frequency after each update, I tracked how many values had reached their required count.

Once a value exceeds its required frequency, extending the subarray cannot fix it, so we can stop exploreing that starting point.

Time: O(N^2), Space: O(N)

DFSの空間計算量

DFSの空間計算量は最大再帰深度で決まる。いつもコードから判断しようとしてこんがらがってしまう。例えばグリッドを左上から右下までDFSで探索するとしたら、最大再帰進度はどれだけ進むかに一致するので、横M,縦Nとすると、O(M+N)となる。移動距離は左上から右下までなので。

経路の最小値などを求める問題、単調増加じゃないパターン

経路の数字のXORが最小となるパスを求める問題。

(i,j)を通ってXORがxとわかっている場合、その後の経路はすでに探索している場合、スキップできる。

class Solution:
    def minCost(self, grid: list[list[int]]) -> int:
        best = float('inf')
        m,n= len(grid), len(grid[0])
        dp = [[set() for _ in range(n)] for _ in range(m)]
        def dfs(x, y, current):
            nonlocal best
            if x == m -1 and y==n-1:
                best = min(best, current)
                return
            if current in dp[x][y]:
                return
            dp[x][y].add(current)
            if x+1 < m:
                dfs(x+1,y,current^grid[x+1][y])
            if y+1<n:
                dfs(x,y+1,current^grid[x][y+1])
        dfs(0,0,grid[0][0])
        return best

各セルごとに異なるXORがUあるとすると、TC: O(MNU), SC(MNU)

class Solution:
    def minCost(self, grid: list[list[int]]) -> int:
        m,n = len(grid), len(grid[0])
        dp = [set() for _ in range(n)]
        dp[0].add(grid[0][0])
        for i in range(m):
            for j in range(n):
                if i == 0 and j == 0:
                    continue
                value = grid[i][j]
                reachable = dp[j] | (dp[j-1] if j > 0 else set())
                dp[j] = {k ^ value for k in reachable}
        return min(dp[-1])

空間計算量を最適化したケース。今回だと、移動は右か下のみ、したがって、上の状態、左の状態から次の状態を計算できる。 したがって、columns方向のdpを保持して、それを上からした、左から右へ更新していく。 すると、dp[j]は一個上（前回のmのループ）で計算した状態、dp[j-1]は一個左（同じmループ、j-1まで処理してきた）の状態.

よって、新しいdpjはdp[j] | dp[j-1] or set() で求められる。

TC: O(MNU), SC: (NU)となる。

人を扱う場合には、相手を論理の動物だと思ってはならない

およそ人を扱う場合には、相手を論理の動物だと思ってはならない。相手は感情の動物であり、偏見に満ちており、自衛心と虚栄心によって行動する動物だと思わなければならない。

だから、批判も非難も意味がない。相手を説得できる、相手に考えを改めさせようとする行為だからだ。それよりも、相手がなぜそうしたかを正しく親身に理解することが大事だ。

藤田晋氏が言ってたな、同業者を批判する社長は大抵成功しないと。論理を欠いているとも言えるし、そういう人は周りの人たちをうまく使うことができないからだろう。

人を素直に褒めることほど重要な能力はない

人を動かすモチベーションとなるのは、大きく二つ。性衝動と偉くなりたいという欲望。偉い、は環境によって異なるが、人から重要な人物だと認められることだ。

よっぽど魅力的無人なら、性衝動で人を動かすことができるが、ビジネスにおいてはそうはいかない。よって、偉くなりたいという願望をコントロールする。

結局は、素直に人を褒めることだ。だが、なかなかこれができない。一般の人は、目についた悪いところを非難するが、いいところは誉めず何も言わないことが多いからだ。

お世辞を言うことで他人を褒めようとする人がいるが、これは効果的ではない。お世辞は多くの場合、真実ではないからだ。真実に対して感嘆を表現することが褒めると言うことだ。

伝えたいことを日本語で話した場合の文字量の半分で英語で伝える

英語で話す力を鍛えるトレーニングの一つ。自分は英語で話す時、冗長に話す癖がある。何度も同じようなことを話してしまう。なぜなら、伝わってないから、伝わってないと感じるから。でも繰り返すたびに余計に伝わらなくなる。

だから、英語で話すときは、日本語で話すよりもずっと分量を少なくすることを心がける必要がある。より伝えたいことをシンプルに、わかりやすく構成しないといけない。英語の量が少なく、たくさん伝えることができたら、その分効率もよくなったと言える。

これ、誰かがnoteで言ってたことなんだが、誰の記事だか忘れてしまった。ただ、読んでから何回も思い出すので、ここにメモっておく。

English!

最近はXXしてる

小さなraft実装を作っている.

I'm building a small Raft implementation.

I build xx. だと慣習的になって不自然。今作っているんだ、なら現在進行形が適切。

バグが多い

バイトオフセットを手動で管理しているから、バグが多い。

I ran into a couple of bugs caused by manually tracking byte offsets.

バグが多い、をバグによく当たると表現する。I ran into A. どんなバグがを後ろから修飾している。 これと、because I manually track byte offsets, so I ran into a couple of bugs.　とすると、 伝わるけど、情報が二つに別れちゃっている。

バグを見つけられる？

バグを見つけることができるか?

Can you spot the bugs?  

バグを見つける -> spot the bug.

uint32でエンコードされている

そのペイロードはuint32でエンコードされている。

The payload is encoded as uint32.

encode as .

コードが短くなって読みやすくなった

コードが短くなって読みやすくなった

The code is shorter and easier to read.

XXができるようになる

A lets us to do.が使える。We can do A.でもいいけど。

Using `bytes.Buffer` lets us write bytes without manually tracking offsets.

Aすることはバグを防ぐのに役立ち、コードの可読性も向上させる。

簡単にいうなら

A helps prevent bugs and makes the code easier to understand.

人間の最も強い衝動

重要人物になりたいと思う欲求は人間の最も強い衝動だ 承認欲求もこれで説明できそうだ 聞き手に徹するのが良いのは話し手のその欲求を満たすためだ 相手の関心があることを話してもらい聞き手に徹するのが最も効率がいい

フリーランスの自己紹介

どこで業務委託しているか言わなくていいかも。聞かれたらでいい。自己紹介でもフリーランスやってます、でいい気がする。メインのクライアントはーとか自分からいう必要はない。

常連

常連ぽくない常連がいい。 私常連です、みたいな感じが表に出過ぎると途端に小物感が出る。常連という特権を使いたくなっている感じだ。まあそれでも少し特別扱いされると嬉しいんだけどね。