🧊foril
🧊foril
力扣刷题笔记（四）
494. 目标和
题目
给你一个整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
- 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
提示：
- 1 <= nums.length <= 20
- 0 <= nums[i] <= 1000
- 0 <= sum(nums[i]) <= 1000
- -1000 <= target <= 100
思路
方法一：回溯
这里我列出题目中的提示，重点是想说明题目要求的范围并不大，一共不超过20个数，所有数都是非负数且总和也没有超过1000，通过这样的提示，我们可以想到通过回溯解决问题，因为回溯的时间复杂度是 ，所以只有在明确了题目中数字不会太大之后，我们才能考虑使用回溯方法。
如果考虑使用回溯，那么这个题的思路就很明确了，定义出口是到了最后一个数字之后，否则分别考虑加减当前数字。
class Solution { int res = 0; void bt(vector<int>& v, int index, int target, int curr){ int len = v.size(); if(index==len){ //出口 if(curr == target) res++; return; } bt(v, index+1, target, curr+v[index]); bt(v, index+1, target, curr-v[index]); } public: int findTargetSumWays(vector<int>& nums, int target) { bt(nums, 0, target, 0); return res; } };
方法二：动态规划
同样因为这个题目中要求的范围很小，我们可以考虑通过动态规划解题，表示通过前个数可以得到的方案数量，由此，答案所求即为，状态转移方程为：
不过这里需要考虑的是，对每一个，要检查所有的 ，判断对 得到的结果中能否得到或是，还要判断加减当前数字是否为越界。我们可以将状态转换方程，判断 得到的结果中，不为一的数将他加减当前的数字。
另外要注意的是虽然总和不超过1000，但要考虑到如果全部是负号，会有-1000，所以需要开2001个空间加以映射。
class Solution { public: int findTargetSumWays(vector<int>& nums, int target) { int* dp = new int[2001];//+1000 memset(dp, 0, 2001*sizeof(int)); int init = nums[0]; dp[init+1000] +=1; dp[-init+1000] +=1; int len = nums.size(); for(int i = 1;i<len;i++){ int* next = new int[2001]; memset(next, 0, 2001*sizeof(int)); for(int j = -1000;j<1001;j++){ if(dp[j+1000]>0){ printf("dp[0][%d]>0\n",j+1000); next[j-nums[i]+1000] += dp[j+1000]; next[j+nums[i]+1000] += dp[j+1000]; } } delete[] dp; dp = next; } return dp[target+1000]; } };
31. 下一个排列
题目
实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须 原地 修改，只允许使用额外常数空间。
示例 1：
输入：nums = [1,2,3]
输出：[1,3,2]
示例 2：
输入：nums = [3,2,1]
输出：[1,2,3]
示例 3：
输入：nums = [1,1,5]
输出：[1,5,1]
示例 4：
输入：nums = [1]
输出：[1]
思路
对于长度为 n 的排列 a：
首先从后向前查找第一个顺序对 (i,i+1)，满足 a[i] < a[i+1] 。此时 [i+1,n)[i+1,n) 必然是下降序列。
如果找到了顺序对，那么在区间 [i+1,n) 中从后向前查找第一个元素 j 满足 a[i] < a[j] 。
交换 a[i] 与 a[j] ，此时可以证明区间 [i+1,n) 必为降序。我们可以直接反转区间 [i+1,n) 使其变为升序，而无需对该区间进行排序。
官方简洁代码：
class Solution { public: void nextPermutation(vector<int>& nums) { int len = nums.size(); if(len==1) return; auto it1 = nums.begin()+len-2; auto it2 = it1+1; while(it2!=nums.begin()){ if(*it1<*it2){ auto tmp = nums.end(); while(--tmp!=it1){ if(*tmp>*it1){ //交换 swap(*it1,*tmp); break; } } sort(it1+1,nums.end()); return; } it1--,it2--; } sort(nums.begin(), nums.end()); } };
PS:cpp自带api可以找到下一个字典序排序。
class Solution { public: void nextPermutation(vector<int>& nums) { next_permutation(nums.begin(), nums.end()); } };
33. 搜索旋转排序数组
题目
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1
示例 3：
输入：nums = [1], target = 0
输出：-1
进阶：你可以设计一个时间复杂度为 O(log n) 的解决方案吗？
思路
要求设计一个时间复杂度为的算法，可以想到利用二分解决问题，但是本题目中的序列并不是有序的，好在题目是数组中的值各不相同，对任意一个下标的左侧或右侧必有一侧有序且可判断。
利用二分思想，找到中间点mid，如果左侧有序，判断目标在左侧有序范围内就更新右侧下标，不在左侧有序范围内，只可能在右侧，更新左侧下标，进入下一次循环。
同理如果右侧有序，判断目标在右侧有序范围内就更新左侧下标在右侧寻找，不在右侧有序范围内，只可能在左侧，更新右侧下标，进入下一次循环。
class Solution { public: int search(vector<int>& nums, int target) { int len = nums.size(); if(len==0) return -1; int l = 0, r = len - 1; while(l<=r){ int m = (l+r)/2; if(nums[m]==target) return m; if(nums[0]<=nums[m]){ //左侧有序 if(target>=nums[l] && target<=nums[m]){ //在左侧有序区间 r = m - 1; }else{ //只可能在右侧 l = m + 1; } }else{ if(target>=nums[m] && target<=nums[r]){ l = m + 1; }else{ r = m - 1; } } } return -1; } };
16. 最接近的三数之和
题目
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
示例：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
提示：
- 3 <= nums.length <= 10^3
- -10^3 <= nums[i] <= 10^3
- -10^4 <= target <= 10^4
思路
最容易想到的自然是构造一个 复杂度的三重循环，寻找 abs(a+b+c - target) 的最小值，在题目中，数组长度为 ，这样的算法一般来说会超时，虽然我在力扣上试了一下，908ms居然都能AC。
更高效的想法是 排序+双指针，对整个数组进行升序排序，我们便可以利用排序的信息。
遍历第一个数字a，后两个数字分别初始化为a后的最小的数b和最大的数c，接着判断a+b+c - target，若为负，将b右移，若为正，左移c，若等于零，可直接返回target，因为最接近的值必然是target。
class Solution { public: int threeSumClosest(vector<int>& nums, int target) { int len = nums.size(); sort(nums.begin(),nums.end()); int recorder = INT_MAX; int nearest = INT_MAX; for(int i = 0;i<len-2;i++){ int j = i+1, k = len - 1; while(j<k){ if(abs(nums[i]+nums[j]+nums[k]-target)<nearest){ nearest = abs(nums[i]+nums[j]+nums[k]-target); recorder = nums[i]+nums[j]+nums[k]; } if(nums[i]+nums[j]+nums[k]-target<0){ j++; }else if(nums[i]+nums[j]+nums[k]-target==0){ return target; }else{ k--; } } } return recorder; } };
实际上，每一次枚举的过程中，我们尝试边界上的两个元素，根据它们与 target 的值的关系，选择 抛弃 左边界的元素还是右边界的元素，从而减少了枚举的范围。这种思路与 11. 盛最多水的容器 中的双指针解法也是类似的。
24. 两两交换链表中的节点
题目
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1：
输入：head = [1,2,3,4]
输出：[2,1,4,3]
示例 2：
输入：head = [1,2,3]
输出：[2,1,3]
示例 3：
输入：head = [1]
输出：[1]
思路
之前说过做指针的题目重要的是理清思路一遍写完代码，这里先上自己的代码。
class Solution { public: ListNode* swapPairs(ListNode* head) { ListNode nullHead = ListNode(-1,head); //加入一个空头指针 ListNode* l = head, * prev = &nullHead; while(l!=nullptr){ ListNode* r = l->next; if(r!=nullptr){ //交换 prev->next = r; l->next = r->next; r->next = l; //更新l prev prev = l; l = l->next; }else{ break; } } return nullHead.next; } };
官方有一种递归的解法，重要的是明白方法在栈中叠加，在回溯阶段解决问题的思路。
class Solution { public: ListNode* swapPairs(ListNode* head) { if (head == nullptr || head->next == nullptr) { return head; } ListNode* newHead = head->next; head->next = swapPairs(newHead->next); //递归 //在回溯阶段解决问题 newHead->next = head; return newHead; } };
23. 合并K个升序链表
题目
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
思路
最基础的思路就如同之前做过的两个升序链表合并，每次取出所有链表第一个元素中的最小值，然后构建新的链表。
在这里我们可以通过优先队列（最大堆）的数据结构来简化代码。
这里值得注意的是对ListNode做了包装，重载了小于号，使结构体能够直接作为优先队列的泛型，同时使最大堆成为最小堆。
class Solution { public: struct Status { int val; ListNode *ptr; bool operator < (const Status &rhs) const { return val > rhs.val; } }; priority_queue <Status> q; ListNode* mergeKLists(vector<ListNode*>& lists) { for (auto node: lists) { if (node) q.push({node->val, node}); } ListNode head, *tail = &head; while (!q.empty()) { auto f = q.top(); q.pop(); tail->next = f.ptr; tail = tail->next; if (f.ptr->next) q.push({f.ptr->next->val, f.ptr->next}); } return head.next; } };
1530. 好叶子节点对的数量
题目
给你二叉树的根节点 root 和一个整数 distance 。
如果二叉树中两个 叶 节点之间的 最短路径长度 小于或者等于 distance ，那它们就可以构成一组 好叶子节点对 。
返回树中 好叶子节点对的数量 。
提示：
- tree 的节点数在 [1, 2^10] 范围内。
- 每个节点的值都在 [1, 100] 之间。
- 1 <= distance <= 10
思路
这个题目比较有难度的是想到利用递归计算，因为题目中提示distance<=10这就给我们用一个数据结构记录他左右两部分不同距离的叶子节点数量的可能。
我们通过递归，每一次向传递以当前节点作为根节点的距离在distance以内的叶子节点数量，同时传递当前节点以下的所有可能好叶子节点对数量。
这样，在每一次递归里，是需要计算左右孩子距离之和不超过distance的节点对数量，加上孩子节点传递的节点对数量再向上传递即可。
其中需要注意更新depths，阅读代码更能体会其中的思路。
//递归 class Solution { public: pair<vector<int>, int> dfs(TreeNode* root, int distance) { vector<int> depths(distance + 1, 0); bool ifLeaf = !root->left && !root->right; if (ifLeaf) { //是叶节点 depths[0] = 1; return make_pair(depths, 0); } //非叶节点 vector<int> leftDepths, rightDepths; int leftCount, rightCount; if (root->left) { auto tmp = dfs(root->left, distance); leftDepths = tmp.first; leftCount = tmp.second; } if (root->right) { auto tmp = dfs(root->right, distance); rightDepths = tmp.first; rightCount = tmp.second; } //更新depths for (int i = 0; i < distance; i++) { depths[i + 1] += leftDepths[i]; depths[i + 1] += rightDepths[i]; } int count = 0; //当前节点的左右孩子组合 for (int i = 0; i <= distance; i++) { for (int j = 0; i+j+2 <= distance; j++) { count += leftDepths[i] * rightDepths[j]; } } return make_pair(depths, leftCount + rightCount + count); } int countPairs(TreeNode* root, int distance) { auto p = dfs(root, distance); return p.second; } };