剑指 Offer 03. 数组中重复的数字
做法
数组中找重复数字我们第一个能想到的就是一一遍历 然后拿hash表记录下来
只要有一个键的值超过了1 那就直接输出
我的办法也是 可开辟一个vectorcan每个数字值就是他的位置 然后出现一次的就把值标位false 下次再遇见can[i] == false这个值的时候就直接输出
更好的办法
核心思想
一个重要的点是题目中数一定都比总数量n小 所以如果没有重复的数字 在0-n这些坑里面应该放着0-n数字对齐 也就是0号坑里面一定是0 所以我们就在每次遍历的时候把这些数字放回去 假设num[i] = x 那说明num[i]这个数字应该属于x这个坑 我们就不把他和num[x](也就是num[num[i]])做交换 那在交换的如果这个数字是第二次出现的 在他交换的时候肯定已经放着相同的数字了
从头开始遍历每一个数
例如
0 1 2 3 4 坑
2 2 4 1 2 萝卜
第一次找2 将2和4交换 放回2坑
0 1 2 3 4 坑
4 2 2 1 2 萝卜
接下去就换下一个数 2 将他放到2坑的时候 发现那里已经是2了 就说明他重复了
实现代码
bool swap(int &a,int &b)
{
if(a == a)
return true;
int temp = a;
a= b;
b = temp;
return false;
}
int findRepeatNumber(vector<int>& nums) {
for(int i =0;i<nums.size();i++)
{
if(nums[i] != i)
{
if(swap(nums[i],nums[nums[i]]))
return nums[i];
}
}
return -1;
}
剑指 Offer 05. 替换空格
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
示例 1：
输入：s = “We are happy.”
输出：“We%20are%20happy.”
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
做法
第一时间想的就是遍历一遍 用另外一个string存字符 碰到’ '就依次push_back（‘%’） push_back（‘2’） push_back（‘0’）
更好的办法
貌似还没有
剑指 Offer 09. 用两个栈实现队列
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
示例 1：
输入：
[“CQueue”,“appendTail”,“deleteHead”,“deleteHead”]
[[],[3],[],[]]
输出：[null,null,3,-1]
示例 2：
输入：
[“CQueue”,“deleteHead”,“appendTail”,“appendTail”,“deleteHead”,“deleteHead”]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方法
一个栈用来添加数据 一个栈用来删除数据 如果删除栈空了 就把添加栈的而所有数据放过来
核心思想 目的就是要能删到栈底的元素
因为栈是删除栈顶元素 把一个栈的元素放到另一个栈里 原来栈顶元素就会变成栈底元素了 原栈底元素就在栈顶 这样就跟队一样了
代码
class CQueue {
stack<int> del,add;
public:
CQueue() {
while(!del.empty())
{
del.pop();
}
while(!add.empty())
{
add.pop();
}
}
void appendTail(int value) {
add.push(value);
}
int deleteHead() {
int out;
if(del.empty())
{
if(add.empty())
{
return -1;
}
while(!add.empty())
{
del.push(add.top());
add.pop();
}
out = del.top();
del.pop();
}
else
{
out = del.top();
del.pop();
}
return out;
}
};
剑指 Offer 10- I. 斐波那契数列
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入：n = 2
输出：1
示例 2：
输入：n = 5
输出：5
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
做法
正常就是从i =0 和1的时候是0和1
很明显的递归终止条件 直接递归 return f(n-1)+f(n-2);
这个时候会发现时间是超时的 因为有很多重复的运算
所以就需要用个东西记一下过去的东西就行了 实际上只需要记两项 然后加起来就行了
代码
int fib(int n) {
int mod = 1e9+7;
if(n == 0||n == 1)
{
return n;
}
int first=0;
int second=1;
int third=0;
for(int i=2;i<=n;i++){
third=(first+second)%mod;
first=second;
second=third;
}
return third%mod;
}
剑指 Offer 15. 二进制中1的个数
n = n & (n - 1);
1011 1010
1010
一
1010 1001
1000
二
1000 0111
0000
三
剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
示例：
输入：nums = [1,2,3,4]
输出：[1,3,2,4]
注：[3,1,2,4] 也是正确的答案之一。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
双指针
一个是偶数的位置 一个是奇数的位置
void swap(int &a,int &b){
int temp = a;
a = b;
b = temp;
}
vector<int> exchange(vector<int>& nums)
{
int dou = nums.size()-1;
for(int i = 0;i<nums.size();i++)
{
if(dou == i)
return nums;
if(nums[i]%2 == 0)
{
swap(nums[i],nums[dou]);
dou--;
i--;
}
}
return nums;
}
快慢指针 快指针一直走找奇数位置 快指针会经过所有奇数的位置 快指针不会管慢指针指的是哪
void swap(int &a,int &b){
int temp = a;
a = b;
b = temp;
}
vector<int> exchange(vector<int>& nums)
{
int fast = 0;int low = 0;
while(fast<nums.size())
{
if(nums[fast]%2 == 1)
{
swap(nums[fast],nums[low]);
low++;
}
fast++;
}
return nums;
}
剑指 Offer 22. 链表中倒数第k个节点
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
示例：
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
做法
快慢指针
先让快指针走k步 k走到链表尾部的时候 慢指针就走到了倒数第k个位置了
ListNode* getKthFromEnd(ListNode* head, int k)
{
ListNode* fast = head;
ListNode *low = head;
while(k)
{
k--;
fast = fast->next;
}
while(fast)
{
fast = fast->next;
low = low->next;
}
return low;
}
|