代码随想录_刷题笔记

链表 — 环形链表

题目链接：142. 环形链表 II - 力扣（LeetCode）

题目要求：

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例：

输入：head = [3,2,0,-4] , pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

**思路：**判断是否有环（快慢指针，看它们是否会相遇），找到环的入口节点（设置两个指针，一个从相遇位置向前移动，一个从头节点开始移动，两者会在环的入口节点处相遇）

解法：

struct ListNode *detectCycle(struct ListNode *head) {typedef struct ListNode ListNode;ListNode* fast = head;ListNode* slow = head;while(fast && fast->next){fast = fast->next->next;    // 快指针一次向后移动两步slow = slow->next;          // 慢指针一次向后移动一步if(fast == slow){           // 存在环ListNode* tmp1 = head;ListNode* tmp2 = fast;while(tmp1 != tmp2){tmp1 = tmp1->next;tmp2 = tmp2->next;}return tmp1;}    }return NULL;
}

class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode* fast = head;ListNode* slow = head;while(fast != NULL && fast->next !=NULL){fast = fast->next->next;    // 快指针一次移动两个节点slow = slow->next;          // 慢指针一次移动一个节点while(fast == slow){ListNode* begin = head;   // 一个节点从起点开始ListNode* end   = fast;   // 一个节点从相遇的点开始while(begin != end){begin = begin->next;end = end->next;}return end;}}return NULL;}
};

哈希表 — 有效的字母异位词

题目链接：242. 有效的字母异位词 - 力扣（LeetCode）

**题目要求：**给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

示例：

输入: s = "anagram", t = "nagaram"
输出: true

输入: s = "rat", t = "car"
输出: false

**思路：**遍历第一个字符串，使用数组统计每一个字符出现的频率，遍历第二个字符串，字符每出现一次，频率 -1，判断数组是否每一项都为 0

解法：

bool isAnagram(char* s, char* t) {int len_s = strlen(s);int len_t = strlen(t);if(len_s != len_t)     // 如果长度不行等直接返回 falsereturn false;int tmp[26] = {0};int i;for(i = 0; i < len_s; i++){tmp[s[i] - 'a']++;}for(i = 0; i < len_t; i++){tmp[t[i] - 'a']--;}for(i = 0; i < 26; i++){if(tmp[i] != 0)      // 如果有一项不等于0，则返回 false    return false;}return true;
}

class Solution {
public:bool isAnagram(string s, string t) {if(s.size() != t.size()){return false;}int tmp[26];for(int i = 0; i < s.size(); i++){tmp[s[i] - 'a']++;}for(int j = 0; j < t.size(); j++){tmp[t[j] - 'a']--;}for(int k = 0; k < 26; k++){if(tmp[k])return false;}return true;}
};

哈希表 — 两个数组的交集

题目链接：349. 两个数组的交集 - 力扣（LeetCode）

题目要求：给定两个数组nums1和nums2，返回 它们的交集 ，输出结果中的每个元素一定是唯一的，我们可以不考虑输出结果的顺序。

示例：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的

**思路：**哈希表使用数组，遍历第一个数组，将出现的值对应的哈希数组项设为1，遍历第二个数组，如果值对应的哈希数组项为1，则这个值出现过

解法：

C（使用数组作为哈希表，但是数组中的值必须介于 0~1000 之间，局限性太大）

int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {int map[1001] = {0};       // 给定数组中值的大小：0 ~ 1000 int min = nums1Size < nums2Size ? nums1Size : nums2Size;int* result = (int*)malloc(sizeof(int) * min);    int i, k = 0;for(i = 0; i < nums1Size; i++){map[nums1[i]] = 1;}for(i = 0; i < nums2Size; i++){if(map[nums2[i]] == 1){map[nums2[i]] = 0;         // 每个数据只写入一次result[k++] = nums2[i];             }}*returnSize = k;return result;
}

C++（使用 set）

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {unordered_set<int> result_set;   // 往unordered_set中放入元素有自动去重功能unordered_set<int> nums_set(nums1.begin(), nums1.end());for(int num : nums2){   // 遍历 nums2 数组if(nums_set.find(num) != nums_set.end()){   result_set.insert(num);  // 如果能找到对应元素，则代表重复}}return vector<int>(result_set.begin(), result_set.end());}
};

哈希表 — 两数之和

题目链接：1. 两数之和 - 力扣（LeetCode）

题目要求：

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。（多个答案返回一个）

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1]

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

**思路：**C：两层 for 循环

C++：使用 map 保存元素的数值（key）以及它所对应的下标（value），注意（map 中所保存的是已经遍历过的元素），每到数组中的一项，就查找 map 看是否有曾经的元素加上现在数组项的值等于 target

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {int tmp = 0;int* result = (int*)malloc(sizeof(int)*2);for(int i = 0; i < numsSize; i++){tmp = nums[i];result[0] = i; for(int j = 0; j < numsSize; j++){if(tmp + nums[j] == target){if(i != j){              // 避免返回的两个下标结果相同result[1] = j;*returnSize = 2;return result;                    }}}}return NULL;
}

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> map;   // 创建map容器，存放遍历过的元素，以及它所对应的下标for(int i = 0; i < nums.size(); i++){int num = target - nums[i];auto index = map.find(num);if(index != map.end()){   // 之前的元素存在相加等于 target的return {index->second, i};}map.insert(pair<int, int>(nums[i], i)); }return {};}
};

哈希表 — 四数相加II

题目链接：454. 四数相加 II - 力扣（LeetCode）

题目要求：

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

示例 1：

输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

示例 2：

输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出：1

**思路：**遍历A和B数组，统计两个数组元素之和，和出现的次数，放到map中，再遍历C和D数组，找到如果 0-(c+d) 在map中出现过的话，就用 result 把 map 中 key 对应的 value 统计出来

解法：

class Solution {
public:int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {unordered_map<int, int> map;for(int m : nums1){for(int n : nums2){map[m + n]++;}}int result = 0;for(int i : nums3){for(int j : nums4){if(map.find(0 - (i + j)) != map.end()){result += map[0 - (i + j)];}}}return result;}
};

哈希表 — 三数之和

题目链接：15. 三数之和 - 力扣（LeetCode）

题目要求：

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

**注意：**答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

**思路：**虽然可以使用哈希法解决（方法与四数相加差不多，但是需要进行去重，这就比较麻烦），这里使用双指针法

解法：

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> result;sort(nums.begin(), nums.end());   // 先对整个数组进行排序（从小到大）for (int i = 0; i < nums.size(); i++) {   if (nums[i] > 0) {           // 如果第一个数就大于零，就不可能存在还有两个数与它相加等于零return result;}if (i > 0 && nums[i] == nums[i - 1]) {   // 对第一个数进行去重操作continue;}                               // 第一个指针从左开始，第二个指针从右开始int left = i + 1;               // 指向第二个数的指针int right = nums.size() - 1;    // 指向第三个数的指针while (right > left) {          if (nums[i] + nums[left] + nums[right] > 0){right--;}else if (nums[i] + nums[left] + nums[right] < 0){left++;}else {result.push_back(vector<int>{nums[i], nums[left], nums[right]});while (right > left && nums[right] == nums[right - 1]) right--;   // 第三个数的去重操作 while (right > left && nums[left] == nums[left + 1]) left++;      // 第二个数的去重操作right--;left++;}}}return result;}
};

哈希表 — 四数之和

题目链接：18. 四数之和 - 力扣（LeetCode）

题目要求：

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案。

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

**思路：**延续了三数之和的思路，多使用一层for循环（时间复杂度 O(n^3) ）

解法：

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> result;sort(nums.begin(), nums.end());   // 对整个数组进行排序（从小到大）for(int i = 0; i < nums.size(); i++){if(nums[i] > target && nums[i] >= 0){   // 两个负数相加，值会越来越小(一级剪枝)break;}if(i > 0 && nums[i] == nums[i - 1]){   // 去重操作continue; }for(int j = i + 1; j < nums.size(); j++){if(nums[i] + nums[j] > target && nums[i] + nums[j] >=0){   // 二级剪枝操作break;}if(j > i + 1 && nums[j] == nums[j - 1]){   // 去重操作continue;}int left  = j + 1;               // 其余两个数进行双指针操作int right = nums.size() - 1;while(left < right){// 如果不加 long 的话，结果会溢出if((long) nums[i] + nums[j] + nums[left] + nums[right] > target){right--;}else if((long) nums[i] + nums[j] + nums[left] + nums[right] < target){left++;}else{result.push_back(vector<int>{nums[i], nums[j], nums[left], nums[right]});while (right > left && nums[right] == nums[right - 1]) right--;   while (right > left && nums[left] == nums[left + 1]) left++;     right--;left++;}}}}return result;}
};

字符串 — 反转字符串I

题目链接：344. 反转字符串 - 力扣（LeetCode）

**题目要求：**编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须**原地修改输入数组**、使用 O(1) 的额外空间解决这一问题。

示例 1：

输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]

示例 2：

输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

**思路：**双指针（一个指向头部，一个指向尾部，进行数据的交换）

解法：

void reverseString(char* s, int sSize) {int left = 0;int right = sSize - 1;while(left < right){char str = s[left];s[left++] = s[right];s[right--] = str;}
}

class Solution {
public:void reverseString(vector<char>& s) {for(int i = 0, j = s.size() - 1; i < s.size() / 2; i++, j--){swap(s[i], s[j]);   // swap 交换两个变量的值}      }
};

字符串 — 反转字符串II

题目链接：541. 反转字符串 II - 力扣（LeetCode）

题目要求：

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例 1：

输入：s = "abcdefg", k = 2
输出："bacdfeg"

示例 2：

输入：s = "abcd", k = 2
输出："bacd"

**思路：**每一次 for 循环 += 2，计算剩余字符串的长度，从而得知要翻转的字符个数

解法：

char* reverseStr(char* s, int k) {int len = strlen(s);for(int i = 0; i < len; i += (2 * k)){// 剩余字符串的长度，不足k时设为剩余的字符串长度，大于k时设为kint num = i + k > len ? len - i : k;if(num){int left  = i;int right = i + num - 1;while(left < right){char tmp = s[left];s[left++] = s[right];s[right--] = tmp;}}}return s;
}

class Solution {
public:string reverseStr(string s, int k) {for (int i = 0; i < s.size(); i += (2 * k)) {if (i + k <= s.size()) {reverse(s.begin() + i, s.begin() + i + k ); // 反转前k个字符} else {reverse(s.begin() + i, s.end()); // 全部反转} }return s;}
};

字符串 — 反转字符串里的单词

题目链接：151. 反转字符串中的单词 - 力扣（LeetCode）

题目要求：

给你一个字符串 s ，请你反转字符串中单词的顺序。

单词是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的单词分隔开。

返回单词顺序颠倒且单词之间用单个空格连接的结果字符串。

**注意：**输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 1：

输入：s = "the sky is blue"
输出："blue is sky the"

示例 2：

输入：s = "  hello world  "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。

示例 3：

输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

**思路：**先对字符串进行整体的反转，再对每一个单词进行反转

解法：

//反转字符串中的指定范围
void reverse(char* s, int start, int end) {for(; start < end; ){char tmp = s[start];s[start++] = s[end];s[end--] = tmp;}
}// 删除字符串两端和中间多余的空格
void removeExtraSpace(char* s) {int start = 0;int end = strlen(s) - 1;int index = 0;      // 新字符串的实时下标while(s[start] == ' ') start++;   // 去除开头多余的字符while(s[end] == ' ') end--;       // 去除结尾多余的字符for(int i = start; i <= end; i++){if(s[i] == ' ' && s[i+1] == ' '){continue;      // 这个字符不做处理}s[index] = s[i];   // 将这个字符写入新的字符串中index++;}s[index] = '\0';
}char* reverseWords(char* s) {int strstart = 0;removeExtraSpace(s);     // 先删除多余的空格reverse(s, 0, strlen(s) - 1);  // 将整个字符串进行反转for(int strend = 0; strend <= strlen(s); strend++){if(s[strend] == ' ' || s[strend] == '\0'){    // '\0':对最后一个单词进行反转reverse(s, strstart, strend - 1);     // 对这个范围的字符串进行反转strstart = strend + 1;} }return s;
}

class Solution {
public:void reverse(string& s, int start, int end){ // 反转字符串for (int i = start, j = end; i < j; i++, j--) {swap(s[i], s[j]);}}void removeExtraSpaces(string& s) {int slow = 0; for (int i = 0; i < s.size(); i++) { if (s[i] != ' ') {  // 去除开头的空格if (slow != 0) s[slow++] = ' ';   // 为每一个完整的单词后面加上空格while (i < s.size() && s[i] != ' ') {  // 获取一个完成的单词s[slow] = s[i];i++;slow++;}}}s.resize(slow);  // 改变字符串容器的大小}string reverseWords(string s) {removeExtraSpaces(s); // 为字符串去除多余的空格reverse(s, 0, s.size() - 1); // 反转整体的字符串int start = 0; for (int i = 0; i <= s.size(); i++) {if (i == s.size() || s[i] == ' ') { reverse(s, start, i - 1);start = i + 1;}}return s;}
};