【牛客网刷题】（第四弹）多道中等难度题，早日拿offer，快来看看

🧸🧸🧸各位大佬大家好，我是猪皮兄弟🧸🧸🧸

废话不多说，直接来做题！！

一、📖旋转数组的最小数字

newcoder旋转数组的最小数字

这道题利用二分法就oj，控制left 和right需要移动的条件

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        if(rotateArray.size()==0)
            return 0;
        int left=0,right=rotateArray.size()-1;
        while(left<right)
        {
            int mid=left+(right-left)/2;
            if(rotateArray[mid]<rotateArray[right])
            {
                right=mid;
            }
            else if(rotateArray[mid]>rotateArray[right])
            {                
                left=mid+1;
            }
            else
            {
                right--;    
            }
        }
        return rotateArray[left];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

二、📖最小的k个数（中等）值得一做

nowcoder最小的 k个数
要求空间复杂度O(N)，时间复杂度O(NlogN)你会做吗，来看看这道题吧，我用的是堆排序+创建了一个临时数组，堆排序利用的是向下调整建堆，时间复杂度为O(N)

class Solution {
public:
    void AdjustDown(vector<int>& input,int parent)
    {
        int child=parent*2;
        while(child<=input.size()-1)
        {
            if(child+1<input.size()&&input[child]>input[child+1])
            {
                   child++;
            }
            if(input[child]<input[parent])
            {
                swap(input[child],input[parent]);
                parent=child;
                child=2*parent;
            }
            else
                break;
        }
    }
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> v;
        if(k==0)
            return v;
        for(int i=(input.size())/2;i>=0;i--)
        {
            AdjustDown(input,i);
        }
        for(int i=0;i<k;i++)
        {
            swap(input[0],input[input.size()-1]);
            v.push_back(input[input.size()-1]);
            input.pop_back();
            AdjustDown(input,0);
        }
        return v;
        
        
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

三、📖二叉树的下一个结点（中等）

nowcoder二叉树的下一个结点

class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* p) {
        //中序遍历
        //右子树存在，找最左边的那个点
        if(p->right)
        {
            p=p->right;//先找出结点，然后一直找左
            while(p->left) p=p->left;
            return p;
        }
        //右子树不存在，
        while(p->next)
        {
            //p不是根结点
            if(p==p->next->left)
                return p->next;
            p=p->next;
        }
        
        return nullptr;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

四、📖矩阵中的路径（中等）

nowcoder矩阵中的路径
矩阵中的路径一直都是比较难的问题，这里用到了dfs

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型vector> 
     * @param word string字符串 
     * @return bool布尔型
     */
    bool hasPath(vector<vector<char> >& matrix, string word) {
        // write code here
        if(matrix.size()==1&&matrix[0].size()==1)
            if(matrix[0][0]==word[0])
                return true;
            else
                return false;
        for(int i=0;i<matrix.size();i++)
        {
            for(int j=0;j<matrix[0].size();j++)
            {
                if(dfs(matrix,word,0,i,j))
                    return true;
            }
        }
        return false;
    }
    
    bool dfs(vector<vector<char>>&matrix,string word,int u,int x,int y)
    {
        
        int row=matrix.size();
        int col=matrix[0].size();
        if(word[u]=='\0')
            return true;
        int dx[4]={-1,0,1,0};
        int dy[4]={0,1,0,-1};
        for(int i=0;i<4;i++)
        {
            int a=x+dx[i],b=y+dy[i];
            if(a>=0&&a<row&&b>=0&&b<col&&matrix[a][b]==word[u])
            {
                char t =matrix[a][b];
                matrix[a][b]='*';
                if(dfs(matrix,word,u+1,a,b))
                    return true;
                matrix[a][b]=t;
            }
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

五、📖牛客oj总结

牛客网是个很不错的刷题软件，也希望大家能天天在上面刷刷题，大厂offer指日可待啊兄弟们。刷起来。