這是業(yè)務上遇到的一個真實問題。不過原問題比較抽象，為了便于表述，轉(zhuǎn)成一個大家熟悉的場景。
問題描述
某小國的行政劃分包含國，省，市，區(qū)四個級別。它們的關系在邏輯上滿足樹結構，即:
- 除了國以外的節(jié)點，有且僅有一個父節(jié)點。例如某區(qū)只可能屬于唯一的市
- 每個節(jié)點有0~N個子節(jié)點。例如省可以有多個市， 區(qū)沒有下屬行政單位
該小國的法律規(guī)定，低級的行政區(qū)域繼承它的上屬行政區(qū)域的法律條文，并可根據(jù)實際情況自治。
每個行政區(qū)域的政府數(shù)據(jù)庫里記錄了增量的部分。
---文件名: countryA/rule
#國A
rules = {
'increase': ['A1', 'A2', 'A3']
}
---文件名:countryA/provinceA/rule
#省A
rules = {
'increase': ['A4'],
'decrease': ['A1']
}
上面的例子表示國A的條文是A1, A2, A3， 省A的條文是A2, A3, A4，因為省A首先繼承了國A的條文。
不僅如此，每個行政區(qū)域的記錄還可以加入簡單的條件判斷（條文受外部事件影響，例如當發(fā)生戰(zhàn)爭時，新增某個條文），記錄方式如下:
if condition:
rules = {'increase': ['A1', 'A2']}
else:
rules = {'increase': ['A1', 'A3']}
有一天發(fā)生了事故，黑客入侵了系統(tǒng)，刪除了數(shù)據(jù)庫里的記錄。
幸運的是有一個備份系統(tǒng)存儲了所有行政區(qū)域在不同外部條件下的具體條文。
例如某區(qū)C的快照如下:
- no_condition:
A1, A2, A3, A4, A5 - condition1:
A1, A2, A4, A5 - condition2:
A1, A2, A4, A6 - condition3:
A1, A2, A5, A6
現(xiàn)在，希望你寫個程序把被刪掉的記錄(每個行政區(qū)域的增量記錄)恢復。
問題分析
這個問題有兩個關鍵點:
- 把每個節(jié)點的全量數(shù)據(jù)轉(zhuǎn)成以增量數(shù)據(jù)
- 反推條件對值的作用
根據(jù)題意，這是一個樹形結構，我們首先把數(shù)據(jù)結構定義好。
public class Node {
private String name; //節(jié)點名稱
private Node father; //父節(jié)點
private List<Node> sonList; //子節(jié)點列表
private List<String> rules; //節(jié)點的rules
private List<String> increaseRules; //節(jié)點增加的rules
private List<String> decreaseRules; //節(jié)點減少的rules
}
public class Tree {
private String name; //樹名稱
private Node rootNode; //樹的根節(jié)點
}
定義好數(shù)據(jù)結構后，整理輸入和輸出。
輸入:
假設有5個condition，輸入為5份文件，每份文件記錄了一堆節(jié)點信息（只有節(jié)點名稱和rules)， 示例如下：
# condition1
[
{
'name': 'countryA/provinceC/cityM/rules',
'rules': ['A1', 'A2', 'A3']
},
{...}
]
輸出：
1 份文件， 文件記錄每個節(jié)點的增量信息和條件表達式。示例:
if condition1:
node1_increase_rules = ['A1']
else:
node1_increase_rules = ['A2']
node1_decrease_rules = []
node1 = {
'name': 'countryA/provinceC/cityM/rules',
'increase_rules': node1_increase_rules,
'decrease_rules': node1_decrease_rules
}
node_list = [node1, ...]
接下來，就是把結構建好，并轉(zhuǎn)化成我們最終想要的結果了。我們分兩步解決：
- 在默認的
condition（參考系）下, 把節(jié)點組織成樹，并補全節(jié)點的信息。 - 依次代入一個
condition，比較相同位置的節(jié)點之間的差異。
第一步的關鍵是組織這棵樹，可以采用深度優(yōu)先的方式，從根節(jié)點開始，把子節(jié)點加入sonList中，樹就組好了。通過對比父子節(jié)點的rules成員變量，可以把子節(jié)點的increaseRules和decreaseRules計算出來。
第二步的關鍵是找到不同樹中相同位置（其實就是name相同）的節(jié)點，并對比節(jié)點的值如何受到condition影響。要注意的是，對比兩節(jié)點的時候，要比較的是increaseRules和decreaseRules，而不是rules， 因為我們的配置記錄的是increaseRules和decreaseRules
問題解決
實際工程中"法律條文"這一塊是字典形式，編碼實現(xiàn)起來比較冗長，就不貼代碼了。針對上面的問題，大致把類和函數(shù)定義下，其實只要思路清晰，代碼還是很好寫的。
---
public class Node {
private String name; //節(jié)點名稱
private Node father; //父節(jié)點
private List<Node> sonList; //子節(jié)點列表
private List<String> rules; //節(jié)點的rules
private List<String> increaseRules; //節(jié)點增加的rules
private List<String> decreaseRules; //節(jié)點減少的rules
}
public class Tree {
private String name; //樹名稱
private Node rootNode; //樹的根節(jié)點
}
---
public interface Tool {
// condition 編碼
String conditionEncode(Map<String, String> condition);
// condition解碼
Map conditionDecode(String conditionId);
}
---
public interface NodeInterface {
// 生成Node節(jié)點，根據(jù)父節(jié)點的rules和子節(jié)點的rules補全Node的信息
Node generateNode(Node father, String name, List<String> fatherRules, List<String> currentRules);
// 比較兩個節(jié)點，返回increaseRules 和 decreaseRules
Map<String, List> compareTwoNodes(Node origin, Node current);
}
---
public interface TreeInterface {
// 根據(jù)節(jié)點列表構建一棵樹
Tree buildTree(List<Node> nodeList, String treeName);
// 從樹中根據(jù)節(jié)點名稱找到節(jié)點
Node getNodeFromTreeByNodeName(Tree tree, String nodeName);
}
總結
這個問題剛開始拿到的時候覺得非常困難，主要是數(shù)據(jù)結構和工程中的各種細節(jié)特例混雜在一起，思路不清晰。當嘗試著把數(shù)據(jù)結構剝離出來后，其實并不困難。在平時的編碼工作中，對每一個功能點，要優(yōu)先確立數(shù)據(jù)結構，建立正確的模型。
