链表、DFS-LeetCode 216、213、148、202（链表归并排序，组合数问题）
链表、DFS-LeetCode 216、213、148、202（链表归并排序，组合数问题）
链表、DFS：LeetCode #216 213 148 202
1
编程题
【LeetCode #216】组合总和III
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：
- 所有数字都是正整数。
- 解集不能包含重复的组合。
示例 1:
输入: k = 3, n = 7 输出: [[1,2,4]]
解题思路：
组合数求和问题，一般都能想到回溯法，其中在递归中一共有5个变量，其中k和n全程值不改变，因此主要的变量就是sum、num、start. sum用来标记回溯过程中tmp数组中数字之和，而num则标记tmp数组中数字个数，由于题目中要求在tmp数组中不能够重复，因此使用start标记每个子问题的起始循环数字，每进入一个子问题，起始值加 1, 从而永远不会重复！
class Solution {
public:
vector<vector<int>> res;
vector<int> tmp;
void dfs(int sum, int num, int start, int k, int n){
if(sum > n) return;
if(sum == n){
if(num == k){
res.push_back(tmp);
return;
}
}
for(int i = start; i < 10; ++i){
tmp.push_back(i);
dfs(sum+i, num+1, i+1, k, n);
tmp.pop_back();
}
}
vector<vector<int>> combinationSum3(int k, int n) {
if(k <= 0 || n <= 0){
return res;
}
dfs(0, 0, 1, k, n);
return res;
}
};来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/combination-sum-iii
【LeetCode #213】打家劫舍II
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1: 输入: [2,3,2] 输出: 3 解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
解题思路：
在前几天推送的打家劫舍I中，其递推式为dp[i] = max(dp[i-1], dp[i-2]+nums[i]); 而在这道题目中，其主要的变化是，这些房子连成了一个圈，也就是说对于第一个屋子和最后一个屋子只能选择其中一个来偷。 那么问题就变得简单了，可以分为两种情况，第一种是偷第一家，第二种是不偷第一家，然后分别使用打家劫舍I中的方法求这两种问题的最大值，而两个值得最大值也就是本题的解了！
class Solution {
public:
int rob(vector<int>& nums) {
if(nums.size() == 0) return 0;
if(nums.size() == 1) return nums[0];
vector<int> dp1(nums.size(), 0), dp2(nums.size(), 1);
dp1[0] = 0, dp1[1] = nums[0];
dp2[0] = 0, dp2[1] = nums[1];
for(int i = 2; i < nums.size(); i++){
dp1[i] = max(dp1[i-1], dp1[i-2]+nums[i-1]);
}
for(int i = 2; i < nums.size(); i++){
dp2[i] = max(dp2[i-1], dp2[i-2]+nums[i]);
}
return max(dp1[nums.size()-1], dp2[nums.size()-1]);
}
};来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/house-robber-ii
【LeetCode #148】排序链表
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
示例 1: 输入: 4->2->1->3 输出: 1->2->3->4 示例 2: 输入: -1->5->3->4->0 输出: -1->0->3->4->5
解题思路：
对链表进行归并排序，但是由于使用了递归算法，因此不满足题意中的常数空间！不过可以将归并排序的思想复习一遍，如何用到链表上！
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* sortList(ListNode* head) {
return head == nullptr ? nullptr : mergeSort(head);
}
private:
ListNode* mergeSort(ListNode* head){
if(head->next == nullptr){
return head;
}
// 快慢指针获取链表中心点
ListNode* slow = head, *fast = head, *pre = nullptr;
while(fast != nullptr){
pre = slow;
slow = slow->next;
fast = fast->next ? fast->next->next : fast->next;
}
pre->next = nullptr;
ListNode* l = mergeSort(head);
ListNode* r = mergeSort(slow);
return merge(l, r);
}
ListNode* merge(ListNode* l, ListNode* r){
ListNode* dummy = new ListNode(0);
ListNode* cur = dummy;
while(l != nullptr && r != nullptr){
if(l->val <= r->val){
cur->next = l;
cur = cur->next;
l = l->next;
}else{
cur->next = r;
cur = cur->next;
r = r->next;
}
}
if(l != nullptr){
cur->next = l;
}
if(r != nullptr){
cur->next = r;
}
return dummy->next;
}
};来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/sort-list
【LeetCode #202】快乐数
编写一个算法来判断一个数是不是“快乐数”。
一个“快乐数”定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果可以变为 1，那么这个数就是快乐数。
示例: 输入: 19 输出: true 解释: 12 + 92 = 82 82 + 22 = 68 62 + 82 = 100 12 + 02 + 02 = 1
解题思路：
利用哈希表，建立一个位数求平方和的函数，将每次得到的中间数存入哈希表，快乐的时候，在循环计算时会出现数字 1，从而判断为快乐数，如果不快乐，那必定从某个数开始一直循环，从而while循环的条件就是每个位数平方和的结果会不会出现两次，如果是并且没有为 1 的数，那么必定不快乐！
class Solution {
public:
bool isHappy(int n) {
unordered_set<int> set;
int res;
res = sumsquare(n);
while(set.count(res) == 0){
set.insert(res);
res = sumsquare(res);
if(res == 1) return true;
}
return false;
}
int sumsquare(int num){
int sum = 0;
while(num){
sum += (num%10)*(num%10);
num /= 10;
}
return sum;
}
};来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/happy-number