DP、DFS-LeetCode 198、332、165（DP, DFS）
DP、DFS-LeetCode 198、332、165（DP, DFS）
DP，DFS：LeetCode #198 332 165
1
编程题
【LeetCode #198】打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1: 输入: [1,2,3,1] 输出: 4 解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。
解题思路：
使用动态规划的方法可以很好的解决这个问题，递推式为dp[n] = max(dp[n-2]+nums[i], dp[n-1])。在这里我们可以理解如果dp[n-2]+nums[i]比较大，就说明当前这家小偷要偷的，并且不会触发警戒，而如果dp[n-1]比较大，那么当前这家就不要偷了，否则就会触发警报，直接更新当前dp[n]。
class Solution {
public:
int rob(vector<int>& nums) {
vector<int> dp(nums.size(), 0);
if(nums.size() == 0) return 0;
if(nums.size() == 1) return nums[0];
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
for(int i = 2; i < nums.size();i++){
dp[i] = max(dp[i-2]+nums[i], dp[i-1]);
}
return dp[nums.size()-1];
}
};动态规划的另一种形式！
class Solution {
public:
int rob(vector<int>& nums) {
int sum1 = 0, sum2 = 0;
for(int i = 0;i < nums.size(); i++){
if(i & 1){
sum1 += nums[i];
sum1 = max(sum1, sum2);
}else{
sum2 += nums[i];
sum2 = max(sum1, sum2);
}
}
return sum1 > sum2 ? sum1 : sum2;
}
};来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/house-robber 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
【LeetCode #332】重新安排行程
给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个从JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 出发。
说明: 如果存在多种有效的行程，你可以按字符自然排序返回最小的行程组合。例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前 所有的机场都用三个大写字母表示（机场代码）。 假定所有机票至少存在一种合理的行程。
示例 1: 输入: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]] 输出: ["JFK", "MUC", "LHR", "SFO", "SJC"]
解题思路：
这个题目主要是数据结构的建立，也就是邻接表如何表示，使用map<string, map>来表示一张车票，至于map结构的使用，就不在说明了，然后使用DFS算法寻找一条通路。 注意在回溯阶段，保持全局变量的回溯状态不变！,="">
class Solution {
public:
int n = 0;
vector<string> res, tmp;
unordered_map<string, map<string, int>> mp;
vector<string> findItinerary(vector<vector<string>>& tickets) {
n = tickets.size();
for(auto& ticket: tickets){
++mp[ticket[0]][ticket[1]];
}
tmp.emplace_back("JFK");
dfs();
return res;
}
void dfs(){
if (res.size() == n + 1) return;
if (tmp.size() == n + 1){
res = tmp; return;
}
for(auto& ss: mp[tmp.back()]){
if(ss.second == 0) continue;
--ss.second;
tmp.emplace_back(ss.first);
dfs();
tmp.pop_back();
++ss.second;
}
}
};来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/reconstruct-itinerary 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
【LeetCode #165】比较版本号
比较两个版本号 version1 和 version2。 如果 version1 > version2 返回 1，如果 version1 < version2 返回 -1， 除此之外返回 0。 你可以假设版本字符串非空，并且只包含数字和 . 字符。 . 字符不代表小数点，而是用于分隔数字序列。 例如，2.5 不是“两个半”，也不是“差一半到三”，而是第二版中的第五个小版本。 你可以假设版本号的每一级的默认修订版号为 0。例如，版本号 3.4 的第一级（大版本）和第二级（小版本）修订号分别为 3 和 4。其第三级和第四级修订号均为 0。
示例 1: 输入: version1 = "0.1", version2 = "1.1" 输出: -1
解题思路：
这里使用一个C++中常用来转换处理字符串的东西，istringstream。他可以轻松的将字符串转换成int型变量，比如123.456，这个字符串在第一次sstream >> num1时，由于num1为int型，故只转换了123，第二次sstream >> ch，由于ch为char型，故只转换了'.'。从而可以自由进行字符的切割和转换！
class Solution {
public:
int compareVersion(string version1, string version2) {
char c;
int num1, num2;
istringstream ist1(version1);
istringstream ist2(version2);
while(bool(ist1 >> num1) + bool(ist2 >> num2)){
if(num1 > num2) return 1;
if(num1 < num2) return -1;
num1 = 0;
num2 = 0;
ist1 >> c;
ist2 >> c;
}
return 0;
}
};来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/compare-version-numbers 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。