建网站的设备,网站开发人员知乎,wordpress加入mip,深圳市建筑人才网目录
1.两数之和
2.两数相加-链表
3.无重复字符的最长子串
4.寻找两个正序数组的中位数
5.最长回文子串 1.两数之和
给定一个整数数组 nums 和一个整数目标值 target#xff0c;请你在该数组中找出 和为目标值 target 的那 两个 整数#xff0c;并返回它们的数组下标。…目录
1.两数之和
2.两数相加-链表
3.无重复字符的最长子串
4.寻找两个正序数组的中位数
5.最长回文子串 1.两数之和
给定一个整数数组 nums 和一个整数目标值 target请你在该数组中找出 和为目标值 target 的那 两个 整数并返回它们的数组下标。
你可以假设每种输入只会对应一个答案并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。 第一种方法比较常规暴力枚举时间复杂度 O(n^2)因为我们使用双重循环遍历数组每次检查一对元素的和。 class Solution {
public:vectorint twoSum(vectorint nums, int target) {for (int i0 ; i nums.size() ; i) {for(int ji1 ; jnums.size() ; j){if(nums[i]nums[j] target){return {i,j};}}}return {};}
}; 第二种方法哈希表解法时间复杂度 O(n)因为我们只遍历一次数组对于每个元素的查找和插入操作哈希表的时间复杂度是常数 O(1)。 class Solution {
public:vectorint twoSum(vectorint nums, int target) {unordered_mapint, int num_map;for (int i 0; i nums.size(); i) {int complement target - nums[i]; if (num_map.find(complement) ! num_map.end()){return {num_map[complement], i};}num_map[nums[i]] i;}return {};}
}; 假设 nums [2, 7, 11, 15]目标值 target 9。
第一轮
当前元素是 nums[0] 2计算 complement 9 - 2 7。 哈希表 num_map 为空7 不在哈希表中。 将当前元素 nums[0] 2 存入哈希表num_map {2: 0}。 第二轮
当前元素是 nums[1] 7计算 complement 9 - 7 2。 哈希表 num_map {2: 0}发现 complement 2 在哈希表中说明 nums[0] nums[1] 9。 返回结果{0, 1}。 如何用哈希表来找到两个数 问题的核心思想 对于每一个元素 nums[i]我们希望在之前遍历的数组元素中找到一个数 complement使得 nums[i] complement target从而满足题目条件。也就是
complementtarget−nums[i]\text{complement} \text{target} - \text{nums}[i]complementtarget−nums[i] 这样我们就可以通过查找哈希表中是否存在 complement 来判断是否找到了匹配的两个数。
为什么哈希表有效
哈希表是一个常数时间查找结构 使用哈希表存储之前遍历过的元素每个元素和其下标都作为键值对存储。查找一个元素是否在哈希表中存在的时间复杂度为 O(1)。 早期发现匹配 在遍历数组时我们可以在当前元素 nums[i] 被处理之前检查 target - nums[i] 是否已经出现在哈希表中。这样查找操作变得非常高效我们能快速确定某个值是否已经出现在数组的前面部分。 解释为什么能找到配对
思考过程 对于每一个元素 nums[i]我们在遍历过程中都计算出当前元素和目标值的差值 complement target - nums[i]。然后我们查找哈希表中是否存在 complement如果存在就说明存在两个数它们的和为 target。 哈希表的作用 哈希表的作用是记录我们已经遍历过的元素所以当我们遇到某个元素时我们只需要查找它的差值是否已经存在。这样就可以快速找到一对数。 为什么可以在 O(n) 时间内找到答案一遍扫描 在遍历数组时我们只需要对每个元素进行一次查找和插入操作且每次查找和插入的时间复杂度是常数 O(1)。 不需要重复扫描 不像暴力解法需要两层循环去遍历数组的每一对元素哈希表方法只需要遍历一次数组。 2.两数相加-链表
给你两个 非空 的链表表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的并且每个节点只能存储 一位 数字。
请你将两个数相加并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外这两个数都不会以 0 开头。 /*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode *head new ListNode(0);ListNode *current head;int carry 0;while(l1 ! nullptr || l2 ! nullptr || carry ! 0){int data1 (l1 ! nullptr) ? l1-val : 0;int data2 (l2 ! nullptr) ? l2-val : 0;int sum data1 data2 carry;carry sum / 10;current-next new ListNode(sum % 10);currentcurrent-next;if(l1 ! nullptr) l1 l1-next;if(l2 ! nullptr) l2 l2-next;}return head-next;}
}; 该 while 循环继续执行直到两个链表都遍历完且没有进位。也就是说
如果 l1 和 l2 都为空但 carry 不为零即最后一次加法有进位我们仍然需要处理进位。 在每次循环中我们从 l1 和 l2 中提取当前节点的值如果节点为空则默认为 0。 然后将两个节点的值和进位相加得到当前位的和。 使用 sum / 10 计算进位sum % 10 作为当前位的结果。 将当前位的结果存入新节点并更新 current 指针。 3.无重复字符的最长子串
给定一个字符串 s 请你找出其中不含有重复字符的 最长子串 的长度。 子字符串 是字符串中连续的 非空 字符序列
class Solution {
public:int lengthOfLongestSubstring(string s) {unordered_setchar char_set; int left 0; int max_len 0; for (int right 0; right s.size(); right) {while (char_set.find(s[right]) ! char_set.end()) {char_set.erase(s[left]);left;}char_set.insert(s[right]);max_len max(max_len, right - left 1);}return max_len;}
}; 我们来针对输入 abcabcbb这个测试用例来讲解如下所示 初始化 char_set: 是一个 unordered_set用于存储当前窗口内的字符确保窗口内的字符是唯一的。 left: 左指针初始值为 0表示窗口的左边界。 max_len: 用于记录最长无重复子串的长度初始值为 0。 遍历字符串 我们通过 right 指针从左到右遍历字符串 s并不断更新 max_len。
输入字符串为 abcabcbb其长度为 8。我们按每次循环逐步分析。
第 1 次循环 (right 0) 当前字符 s[right] a。 检查 char_set 是否包含 achar_set.find(a) 返回 char_set.end()说明没有重复字符。 将 a 插入到 char_set 中char_set {a}。 计算当前窗口的长度 right - left 1 0 - 0 1 1更新 max_len max(0, 1) 1。第 2 次循环 (right 1) 当前字符 s[right] b。 检查 char_set 是否包含 bchar_set.find(b) 返回 char_set.end()说明没有重复字符。 将 b 插入到 char_set 中char_set {a, b}。 计算当前窗口的长度 right - left 1 1 - 0 1 2更新 max_len max(1, 2) 2。第 3 次循环 (right 2) 当前字符 s[right] c。 检查 char_set 是否包含 cchar_set.find(c) 返回 char_set.end()说明没有重复字符。 将 c 插入到 char_set 中char_set {a, b, c}。 计算当前窗口的长度 right - left 1 2 - 0 1 3更新 max_len max(2, 3) 3。第 4 次循环 (right 3) 当前字符 s[right] a。 检查 char_set 是否包含 achar_set.find(a) 返回非 char_set.end()说明有重复字符。 进入 while 循环开始调整窗口的左边界 left 移除 s[left] a 从 char_set 中char_set {b, c}。 左指针右移left 1。 继续检查 char_set 是否包含 a此时不再包含 a。 将 a 插入到 char_set 中char_set {b, c, a}。 计算当前窗口的长度 right - left 1 3 - 1 1 3max_len 不变仍为 3。第 5 次循环 (right 4) 当前字符 s[right] b。 检查 char_set 是否包含 bchar_set.find(b) 返回非 char_set.end()说明有重复字符。 进入 while 循环开始调整窗口的左边界 left 移除 s[left] b 从 char_set 中char_set {c, a}。 左指针右移left 2。 继续检查 char_set 是否包含 b此时不再包含 b。 将 b 插入到 char_set 中char_set {c, a, b}。 计算当前窗口的长度 right - left 1 4 - 2 1 3max_len 不变仍为 3。第 6 次循环 (right 5) 当前字符 s[right] c。 检查 char_set 是否包含 cchar_set.find(c) 返回非 char_set.end()说明有重复字符。 进入 while 循环开始调整窗口的左边界 left 移除 s[left] c 从 char_set 中char_set {a, b}。 左指针右移left 3。 继续检查 char_set 是否包含 c此时不再包含 c。 将 c 插入到 char_set 中char_set {a, b, c}。 计算当前窗口的长度 right - left 1 5 - 3 1 3max_len 不变仍为 3。第 7 次循环 (right 6) 当前字符 s[right] b。 检查 char_set 是否包含 bchar_set.find(b) 返回非 char_set.end()说明有重复字符。 进入 while 循环开始调整窗口的左边界 left 移除 s[left] a 从 char_set 中char_set {b, c}。 左指针右移left 4。 继续检查 char_set 是否包含 b此时不再包含 b。 将 b 插入到 char_set 中char_set {b, c}。 计算当前窗口的长度 right - left 1 6 - 4 1 3max_len 不变仍为 3。第 8 次循环 (right 7) 当前字符 s[right] b。 检查 char_set 是否包含 bchar_set.find(b) 返回非 char_set.end()说明有重复字符。 进入 while 循环开始调整窗口的左边界 left 移除 s[left] b 从 char_set 中char_set {c}。 左指针右移left 5。 继续检查 char_set 是否包含 b此时不再包含 b。 将 b 插入到 char_set 中char_set {c, b}。 计算当前窗口的长度 right - left 1 7 - 5 1 3max_len 不变仍为 3。 4.寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序从小到大数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。算法的时间复杂度应该为 O(log (mn)) 。
方法一不推荐 class Solution {
public:double findMedianSortedArrays(vectorint nums1, vectorint nums2) {vectorint merged;double median 0;int i0,j0;while(i nums1.size() j nums2.size()){if(nums1[i] nums2[j]){merged.push_back(nums1[i]);i;} else {merged.push_back(nums2[j]);j;}}while (i nums1.size()) {merged.push_back(nums1[i]);i;}while(j nums2.size()){merged.push_back(nums2[j]);j;}int n merged.size();if (n % 2 0) {median (merged[n / 2 - 1] merged[n / 2]) / 2.0;} else {median merged[n / 2];}return median;}
}; 使用双指针 i 和 j 分别指向 nums1 和 nums2 的起始位置。 比较 nums1[i] 和 nums2[j]将较小的元素放入 merged 数组。 将较小元素的指针后移即继续检查数组中的下一个元素。 直到一个数组被完全遍历。 如果 nums1 还有剩余元素将其直接追加到 merged 中。 同样地如果 nums2 还有剩余元素也直接追加到 merged 中。 这样merged 就是一个完整的、合并后的有序数组。 首先获取 merged 数组的大小 n。 如果 n 是偶数 中位数是数组中间两个数的平均值即 (merged[n / 2 - 1] merged[n / 2]) / 2.0。 如果 n 是奇数 中位数是数组的中间元素即 merged[n / 2]。 方法二
class Solution {
public:double findMedianSortedArrays(vectorint nums1, vectorint nums2) {// 确保 nums1 是较短的数组if (nums1.size() nums2.size()) {return findMedianSortedArrays(nums2, nums1);}int m nums1.size();int n nums2.size();int totalLeft (m n 1) / 2;int left 0, right m;while (left right) {int i left (right - left) / 2;int j totalLeft - i;if (nums1[i] nums2[j - 1]) {// i 需要右移left i 1;} else {// i 需要左移right i;}}int i left;int j totalLeft - i;// 左半部分的最大值int nums1LeftMax (i 0) ? INT_MIN : nums1[i - 1];int nums2LeftMax (j 0) ? INT_MIN : nums2[j - 1];int leftMax max(nums1LeftMax, nums2LeftMax);// 如果总长度是奇数if ((m n) % 2 1) {return leftMax;}// 右半部分的最小值int nums1RightMin (i m) ? INT_MAX : nums1[i];int nums2RightMin (j n) ? INT_MAX : nums2[j];int rightMin min(nums1RightMin, nums2RightMin);// 如果总长度是偶数返回平均值return (leftMax rightMin) / 2.0;}
}; 1. 确保 nums1 是较短的数组 通过判断 nums1 和 nums2 的长度始终在较短的数组上进行二分查找。
2. 使用二分查找调整分割点 i 是在 nums1 的分割点j 是在 nums2 的分割点。 i j totalLeft保证左半部分元素总数等于右半部分。 根据条件调整 i 如果 nums1[i] nums2[j - 1]说明 i 需要右移。 如果 nums1[i] nums2[j - 1]说明 i 满足条件或需要左移。3. 计算中位数 左半部分最大值为max(nums1[i-1], nums2[j-1])。 右半部分最小值为min(nums1[i], nums2[j])。 如果总长度为奇数直接返回左半部分最大值。 如果总长度为偶数返回左右半部分最大值与最小值的平均值。 5.最长回文子串
给你一个字符串 s找到 s 中最长的 回文子串。
回文性 如果字符串向前和向后读都相同则它满足 回文性子字符串子字符串 是字符串中连续的 非空 字符序列。
动态规划法 class Solution {
public:string longestPalindrome(string s) {int n s.size();if (n 1) return s;vectorvectorbool dp(n, vectorbool(n, false));int start 0, maxLen 1;for (int i 0; i n; i) dp[i][i] true;for (int i 0; i n - 1; i) {if (s[i] s[i 1]) {dp[i][i 1] true;start i;maxLen 2;}}for (int len 3; len n; len) {for (int i 0; i len - 1 n; i) {int j i len - 1;if (s[i] s[j] dp[i 1][j - 1]) {dp[i][j] true;start i;maxLen len;}}}return s.substr(start, maxLen);}
}; 首先我们获取字符串 s 的长度 n。如果字符串长度小于或等于 1则字符串本身就是回文的单个字符本身就是回文直接返回字符串。
dp 是一个二维布尔型数组dp[i][j] 用来表示子串 s[i...j] 是否为回文串。数组大小为 n x n初始化为 false。
每个单字符子串即 s[i...i]自然是回文的因此将 dp[i][i] 设置为 true。
接下来我们处理长度为 2 的子串。如果 s[i] s[i1]那么 s[i...i1] 是回文串设置 dp[i][i1] true。此时我们还更新 start 和 maxLen记录最长回文子串的起始位置和长度。
从长度为 3 的子串开始我们逐步扩展到更长的回文子串。具体来说len 表示当前子串的长度从 3 一直增加到 n。
对于每个长度为 len 的子串我们通过以下条件判断是否为回文
s[i] s[j]当前子串的首尾字符相同。 dp[i1][j-1]即子串 s[i1...j-1] 是否是回文。 如果这两个条件都成立那么 s[i...j] 也是回文子串更新 dp[i][j] true并更新 start 和 maxLen记录当前最长回文子串的起始位置和长度。
输入字符串 s babad
长度为 1 的子串我们从一开始就知道每个单独的字符都是一个回文子串所以 dp[i][i] true 对于所有 i 都成立。对于 s babad初始化时dp 数组是这样的 dp [ [true, false, false, false, false], [false, true, false, false, false], [false, false, true, false, false], [false, false, false, true, false], [false, false, false, false, true] ]
长度为 2 的子串接着代码检查相邻的字符是否相同。如果相同设置 dp[i][i1] true。在 s babad 中s[0] ! s[1]b ! as[1] ! s[2]a ! bs[2] ! s[3]b ! as[3] ! s[4]a ! d。所以 dp 数组没有更新。 dp 仍然是
dp [ [true, false, false, false, false], [false, true, false, false, false], [false, false, true, false, false], [false, false, false, true, false], [false, false, false, false, true] ]
长度为 3 及以上的回文子串接着程序检查长度为 3 及以上的子串逐步扩展回文子串的长度。对每一个 len长度从 3 到 n我们依次检查每个子串的起始位置 i。
当 len 3 时
对于 s[0...2] babs[0] s[2]b b并且 dp[1][1] true即 a 是回文。所以 dp[0][2] truestart 0maxLen 3。 现在 dp 数组更新为 dp [ [true, false, true, false, false], [false, true, false, false, false], [false, false, true, false, false], [false, false, false, true, false], [false, false, false, false, true] ]
这时我们已经找到了 bab 作为一个回文子串。
继续检查更长的回文子串当 len 4 时 对于 s[1...4] abads[1] ! s[4]a ! d所以 dp[1][4] 不会被设置。 当 len 5 时 对于 s[0...4] babads[0] ! s[4]b ! d所以 dp[0][4] 也不会被设置。 经过这些步骤程序最终会返回最长的回文子串 bab因为 start 0 和 maxLen 3。
