- 剑指 Offer 18. 删除链表的节点">剑指 Offer 18. 删除链表的节点
- 剑指offer22链表中倒数第k个节点
- 剑指 Offer 25. 合并两个排序的链表">剑指 Offer 25. 合并两个排序的链表
- 剑指 Offer 52. 两个链表的第一个公共节点">剑指 Offer 52. 两个链表的第一个公共节点
- 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面">剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
- 剑指 Offer 57. 和为s的两个数字（重要）">剑指 Offer 57. 和为s的两个数字（重要）
- 剑指 Offer 58 - I. 翻转单词顺序">剑指 Offer 58 - I. 翻转单词顺序
- 剑指 Offer II 007. 数组中和为 0 的三个数（双指针+二分法）">剑指 Offer II 007. 数组中和为 0 的三个数（双指针+二分法）
- 滑动窗口
- 剑指 Offer II 008. 和大于等于 target 的最短子数组">剑指 Offer II 008. 和大于等于 target 的最短子数组
- 剑指 Offer II 009. 乘积小于 K 的子数组（求数组个数的滑动窗口）">剑指 Offer II 009. 乘积小于 K 的子数组（求数组个数的滑动窗口）
- 剑指 Offer II 014. 字符串中的变位词(奇妙)">剑指 Offer II 014. 字符串中的变位词(奇妙)
- 剑指 Offer II 015. 字符串中的所有变位词">剑指 Offer II 015. 字符串中的所有变位词
- 剑指 Offer II 018. 有效的回文">剑指 Offer II 018. 有效的回文
- 剑指 Offer II 019. 最多删除一个字符得到回文">剑指 Offer II 019. 最多删除一个字符得到回文
- 剑指 Offer II 020. 回文子字符串的个数(中心扩散法)">剑指 Offer II 020. 回文子字符串的个数(中心扩散法)
- 剑指 Offer II 017. 含有所有字符的最短字符串（重点）">剑指 Offer II 017. 含有所有字符的最短字符串（重点）
- 剑指 Offer II 057. 值和下标之差都在给定的范围内（难）">剑指 Offer II 057. 值和下标之差都在给定的范围内（难）
- 剑指 Offer II 058. 日程表（需要看）">剑指 Offer II 058. 日程表（需要看）
剑指 Offer 18. 删除链表的节点
第一次写：
class Solution {public:ListNode* deleteNode(ListNode* head, int val) {ListNode* cur = head,pre = head;while(cur){if(cur->val == val){if(cur == head){return head->next;}pre->next = cur->next;break;}pre = cur;cur = cur->next;}return head;}};
第二次写
class Solution {
public:
ListNode* deleteNode(ListNode* head, int val) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* pre = dummy, *cur = head;
while(cur){
if(cur->val == val){
pre->next = cur->next;
}
pre = cur;
cur = cur->next;
}
return dummy->next;
}
};
答案：
class Solution {
public:
ListNode* deleteNode(ListNode* head, int val) {
if(head->val == val) return head->next;
ListNode *pre = head, *cur = head->next;
while(cur != nullptr && cur->val != val) {
pre = cur;
cur = cur->next;
}
if(cur != nullptr) pre->next = cur->next;
return head;
}
};
增加前节点
直接增加一个前节点，这样就不用判断是否头节点符合条件了。
class Solution {
public:
ListNode* deleteNode(ListNode* head, int val) {
ListNode* pre = new ListNode(0);
pre->next = head;
ListNode* res = pre;
while(pre->next->val != val){ // 不相等则直接往下遍历
pre = pre->next;
}
pre->next = pre->next->next; // 找到之后直接删除
return pre->next;
}
};
剑指offer22链表中倒数第k个节点
这一题，用顺序遍历非常简单，但是用快慢指针属实是没想到。有点类似滑动窗口的思想，保证快节点与慢节点之间差k，等到快节点到尾部，慢节点就是倒数第k个节点的位置。
class Solution {
public:
ListNode* getKthFromEnd(ListNode* head, int k) {
ListNode* fast = head;
ListNode* slow = head;
while (fast && k > 0) {
fast = fast->next;
k--;
}
while (fast) {
fast = fast->next;
slow = slow->next;
}
return slow;
}
};
剑指 Offer 25. 合并两个排序的链表
通过比较l1的值与l2的值来进行新的链表的构建。当l1与l2中的某一个为null时，直接把不为空的另外一个接在l3的后面即可。
class Solution {
public:
ListNode* l3;
ListNode* mergeTwoLists(ListNode *l1, ListNode *l2) {
ListNode *dummy = new ListNode(0), *node = dummy;
while (l1 && l2) {
if (l1->val <= l2->val) {
node->next = l1;
l1 = l1->next;
} else {
node->next = l2;
l2 = l2->next;
}
node = node->next;
}
node->next = l1? l1: l2;//这里别看错了，将剩下的一个接在后面。
return dummy->next;
}
};
剑指 Offer 52. 两个链表的第一个公共节点
两个链表同时遍历，为空时直接为另外一个节点的头，当碰到时就是第一个公共节点。
这样子时间复杂度会低点，如果是从自己的头循环的话，时间复杂度会很多。
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode* a = headA,*b = headB;
while(a!=b){
if(a == NULL){
a = headA;
} else {
a = a ->next;
}
if(b == NULL){
b = headB;
} else {
b = b->next;
}
}
return a;
}
};
剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
一个从头找，一个从尾部找，这里需要注意溢出的问题。
class Solution {
public:
vector<int> exchange(vector<int>& nums)
{
int i = 0, j = nums.size() - 1;
while (i < j)
{
while(i < j && (nums[i] & 1) == 1){
i++;
}
while(i < j && (nums[j] & 1) == 0){
j--;
}
swap(nums[i], nums[j]);
}
return nums;
}
};
剑指 Offer 57. 和为s的两个数字（重要）
递增（双指针）
这一题与主站的第一题两数之和有些不同，这一题多加了一个数组是递增的。直接使用双指针，根据大小来调试的方法来获取最终结果。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int n = nums.size();
for(int i = 0, j = n -1; i < j;){
if(nums[i] + nums[j] > target) {
j--;
} else if(nums[i] + nums[j] < target){
i++;
} else {
return{nums[i], nums[j]};
}
}
return {};
}
};
普通（哈希）
注意这里为了防止，同一个元素选取两次，先进行判断，然后再录入。
这里返回的是下标
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> hashtable;
for (int i = 0; i < nums.size(); ++i) {
auto it = hashtable.find(target - nums[i]);
if (it != hashtable.end()) {
return {it->second, i};
}
hashtable[nums[i]] = i;
}
return {};
}
};
剑指 Offer 58 - I. 翻转单词顺序
偷懒(使用stringsteam)
复杂度高的写法
主要是时间成本高 c++ string 底层实现是一个数组 在数组前面插入元素 需要将每个元素向后移动 O（n）的时间复杂度
class Solution {
public:
string reverseWords(string s) {
string res="",temp;
stringstream ss(s);
while(ss>>temp){
res=temp+" "+res;//主要是这里的字符串相加的复杂度高
}
res.pop_back();
return res;
}
};
使用append就会好很多
class Solution {
public:
string reverseWords(string s) {
stack<string> stack1;
istringstream input(s);
string t;
string res;
while(input>>t) stack1.push(t);
while(!stack1.empty()){
res.append(stack1.top());
res.append(" ");
stack1.pop();
}
if(res.length()==0) return res;
res.pop_back();//把最后一个空格去掉。
return res;
}
};
正常双指针
这里正常的想法还是从后面遍历，然后定义一个字符串重新来赋值。我一开始的想法是两个指针分别从前面和后面开始遍历，然后直接再原字符串替换，现在感觉是想多了。
class Solution {
public:
string reverseWords(string s) {
if (s.empty())
return s;
string res = "";
int i = s.size() - 1;
while (i >= 0){
while (i >= 0 && s[i] == ' ')
--i;
int j = i;
while (i >= 0 && s[i] != ' '){
--i;
}
if (i < j){
res += s.substr(i + 1, j - i);
res += " ";
}
}
return res.substr(0, res.size() - 1);
}
};
剑指 Offer II 007. 数组中和为 0 的三个数（双指针+二分法）
- 先固定一个数a，然后b、c只能从两边向中间靠拢（在a之后）
- 去重就是看当数是否等于前一个数，如果相等则跳过当前循环
- 复杂度为o（n2），因为第一次循环遍历了n次，第二次循环两个指针加起来遍历n次
使用二分法的方法判断时，注意是while，不能是if因为在c判断完之前b应该保持不动。
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { int n = nums.size(); sort(nums.begin(), nums.end()); vector<vector<int>> ans; // 枚举 a for (int first = 0; first < n; ++first) { // 需要和上一次枚举的数不相同 if (first > 0 && nums[first] == nums[first - 1]) { continue;//避免相同 } // c 对应的指针初始指向数组的最右端 int third = n - 1; int target = -nums[first]; // 枚举 b for (int second = first + 1; second < n; ++second) { // 需要和上一次枚举的数不相同 if (second > first + 1 && nums[second] == nums[second - 1]) { continue; } // 需要保证 b 的指针在 c 的指针的左侧 while (second < third && nums[second] + nums[third] > target) { --third; } // 如果指针重合，随着 b 后续的增加 // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环 if (second == third) { break; } if (nums[second] + nums[third] == target) { ans.push_back({nums[first], nums[second], nums[third]}); } } } return ans; } };滑动窗口
剑指 Offer II 008. 和大于等于 target 的最短子数组
一定要注意条件，要认真，胆大心细！！！
千万注意边界条件！！！！
class Solution { public: int minSubArrayLen(int target, vector<int>& nums) { int n = nums.size(); int sum = 0; int minlen = INT_MAX; for(int i = 0, j = 0; j < n;j++){ sum = sum + nums[j]; while(sum >=target&&i<=j){ minlen = min(minlen,j-i+1); sum -= nums[i]; i++; } } return minlen == INT_MAX? 0 :minlen; } };剑指 Offer II 009. 乘积小于 K 的子数组（求数组个数的滑动窗口）
比如某次遍历符合题意的子数组为 ABCX，那么在该条件下符合条件的有X，CX，BCX，ABCX共四个（可以进行多个例子，发现个数符合right-left+1）
我们可能会有疑问：AB，BC也算，为什么不算进去？
记住一点我们是以最右边的X为必要条件，进行计算符合条件的子数组，否则会出现重复的！每向右移动一个窗口，即可多r-l+1个子数组。
比如在X为右侧边界时（ABCX），我们把BC算进去了，可是我们在C为最右侧时（ABC），BC已经出现过，我们重复加了BC这个子数组两次！
换言之，我们拆分子数组时，让num[right]存在，能避免重复计算class Solution { public: int numSubarrayProductLessThanK(vector<int>& nums, int k) { int res = 0, mul = 1, n = nums.size(); if(k == 0||k==1){ return 0; } for(int l = 0, r = 0; r < n; r++){ mul = mul*nums[r]; while(mul >= k&&l <= r){ mul = mul/nums[l]; l++; } res = res+r-l+1; } return res; } };剑指 Offer II 014. 字符串中的变位词(奇妙)
这题就神奇在可以使用数组来判断两个字符串是不是变位词
使用两个字符数组cnt1和cnt2，cnt1代表s1中的所有字符，cnt2为滑动窗口维护的一个与s1等长的字符数组，当cnt1等于cnt2的时候就可以了。
class Solution { public: bool checkInclusion(string s1, string s2) { int n = s1.length(), m = s2.length(); if (n > m) { return false; } vector<int> cnt1(26), cnt2(26);//使用数组来判断两个字符串是不是变位串 for (int i = 0; i < n; ++i) { ++cnt1[s1[i] - 'a']; ++cnt2[s2[i] - 'a']; } if (cnt1 == cnt2) { return true; } for (int i = n; i < m; ++i) { ++cnt2[s2[i] - 'a']; --cnt2[s2[i - n] - 'a']; if (cnt1 == cnt2) { return true; } } return false; } };剑指 Offer II 015. 字符串中的所有变位词
就是上一题的变种
-
剑指 Offer II 018. 有效的回文
需要几个函数
isalpha ：判断一个字符是否为字母，如果是则返回true，否则返回false； isdigit : 判断一个字符是否表示数字，如果是则返回true，否则返回false； isalnum : 判断一个字符是否表示数字或者字母，如果是则返回true，否则返回false; islower : 判断一个字符是否为小写字母，如果是则返回true，否则返回false; isupper : 判断一个字符是否为大写字母，如果是则返回true，否则返回false； tolower : 若字符为字母则转化为小写字母； toupper : 若字符为字母则转化为大写字母；class Solution { public: bool isPalindrome(string s) { int i = 0; int j = s.size() - 1; while (i < j) { while (i < s.size()&&!isalnum(s[i])) { i++; } while (j>=0&&!isalnum(s[j])) { j--; } if(i >= j) return true; if (tolower(s[i]) != tolower(s[j])) { return false; } else { i++; j--; } } return true; } };剑指 Offer II 019. 最多删除一个字符得到回文
就是暴力解法
注意写一个函数来判断是否是回文串会更加简单
class Solution { public: bool checkPalindrome(const string& s, int low, int high) { for (int i = low, j = high; i < j; ++i, --j) { if (s[i] != s[j]) { return false; } } return true; } bool validPalindrome(string s) { int low = 0, high = s.size() - 1; while (low < high) { char c1 = s[low], c2 = s[high]; if (c1 == c2) { ++low; --high; } else { return checkPalindrome(s, low, high - 1) || checkPalindrome(s, low + 1, high); } } return true; } };剑指 Offer II 020. 回文子字符串的个数(中心扩散法)
动态规划
dp写法，每个i，j判断是否是回文串
class Solution { public: int countSubstrings(string s) { int n = s.size(), res = 0; vector<vector<int>> dp(n+1, vector<int>(n+1)); for(int i = 1; i <= n; i++){ dp[i][i] = true; res++; } for(int i = n; i >= 1; i--){ for(int j = i+1; j <= n; j++){ if(s[i-1]==s[j-1]){ if(i == j-1) { dp[i][j] = true; } else dp[i][j] = dp[i+1][j-1]; } else { dp[i][j] = false; } if(dp[i][j]) res++; } } return res; } };中心扩散法
以每个点为中心，累加以当前点为中心的回文串的数目，因为中心不同，所以回文串也一定不同，注意的是回文串的长度可能是奇数也可能偶数，也就是中心可能为1个，也可能是2个，所以需要分开计算。
class Solution { public: int countSubstrings(string s) { int count = 0; for(int i = 0; i < s.size(); i++){ count += ext(s, i, i);//有一个中心，也就是说长度为奇数 count += ext(s, i, i + 1);//有两个中心，也就是说长度为偶数 } return count; } int ext(string s, int l , int r){ int count = 0; while(l >= 0&& r < s.size()&&s[l] == s[r]){ --l; ++r; ++count; } return count; } }; //有一说一想法还挺奇特，确实中点定了之后，每个子集并不相交 //与之前的dp法相比，没有浪费额外的空间，也没有遍历多余的子集剑指 Offer II 017. 含有所有字符的最短字符串（重点）
超级复杂的滑动窗口
- 使用一个long long类型的num来判断是否满足窗口左端滑动的条件
- 千万注意，一个常数1默认是int类型的，因此只有32位，不能进行超过32位的移位。必须要定义longlong bit = 1，然后进行移位
- 使用两个哈希表来判断是否满足num赋值条件
千万注意优先级的问题，一定要加括号，即使在复杂也是这样
class Solution { public: string minWindow(string s, string t) { unordered_map<char, int> hash1; unordered_map<char, int> hash2; long long num = 0, bit = 1; string ansstr = ""; int n = s.size(), m = t.size(); for(int i = 0; i < m; i++){ hash1[t[i]]++; if(t[i] >= 'a') num = num|bit << (t[i]-'a'+26); else num = num|bit<<(t[i]-'A'); } for(int i = 0, j = 0; j < n; j++){ hash2[s[j]]++; if(hash2[s[j]] >= hash1[s[j]]){ if(s[j] >= 'a'){ if(num&bit<<(s[j]-'a'+26)) { num = num^bit<<(s[j]-'a'+26); } } else { if(num&bit<<(s[j]-'A')){ num = num^bit<<(s[j]-'A'); } } } while(num == 0&&i<=j){ if(j-i+1 < ansstr.size()||ansstr.size()==0){ ansstr = s.substr(i, j-i+1); } hash2[s[i]]--; if(hash2[s[i]] < hash1[s[i]]){ if(s[i] >= 'a') num = num|bit << s[i]-'a'+26; else num = num|bit<<s[i]-'A'; } i++; } } return ansstr; } };剑指 Offer II 057. 值和下标之差都在给定的范围内（难）
滑动窗口+有序集合
题目可以看作，对于序列中每一个元素x的左侧至多k个元素，如果这k个元素中存在一个元素落在区间[x-t,x+t]中，则完成条件。
因此使用滑动窗口来维护一个长度为k的窗口，使用有序集合set来存储滑动窗口中的元素。方便进行二分查找。class Solution { public: bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) { int n = nums.size(); set<int> rec; for (int i = 0; i < n; i++) { auto iter = rec.lower_bound(max(nums[i], INT_MIN + t) - t);//第一个大于等于。 //而且INT_MIN防止越界。 if (iter != rec.end() && *iter <= min(nums[i], INT_MAX - t) + t) { return true; } rec.insert(nums[i]); if (i >= k) {//维护滑动窗口 rec.erase(nums[i - k]); } } return false; } };桶排序
这题也可以使用桶排序的思想解决，按照元素大小进行分桶，维护一个滑动窗口内的元素对应的元素。
对于元素x，影响区间为[x-t,x+t]。于是我们可以设定桶得大小为t+1.如果两个元素属于同一个桶，那么这两个元素必然符合条件。如果两个元素属于相邻桶，那么我们需要校验这两个元素得差值不超过t。否则比然不符合条件。class Solution { public: int getID(int x, long w) { return x < 0 ? (x + 1ll) / w - 1 : x / w;//返回桶的id，这里的+1ll就是为了把数据转换成longlong类型。 } bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) { unordered_map<int, int> mp; int n = nums.size(); for (int i = 0; i < n; i++) { long x = nums[i]; int id = getID(x, t + 1ll);//这里的意思是桶的大小为t+1 if (mp.count(id)) { return true; } if (mp.count(id - 1) && abs(x - mp[id - 1]) <= t) { return true; } if (mp.count(id + 1) && abs(x - mp[id + 1]) <= t) { return true; } mp[id] = x;//桶里面保存前面的元素 if (i >= k) { mp.erase(getID(nums[i - k], t + 1ll)); } } return false; } };剑指 Offer II 058. 日程表（需要看）
用红黑树来完成
- 不可能插入相同的键值，因为直接就会返回false
都是先进行判断然后入队。
class MyCalendar { private: map<int,int> calendar; public: MyCalendar() { } bool book(int start, int end) { auto iter = calendar.lower_bound(start); //第一个大于等于插入元素的时间段。这个时间段的起始时间不能小于插入时间的终止时间 if(iter != calendar.end() && iter->first < end) return false; //迭代器往前走一步就是小于等于当前时间段的最大时间段。这个时间段的终止时间不能大于插入的起始时间 if(iter != calendar.begin() && (--iter)->second > start) return false; calendar[start] = end;//不用担心插入相同键值 return true; } };
若有收获，就点个赞吧
0 人点赞
