在线提交地址:https://www.nowcoder.com/ta/coding-interviews?page=1 (牛客网)


面试题4:二维数组中的查找

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

思路:

1、可以考虑对每行进行二分查找

2、以右上或左下为起点,这里选择右上,依次向左扫描,如果当前值小于target,则row++(每行最后一个是该行最大的,如果它都小了,这一行都小了),如果大于,则col--(同理),直至扫描完。

代码:

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

面试题5:替换空格

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

思路:首先要确定是不是在本身上修改,如果是,则要题目保证内存足够。否则,可以考虑自己new空间。

    先统计空格数,然后倒着赋值即可。

代码:

class Solution {
public:
    void replaceSpace(char *str,int length) {
        if(str == nullptr || length <= 0) return;
        int count = 0;
        for(int i = 0; i < length; i++)
            if(str[i] == ' ') count++;
        // 假设是在原有的基础上进行替换,且保证内存足够
        int newLength = length + count*2;
        int p = length;
        while(newLength >= 0)
        {
            if(str[p] != ' ')
                str[newLength--] = str[p--];
            else 
            {
                str[newLength--] = '0';
                str[newLength--] = '2';
                str[newLength--] = '%';
                p--;
            }
        }
	}
};

面试题6:从尾到头打印链表

输入一个链表,按链表值从尾到头的顺序返回一个ArrayList。

思路:有两种方向,一是循环,用栈存储。二是递归。但是由于递归可能导致爆栈,故不建议采用。

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> V;
        stack<int> S;
        while(head != nullptr)
        {
            S.push(head->val);
            head = head->next;
        }
        while(!S.empty())
        {
            int p = S.top();
            S.pop();
            V.push_back(p);
        }
        return V;
    }
};

面试题7:重建二叉树

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

思路:根据二叉树遍历的性质,得知前序的第一个元素为父节点,中序父节点两边的分别为它的左右子树,递归即可。

代码:

class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if(pre.size() == 0 || vin.size() == 0) return nullptr;
        TreeNode *p = build(pre, 0, pre.size()-1, vin, 0, vin.size()-1);
        return p;
    }
    TreeNode* build(vector<int> pre, int ps, int pe, vector<int> vin, int vs, int ve)
    {
        if(ps > pe || vs > ve) return nullptr;
        TreeNode *p = new TreeNode(pre[ps]);
        for(int i = vs; i <= ve; i++)
        {
            if(vin[i] == pre[ps])
            {
                p->left = build(pre, ps+1, ps+i-vs, vin, vs, i-1);
                p->right = build(pre, ps+i-vs+1, pe, vin, i+1, ve);
                break;
            }
        }
        return p;
    }
};

面试题9:用两个栈实现队列

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

思路:用stack2用于输出,每次存入stack1,当要输入时,倒入到stack2。

代码:

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 p = stack2.top();//可能需要抛出一个异常,如果stack2还为空的话
        stack2.pop();
        return p;
    }
private:
    stack<int> stack1;
    stack<int> stack2;
};

面试题10:斐波那契数列

题目一:寻找斐波那契第n项

大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。n<=39

思路:

1、递归(由于可能发生栈溢出,故不推荐)

2、循环(推荐,这里使用)

3、公式法(可以了解)

代码:

class Solution {
public:
    int Fibonacci(int n) {
        if(n == 1) return 1;
        long long a = 0, b = 1, c = 0;
        for(int i = 1; i < n; i++)
        {
            c = a + b;
            b = c;
            a = c - a;
        }
        return c;
    }
};

题目二:跳台阶

一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。

思考:1级时1种,2级时2种,当n>2时,每次跳法有两种不同的选择,一是第一次跳了1级,故后面的跳法为f(n-1),二是第一次跳了2级,故后面的跳法为f(n-2)。

    故,本题就是在求斐波那契数列。

代码:

class Solution {
public:
    int jumpFloor(int n) {
        if(n == 1) return 1;
        long long a = 0, b = 1, c = 0;
        for(int i = 0; i < n; i++)
        {
            c = a + b;
            b = c;
            a = c - a;
        }
        return c;
    }
};

题目三:变态跳台阶

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

思考:

f(1) = 1

f(2) = f(2-1) + f(2-2)         // 第一次跳一阶,第一次跳二阶

f(3) = f(3-1) + f(3-2) + f(3-3)  // 第一次跳一阶,第一次跳二阶,第一次跳三阶

...

f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(n-(n-1)) + f(n-n) 

具体:

1、f(n) 代表的是n个台阶有一次1,2,...n阶的 跳法数。

2、n = 1时,只有1种跳法,f(1) = 1

3、n = 2时,会有两个跳得方式,一次1阶或者2阶,这回归到了问题(1) ,f(2) = f(2-1) + f(2-2) 

4、n = 3时,会有三种跳得方式,1阶、2阶、3阶,

    那么就是第一次跳出1阶后面剩下:f(3-1);第一次跳出2阶,剩下f(3-2);第一次3阶,那么剩下f(3-3)

    因此结论是f(3) = f(3-1)+f(3-2)+f(3-3)

5、n = n时,会有n中跳的方式,1阶、2阶...n阶,得出结论:

    f(n) = f(n-1)+f(n-2)+...+f(n-(n-1)) + f(n-n) => f(0) + f(1) + f(2) + f(3) + ... + f(n-1)

6、由以上已经是一种结论,但是为了简单,我们可以继续简化:

    f(n-1) = f(0) + f(1)+f(2)+f(3) + ... + f((n-1)-1) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2)

    f(n) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2) + f(n-1) = f(n-1) + f(n-1)

    可以得出:f(n) = 2*f(n-1)

7、得出最终结论,在n阶台阶,一次有1、2、...n阶的跳的方式时,总得跳法为:

           | 1       ,(n=0 ) 

f(n) =  | 1       ,(n=1 )

           | 2*f(n-1),(n>=2)

代码:

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

面试题11:旋转数组的最小数字

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

思路:由于旋转数组的特性,尾元素肯定是小于首元素的(当不考虑重复值时)。所以,每次找中间值,如果中间值大于首元素,则中元素为前面那段,相反,则为后面那段。截止条件为s,e相差1。

    其次,考虑旋转0个的情况,返回的是第一个。在其次,考虑有重复的情况。如{1,0,1,1,1},{1,1,1,0,1}都可以看成{0,1,1,1,1}的旋转,故此时使用循环依次查找。

代码:

class Solution {
public:
    int minNumberInRotateArray(vector<int> arr) {
        if(arr.size() == 0) return 0;
        int length = arr.size();
        int s = 0, e = length - 1, mid = 0;
        while(arr[s] >= arr[e])
        {
            if(e - s == 1) return arr[e];
            mid = (s + e) / 2;
            // 如果三个下标相等,则不能使用该方法,只得顺序查找
            if(arr[s] == arr[mid] && arr[e] == arr[mid])
            {
                int minx = arr[s];
                for(int i = s; i <= e; i++)
                    if(minx > arr[i]) minx = arr[i];
                return minx;
            }
            if(arr[mid] >= arr[s])
                s = mid;
            else if(arr[mid] <= arr[e]) 
                e = mid;
        }
        return arr[mid];
    }
};


面试题12:矩阵中的路径

请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则之后不能再次进入这个格子。 例如 a b c e s f c s a d e e 这样的3 X 4 矩阵中包含一条字符串"bcced"的路径,但是矩阵中不包含"abcb"路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入该格子。

思路:dfs暴力搜即可。

代码:

class Solution {
public:
    bool hasPath(char* matrix, int rows, int cols, char* str)
    {
        int *p = new int[rows*cols];
        for(int i = 0; i < rows*cols; i++) p[i] = 0;
        int flag = 0;
        for(int i = 0; i < rows; i++)
            for(int j = 0; j < cols; j++)
                find(matrix, rows, cols, str, i, j, p, flag);
        return flag;
    }
    void find(char* matrix, int rows, int cols, char* str, int x, int y, int *p, int &flag)
    {
        if(*str == 0)
        {
            flag = 1;
            return;
        }
        if(x < 0 || y < 0 || x >= rows || y >= cols) return;
        if(flag || p[x*cols + y]) return;
        p[x*cols + y] = 1;
        int fx[4][2] = {0,1,1,0,-1,0,0,-1};
        if(matrix[x*cols + y] == *str)
        {
            for(int i = 0; i < 4; i++)
            {
                int tx = x + fx[i][0];
                int ty = y + fx[i][1];
                find(matrix, rows, cols, str+1, tx, ty, p, flag);
            }
        }
        p[x*cols + y] = 0;
    }
};

面试题13:机器人的运动范围

地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动,每一次只能向左,右,上,下四个方向移动一格,但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如,当k为18时,机器人能够进入方格(35,37),因为3+5+3+7 = 18。但是,它不能进入方格(35,38),因为3+5+3+8 = 19。请问该机器人能够达到多少个格子?

思路:dfs狂搜

代码:

class Solution {
public:
    int movingCount(int threshold, int rows, int cols)
    {
        int *p = new int[rows*cols];
        for(int i = 0; i < rows*cols; i++) p[i] = 0;
        return find(0, 0, threshold, rows, cols, p);
    }
    
    int find(int x, int y, int threshold, int rows, int cols, int *p)
    {
        if(x < 0 || y < 0 || x >= rows || y >= cols) return 0;
        if(p[x*cols+y] || get(x, y) > threshold) return 0;
        p[x*cols+y] = 1;
        return 1 + find(x+1, y, threshold, rows, cols, p)+find(x, y+1, threshold, rows, cols, p)+
            find(x-1, y, threshold, rows, cols, p)+find(x, y-1, threshold, rows, cols, p);
    }
    
    int get(int x, int y)
    {
        int sum = 0;
        while(x) 
        {
            sum += x%10;
            x/=10;
        }
        while(y) 
        {
            sum += y%10;
            y/=10;
        }
        return sum;
    }
};

面试题15:二进制中1的个数

输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。

思路:方法1,使用一个无符号的整数1,从右到左去&n,执行完一次后,向左移位(对于32位整数来说,需要执行32次)。方法2,使用n&(n-1),来求(执行次数为1的个数)。

代码一(普通解法):

int NumberOf1(int n)
{
    int count = 0;
    unsigned int flag = 1;
    while(flag)
    {
        if(n & flag) count++;
        flag = flag << 1;
    }
}

代码二(优秀解法):

class Solution {
public:
     int NumberOf1(int n) 
     {
         int sum = 0;
         while(n)
         {
             sum++;
             n = n & (n - 1);
         }
         return sum;
     }
};

面试题16:数值的整数次方

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

思路:方法1,直接求,注意任意数的0次方等于1,负数的次方等于它的倒数(时间复杂度O(n))。方法2,利用平方的性质,a^n=a^(n/2) * a^(n/2)或a^n=a^(n-1/2) * a^(n-1/2)*a(分别为偶数、奇数的情况)(时间复杂度O(logn))

代码一(直接求):

class Solution {
public:
    double Power(double base, int exponent) {
        double sum = 1;
        if(exponent > 0) 
            while(exponent--) sum *= base;
        else if(exponent < 0){
            exponent = -exponent;
            while(exponent--) sum *= base;
            sum = 1.0 / sum;
        }
        return sum;
    }
};

代码二(利用性质):

class Solution {
public:
    double Power(double base, int exponent) {
        if(exponent == 0) return 1;
        if(exponent == 1) return base;
        int n = exponent > 0 ? exponent : -exponent;
        double res = Power(base, n >> 1);
        res *= res;
        if(n & 1) res *= base;
        if(exponent < 0) res = 1 / res;
        return res;
    }
};

面试题17:打印从1到最大的n位数(牛课无该题)

输入数字n,按顺序打印出从1到最大的n位十进制数,比如输入3,则打印出1、2、3....999。

思路:由于n的大小不一定,所以可能long long也存不下。

    1、模拟法,利用字符串模拟加法操作

    2、全排列,利用递归处理

代码一(模拟):

bool increment(char *s, int n)
{
    s[0]++;
    int t = 0;
    while(s[t] > '9')
    {
        s[t] = '0';
        s[++t] ++;
    }
    if(t == n) return false;
    return true;
}
void print(char *s, int n)
{
    int i, j;
    for(i = n-1; s[i] == '0' && i >= 0; i--);
    for(j = i; j >= 0; j--)
        cout << s[j];
    cout << endl;
}
void printN(int n)
{
    char *s = new char[n+1];
    for(int i = 0; i < n; i++) s[i] = '0';
    s[n] = 0;
    while(increment(s, n))
    {
        print(s, n);
    }
}

代码二(全排列):

void find(char *s, int now, int n)
{
    if(now == n)
    {
        int i;
        for(i = 0; s[i] == '0' && i < n; i++);
        if(i != n) cout << s+i << endl;
        return;
    }
    for(char i = '0'; i <= '9'; i++)
    {
        s[now] = i;
        find(s, now+1, n);
    }
}
void get(int n)
{
    char *s = new char[n+1];
    s[n] = 0;
    find(s, 0, n);
}

面试题18:删除链表的结点

题目一:在O(1)的时间内删除链表结点(牛课无该题)

给定单向链表的头指针和一个节点指针,定义一个函数在O(1)时间内删除该节点。

思路:首先判断该节点p有没有next,如果有,直接p=p->next,相当于就删除了该节点。其次,在没有next的情况下,分两种情况,该节点是头结点(链表只有一个元素)或者该节点不是头结点。当该节点是头结点的时候,返回nullptr即可,不是的时候,从头往后遍历后删除。

代码:略

题目二:删除链表中重复的结点

在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为 1->2->5

思路:首先,由于头结点可能会被删掉,故创建了指向头结点的指针。其次,依次遍历链表,当p与p->next的值相同时,进入循环,删掉与p相同的所有结点。出循环后,删掉p即可。

代码:

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead)
    {
        if(pHead == nullptr || pHead->next == nullptr) return pHead;
        ListNode *myHead = new ListNode(-1); //头结点可能会被删除
        myHead->next = pHead;
        ListNode *pre = myHead;
        ListNode *node = pHead;
        ListNode *next = nullptr;
        while(node != nullptr && node->next != nullptr)
        {
            next = node->next;
            if(node->val != next->val)
            {
                pre = node;
                node = node->next;
            }
            else
            {
                while(next != nullptr && next->val == node->val)
                {
                    ListNode *del = next;
                    next = next->next;
                    delete del;
                }
                delete node;
                node = nullptr;
                pre->next = next;
                node = next;
            }
        }
        return myHead->next;
    }
};

面试题19:正则表达式匹配

请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符,而'*'表示它前面的字符可以出现任意次(包含0次)。 在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串"aaa"与模式"a.a"和"ab*ac*a"匹配,但是与"aa.a"和"ab*a"均不匹配

思路:由于*号比较难处理,先考虑*号的情况。

    当*(pattern+1) == '*'的时候,由于可以匹配0次,故要么匹配,要么不匹配。如果不匹配的话,直接返回str,pattern+2,如果匹配,则一直匹配(str+1,pattern)或者只匹配这一次(str+1,pattern+2)即可

    其他情况,正常来就行,当*str==*pattern就放行,或者为点的时候,但是点不能匹配空,所以要求点必须要匹配一个字符。

代码:

class Solution {
public:
    bool match(char* str, char* pattern)
    {
        if(str == nullptr || pattern == nullptr) return false;
        if(*str == '\0' && *pattern == '\0') return true;
        if(*str != '\0' && *pattern == '\0') return false;
        if(*(pattern+1) == '*')
        {
            if(*str == *pattern || *pattern == '.' && *str != '\0')
                //1 不处理,匹配0次          2 匹配当前后继续匹配        3 匹配当前后不继续匹配
                return match(str, pattern+2) || match(str+1, pattern) || match(str+1, pattern+2);
            else 
                return match(str, pattern+2);
        }
        if(*str == *pattern || *pattern == '.' && *str != '\0')
            return match(str+1, pattern+1);
        return false;
    }
};

面试题20:表示数值的字符串

请实现一个函数用来判断字符串是否表示数值(包括整数和小数)。例如,字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。

思路:首先可以推出格式(+-)(num1)(.num2)([Ee](+-)(num3)),其中num123均为1-9的数字串。当Ee存在时,后面的数字才能存在。

    1、使用正则表达式处理

    2、一步一步按格式处理

代码一(正则):

#include <regex>
class Solution {
public:
    bool isNumeric(char* str)
    {
        regex pattern("[\\+\\-]?\\d*(\\.\\d+)?([eE][\\+\\-]?\\d+)?");
        return regex_match(str, pattern);
    }
};

代码二(模拟):

class Solution {
public:
    bool isNumeric(char* str)
    {
        if(str == nullptr) return false;
        // (+-)(num1)(.num2)[Ee](+-)(num3)
        // 1 最开始的符号位
        if(*str == '+' || *str == '-') str++;
        // 2 num1
        while(*str != '\0')
        {
            if(*str < '0' || *str > '9') break;
            str++;
        }
        // 3 .num2
        if(*str == '.')
        {
            str++;
            // 类似12.是符合要求的
            while(*str != '\0')
            {
                if(*str < '0' || *str > '9') break;
                str++;
            }
        }
        // 4 Ee
        if(*str == 'E' || *str == 'e')
        {
            str++;
            // 类似12e不符合要求
            if(*str == '\0') return false;
            if(*str == '+' || *str == '-') str++;
            while(*str != '\0')
            {
                if(*str < '0' || *str > '9') break;
                str++;
            }
        }
        return *str == '\0';
        
    }
};

面试题21:调整数组顺序使奇数位于偶数前面

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

思路:1、利用冒泡排序的性质,如果前面数为偶数,后面数为奇数,则交换

    2、新开数组直接模拟,或者用插入排序等方法(略)

代码(冒泡性质):

class Solution {
public:
    void reOrderArray(vector<int> &array) {
        int length = array.size(), t;
        for(int i = 0; i < length-1; i++)
        {
            for(int j = 0; j < length-1-i; j++)
            {
                if(array[j]%2==0 && array[j+1]%2 == 1)
                {
                    t = array[j]; array[j] = array[j+1]; array[j+1] = t;
                }
            }
        }
    }
};

面试题22:链表中倒数第k个结点

输入一个链表,输出该链表中倒数第k个结点。

思路:方法1,遍历两次,第一次计算总长度,第二次找length-k+1个即可。(略)

    方法2,遍历一次,用两个指针,第一个指针指向第i个,第二个指针指向i+k-1个即可,当第二个指针指向最后一个时,第一个指针指向的是倒数第k个。注意考虑空指针,k为0的情况(k为无符号,无符号-1很大的)

代码:

/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        if(pListHead == nullptr || k == 0) return nullptr;
        ListNode *p1 = pListHead, *p2 = pListHead;
        for(int i = 0; i < k-1; i++)//无符号0-1=4294967295(0xFFFFFFFF)
        {
            if(p1->next != nullptr) p1 = p1->next;
            else return nullptr;
        }
        while(p1->next != nullptr)
        {
            p1 = p1->next;
            p2 = p2->next;
        }
        return p2;
    }
};

面试题23:链表中环的入口结点

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

思路:一开始,想了一个比较简单的方法,没有考虑复杂度等一些东西。就是利用map或者set,记录次数,当发现第二次入map或者set插入失败,则该结点是环。

方法二是书上的思路:

    首先,选取两个指针p1,p2,p1一次走1步,p2一次走两2步,如果两个指针碰面了,则说明有环(可以画图模拟一下,只要有环一定会碰面)。

    其次,确定有环后,需要找到入口结点。假设环的长度为n,此时p1先走n步,接着p1,p2同时向前一次一步走,他们碰面的点编为入口点。

    最后,需要求环的长度,在第一步p1==p2碰面时,p1不动,p2一步一步走,当p2在碰到p1时,即可知道长度。

代码一(时间空间复杂度有问题):

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        map<ListNode*, int> M;
        while(pHead != nullptr)
        {
            M[pHead]++;
            if(M[pHead] == 2) return pHead;
            pHead = pHead->next;
        }
        return nullptr;
    }
};

代码二:

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        if(pHead == nullptr) return nullptr;
        // 第一步 求是否有环
        bool flag = false;
        ListNode *p1 = pHead->next;
        if(p1 == nullptr) return nullptr;
        ListNode *p2 = p1->next;
        while(p1 != nullptr && p2 != nullptr)
        {
            if(p1 == p2) 
            {
                flag = true;
                break;
            }
            p1 = p1->next;
            if(p2->next == nullptr) return nullptr;
            p2 = p2->next->next;
        }
        // 第二步 找环的长度
        if(flag)
        {
            int count = 1;
            while(p1->next != p2)
            {
                count++;
                p1 = p1->next;
            }
            // 第三步 找入口
            p1 = pHead;
            p2 = pHead;
            for(int i = 0; i < count; i++) p2 = p2->next;
            while(p1 != p2)
            {
                p1 = p1->next;
                p2 = p2->next;
            }
            return p1;
        }
        return nullptr;
    }
};

面试题24:反转链表

输入一个链表,反转链表后,输出新链表的表头。

思路:遍历时,新链表newhead指向当前遍历结点,newhead->next指向上一个遍历的结点。为了防止断链,需要加临时变量存储当前的next。

代码:

/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        // ans为结果,pr记录前一个
        ListNode *ans = nullptr, *pNode = pHead, *pr = nullptr;
        while(pNode != nullptr)
        {
            ListNode *pt = pNode->next;
            ans = pNode;
            ans->next = pr;
            pr = pNode;
            pNode = pt;
        }
        return ans;
    }
};

面试题25:合并两个排序的链表

输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。

思路:利用递归思想写,代码会比较简洁

代码一(递归):

/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        if(pHead1 == nullptr) return pHead2;
        if(pHead2 == nullptr) return pHead1;
        ListNode *ans = nullptr;
        if(pHead1->val <= pHead2->val)
        {
            ans = pHead1;
            ans->next = Merge(pHead1->next, pHead2);
        }
        else
        {
            ans = pHead2;
            ans->next = Merge(pHead1, pHead2->next);
        }
        return ans;
    }
};

代码二(非递归):

/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        if(pHead1 == nullptr) return pHead2;
        if(pHead2 == nullptr) return pHead1;
        ListNode *ans = nullptr, *pNode = nullptr;
        while(pHead1 != nullptr && pHead2 != nullptr)
        {
            if(pHead1->val <= pHead2->val)
            {
                if(ans == nullptr) ans = pNode = pHead1;
                else{
                    pNode->next = pHead1;
                    pNode = pNode->next;
                }
                pHead1 = pHead1->next;
            }
            else
            {
                if(ans == nullptr) ans = pNode = pHead2;
                else{
                    pNode->next = pHead2;
                    pNode = pNode->next;
                }
                pHead2 = pHead2->next;
            }
        }
        if(pHead1 != nullptr) pNode->next = pHead1;
        if(pHead2 != nullptr) pNode->next = pHead2;
        return ans;
    }
};

面试题39:数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。

思路:

1、利用快排的性质,每次确定一个数,使其左边小于该数,右边大于该数。然后根据题意只,一个数如果出现次数大于一半,那么中位数肯定是这个数。故当partition的时候,当返回的是划分位置在中间时,即可判断。判断通过扫描一遍数组实现。(时间复杂度为O(n),分析比较麻烦)

2、根据数组特点。由于一个数字的出现次数超过一半,那么他出现的次数比其他所有数字出现的次数的和还要多。因此可以考虑遍历数组的时候保存2个值;一是数组中的一个数字,另一个是次数。当遍历到下一个数字的时候,如果下一个数字与我们之前保存的数字相同,则次数+1,否则-1。当次数为0时,该次遍历的数字为记录的数字,次数为1。由于该数组的性质,可以肯定最后一次把次数设为1的数字就是我们要找的数字。当然,最后需要循环确认一下。(时间复杂度O(n))

代码一:

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) 
    {
        int mid = numbers.size()/2;
        int start = 0, end = numbers.size()-1;
        int p = partition(numbers, start, end);
        while(p != mid)
        {
            if(p > mid) end = p-1;
            else start = p+1;
            p = partition(numbers, start, end);
        }
        // 如果存在,则中位数必然是该数,故此时统计一下数量是否大于即可(当5数,0 1 2 2 3中,2虽然是中位数,但是没有超过一半)
        int res = numbers[mid], count = 0;
        for(int i = 0; i < numbers.size(); i++)
            if(numbers[i] == res) count++;
        if(count > mid) return res;
        return 0;
    }
    
    int partition(vector<int> a, int l, int r)
    {
        int i = l, j = r, x = a[l];
        while(i < j)
        {
            while(i < j && a[j] >= x) j--;
            if(i < j) a[i] = a[j];
            while(i < j && a[i] <= x) i++;
            if(i < j) a[j] = a[i];
        }
        a[i] = x;
        return i;
    }
};

代码二:

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) 
    {
        if(numbers.size() == 0) return 0;
        int res = numbers[0], cs = 1;
        for(int i = 1; i < numbers.size(); i++)
        {
            if(cs == 0)
            {
                cs++;
                res = numbers[i];
            }
            else if(numbers[i] == res)
                cs++;
            else cs--;
        }
        int count = 0;
        for(int i = 0; i < numbers.size(); i++)
            if(numbers[i] == res) count++;
        if(count > numbers.size()/2) return res;
        return 0;
    }
};


你可能感兴趣的文章

评论区

发表评论

必填

选填

选填

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

您好,欢迎到访网站!
  查看权限

«   2019年1月   »
123456
78910111213
14151617181920
21222324252627
28293031

最新留言