Leetcode编程练习一：盗马三则
Leetcode上有三道連續的題目，名字叫做Horse Robber，下面我們一一描述。
一、Horse Robber(id:198)
原文描述：
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and?it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight?without alerting the police.
這道題目簡單的意思就是從一個正整數數列里面盡可能挑選互不相鄰的數字，使它們的和最大。題目的輸入是一個整數數字，輸出是最大的和。比如說【2，1，1，2】最大的和是4 ，【5，1，1，1，5】最大的和為11。
筆者看到這個題目最直接的想法是分別求奇數標號和偶數標號元素的和，這種想法顯然是錯的，舉的第一個例子就是反例。有時候為了特別大的兩個數字能同時添加需要放棄隔一個取一個這種數字數量上最優的選法。這個問題最直觀的解法是枚舉取法，在決策樹的每個內部節點最多只能去掉數列中的2個元素，樹的深度大約是n的一半，時間復雜度是指數級別的。
實際上上述的做法會有大量的重復判斷和計算。用迭代的思想考慮問題，如果我們知道一個數列能得到的最大和是多少，在它后面再增加一個數字，這個新數列能得到的最大值是能容易知道的，因為我們只需要判斷要不要在選取時加入最后一個數所以我們就能從記憶化搜索的角度得到迭代公式。假設數列前k項得到的最大和是f(k),那么：
f(k)=max(f(k-1)+f(k-2)+ak),另外f(0)=0,f(1)=a1
用這個公式對數列進行一次遍歷，就能找到整個數列能得到的最大和。另外，我們看到每一步式子里只涉及最后兩個f的值，可以把解的數組壓縮成奇偶兩個取值，這個算法的時間復雜度是O(n),空間上幾乎完全是原地作業。
源代碼如下：
<span style="font-family: Arial, Helvetica, sans-serif; background-color: rgb(255, 255, 255);"></span><pre name="code" class="cpp"><span style="font-size:14px;">class Solution { public:int rob(vector<int>& nums) {int even=0;int odd=0;int n=nums.size();for (int i=0;i<n;i++){if (i%2){odd=max(odd+nums[i],even);}else{even=max(even+nums[i],odd);}}return max(odd,even);} };</span>
二、Horse Robber (id:213)
原文描述：
After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention.
This time, all houses at this place are?arranged in a circle.?That means the first house is the neighbor of the last one. Meanwhile,
the security system for these houses remain the same as for those in the previous street.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can
rob tonight?without alerting the police.
這個題目和上一個幾乎一樣，求一個數列中互不相鄰數字的最大和，唯一的不同是這次的數列是環形的，首項和末項被視為相鄰的數，我們不能再直接套用上面的算法，因為不能確定f(1)的取值。
筆者首先想到的方法是對數列中每一個元素進行一次嘗試，將其挑選后其左右兩個元素都不用再考慮，然后剩下的數列是頭尾不相鄰的數列，可直接使用上面的算法解決，之后再匯總每次嘗試的最大值得到答案。這種算法時間復雜度是O(n^2).
然而，細心的讀者不難發現這種方法會有大量的重復的判斷，每一次循環在數列相同的位置都在做差不多的判斷。筆者希望能將上一例中較為聰明的算法經過一定轉化在這個問題中轉化，但忘記了除了轉化算法適應問題之外，還有轉化問題適應算法的做法。首尾相鄰的數列和首位不相鄰的數列，在這個問題上除了頭和尾不能同時選擇外沒有其他任何的區別。只要去掉首項或者末項，數列就變成和上例一樣的數列。反正首項和末項我們最多只能取一個，我們只要分別對去掉首項和去掉末項的數列應用上面的算法，再比較得到的兩個最大值，就能得到問題的解了。實際操作過程中發現這個做法不適合只有一個元素的數列，我們要加入一次小小的判斷。
源代碼如下：
class Solution { public:int rob(vector<int>& nums) {int even=0;int odd=0;int x=0,y=0;int n=nums.size();for (int i=0;i<n-1;i++){if (i%2){odd=max(odd+nums[i],even);}else{even=max(even+nums[i],odd);}}x=max(odd,even);even=0;odd=0;for (int i=1;i<n;i++){if (i%2){odd=max(odd+nums[i],even);}else{even=max(even+nums[i],odd);}}y=max(odd,even);if (n==1) return nums[0];return max(x,y); } };
原文描述：
The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root." Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that "all houses in this place forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night.
Determine the maximum amount of money the thief can rob tonight without alerting the police.
這次的問題又稍有不同，我們要從一棵二叉樹中選取盡量多不鄰接的節點，使得它們的和最大。和前面兩次一樣，因為選擇元素的限制僅僅是相鄰，我們希望通過迭代解決問題。因為作和過程中父節點和子節點沒什么區別，我們既可以從下往上求解，也可以從上往下求解。限于輸入結構體的限制，我們選擇前者。設二叉樹根節點為r，記它能得到的最大和是f(r),那么：
f(r)=max(ar+f(r->left->left)+f(r->left->right)+f(r->right->left)+f(r->right->right),f(r->left)+f(r->right));
簡單來說要在兩課子樹的最大和以及4顆子樹的子樹加上根節點的值這兩個值之間選擇。由于 遞推式涉及子節點的子節點，這個算法實現過程中要避免指針指空比較的麻煩，代碼中出現了較多的分支，源代碼如下：
<span style="font-size:14px;">/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/#include <queue>#include <vector> class Solution { public:int rob(TreeNode* root) {if (root==NULL) return 0;if (root->left==NULL&&root->right==NULL){return root->val;}if (root->right==NULL){return max(rob(root->left),root->val+rob(root->left->left)+rob(root->left->right));}if (root->left==NULL){return max(rob(root->right),root->val+rob(root->right->left)+rob(root->right->right));}return max(rob(root->left)+rob(root->right),root->val+rob(root->left->left)+rob(root->left->right)+rob(root->right->left)+rob(root->right->right));} };</span> 根據遞推式簡單估計我們得到時間復雜度滿足：O(n)=2O(n/2)+4O(n/4)
實際運行124個樣例需要1301ms，在計算f(r->left)時就調用了f(r->left->left)等，所以這些重復的調用通過把第一次算出來的值存起來是可以去掉的，我們在結構體中增加一個數據域，在計算前把輸入深拷貝到新的對象中，再進行計算，這樣我們實際上每個節點只用進行一次計算，時間復雜度是O(n)，運行124個OJ上的樣例只用13ms
源程序如下（新類用TreeNode的派生類會更合適，但還是要寫深拷貝函數）
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/ class Solution { public:int rob(TreeNode* root) {node* root2=copy(root);return getRob(root2);}private: struct node{int val;int rob; //rob=-1表示沒有訪問過這個節點node* left;<span style="white-space:pre"> </span>node* right;node(int x){val=x;left=NULL;right=NULL;rob=-1;}node(int x,node* l,node* r){val=x;left=l;right=r;rob=-1;}};node* copy (TreeNode* b){if (b==NULL){return NULL;}return new node(b->val,copy(b->left),copy(b->right));}int getRob(node*& root){if (root==NULL) return 0;if (root->rob==-1){if (root->left==NULL&&root->right==NULL){root->rob=root->val;}elseif (root->right==NULL){root->rob= max(getRob(root->left),root->val+getRob(root->left->left)+getRob(root->left->right));}elseif (root->left==NULL){root->rob= max(getRob(root->right),root->val+getRob(root->right->left)+getRob(root->right->right));}elseroot->rob=max(getRob(root->left)+getRob(root->right),root->val+getRob(root->left->left)+getRob(root->left->right)+getRob(root->right->left)+getRob(root->right->right));}<span style="white-space:pre"> </span> return root->rob;} }; 四、結語要成為一名出色的盜馬賊不是一件簡單的事情。在第一次盜馬過程中我們學會了通過記憶化搜索把問題簡化成只用決定最后一步，在第二次偷竊中我們懂得稍稍改變輸入讓其適應我們已有的算法，在最后一次嘗試中我們學會了把搜索過程中訪問的值進行存儲減少分治過程中運算量的消耗。
總結
以上是生活随笔為你收集整理的Leetcode编程练习一：盗马三则的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： extern小结（转）
- 下一篇： 用python将视频转化为图片