剑指offer - 旋转数组的最小数字

发表于 2017-08-10 | 更新于 2020-09-15

题目

https://www.nowcoder.com/questionTerminal/9f3231a991af4f55b95579b44b7a01ba

题意

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

题解

二分，如果mid位置的值大于等于ft位置的值并且大于等于righht位置的值，那么可以推断出最小值在右半个区间，否则最小值在左半个区间。

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        if(rotateArray.empty()) return 0;
        int l=0,r=rotateArray.size()-1;
        while(l<r){
            int mid = l+(r-l)/2;
            if(rotateArray[mid]>=rotateArray[l]&&rotateArray[mid]>=rotateArray[r])
                l=mid+1;
            else
                r=mid;
        }
        return rotateArray[l];
    }
};

剑指offer - 斐波那契数列

发表于 2017-08-09 | 更新于 2020-09-15

题目

https://www.nowcoder.com/questionTerminal/c6c7742f5ba7442aada113136ddea0c3

题意

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。n<=39

题解

递归或迭代均可，递归会进行较多重复计算，迭代更好。

class Solution {
public:
    int Fibonacci(int n) {
        int a=0,b=1,c;
        if(n==0|n==1) return n;
        while(n-->1)
        {
            c=a+b;
            a=b;
            b=c;
        }
        return c;
    }
};

更炫的写法：

class Solution {
public:
    int Fibonacci(int n) {
        int a=0,b=1;
        while(n--)
        {
            b+=a;
            a=b-a;
        }
        return a;
    }
};

扩展题目1

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

题解

跳上n级台阶，最后一步可以跳一级，也可以跳两级，所以f(n)=f(n-1)+f(n-2)。斐波那契数列。

扩展题目2

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

题解

与上题类似，
f(n)=f(n-1)+f(n-2)+……+f(2)+f(1),
f(n-1)=f(n-2)+f(n-3)+……+f(2)+f(1)
所以有
f(n)=f(n-1)*2
f(1)=1
可得到通项公式f(n)=2^(n-1)

扩展题目3

我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

题解

假设最后一个矩形竖着放，共有f(n-1)中方法，假设最后两个横着放，共有f(n-2)种方法。也是斐波那契数列。

思考

上面求斐波那契的方法都是O(N)的，如果我们要求复杂度更小呢？

这样我们就可以用矩阵快速幂来求解了。复杂度O(LogN)

剑指offer - 用两个栈实现队列

发表于 2017-08-09 | 更新于 2020-09-15

题目

https://www.nowcoder.com/questionTerminal/54275ddae22f475981afa2244dd448c6

题意

用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。

题解

栈的特点是先进后出，队列的特点是先进先出，假设两个栈A和B
入队操作：栈A入栈
出队操作：出队要出的是栈底的元素，所以可以将栈A全部出栈依次存入B栈，这样顺序颠倒了过来，再次出队时，再从B中弹出一个即可，如果B空了，再将A中的元素搬过来，并弹出一个。

class Solution
{
public:
    void push(int node) {
        stack1.push(node);
    }

    int pop() {
        if(stack2.empty()){
            while(!stack1.empty()){
                stack2.push(stack1.top());
                stack1.pop();
            }
        }
        int ans = stack2.top();
        stack2.pop();
        return ans;
    }

private:
    stack<int> stack1;
    stack<int> stack2;
};

扩展题目

用两个队列来实现一个栈，完成栈的Push和Pop操作。栈中的元素为int类型。

题解

假设两个队列A和B
入栈操作：入队列A
出栈操作：这时要出队的元素其实应该是队尾的元素，但队列只能出队首的元素，所以我们让队A中除队尾以外的元素全部到队B中去，然后队A出队，然后再将队B中的元素回到队A。
其实在这个过程中，队B只是起到一个调度的作用，在将队B中的元素移回队A中时，其实做的是无用的操作，我们只需要将两个队列的角色互换，这样便省去多余的移动操作。

class Solution
{
public:
    void push(int node){
        if(queue1.empty())
            swap(queue1,queue2);
        queue1.push(node);
    }
    int pop(){
        if(queue1.empty())
            swap(queue1,queue2);
        while(queue1.size()>1){
            queue2.push(queue1.front());
            queue1.pop();
        }
        int ans = queue1.front();
        queue1.pop();
        return ans;
    }
private:
    queue<int> queue1;
    queue<int> queue2;
};

剑指offer - 二叉树的下一个节点

发表于 2017-08-08 | 更新于 2020-09-15

题目

https://www.nowcoder.com/questionTerminal/9023a0c988684a53960365b889ceaf5e

题意

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

题解

中序遍历顺序：左-根-右。
有以下两种情况：
(1) 如果当前节点存在右子树，则返回右子树中的最靠左的节点。
(2)如果不存在右子树，则应该回溯到上一层，如果当前节点是其父节点的左儿子，则应该返回这个父节点，如果不是，一直向上回溯直到找到一个节点是其父节点的左儿子，如果已知找到树根都没有找到，说明已经遍历到最后一个节点了，返回NULL。

struct TreeLinkNode {
    int val;
    struct TreeLinkNode *left;
    struct TreeLinkNode *right;
    struct TreeLinkNode *next;
    TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {}
};

class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode)
    {
        if(pNode == NULL) return NULL;
        if(pNode->right){  //当前节点存在右子树，返回右子树中最靠左的节点
            TreeLinkNode *root = pNode->right;
            while(root->left != NULL){
                root=root->left;
            }
            return root;
        }
        TreeLinkNode * current = pNode;
        TreeLinkNode * parent = pNode->next;
        while(parent&&parent->right == current)
        {
            current = parent;
            parent = parent->next;
        }
        if(parent==NULL) //找到根节点,则返回NULL
            return NULL;
        return parent;  //找到某个节点是其父节点的左儿子
    }
};

剑指offer - 重建二叉树

发表于 2017-08-08 | 更新于 2020-09-15

题目

https://www.nowcoder.com/questionTerminal/8a19cbe657394eeaac2f6ea9b0f6fcf6

题意

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

题解

二叉树前序遍历：根-左子树-右子树，二叉树中序遍历：左子树-根-右子树，根据根节点的位置，可以将左右技子树分开，然后递归操作即可。

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution
{
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin)
    {
        if(pre.empty()) return NULL;
        TreeNode * root = new TreeNode(pre[0]);
        int pos = find(vin.begin(),vin.end(),pre[0])-vin.begin();
        vector<int> lpre,lvin,rpre,rvin;
        //如果pos = 0，表示左子树为空
        if(pos>0){
            lpre = vector<int>(pre.begin()+1,pre.begin()+pos+1);
            lvin = vector<int>(vin.begin(),vin.begin()+pos);
        }
        //如果pos = pre.size-1 ,表示右子树为空
        if(pos<pre.size()-1){
            rpre = vector<int>(pre.begin()+pos+1,pre.end());
            rvin = vector<int>(vin.begin()+pos+1,vin.end());
        }
        root->left = reConstructBinaryTree(lpre,lvin);
        root->right = reConstructBinaryTree(rpre,rvin);
        return root;
    }
};

已知中序遍历和前序或者后后续遍历，都可以唯一确定一棵二叉树，但是已知前序和后序无法确定。
如果要得到后序遍历序列，只需要在返回前打印或者存储根节点的值即可。
如果要得到层次遍历序列，可以将树建好之后用队列实现一遍。
还有一种方法，就是按照数组存储满二叉树的思想，用一个map记录，对应下标上的值，由于是map，没有节点的地方map也不会有值，不用担心存不下所有的点，但是这种方法有一个缺点，由于map key类型的限制，使用会有一定限制，比如int的key类型，只能存储31层左右的树，long long 类推。

class Solution
{
public:
    map<int,int> levelTravelMap;
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin,int index)
    {
        if(pre.empty()) return NULL;
        levelTravelMap[index]=pre[0];
        TreeNode * root = new TreeNode(pre[0]);
        int pos = find(vin.begin(),vin.end(),pre[0])-vin.begin();
        vector<int> lpre,lvin,rpre,rvin;
        //如果pos = 0，表示左子树为空
        if(pos>0){
            lpre = vector<int>(pre.begin()+1,pre.begin()+pos+1);
            lvin = vector<int>(vin.begin(),vin.begin()+pos);
        }
        //如果pos = pre.size-1 ,表示右子树为空
        if(pos<pre.size()-1){
            rpre = vector<int>(pre.begin()+pos+1,pre.end());
            rvin = vector<int>(vin.begin()+pos+1,vin.end());
        }
        root->left = reConstructBinaryTree(lpre,lvin,index<<1);
        root->right = reConstructBinaryTree(rpre,rvin,index<<1|1);
        return root;
    }
};

剑指offer - 从尾到头打印链表

发表于 2017-08-07 | 更新于 2020-09-15

题目

https://www.nowcoder.com/questionTerminal/d0267f7f55b3412ba93bd35cfa8e8035

题意

输入一个链表，从尾到头打印链表每个节点的值。

题解

从尾到头，要访问到链表的尾节点，必须从头开始访问遍历整个链表。在不增加指针的情况下，只能遍历的时候存储每个节点的值，然后倒序输出，可以用栈来实现。当然不存也可以，递归的访问，输出每个点之前先将之后的节点输出。其实也用到了栈，都免不了O(N)的空间复杂度。

class Solution
{
public:
    vector<int> printListFromTailToHead(ListNode* head)
    {
        stack<int> st;
        while(head!=NULL){
            st.push(head->val);
            head = head->next;
        }
        vector<int> ans;
        while(!st.empty()){
            ans.push_back(st.top());
            st.pop();
        }
        return ans;
    }
};

递归实现：

class Solution
{
public:
    vector<int> printListFromTailToHead(ListNode* head)
    {
        vector<int> ans;
        dfs(ans,head);
        return ans;
    }
    void dfs(vector<int> &ans,ListNode * head)
    {
        if(head==NULL) return;
        dfs(ans,head->next);
        ans.push_back(head->val);
    }
};

剑指offer - 替换空格

发表于 2017-08-07 | 更新于 2020-09-15

题目

https://www.nowcoder.com/questionTerminal/4060ac7e3e404ad1a894ef3e17650423

题意

请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

题解

从头到尾依次复制，如果遇到空格将后面的字符依次后移，当然这很低效，最欢时间复杂度O(N*N)。可以用O(N)的额外空间来依次复制，遇到空格替换%20，时间复杂度O(N)。其实可以不用花这O(N)的空间，我们可以先计算出恭需要增加多大的空间，然后从尾到头填充字符，因为，长度不可能比原来短，所以直接在原来的数组空间操作即可，不用担心覆盖。

class Solution {
public:
	void replaceSpace(char *str,int length) {
	    int spaceCount=0;
        for(int i=0;i<length;i++){
            if(str[i]==' ') spaceCount++;
        }
        int j=length+spaceCount*2;
        str[j--] = 0;
        for(int i=length-1;i>=0;i--){
            if(str[i]==' '){
                str[j--] = '0';
                str[j--] = '2';
                str[j--] = '%';
            }
            else{
                str[j--] = str[i];
            }
        }
	}
};

扩展题目

有两个有序的数组A和B，要将B插入到A中使得整个数组仍然有序。
其实是一样的，计算出两个数组的总长度，然后在A数组中从后往前依次填充，比较A数组和B数组将大的填入。

剑指offer - 二维数组中的查找

发表于 2017-08-06 | 更新于 2020-09-15

题目

https://www.nowcoder.com/questionTerminal/abc3fe2ce8e146608e868a70efebf62e

题意

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

题解

依次扫描的方法在此不表。
对于这样的四个数，a < b，c < d，a < c，b < d

所以a < c < d，a < b < d 。
由上述关系我们可以得到一种方法。从左下角出发，如果小于目标数则应该向右继续寻找，否则向上寻找，一直到等于目标数。如果越界则表示没有没有找到。
当然可以从右上角来寻找。

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

剑指offer - 数组中重复的数字

发表于 2017-08-06 | 更新于 2020-09-15

题目

https://www.nowcoder.com/questionTerminal/623a5ac0ea5b4e5f95552655361ae0a8

题意

在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是2或3。

题解

解法一：排序判断相邻的数字是否相等。时间复杂度O(NLogN)，空间复杂度O(1)。

class Solution {
public:
    // Parameters:
    //        numbers:     an array of integers
    //        length:      the length of array numbers
    //        duplication: (Output) the duplicated number in the array number
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
    bool duplicate(int numbers[], int length, int* duplication) {
        sort(numbers,numbers+length);
        for(int i=1;i<length;i++){
            if(numbers[i]==numbers[i-1]){
                duplication[0]=numbers[i];
                return true;
            }
        }
        return false;
    }
};

解法二：用hash表存每个数字出现的次数，当一个数字出现的次数大于1时，返回结果。时间复杂度O(N)，空间复杂度O(N)。

class Solution {
public:
    // Parameters:
    //        numbers:     an array of integers
    //        length:      the length of array numbers
    //        duplication: (Output) the duplicated number in the array number
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
    bool duplicate(int numbers[], int length, int* duplication) {
        unordered_map<int,int> cnt;
        for(int i=0;i<length;i++){
            cnt[numbers[i]]++;
            if(cnt[numbers[i]]>1){
                duplication[0] = numbers[i];
                return true;
            }
        }
        return false;
    }
};

解法三：给出的数都是1~N之间的数，所以如果我们将数组重排是的每个数都回到自己的位置上，即 i=numbers[i] ,如果有重复数字，则必定有数字在多个位置出现。
重排数组对每个数字numbers[i]，如果i=numbers[i]，则表示已经满足条件，继续下一个，如果不等于比较numbers[ numbers[i] ]和numbers[i] ，如果相等，则找到重复的数字，如果不相等，则交换numbers[i]和numbers[ numbers[i] ]，此时numbers[i] 位置上已经归位，继续比较交换过来的数字，直到找到重复数字或者i=numbers[i]。
时间复杂度：O(N)，虽然是两层循环，但是，每个数字最多交换两次就能回到自己的位置，时间复杂度O(1)。

class Solution {
public:
    // Parameters:
    //        numbers:     an array of integers
    //        length:      the length of array numbers
    //        duplication: (Output) the duplicated number in the array number
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
    bool duplicate(int numbers[], int length, int* duplication) {
        for(int i=0;i<length;i++){
            while(numbers[i]!=i){
                if(numbers[i]==numbers[numbers[i]]){
                    duplication[0]=numbers[i];
                    return true;
                }
                swap(numbers[i],numbers[numbers[i]]);
            }
        }
        return false;
    }
};

扩展题目

在一个长度为 n+1 的数组里的所有数字都在1到n的范围内。所以数组中至少有一个数字是重复的，请找出数组中任意一个重复的数字，但不能修改输入的数组。

题解

上述解法一仍然适用，只不过需要增加O(N)的空间复杂度用来存储辅助数组，存放原数组的副本。
解法二也仍然适用。复杂度不变。
解法三也可以，同样需要O(N)的辅助空间。实际上，由于不能原来的数组，可以直接在复制到辅助数组时，便将其放到对应的位置上，如果有发现该位置已经有数字，则找到重复数字。时间杂度O(N)，空间复杂度O(N)。

如何能达到O(1)空间呢？不能用哈希表存数字出现的次数，我们只能计算每个数时，都对全数组扫描一遍，这样是O(N*N)时间复杂度+O(1)空间复杂度。还有优化余地吗？实际上我们可以发现，如果1~m之间的数的个数超过m，则必定有重复的数字（鸽巢原理），这样我们可以利用二分法，将范围不断缩小。直到范围为1。时间复杂度O(NLogN)，空间复杂度O(1)。

class Solution {
public:
    bool duplicate(int numbers[], int length, int* duplication) {
        int left = 1,right = length-1;
        while(left<=right){
            int mid = (left+right)/2;
            int count = getCount(numbers,length,left,mid);
            if(left==right){
                if(count>1){
                    duplication[0]=left;
                    return true;
                }
            }
            if(count>(mid-left+1))
                right=mid;
            else
                left=mid+1;
        }
        return false;
    }
    int getCount(int *numbers,int length,int left,int end)
    {
        int count=0;
        for(int i=0;i<length;i++){
            if(numbers[i]>=left&&numbers[i]<=end)
                count++;
        }
        return count;
    }
};

leetcode 6. ZigZag Conversion

发表于 2017-07-02 | 更新于 2020-09-15

题目链接：

https://leetcode.com/problems/zigzag-conversion/#/description

题意：

给一个字符串，要求将字符串排列成锯齿状，然后按行从左到右输出。如下图，原来的字符串顺序为： BFGAHIDJKCLME，按行读就是BDEFIJMGHKLAC。

题解：

找规律即可，按行来看相邻两个点的距离分为两个，假设为a和b，第 i 行为[2(n-i-1)，2i]，第一行相当于b为0，第二行相当于a为0，距离为零表示两点重合，不考虑。依次输出。

代码：

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    string convert(string s, int numRows)
    {
        if(numRows==1) return s;
        string ans="";
        for(int i=0; i<numRows; i++)
        {
            int a=2*(numRows-i-1),b=2*i;
            for(int j=i; j<s.size();)
            {
                if(a){
                    ans+=s[j];
                    j+=a;
                }
                if(j>=s.size()) break;
                if(b){
                    ans+=s[j];
                    j+=b;
                }
            }
        }
        return ans;
    }
};
int main()
{
    Solution sol;
    string str;
    int n;
    while(cin>>str>>n){
        cout<<sol.convert(str,n)<<endl;
    }
    return 0;
}