剑指offer记录
刷题思路
第一遍:
- 使用c++独立解。
- 20分钟以上无思路再看他人题解，且标记。
- 解题完毕，记录自己的题解。
- 看他人题解的其他办法
字符串
剑指 Offer 05. 替换空格 简单
我的题解
class Solution {
public:
string replaceSpace(string s) {
string r;
for(int i=0; i<s.length();i++){
char c = s[i];
if(c==' ')
{
r.push_back('%');
r.push_back('2');
r.push_back('0');
}
else
r.push_back(c);
}
return r;
}
};剑指 Offer 58 - II. 左旋转字符串 简单
我的题解
//切片法
class Solution {
public:
string reverseLeftWords(string s, int n) {
return s.substr(n,s.length()-n) + s.substr(0,n);
}
};//切片法过于暴力
//遍历法取余
class Solution {
public:
string reverseLeftWords(string s, int n) {
string r = s;
int len = s.length();
for(int i=0; i<len;i++)
{
r[(i+len-n)%len] = s[i];
}
return r;
}
};剑指 Offer 67. 把字符串转换成整数 中等
class Solution {
public:
int strToInt(string str) {
int len = str.length();
if(len == 0) return 0; //字符串长度为o
int res = 0;//结果
int sign = 1;//符号，默认为无符号正数
int i = 0;//序号
while(str[i]==' ') i++; //索引到第一个无空格的字符
if(str[i]=='-') sign = -1; //负号
if(str[i]=='-' || str[i]=='+') ++i; // 有符号则向后移一位
for(;i<len;++i)
{
if(str[i]<'0'||str[i]>'9') break;
if (res > INT_MAX / 10 || (res == INT_MAX / 10 && str[i] - '0' > 7)) //溢出判定
return sign == 1 ? INT_MAX : INT_MIN;
res = res * 10 + (str[i] - '0');
}
return sign * res;
}
};链表
剑指 Offer 06. 从尾到头打印链表 简单
//回溯
//依次存入temp，再反向存入输出数组
class Solution {
public:
vector<int> reversePrint(ListNode* head) {
vector<int> temp, res;
ListNode *p = head;
while(p)
{
temp.push_back(p->val);
p = p->next;
}
for(int i = temp.size()-1; i>=0; --i)
{
res.push_back(temp[i]);
}
return res;
}
};顺便复习STL中的vector
剑指 Offer 24. 反转链表
//头插法
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* res=NULL, *cur=head;
while(cur!=NULL)
{
ListNode* temp = cur->next;
cur->next = res;
res = cur;
cur = temp;
}
return res;
}
};双指针
剑指 Offer 18. 删除链表的节点
class Solution {
public:
ListNode* deleteNode(ListNode* head, int val) {
if(head == NULL) return head;//判断空
ListNode *pre=head,*cur=head->next;
if(pre->val == val) return cur; // 判断第一个节点
while(cur!=NULL) //判断后面的阶段
{
if(cur->val == val)
{
pre->next = cur->next;
cur = cur->next;
break;
}
pre = pre->next;
cur = cur->next;
}
return head;
}
};剑指 Offer 22. 链表中倒数第k个节点
//统计法
class Solution {
public:
ListNode* getKthFromEnd(ListNode* head, int k) {
ListNode *p = nullptr;
int cnt = 0;
for(p=head;p!=NULL;p=p->next)
cnt++;
for(p=head;cnt>k;--cnt)
p = p->next;
return p;
}
};//双指针
class Solution {
public:
ListNode* getKthFromEnd(ListNode* head, int k) {
ListNode* p=head, *q = head;
for(int n=0; n<k; ++n)
p = p->next;
while(p!=NULL)
{
p = p->next;
q = q->next;
}
return q;
}
};剑指 Offer 25. 合并两个排序的链表
//迭代
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* head = new ListNode(0);
ListNode* res = head;
while(l1 && l2)
{
if(l1->val < l2->val)
{
res->next = l1;
l1 = l1->next;
}
else
{
res->next = l2;
l2 = l2->next;
}
res = res->next;
}
if(l1)
res->next = l1;
else if(l2)
res->next = l2;
return head->next;
}
};//递归
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(!l1) return l2;
if(!l2) return l1;
if(l1->val < l2->val)
{
l1->next = mergeTwoLists(l1->next,l2);
return l1;
}
else
{
l2->next = mergeTwoLists(l1,l2->next);
return l2;
}
}
};剑指 Offer 52. 两个链表的第一个公共节点
//双指针遍历相遇
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *a = headA;
ListNode *b = headB;
while(a != b )
{
a = a != nullptr ? a->next : headB;
b = b != nullptr ? b->next : headA;
}
return a;
}
};剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
class Solution {
public:
vector<int> exchange(vector<int>& nums) {
int left = 0, right = nums.size()-1;
while(left < right)
{
if(nums[left]%2==0||nums[left]==0)//偶数
{
while(nums[right]%2==0||nums[right]==0)//从后往前直到找到第一个奇数
{
if(right < 0 || right<=left) break; //right不能在left左边且不能小于0
right--;
}
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
left++;
}
return nums;
}
};其他思路，可以使用双向队列deque进行实现，但是要求结果是vector，实现deque之后需要再依次赋值给新的vector，效率很低，所以在题目要求的情况下，不建议使用deque
剑指 Offer 57. 和为s的两个数字
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> res;
int left = 0, right = nums.size()-1;
while(left<right)
{
if(target-nums[left] < nums[right]) right--;
else if (target-nums[left] > nums[right]) left++;
else
{
res.push_back(nums[left]);
res.push_back(nums[right]);
return res;
}
}
return res;
}
};剑指 Offer 58 - I. 翻转单词顺序
class Solution {
public:
string reverseWords(string s) {
string res = "";
int len = s.length();
int right = len-1;
int left = right;
while(left>=0)
{
//首尾空格
if(s[right] == ' ')
{
right--;
left--;
continue;
}
//正常
if(s[left]==' '||left == 0)
{
int temp = right;
if(left==0 &&s[left]!=' ') right = left;//第0个字符问题
else right = left+1;
while(right<=temp)
{
res +=s[right++];
}
res += ' ';
right = left-1;
}
left--;
}
res.pop_back();
return res;
}
};栈和队列
剑指 Offer 09. 用两个栈实现队列
class CQueue {
public:
stack<int> s1,s2;
CQueue() {
}
void appendTail(int value) {
s1.push(value);
}
int deleteHead() {
if(s1.empty()) return -1;
int len = s1.size();
while(!s1.empty())
{
s2.push(s1.top());
s1.pop();
}
int res = s2.top();
s2.pop();//删除栈顶
while(!s2.empty())
{
s1.push(s2.top());
s2.pop();
}
return res;
}
};剑指 Offer 30. 包含min函数的栈
class MinStack {
public:
/** initialize your data structure here. */
stack<int> s,s_min;
int m=0;
MinStack() {
}
void push(int x) {
if(s.empty())
{
m = x;
s.push(x);
s_min.push(x);
}
else
{
s.push(x);
if(x<m)
m=x;
s_min.push(m);
}
}
void pop() {
s.pop();
s_min.pop();
//剔除已经删除的元素，这里是易错易忽略点
if(!s_min.empty()) m = s_min.top();
}
int top() {
return s.top();
}
int min() {
return s_min.top();
}
};剑指 Offer 59 - II. 队列的最大值
class MaxQueue {
public:
queue<int> q;
deque<int> dq;
int max;
MaxQueue() {
}
int max_value() {
return dq.empty() ? -1 : dq.front();
}
void push_back(int value) {
q.push(value);
while(!dq.empty()&&dq.back()<value)
dq.pop_back();
dq.push_back(value);
}
int pop_front() {
if(q.empty()) return -1;
int max = q.front();
if(max == dq.front())
{
dq.pop_front();
}
q.pop();
return max;
}
};使用一个双端队列保存最大数的序列，尾部放入数之前，先推出所有比该数小的数，然后放入该数。
模拟
剑指 Offer 29. 顺时针打印矩阵
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
//空的情况
if(matrix.size()==0 || matrix[0].size()==0) return {};
//
vector<int> ans;
int top = 0;
int bottom = matrix.size()-1;
int left = 0;
int right = matrix[0].size()-1;
while(true)
{
//从左到右
for(int i=left; i<=right; ++i) ans.push_back(matrix[top][i]);
if(++top > bottom) break; // 每次从左到右，都要下移一行
//从上到下
for(int i=top; i<=bottom; ++i) ans.push_back(matrix[i][right]);
if(--right < left) break; // 每次从上到下都要，左移一列
//从右到左
for(int i=right; i>=left; --i) ans.push_back(matrix[bottom][i]);
if(--bottom < top) break;// 每次从右到左，都要上移一行
//从下到上
for(int i=bottom; i>=top; --i) ans.push_back(matrix[i][left]);
if (++ left > right) break;//每次从下到上，都要右移一列
}
return ans;
}
};剑指 Offer 31. 栈的压入、弹出序列 ✨中等
class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
stack<int> stack;
int cnt = pushed.size();
for(int i=0,j=0; i<cnt; ++i)
{
stack.push(pushed[i]);
while(!stack.empty()&& stack.top()==popped[j])
{
stack.pop();
j++;
}
}
if(stack.empty()) return true;
else return false;
}
};查找算法
剑指 Offer 03. 数组中重复的数字
使用hash set的唯一性进行遍历，一旦遇到存在的hash set则返回该数。
class Solution {
public:
int findRepeatNumber(vector<int>& nums) {
std::unordered_map<int,bool> map;
for(int num:nums){
if(map[num]) return num;
map[num] = true;
}
return 0;
}
};剑指 Offer 53 - I. 在排序数组中查找数字 I
使用哈希查找，遍历数组，key为数字，value为出现次数。
class Solution {
public:
int search(vector<int>& nums, int target) {
std::unordered_map<int, int> map;
for(int num:nums)
{
if(map[num]) map[num]++;
else map[num] = 1;
}
if(map[target]) return map[target];
else return 0;
}
};剑指 Offer 53 - II. 0～n-1中缺失的数字
常规使用顺序遍历，这里使用二分法。当nums[mid] = mid时，说明前一半数字（左边）并没有缺少，所以继续查找右边即可。
class Solution {
public:
int missingNumber(vector<int>& nums) {
int left = 0;
int right = nums.size()-1;
while(left<=right)
{
int mid = (left + right) / 2;
if(nums[mid]==mid) left = mid+1;
else right = mid - 1;
}
return left;
}
};剑指 Offer 04. 二维数组中的查找✨中等
把二维举行想象成菱形(树的思想演变) https://leetcode.cn/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/solutions/95306/mian-shi-ti-04-er-wei-shu-zu-zhong-de-cha-zhao-zuo/?envType=study-plan-v2&envId=coding-interviews
class Solution {
public:
bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
if(matrix.size()==0) return false;
int i = matrix.size()-1, j=0;
int max_col = matrix[0].size();
while(i>=0 && j< max_col)
{
if(target<matrix[i][j]) i--;
else if (target > matrix[i][j]) j++;
else return true;
}
return false;
}
};本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Miasol's Blog！