前言
AI輔助已經(jīng)成為勢(shì)不可擋的趨勢(shì)，學(xué)如逆水行舟不進(jìn)則退。
那么便擁抱趨勢(shì)，嘗試用AI來(lái)解決問(wèn)題。
但工作上內(nèi)容有太多上下文，不方便清晰表述問(wèn)題，下面分享我用AI來(lái)如何做題。
題目A
傳統(tǒng)算法練習(xí)的第一件事就是讀題。（對(duì)應(yīng)到工作中的需求開(kāi)發(fā)，就是讀懂需求）
過(guò)往每次讀題都是比較痛苦的事情，以下面題目為例，已經(jīng)是非常簡(jiǎn)潔的題目。
現(xiàn)在大模型可以直接幫忙翻譯，并且效果非常不錯(cuò)：
A.烤羊肉串（Shashliks）
你是一家熱門烤羊肉串餐廳的老板，而你的烤架是廚房的核心。
不過(guò)，這臺(tái)烤架有個(gè)特點(diǎn)：每烤完一串羊肉串后，它的溫度會(huì)下降。
你需要盡可能多地烤制羊肉串，并且有無(wú)限量的兩種類型的串可供烤制：
- 第一種類型在開(kāi)始烤制時(shí)，要求烤架溫度至少為α度，烤制完成后，烤架溫度會(huì)下降x度。
- 第二種類型在開(kāi)始烤制時(shí)，要求烤架溫度至少為b度，烤制完成后，烤架溫度會(huì)下降y度。
最初，烤架的溫度是k度。請(qǐng)確定最多能烤制的羊肉串份數(shù)。
注意，烤架的溫度可以是負(fù)數(shù)。
輸入
每個(gè)測(cè)試包含多個(gè)測(cè)試用例。第一行包含測(cè)試用例的數(shù)量t（t ≤ 10?）。接下來(lái)是各測(cè)試用例的描述。
每個(gè)測(cè)試用例僅一行，包含五個(gè)整數(shù)k、a、b、x、y（1 ≤ k, a, b, x, y ≤ 10?）
分別是烤架的初始溫度、烤制第一種和第二種羊肉串所需的起始溫度，以及烤制第一種和第二種羊肉串后烤架的溫度下降值。
輸出
對(duì)于每個(gè)測(cè)試用例，輸出一個(gè)整數(shù)——即你最多能烤制的羊肉串份數(shù)。
示例
輸入
5
10 3 4 2 1
1 10 10 1 1
100 17 5 2 3
28 14 5 2 4
277 5 14 1 3
輸出
8
0
46
10
273
題目解析：
翻譯只是牛刀小試，并沒(méi)有真正發(fā)揮AI的作用，最多算是熱身。
對(duì)于我而言，我會(huì)有自己的一套解題思路和習(xí)慣，而現(xiàn)在就是需要讓AI順著我的思路去做。（切記，這里不是讓AI直接輸出答案）
比如說(shuō)，我會(huì)按照我的思維，先輸入前面的提示詞“假設(shè)只有一種肉串” ，然后AI會(huì)沿著我的思路補(bǔ)全結(jié)果。
這里如果沒(méi)有前置的提示詞，那么AI的解題思路就會(huì)非常隨機(jī)，容易出現(xiàn)幻覺(jué)。
我們發(fā)現(xiàn)AI提示的做法不錯(cuò)，那么可以采用它所給出的建議。
然后為了方便計(jì)算，我們希望交換x、y保證x<y，于是可以簡(jiǎn)單描述，讓AI補(bǔ)全。
得到最終解法：
假設(shè)只有一種肉串，那么可以直接計(jì)算得到結(jié)果，計(jì)算k與a之間的差值，除以x就可以得到數(shù)量；
假設(shè)只有兩種肉串，我們會(huì)優(yōu)先烤制溫度下降更少的類型，當(dāng)無(wú)法烤制這種肉串時(shí)，再去烤制另外一種類型的肉串，這樣就得到最優(yōu)解了。
我們可以通過(guò)交換，使得假設(shè)溫度下降更多的類型為a，溫度下降更少的類型為b；
如果x>y，我們可以交換x和y，以及a和b，這樣可以保證x<=y；
如果k<a，那么無(wú)論如何都無(wú)法烤制到第一種類型的肉串，輸出0；
如果k>=a，先計(jì)算可以烤制a類型的肉串的數(shù)量，再計(jì)算可以烤制b類型的肉串的數(shù)量；
具體代碼：
在前面寫(xiě)完解法之后，下面的實(shí)現(xiàn)過(guò)程就會(huì)非常輕松，比如說(shuō)這里的交換。
又比如接下來(lái)的計(jì)算過(guò)程。
題目B 良好開(kāi)端
屋頂是一個(gè)尺寸為w×h的矩形，其左下角在平面上的點(diǎn)(0, 0)處。你的團(tuán)隊(duì)需要用尺寸為a×b的相同屋面板完全覆蓋這個(gè)屋頂，需滿足以下條件：
- 屋面板不能旋轉(zhuǎn)（即使旋轉(zhuǎn)90度也不行）。
- 屋面板之間不能重疊（但邊緣可以接觸）。
- 屋面板可以延伸到矩形屋頂?shù)倪吔缰狻?/li>
你團(tuán)隊(duì)的一名新手已經(jīng)以屋面板不重疊且每塊都部分覆蓋屋頂?shù)姆绞?，在屋頂上放置了兩塊這樣的屋面板。
你的任務(wù)是判斷，在不移除已放置的這兩塊屋面板的情況下，是否有可能完全鋪滿屋頂。
輸入
每個(gè)測(cè)試包含多個(gè)測(cè)試用例。第一行包含測(cè)試用例的數(shù)量t（1 ≤ t ≤ 10?）。接下來(lái)是各測(cè)試用例的描述。
每個(gè)測(cè)試用例的第一行包含四個(gè)整數(shù)w、h、a、b（1 ≤ w, h, a, b ≤ 10?）——分別是屋頂?shù)某叽绾臀菝姘宓某叽纭?br>
每個(gè)測(cè)試用例的第二行包含四個(gè)整數(shù)x?、y?、x?、y?（-a + 1 ≤ x?, x? ≤ w - 1，-b + 1 ≤ y?, y? ≤ h - 1）——已放置屋面板左下角的坐標(biāo)。保證這些屋面板不重疊。
輸出
對(duì)于每個(gè)測(cè)試用例，如果在不移除已放置的兩塊屋面板的情況下有可能完全鋪滿屋頂，輸出“Yes”（不加引號(hào)）；否則輸出“No”（不加引號(hào)）。
你可以用任意大小寫(xiě)輸出答案。例如，字符串“yEs”、“yes”、“Yes”和“YES”都會(huì)被視為有效肯定回復(fù)。
示例
輸入
7
6 5 2 3
-1 -2 5 4
4 4 2 2
0 0 3 1
10 9 3 2
0 0 4 3
10 9 3 2
0 0 6 3
5 5 2 2
-1 -1 4 -1
5 5 2 2
-1 -1 2 3
7 8 2 4
0 0 0 5
輸出
Yes
No
No
Yes
No
Yes
No
題目解析：
核心思路和上面一樣，先提供一點(diǎn)想法讓AI補(bǔ)全，自己判斷是否可行，以及是否能從補(bǔ)全中獲取到提示。
不斷選擇有用的信息，讓整個(gè)想法趨于完整，注意看自己的分類討論是否符合MECE原則。
先假設(shè)只有一個(gè)已存在木板的情況，由于題目要求允許木板延伸到邊界之外，那么只需要從已存在木板按照邊緣對(duì)齊的方式開(kāi)始向外延伸，最終總是能鋪滿整個(gè)區(qū)域；
那有兩個(gè)木板的情況呢？
先考慮兩個(gè)木板橫坐標(biāo)相同，縱坐標(biāo)有差別的情況，此時(shí)上下間距如果是木板高的整數(shù)倍，那么一定可以鋪滿；（如果不是整數(shù)倍，那么中間要么放不下，要么留下空隙）
再考慮兩個(gè)木板縱坐標(biāo)相同，橫坐標(biāo)有差別的情況，此時(shí)左右間距如果是木板寬的整數(shù)倍，那么一定可以鋪滿；（道理同上）
如果橫縱坐標(biāo)都不相同，那么上面兩種情況都可以考慮，比如說(shuō)順著原來(lái)已有木板上下延伸，這樣肯定可以鋪出來(lái)兩條線，接下來(lái)就看兩條線中間是否能夠鋪滿即可；
如果兩條線中間的間距不是木板高的整數(shù)倍，那么一定無(wú)法鋪滿。
具體代碼：
注意在使用IDE的過(guò)程中，最好是先輸入A的判斷條件，等待AI補(bǔ)全，觀察是否正確，然后采用；
接著等待AI補(bǔ)全，選用代碼塊B，然后再選用代碼塊C。
先寫(xiě)判斷條件，讓補(bǔ)全代碼塊A，這樣正確率會(huì)比較高；（如果A/B/C一起補(bǔ)全，大概率會(huì)遺漏一些細(xì)節(jié)，不管是AI還是作為review人的自己）
當(dāng)代碼塊A處理正確，代碼塊B作為同類代碼，大模型推薦準(zhǔn)確率能到99%；
接著代碼塊C準(zhǔn)確率也很高，只要前面的注釋寫(xiě)清楚了思路。
題目鏈接 C. 斯米洛與《我的世界》（Smilo and Minecraft）
男孩斯米洛正在玩《我的世界》！
為了準(zhǔn)備與末影龍的戰(zhàn)斗，他需要大量的金蘋果，而這需要很多金子。
因此，斯米洛前往礦井。
礦井是一個(gè)尺寸為n×m的矩形網(wǎng)格，每個(gè)單元格可能是金礦石、石頭或空單元格。
斯米洛可以在任意空單元格引爆炸藥。
當(dāng)炸藥在坐標(biāo)為(x, y)的空單元格爆炸時(shí)，以(x, y)為中心、邊長(zhǎng)為2k + 1的正方形內(nèi)的所有單元格都會(huì)變成空的。
如果金礦石嚴(yán)格位于這個(gè)正方形內(nèi)部（不在邊界上），它會(huì)消失。
然而，如果金礦石位于這個(gè)正方形的邊界上，斯米洛會(huì)收集到那些金子。
炸藥只能在礦井內(nèi)部引爆，但爆炸形成的正方形可能會(huì)延伸到礦井邊界之外。
確定斯米洛能收集到的最大金子數(shù)量。
輸入
每個(gè)測(cè)試包含多個(gè)測(cè)試用例。第一行包含測(cè)試用例的數(shù)量t（1 ≤ t ≤ 10?）。接下來(lái)是各測(cè)試用例的描述。
每個(gè)測(cè)試用例的第一行包含三個(gè)整數(shù)n、m、k（1 ≤ n, m, k ≤ 500）——分別表示行數(shù)、列數(shù)和爆炸參數(shù)k。
接下來(lái)的n行，每行包含m個(gè)字符，字符為'.'、'#'或'g'，其中'.'表示空單元格，'#'表示石頭，'g'表示金子。保證至少有一個(gè)單元格是空的。
保證所有測(cè)試用例的n·m之和不超過(guò)2.5·10?。
輸出
對(duì)于每個(gè)測(cè)試用例，輸出一個(gè)整數(shù)——能獲得的最大金子數(shù)量。
示例
輸入
3
2 3 1
#.#
g.g
2 3 2
#.#
g.g
3 4 2
.gg.
g..#
g##.
輸出
2
0
4
題目解析：
這個(gè)題目難度比前面兩道題目有明顯提升，并且會(huì)有對(duì)應(yīng)的算法優(yōu)化操作，AI很難直接給出正確解法，更多時(shí)候是補(bǔ)全似是而非的做法， 反而提高了題目復(fù)雜度。
我個(gè)人習(xí)慣，還是從簡(jiǎn)單開(kāi)始分析題目。
我提供解題框架，AI不斷補(bǔ)充細(xì)節(jié)，提供想法擴(kuò)展，最終組合出來(lái)正確解法。
注意題目限制，爆炸的次數(shù)并沒(méi)有任意限制，并且爆炸區(qū)域是可以超出邊界；
并且由于爆炸之后，會(huì)把爆炸區(qū)域內(nèi)的所有東西都清空，包括之前已經(jīng)有的東西，也就是會(huì)制造新的空格子。
那么，選擇哪個(gè)空格子開(kāi)始爆炸，以及爆炸的先后順序都會(huì)影響最終答案。
先從k=1的情況開(kāi)始考慮，此時(shí)爆炸區(qū)域和收獲區(qū)域相同，那么隨便找一個(gè)空格子放置炸彈，然后不斷沿著爆炸邊緣的空格子繼續(xù)爆炸，直到?jīng)]有空格子；
由于題目限制，至少存在一個(gè)空格子，那么結(jié)果就是所有金子數(shù)量。
再考慮k=2的情況，當(dāng)我們選擇某個(gè)位置(x, y)開(kāi)始爆炸之后，我們只需要沿著(x+1, y)和（x, y+1）的位置繼續(xù)放炸彈，這樣總是能炸完整個(gè)區(qū)域；
并且除了最初格子之外的金子我們都能收獲。
那么k=2就是找到一個(gè)空格子，以該格子為爆炸中心，所損失的金子數(shù)最少的，那么最終收獲的格子就會(huì)盡可能多。
題目就變成了：尋找一個(gè)空格子為中心，爆炸距離為(k-1)范圍內(nèi)的金子數(shù)量最少的區(qū)域。
遍歷整個(gè)區(qū)域，找到空格子，一共有O(N2）的復(fù)雜度；
每個(gè)格子的計(jì)算成本，也是需要遍歷矩形，單次復(fù)雜度是O(N2）；
那么總的復(fù)雜度就是O(N^4），整體復(fù)雜度會(huì)比較高。
遍歷的復(fù)雜度比較容易優(yōu)化，我們可以先計(jì)算好每個(gè)空格子到左上角（0，0）的金子數(shù)量sum[i][j]，那么在計(jì)算金子數(shù)量時(shí)，可以用公式：
sum[i+k-1][y+k-1] - sum[x-k][y] - sum[x][y-k] + sum[x-k][y-k]；
這樣計(jì)算的復(fù)雜度可以控制在O(1)，那么總體復(fù)雜度是O(N^2）；
這個(gè)題目首先需要我明確從k=1開(kāi)始考慮，此時(shí)條件很簡(jiǎn)單，AI也能補(bǔ)全正確解法。
k=2開(kāi)始有點(diǎn)復(fù)雜，我根據(jù)題目限制找到最少有一個(gè)空格子，那么也就是一定可以找到一個(gè)起點(diǎn)爆炸，然后順著這個(gè)爆炸區(qū)域把所有格子炸完。
題解寫(xiě)到這里的時(shí)候，AI已經(jīng)明白了這種一種解法，但是仍然沒(méi)有最優(yōu)解。
于是我再補(bǔ)充了額外的信息，也就是去找到首次爆炸損失金子最少的區(qū)域，再用所有金子數(shù)量去減掉損失數(shù)，得到最多金子。
但是，我粗估了一下，直接計(jì)算復(fù)雜度比較高，肯定會(huì)超時(shí)。
于是我繼續(xù)補(bǔ)充優(yōu)化措施，最常見(jiàn)的預(yù)處理操作，這個(gè)是AI非常擅長(zhǎng)的。
我僅僅提示了預(yù)處理的sum[i][j]，AI就幫我補(bǔ)全了公式內(nèi)容、算法復(fù)雜度。
亮點(diǎn)不僅于此，AI提效最明顯的還是下面的代碼部分。
具體代碼：
當(dāng)寫(xiě)完題解、開(kāi)始寫(xiě)代碼時(shí)，可以感受到AI輔助的高效所在。
代碼塊A的輔助是直接補(bǔ)全，并且直接達(dá)到了可用程度。
代碼塊B的補(bǔ)全最重要的細(xì)節(jié)就是116這一行公式，通常我們?cè)谟?jì)算的時(shí)候，不僅需要考慮各種邊界情況，還容易遺漏某個(gè)數(shù)字、寫(xiě)錯(cuò)某個(gè)操作符等。
而AI補(bǔ)全不僅很全面，還完全對(duì)應(yīng)到前面題解所推導(dǎo)出來(lái)的公式。
我作為代碼reviewer僅僅需要做一個(gè)校驗(yàn)。
總結(jié)
AI輔助效果非常明顯，周末所做的三個(gè)題都是一次過(guò)，100%正確率。
把算法題當(dāng)做需求，在需求理解、需求分析和需求實(shí)現(xiàn)的過(guò)程中，AI輔助的效果還是非常明顯。
本次所用IDE為Trae。
