剑指 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
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;
    }