剑指offer编程题总结

终于刷完了剑指offer的编程题，以下是github链接：https://github.com/staight/algorithm/tree/master/%E5%89%91%E6%8C%87offer。

话说剑指offer都刷完了，我的offer呢？

总计67道题目，从1号开始刷起，总共花了6天的时间，总体上来说题目还是挺简单的。不过仍然有一些题目比较困难，或者说可以有更好的方法。

以下是我认为比较有难度的题目…

二维数组中的查找

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

看到排序数组+查找，我立即想到了二分查找，然而并不是。。。

正确的方法是从二维数组的左下方开始查找，如果比目标数字大，则向上移动；如果比目标数字小，则向右移动；直到找到目标数字，或到达二维数组边缘无法找到。

class Solution {
  public:
    bool Find(int target, vector<vector<int> > array) {
        if(array.size()==0)
            return false;
        if(array[0].size()==0)
            return false;
        int r = array.size() - 1, l = 0;
        while (r >= 0 && l <= array[0].size()) {
            if (target > array[r][l]) {
                l++;
            } else if (target < array[r][l]) {
                r--;
            } else
                return true;
        }
        return false;
    }
};

变态跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

可以从任一台阶上跳至n级的台阶，那么自然有f(n)=f(n-1)+f(n-2)+...+f(1)。

那么第一种解法就是递归求解。

由于中间有许多计算步骤重复，那么可以创建一个缓存直接得出结果，以优化第一种解法。

还有另一种解法是：f(n)=f(n-1)+f(n-2)+...+f(1)，f(n-1)=f(n-2)+f(n-3)+...+f(1)，两式相减得f(n)=2*f(n-2)，更为快捷。

第一种解法：

class Solution {
  public:
    vector<int> num = vector<int>(10000, 0);

int jumpFloorII(int number) {
        if (number == 1)
            return number;
        if (num[number] != 0)
            return num[number];
        int res = 0;
        for (int i = 1; i < number; i++)
            res += jumpFloorII(i);
        num[number] = res + 1;
        return num[number];
    }
};

第二种解法：

class Solution {
  public:
    int jumpFloorII(int number) {
        return 1<<(number-1);
    }
};

调整数组顺序使奇数位于偶数前面

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

我的思路：

开辟一个新的数组，用来保存偶数。
遍历整数数组，遇到偶数则放入偶数数组中；遇到奇数则前移，使整数数组中的所有奇数都放在前面的位置。
将偶数数组中的数字放置于整数数组的后面。

优化思路：

i++往前走碰到偶数停下来，j = i+1。
若a[j]为偶数，j++前进，直到碰到奇数。
- a[j]对应的奇数插到a[i]位置，j经过的j-i个偶数依次后移。
如果j==len-1时还没碰到奇数，证明i和j之间都为偶数了，完成整个移动

参考链接：https://blog.nowcoder.net/n/40d6a17c8f744804a402ed2b0aa10d35

第一种解法：

class Solution {
  public:
    void reOrderArray(vector<int> &array) {
        vector<int> even;
        int now = 0;
        for (int i = 0; i < array.size(); i++) {
            if (array[i] % 2) {
                array[now] = array[i];
                now++;
            } else {
                even.push_back(array[i]);
            }
        }
        for (int i = even.size() - 1; i >= 0; i--) {
            array[array.size() - even.size() + i] = even[i];
        }
    }
};

第二种解法：

class Solution {
public:
    void reOrderArray(vector<int> &array) {
        int len = array.size();
        if(len <= 1){ // 数组空或长度为1
            return;
        }

int i = 0;
        while(i < len){
            int j = i + 1;
            if(array[i]%2 == 0){ // a[i]为偶数，j前进，直到替换
                while(array[j]%2 == 0){ // j为偶数，前进
                    if(j==len-1)// i为偶数，j也为偶数，一直后移到了末尾，证明后面都是偶数
                         return;
                    j++;
                }
                // 此时j为奇数
                int count = j-i;
                int temp = array[i];
                array[i] = array[j];
                while(count>1){
                    array[i+count] = array[i+count-1];//数组后移
                    count--;
                }
                array[i+1] = temp;
            }
            i++;
        }
    }
};

包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

使用两个栈，额外的辅助栈用来记录之前的min值。

push时：

将数值压入至栈。
如果辅助栈为空，或数值小于等于辅助栈的栈顶，则将数值同时压入至辅助栈。

pop时：

将数值从栈中压出。
如果数值与辅助栈的栈顶相同，则将辅助栈的栈顶同时压出。

class Solution {
  public:
    stack<int> s1, s2;
    void push(int value) {
        if (s2.empty() || s2.top() >= value)
            s2.push(value);
        s1.push(value);
    }
    void pop() {
        if (s1.top() == s2.top())
            s2.pop();
        s1.pop();
    }
    int top() {
        return s1.top();
    }
    int min() {
        return s2.top();
    }
};

最小的K个数

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

比较简单的解法是对数组排序，然后前k位即是答案。

不过这肯定不是该题的本意，实际上可以借鉴快速排序的思想，将数组分为小于哨兵和大于哨兵两部分，如果小于哨兵的数正好有k个的话，对这k个数字排序即可。参考链接：https://www.nowcoder.com/questionTerminal/6a296eb82cf844ca8539b57c23e6e9bf?answerType=1&f=discussion

class Solution {
  public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        if (k > input.size())
            return vector<int>();
        sort(input.begin(), input.end());
        vector<int> res(input.begin(), input.begin() + k);
        return res;
    }
};

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

只包含质因子2，3，5，说明丑数可以被分解为：2^x*3^y*5^z，因此创造一个丑数只需要填入x，y，z的值。另一方面，根据上式，一个丑数一定是另一个丑数的倍数，那么可以从倍数入手构造不同大小的丑数。

class Solution {
  public:
    int GetUglyNumber_Solution(int index) {
        if (index < 1)
            return 0;
        int a = 0, b = 0, c = 0;
        vector<int> res(index, 1);
        for (int i = 1; i < index; i++) {
            res[i] = min(res[a] * 2, min(res[b] * 3, res[c] * 5));
            if (res[i] == res[a] * 2)
                a++;
            if (res[i] == res[b] * 3)
                b++;
            if (res[i] == res[c] * 5)
                c++;
        }
        return res[index - 1];
    }
};

数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。即输出P%1000000007

归并排序，将两个排序数组合并为一个数组时，如果数组A的数a大于数组B的数b，则a以及之后的数都将大于b，这样可以批量得出逆序对。

class Solution {
  public:
    int cnt;
    int InversePairs(vector<int> data) {
        cnt = 0;
        mergeSort(data, 0, data.size());
        return cnt;
    }
    void mergeSort(vector<int> &data, int l, int r) {
        // printf("l:%d r:%d\n", l, r);
        if (l + 1 >= r)
            return;
        int mid = (l + r) / 2;
        mergeSort(data, l, mid);
        mergeSort(data, mid, r);
        merge(data, l, mid, r);
    }

void merge(vector<int> &data, int l, int mid, int r) {
        vector<int> v(r - l);
        int index = 0;
        int p1 = l, p2 = mid;
        // printf("index:%d l:%d mid:%d r:%d\n", index, l, mid, r);
        while (index != v.size()) {
            if (p1 == mid) {
                v[index++] = data[p2++];
            } else if (p2 == r) {
                v[index++] = data[p1++];
            } else if (data[p1] > data[p2]) {
                // printf("p1:%d p2:%d %d %d\n", p1, p2, data[p1], data[p2]);
                cnt += mid - p1;
                cnt %= 1000000007;
                v[index++] = data[p2++];
            } else
                v[index++] = data[p1++];
        }
        for (int i = l; i < r; i++)
            data[i] = v[i - l];
    }
};

两个链表的第一个公共结点

输入两个链表，找出它们的第一个公共结点。

容易想到的做法是遍历一个链表，将每个节点使用散列表保存下来，然后遍历另一个链表，如果有散列表拥有的元素，即是公共节点；否则没有。

另一种解法是将两个链表首尾相连分别变成两个新的大链表，即A+B和B+A。这样两个新链表的长度相等，依据公共节点至尾节点的距离相等的特性，同时遍历两个新链表即可。

class Solution {
  public:
    ListNode *FindFirstCommonNode(ListNode *pHead1, ListNode *pHead2) {
        set<ListNode *> sset;
        while (pHead1) {
            sset.insert(pHead1);
            pHead1 = pHead1->next;
        }
        while (pHead2) {
            if (sset.find(pHead2) != sset.end())
                return pHead2;
            pHead2 = pHead2->next;
        }
        return NULL;
    }
};

class Solution {
  public:
    ListNode *FindFirstCommonNode(ListNode *pHead1, ListNode *pHead2) {
        if(pHead1 == NULL || pHead2 == NULL)return NULL;
        ListNode *p1 = pHead1;
        ListNode *p2 = pHead2;
        while(p1!=p2){
            p1 = p1->next;
            p2 = p2->next;
            if(p1 != p2){
                if(p1 == NULL)p1 = pHead2;
                if(p2 == NULL)p2 = pHead1;
            }
        }
        return p1;
    }
};

和为S的连续正数序列

小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!

我的想法是：

遍历数组，对每个遍历的数不断累加，直至求出第一个等于目标值的组合，比如说目标值100的第一个组合为9~16。
根据第一个组合一定是最长的组合，且所有组合的和相等的特性，从组合最右边开始累加数字，直至能整除剩余数字个数为止为第二个组合，比如说16/7无法整除，(16+15)/6无法整除，(16+15+14)/5=9能够整除，那么第二个组合即为：(9+9), (10+9), (11+9), (12+9), (13+9)。
重复步骤二，得出所有组合。

还有一种比较容易理解的思路是使用双指针分别指向数组最左边和最右边(1和2)，依据序列求和公式：S=n*(a1+an)/2快速得出和，如果大于目标值则右移左指针；如果小于目标值则右移右指针；如果等于则记录下来，同时右移左指针。

class Solution {
  public:
    vector<vector<int>> FindContinuousSequence(int sum) {
        vector<vector<int>> v;
        int now = 1;
        int len = 1;
        for (; now * 2 < sum; now++) {
            int total = 0;
            int i = 0;
            for (; total < sum; i++) {
                total += i + now;
            }
            if (total == sum) {
                len = i;
                break;
            }
        }
        // printf("now:%d len:%d\n", now, len);
        if (len == 1)
            return v;
        v.push_back(vector<int>(len));
        for (int i = 0; i < len; i++)
            v[v.size() - 1][i] = now + i;

int t1 = 0, t2 = 0;
        while (len >= 3) {
            len--;
            t1 += now + len;
            if (t1 % len == 0) {
                t2 = t1 / len;
                // printf("now:%d len:%d\n", now + t2, len);
                v.push_back(vector<int>(len));
                for (int i = 0; i < len; i++)
                    v[v.size() - 1][i] = now + t2 + i;
            }
        }
        return v;
    }
};

链表中环的入口结点

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

快慢指针。快指针一次走两步，慢指针一次走一步，设链表起点到入口结点的长度是x1，快慢指针第一次相遇时距离入口结点的长度是x2，此时慢指针走了x1+x2，快指针走了2x1+2x2，也就是说x1+x2的长度正好是环的一圈大小的倍数。

此时让一个指针从起点出发，一个指针从相遇结点出发，都是一次走一步，当两个指针第一次相遇时恰好是在入口结点。

class Solution {
  public:
    ListNode *EntryNodeOfLoop(ListNode *pHead) {
        ListNode *fast = pHead, *slow = pHead;
        while (fast != NULL && fast->next != NULL) {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow)
                break;
        }
        if (fast == NULL || fast->next == NULL)
            return NULL;
        fast = pHead;
        while (fast != slow) {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};

数据流中的中位数

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

非最优解：

class Solution {
  public:
    vector<int> v;
    void Insert(int num) {
        v.push_back(num);
        sort(v.begin(), v.end());
    }

double GetMedian() {
        if (v.size() % 2 == 0)
            return (v[v.size() / 2 - 1] + v[v.size() / 2]) / double(2);
        else
            return v[v.size() / 2];
    }
};

滑动窗口的最大值

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}；针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。

非最优解：

class Solution {
  public:
    vector<int> maxInWindows(const vector<int> &num, unsigned int size) {
        vector<int> res;
        if (size == 0 || size > num.size())
            return res;
        int l = 0, r = size;
        map<int, int, std::greater<int>> mmap;
        for (int i = l; i < r; i++) {
            if (mmap.find(num[i]) != mmap.end())
                mmap[num[i]]++;
            else
                mmap[num[i]] = 1;
        }
        res.push_back(mmap.begin()->first);
        while (r != num.size()) {
            if (mmap.find(num[r]) != mmap.end())
                mmap[num[r]]++;
            else
                mmap[num[r]] = 1;
            r++;

mmap.erase(num[l]);
            l++;
            res.push_back(mmap.begin()->first);
        }
        return res;
    }
};

给你一根长度为n的绳子，请把绳子剪成m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],...,k[m]。请问k[0]xk[1]x...xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

非最优解：

class Solution {
  public:
    int cutRope(int number) {
        int res = 1;
        if (number == 3)
            return 2;
        for (int i = 2; i <= number / 2; i++) {
            int sum = 1;
            int t1 = number / i, t2 = number % i;
            for (int j = 0; j < t2; j++)
                sum *= (t1 + 1);
            for (int j = t2; j < i; j++)
                sum *= t1;
            res = max(res, sum);
        }
        return res;
    }
};

二维数组中的查找

变态跳台阶

调整数组顺序使奇数位于偶数前面

包含min函数的栈

最小的K个数

数组中的逆序对

两个链表的第一个公共结点

和为S的连续正数序列

链表中环的入口结点

数据流中的中位数

滑动窗口的最大值

Recommend

容器实现-构造实现run命令版本的容器

Kubernetes CRD简介

Kubernetes CRD编写

排序算法的实现

golang实现一个简单的http代理

frontop137's blog

一季度仅营收707元，比不过小贩摊煎饼

onedev构建一个实际java spring应用

Kubernetes创建普通账号

How the TypeScript Omit Type Works

About Joyk