問題連結: https://leetcode.com/problems/uncrossed-lines/
我們有兩個整數陣列A和B, 我們按照整數數字在陣列裡面的順序, 把裡面的數字列成兩排, 屬於A陣列的一排, 屬於B的另一排
若滿足以下條件的話, 我們想要畫線把數字A[i]和B[j]連在一起:
A[i] == B[j];- 當我們從A的某數連到B的某數的時候, 不會跟其他畫的線有任何交集
*當我們說線不能有交集的時候, 也代表一個數字也不能連到一個數字以上
回傳按照這樣條件下, 我們最多可以連幾條線
範例
Input: A = [1,4,2], B = [1,2,4]
Output: 2
解釋: 我們至多可以連兩條線, 1-1跟4-4 或 1-1跟2-2的組合, 不能有三條線是因為若4-4跟2-2放在一起會讓線有交集
想法:
第一個想法應該就是, 我們到底要怎麼樣才能避免線的交集但又同時可以找到最多能畫幾條線?
我一開始並沒有馬上就想到要怎麼做, 我的解法就是先試著看我們用人類的思考模式的時候, 要怎麼直接找答案, 再看看有沒有什麼規律可以讓我們不用在暴力解的方式來解這題
我們可以畫最多線的情況就是A裡面所有的數字都跟B一樣:
比如長這樣:
1 2 3 4
| | | |
1 2 3 4若我們交換3和4在A陣列中的順序 那我們變成只能畫3條線:
1 2 4 3 1 2 4 3
| | / or | | \
1 2 3 4 1 2 3 4然而, 若我們加一個新的數字(或多個)在A陣列或B陣列任一處, 都仍能不改變我們至少能劃出4條線的事實(可能在加數字後我們能畫的線能變多, 但都至少4):
1 2 5 3 4 7
| \ | \
1 6 2 3 5 4所以其實我們大概也找到了一個規律了, 這個問題可以改成要求我們找 兩個陣列中的數字們能組成的最長共同子序列(subsequence).
因為我們在乎的只有數字出現的順序, 就算他們並不是連續著出現或者數字在陣列中的位置沒有一樣, 只要這些數字出現的相對順序在兩陣列中相同就可以幫兩數字畫在一起
只要我們畫的數字們 比我們上一個畫線的兩數字出現順序都還要晚, 我們就能保證兩線不會有交集
程式邏輯:
而其實這個找到兩字串的最長共同子序列(Longest Common Subsequence)算是學習使用動態規劃dynamic programming的入門題, 若你已很熟悉dp概念, 也可以直接滑到最下面看我如何解這題的程式碼
我在解釋完程式碼邏輯後也會用例子跟圖型來解釋我們怎麼解這題
而動態規劃的概念就是我們會利用之前得到的已知結果, 省下重複動作的時間, 算出後面比較大範圍的問題
因為我們現在要找的是最長子序列, 而一個子序列就是由更小的各個子序列們組合而成, 因此若我們把當我們在某特定位置結尾能得到的 最長子序列長度記錄下來, 在之後位置的最長長度就可以參考前面計算過的最長長度
也就是dp[i][j]代表當我們把A陣列中index 0到index i的數字 連 B陣列中index 0到index j的數字的時候, 最多可以連多少線, 因此, dp[2][4]就代表我們想把A[0], A[1], A[2]的數字連上 B[0], B[0], B[1], B[2], B[3], 和B[4]的數字的時候, 最多可以連上幾條不交叉的線
整個邏輯就是我們若想要找到A[0...i]跟B[0...j]數字間 總共可以連幾條的話, 我們必須先檢查A[i] 是否可以跟B[j]連線:
- 若A[i]和B[j]是相同數字, 那我們就可以畫一條線了, 這樣若我們決定要畫線的話, 我們就要來看我們之前找A[0...i-1]跟B[0...j-1]的時候總共可以畫幾條線, 也就是我們要想成若沒有我們沒有我們現在連的這兩個數字的話, 原本圖形可以連幾條線, 只要拿到dp[i-1][j-1]的值, 我們只要再加1就可以代表我們現在A[0]到A[i]間的數字 連到 B[0]到B[j]間的數字可以畫多少線了!
- 若我們不能連A[i]跟B[j], 那代表我們應該看當我們去掉其中一個數字後的整個圖形中最多可以連多少線, 也就是我們要看當我們在我們有數字A[0…i-1] 和 B[0…j] 或 A[0…i] 和B[0…j-1] 的組合中, 哪個可以連最多線, 就當作我們在A[0…i]和B[0…j]組成的圖形最多可以連的線
以下為使用上述邏輯, 4ms的程式碼(贏過 94%):
public int maxUncrossedLines(int[] A, int[] B) {
int count = 0;
int m = A.length, n = B.length;
int[][] dp = new int[m][n];
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(i==0 || j==0)
{
if(A[i]==B[j])
dp[i][j] = 1;
else
{
if(j!=0)
dp[i][j] = dp[i][j-1];
else if(i!=0)
dp[i][j] = dp[i-1][j];
}
continue;
}
if(A[i]==B[j])
dp[i][j] = dp[i-1][j-1]+1;
else
dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);}
}
return dp[m-1][n-1];
}
你會發現因為我們怕當我們參考前一個圖形的時候, 我們會out of bounds, 因此我們用了很多if-else來判斷i=0或j=0的情況 使得整個程式碼比較亂, 因此我們也可以加兩個沒用的格子在A陣列和B陣列的最前面, 之後就不用擔心會參考dp[-1][-1]的問題
因此, dp[i][j]現在代表的是我們從A[0]到A[i-1] 跟 B[0]到B[j-1]之間的數字 最多能連多少線 (如果不要用陣列索引來想的話, 也可以想成dp[i][j]代表A的前i個數字跟B的前j個數字總共可以連多少線)
雖然這樣寫的差別, 時間複雜度並沒有減少, 但至少這樣的程式碼更讓人容易讀得懂(少了很多if-else判斷):
public int maxUncrossedLines(int[] A, int[] B) {
int count = 0;
int m = A.length, n = B.length;
int[][] dp = new int[m+1][n+1];
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
if(A[i-1]==B[j-1])
dp[i][j] = 1 + dp[i-1][j-1];
else
dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
}
}
return dp[m][n];
}👷若你還是不太懂上面的程式碼,那就來看下面的例子能不能讓你更了解整個流程, 假設兩陣列數字為A=[9,6,5,8,7] 和 B=[9,6,6,7,5]:
🔧Step 0. 首先我們需要一個二維矩陣來儲存所有目前找過的結果, 因為我們加了一個空的格子各在A陣列和B陣列的最前面, 已知這些空格不可能可以跟任何數字做相連, 因此我們就直接把這些dp[0][j]和dp[i][0]先填滿0, 代表我們空格跟任何數字能相連的線是0
🔧Step 1: 我們第一個目標就是要找第一列的所有值, 也就是dp[1][j]. 用更容易理解的方式的話, 我們現在就是假設A只有一個數字 — 9️⃣ 我們要依序假設當B 分別有1~5 個數字的時候 — 9️⃣ 6️⃣ 6️⃣ 7️⃣ 5️⃣, 能跟A個別最多能連幾條線
當我們一開始要幫dp[1][1]找值的時候, 也就是代表我們要去找 當A只有一個數字 9️⃣和當 B只有一個數字 9️⃣ 的時候, 最多能連幾條線
我們最先要檢查的就是A的最後一個數字跟B的最後一個數字是否能相連, 因為我們發現這兩個數字可以連在一起, 因此這格dp[1][1]的值就設為1
當我們在幫dp[1][2]找值的時候, 我們要檢查A的9️⃣ 是否能跟B的6️⃣連在一起, 因為無法, 因此我們就保持著我們目前找到最大的值(也就是dp[1][1]的值), 而當我們繼續加數字進去B的結果也都一樣, 一直維持最多只能連成一條線的樣子, 如下圖
9
|
9 6 6 7 5
🔧Step 2: 現在我們要來找第二列的所有值 — dp[2][j], 也就是我們要找當A 只有兩個數字 — 9️⃣6️⃣ , 而B分別有1到5個數字— 9️⃣6️⃣6️⃣7️⃣5️⃣的時候, 總共可以畫幾條線
當我們在dp[2][1]的時候, 代表我們要找當A有2個數字9️⃣6️⃣且B只有 1 個數字9️⃣的時候最多能畫幾條線, 而因為我們不能連線6️⃣ 和9️⃣, 因此我們繼續保持我們在dp[1][1]有的圖形
9 6
|
9接下來, 我們要來看我們在dp[2][2]的值是多少, 我們將會看當A有2個數字9️⃣6️⃣且B也有 2個數字9️⃣ 6️⃣的時候最多能畫幾條線, 現在因為我們能連結A的最後一個數字跟B的最後一個數字, 因此我們接下來要看 當我們去掉這對6的時候可以連多少線(也就是參考dp[1][1]的值), 因為我們在A跟B都只有一個數字的時候就可以連一條線了, 因此現在dp[2][2]可畫的線為2
9 6
| |
9 6接下來, 我們要來看我們在dp[2][3]的值是多少, 我們將會看當A有2個數字9️⃣6️⃣且B有 3個數字9️⃣ 6️⃣6️⃣的時候最多能畫幾條線, 我們發現A的最後一個6️⃣ 可以連到B的最後一個6️⃣, 因此我們要看當我們去掉最後這對6的時候, 我們原本圖形可以畫幾個(也就是參考dp[1][2]的值), 因為原本圖形只能畫一條, 因此dp[2][3]的值為2
9 6
| \
9 6 6接下來, 我們要來看我們在dp[2][4]的值是多少, 我們將會看當A有2個數字9️⃣6️⃣且B有 4個數字9️⃣ 6️⃣6️⃣7️⃣的時候最多能畫幾條線, 因為我們不能連A最後的6️⃣ 跟B最後的7️⃣, 因此我們要來看當我們各去掉A的最後一個6或B去掉最後一個7的時候圖形最多可以連幾條線(也就是參考dp[1][4]跟dp[2][3]), 因為dp[2][3]比較多, 因此在dp[2][4]沿用上個圖形的線條數
9 6
| \
9 6 6 7在 dp[2][5]也是同樣結果, 繼續沿用上個圖形:
9 6
| \
9 6 6 7 8
🔧Step 3. 現在我們要來找第三列的所有值 — dp[3][j], 也就是我們要找當A 有三個數字 — 9️⃣6️⃣ 5️⃣ , 而B分別有1到5個數字 — 9️⃣6️⃣6️⃣7️⃣5️⃣的時候, 總共可以畫幾條線
當我們走到dp[3][5]的時候, 代表我們現在A有3個數字,B有5個數字要來做連連看, 因為我們可以連A陣列中的最後一個5️⃣ 跟B陣列中最後一個5️⃣, 因此我們要來看當我們圖形沒有這兩個數字的時候總共可以連幾條線(也就是參考dp[2][4]的值), 因此我們在這裡總共可以連3條線
9 6 5
| \ |
9 6 6 7 5
🔧Step 4. 現在我們要來找第四列的所有值 — dp[4][j], 也就是我們要找當A 有四個數字 — 9️⃣6️⃣5️⃣8️⃣, 而B分別有1到5個數字 — 9️⃣6️⃣6️⃣7️⃣5️⃣的時候, 總共可以畫幾條線
因為我們在這列新加的數字8並不能連到B中的任一數字, 因此這列的所有結果就會跟上列的結果一模一樣 (直接沿用上列的圖形)
9 6 5 8
| \ |
9 6 6 7 5
🔧Step 5. 現在我們要來找第五列的所有值 — dp[5][j], 也就是我們要找當A 有五個數字 — 9️⃣6️⃣5️⃣8️⃣7️⃣ , 而B分別有1到5個數字 — 9️⃣6️⃣6️⃣7️⃣5️⃣的時候, 總共可以畫幾條線
當我們在dp[5][4]的時候, 代表我們要找A有5個數字且B有4個數字的時候, 總共可以畫幾條線, 因為我們可以把A陣列中最後一個數字7跟B陣列中最後一個數字7連在一起, 因此我們會沿用當A只有前四個數字+B只有前三個數字時的圖形
9 6 5 8 7
| \ |
9 6 6 7當我們來到最後一格dp[5][5]的時候, 代表我們要找A跟B中皆有五個數字的時候, 可以連多少線
因為我們不能把A中最後一個數字跟B中最後一個數字連在一起, 因此我們要來參考先前圖形了, 我們參考當我們去掉A中最後一個數字時跟 參考當我們去掉B中最後一個數字時的圖形, 發現兩者圖形可畫的線都一樣多, 我們可以任意把我們最後一個數字加到其中一個圖形 (所以你也可以說下列兩個圖形都可組成最佳解)
9 6 5 8 7 9 6 5 8 7
| \ | or | \ \
9 6 6 7 5 9 6 6 7 5
👷而我們填完整個dp矩陣後, 我們也找完所有可能的線條數, 在這個例子中我們可以至多連3條線
