深度优先搜索解题算法2

桃扇骨 2023-07-24 14:42 5阅读 0赞

### 深度优先搜索解题算法2 ###

*   *   *  题目1：重新安排行程
         *  题目2：打家劫舍
         *  题目3：员工的重要性
         *  题目4：火柴正方形
         *  题目5：目标和

### 题目1：重新安排行程 ###

给定一个机票的字符串二维数组 \[from, to\]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个从JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 出发

如果存在多种有效的行程，你可以按字符自然排序返回最小的行程组合。例如，行程 \[“JFK”, “LGA”\] 与 \[“JFK”, “LGB”\] 相比就更小，排序更靠前

> 示例 1:  
> 输入: \[\[“JFK”,“SFO”\],\[“JFK”,“ATL”\],\[“SFO”,“ATL”\],\[“ATL”,“JFK”\],\[“ATL”,“SFO”\]\]  
> 输出: \[“JFK”,“ATL”,“JFK”,“SFO”,“ATL”,“SFO”\]  
> 解释: 另一种有效的行程是 \[“JFK”,“SFO”,“ATL”,“JFK”,“ATL”,“SFO”\]。但是它自然排序更大更靠后

解题思路：深度优先搜索

class Solution { 
    public:
        unordered_map<string,multiset<string>>map;
        vector<string> res;
        vector<string> findItinerary(vector<vector<string>>& tickets) { 
            for(auto& t:tickets){ 
                map[t[0]].insert(t[1]);
            }
            dfs("JFK");
            return vector<string>(res.rbegin(),res.rend());
        }
        void dfs(string from){ 
            while(map[from].size()!=0){ 
                string next = *map[from].begin();
                map[from].erase(map[from].begin());
                dfs(next);
            }
            res.push_back(from);
        }
    };

### 题目2：打家劫舍 ###

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

示例 1:
    
    输入: [3,2,3,null,3,null,1]
    
         3
        / \
       2   3
        \   \ 
         3   1
    
    输出: 7 
    解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.

示例 2:
    输入: [3,4,5,1,3,null,1]
    
         3
        / \
       4   5
      / \   \ 
     1   3   1
    
    输出: 9
    解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.

解题思路：深度优先搜索和相邻关系，每个节点有偷和不偷两种可能，如果偷，则子节点不可以偷，但可以偷孙子节点，如果不偷当前节点，则可以偷子节点.

C++ 参考代码

class Solution { 
    public: 
        int rob(TreeNode* root) { 
            if(root == NULL) return 0;
            //偷取该节点
            int s1 = root->val;
            if(root->left != NULL){ 
                s1 += rob(root->left->left) +\
                     rob(root->left->right);
            }
            if(root->right != NULL){ 
                s1 += rob(root->right->left) +\
                    rob(root->right->right);
            }
            //不偷取该节点
            int s0 = 0;
            s0 += rob(root->left) + rob(root->right);
            return max(s0,s1);
        }
    };

避免重复计算，用容器保存已经计算过的值

class Solution { 
    public: 
        unordered_map<TreeNode*,int>map;
        int rob(TreeNode* root) { 
            if(root == NULL) return 0;
            //偷取该节点
            if(map.count(root)){ 
                return map[root];
            }
            int s1 = root->val;
            if(root->left != NULL){ 
                s1 += rob(root->left->left) +\
                     rob(root->left->right);
            }
            if(root->right != NULL){ 
                s1 += rob(root->right->left) +\
                    rob(root->right->right);
            }
            //不偷取该节点
            int s0 = 0;
            s0 += rob(root->left) + rob(root->right);
            map[root] = max(s0,s1);
            return map[root];
        }
    };

### 题目3：员工的重要性 ###

给定一个保存员工信息的数据结构，它包含了员工唯一的id，重要度 和 直系下属的id。

比如，员工1是员工2的领导，员工2是员工3的领导。他们相应的重要度为15, 10, 5。那么员工1的数据结构是\[1, 15, \[2\]\]，员工2的数据结构是\[2, 10, \[3\]\]，员工3的数据结构是\[3, 5, \[\]\]。注意虽然员工3也是员工1的一个下属，但是由于并不是直系下属，因此没有体现在员工1的数据结构中。

现在输入一个公司的所有员工信息，以及单个员工id，返回这个员工和他所有下属的重要度之和。

> 示例 1:  
> 输入: \[\[1, 5, \[2, 3\]\], \[2, 3, \[\]\], \[3, 3, \[\]\]\], 1  
> 输出: 11  
> 解释:  
> 员工1自身的重要度是5，他有两个直系下属2和3，而且2和3的重要度均为3。因此员工1的总重要度是 5 + 3 + 3 = 11

解题思路：通过遍历找到指定 id 的员工重要性，然后迭加

class Employee { 
    public:
        int id;
        int importance;
        vector<int> subordinates;
    };
    
    class Solution { 
    public:
        int importance = 0;
        int getImportance(vector<Employee*> employees, int id) { 
            int index;
            for(int i = 0;i<employees.size();++i){ 
                if(employees[i] == nullptr) return importance;
                if(id == employees[i]->id){ 
                    index = i;
                    importance += employees[i]->importance;
                }
            }
            for(int i = 0;i<employees[index]->subordinates.size();++i){ 
                getImportance(employees,employees[index]->subordinates[i]);
            }
            return importance;
        }
    };

### 题目4：火柴正方形 ###

还记得童话《卖火柴的小女孩》吗？现在，你知道小女孩有多少根火柴，请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴，可以把火柴连接起来，并且每根火柴都要用到。

输入为小女孩拥有火柴的数目，每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形

> 示例 1:  
> 输入: \[1,1,2,2,2\]  
> 输出: true  
> 解释: 能拼成一个边长为2的正方形，每边两根火柴。  
> 示例 2:  
> 输入: \[3,3,3,3,4\]  
> 输出: false  
> 解释: 不能用所有火柴拼成一个正方形

解题思路：对于给定的若干根火柴，将它们分成四组，每一根火柴恰好属于其中的一组；每一组火柴的长度之和都相同，等于所有火柴长度之和的四分之一

使用深度优先搜索枚举出所有的分组情况，并对于每一种情况，判断是否满足上述的条件

我们依次对每一根火柴进行搜索，当搜索到第 i 根火柴时，我们可以把它放到四组中的任意一种。对于每一种放置方法，我们继续对第 i + 1 根火柴进行递归搜索。当我们搜索完全部的 N 根火柴后，再判断每一组火柴的长度之和是否都相同

C++ 参考代码

class Solution { 
    public:
        bool makesquare(vector<int>& nums) { 
            // 先判断简单的情况，如果 nums 元素个数小于4
            int sum = 0;
            for(auto&e:nums){ 
                sum+=e;
            }
            if(nums.size()<4 || sum % 4 != 0) { 
                return false;
            }
            int target = sum / 4;
            // 降序排序
            sort(nums.begin(),nums.end(),greater<int>());
            vector<int>partition(4,0);
            return dfs(target,partition,0,nums);
        }
    
        bool dfs(int target,vector<int>&partition,int index,vector<int>&nums){ 
            if(index == nums.size()){ 
                return (partition[0]==partition[1] &&
                       partition[1] == partition[2] &&
                       partition[2] == partition[3]);
            }
            for(int i = 0;i<4;++i){ 
                if(partition[i] + nums[index] > target){ 
                    continue;
                }
                partition[i] +=nums[index];
                if(dfs(target,partition, index + 1,nums)){ 
                    return true;
                }
                partition[i] -= nums[index];
            }
            return false;
        }
    };

### 题目5：目标和 ###

给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

> 示例 1:  
> 输入: nums: \[1, 1, 1, 1, 1\], S: 3  
> 输出: 5  
> 解释:  
> \-1+1+1+1+1 = 3  
> \+1-1+1+1+1 = 3  
> \+1+1-1+1+1 = 3  
> \+1+1+1-1+1 = 3  
> \+1+1+1+1-1 = 3  
> 一共有5种方法让最终目标和为3。  
> 注意:  
> 数组非空，且长度不会超过20。  
> 初始的数组的和不会超过1000。  
> 保证返回的最终结果能被32位整数存下

解题：暴力搜索法，枚举出所有的可能性，我们可以把问题看做一个将目标值变为 0 的情况个数

class Solution { 
    public:
        int count = 0;
        int findTargetSumWays(vector<int>& nums, int S) { 
            int len = nums.size();
            dfs(nums,S,0,len);
            return count;
        }
        void dfs(vector<int>&nums,long target,int i,int len){ 
            if(i == len && target == 0){ 
                count++;
                return;
            }
            if(i == len) return;
            dfs(nums,target - nums[i],i+1,len);
            dfs(nums,target + nums[i],i+1,len);
        }
    };