Problem Description#

Given two integers $n$ and $m$, output an $n$-row, $m$-column matrix filled with the numbers $1$ through $n \times m$ in a spiral pattern.

See the sample for the exact matrix format.

Input Format#

The input consists of one line containing two integers, $n$ and $m$.

Output Format#

Output the required matrix.

The matrix occupies $n$ lines, each containing $m$ space-separated integers.

Data Range#

$1 \le n,m \le 100$

Solution#

1
#include <iostream>
2
#include <cstring>
3
#include <algorithm>
4
using namespace std;
5
const int N = 110;
6
int n,m,a[N][N];
7
int main(){
8
    cin>>n>>m;
9
    int l = 0,r = m-1, t = 0,d = n-1,cnt=1;
10
    while(l<=r || t <= d){
11
        for(int i=l;i<=r && t<=d;i++) a[t][i] = cnt++;t++;
12
        for(int i=t;i<=d && l<=r;i++) a[i][r] = cnt++;r--;
13
        for(int i=r;i>=l && t<=d;i--) a[d][i] = cnt++;d--;
14
        for(int i=d;i>=t && l<=r;i--) a[i][l] = cnt++;l++;
15
    }
16
    for(int i=0;i<n;i++)
17
        for(int j=0;j<m;j++)
18
            cout<<a[i][j]<<" \\n"[j==m-1];
19

20
    return 0;
21
}

1
#include <iostream>
2
#include <cstring>
3
#include <algorithm>
4
using namespace std;
5
const int N = 110;
6
int n,m,a[N][N],dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
7
int main(){
8
    cin>>n>>m;int x=0,y=0;
9
    for(int i=1,u=0;i<=n*m;i++){
10
        a[x][y] = i;
11
        x += dx[u];y += dy[u];
12
        if(a[x][y] || x<0 || y<0 || x>=n || y>=m)
13
            x-=dx[u],y-=dy[u],u = (u+1)%4,
14
            x += dx[u],y += dy[u];
15
    }
16

17
    for(int i=0;i<n;i++) for(int j=0;j<m;j++)
18
        cout<<a[i][j]<<" \\n"[j==m-1];
19
    return 0;
20
}

Problem Description#

Given a singly linked list, sort it using the quicksort algorithm.

Requirements: the expected average time complexity is $O(nlogn)$, and the expected auxiliary space complexity is $O(logn)$.

Question: What should you do if you may only change the structure of the linked list and cannot modify the val value of each node?

Data Range#

All values in the linked list are within the $int$ range, and the linked-list length is within $[0, 10000]$.

The test data for this problem is generated completely at random.

Solution#

The idea is essentially the same as ordinary quicksort. Partition the linked list into three sections based on a val: values less than val, equal to val, and greater than val. Recursively quicksort the first and last sections, then concatenate the three sorted sections in order.

1
/**
2
 * Definition for singly-linked list.
3
 * struct ListNode {
4
 *     int val;
5
 *     ListNode *next;
6
 *     ListNode(int x) : val(x), next(NULL) {}
7
 * };
8
 */
9
class Solution {
10
public:
11
    ListNode* quickSortList(ListNode* head) {
12
        if(!head || !head->next) return head;
13

14
        auto left = new ListNode(-1),mid=new ListNode(-1),right=new ListNode(-1),
15
            ltail = left,mtail = mid,rtail = right;
16
        int val = head->val;
17

18
        for(auto p=head;p;p = p->next){
19
            if(p->val < val) ltail = ltail->next = p;
20
            else if(p->val == val) mtail = mtail->next = p;
21
            else rtail = rtail->next = p;
22
        }
23

24
        ltail->next = mtail->next = rtail->next = NULL;
25
        left->next = quickSortList(left->next);
26
        right->next = quickSortList(right->next);
27

28
        get_tail(left)->next = mid->next;
29
        get_tail(left)->next = right->next;
30

31
        auto p = left->next;
32
        delete left;delete mid;delete right;
33
        return p;
34
    }
35

36
    ListNode* get_tail(ListNode* head) {
37
        while (head->next) head = head->next;
38
        return head;
39
    }
40
};

Solution#

When a slope exists, following it toward the higher values will lead to an answer.

1
class Solution {
2
public:
3
    int findPeakElement(vector<int>& nums) {
4
        int l=0,r = nums.size()-1;
5
        while(l<r){
6
            int mid = (l+r) >> 1;
7
            long long lm = mid-1,rm = mid+1;
8
            if(lm<0) lm = INT_MIN-1ll;
9
            else lm = nums[lm];
10
            if(rm>=nums.size()) rm = INT_MIN-1ll;
11
            else rm = nums[rm];
12
            long long key = nums[mid];
13
            if(key>lm && key>rm)
14
                return mid;
15
            else if(key>lm &&rm>key)
16
                l = mid+1;
17
            else
18
                r = mid-1;
19
        }return l;
20
    }
21
};

Problem Description#

Given an $n \times n$ matrix containing $n \times n$ distinct integers.

A local minimum is defined as a number whose value is smaller than those of all its adjacent numbers.

The adjacent numbers of a number are those immediately above, below, to the left, and to the right of it. Note that a number on a boundary or in a corner may have fewer than four adjacent numbers.

Find the position of any local minimum within a time complexity of $O(nlogn)$, and output its row and column.

The matrix is hidden in this problem. You can obtain the value at a particular position in the matrix through the predefined $int$ function $query$.

For example, $query(a,b)$ returns the value at row $a$ and column $b$ of the matrix.

Notes:

1. Matrix rows and columns are both indexed from $0$.
2. The number of calls to the query() function must not exceed $(n + 2) \times \lceil log_2n \rceil + n$.
3. The answer is not unique; output the position of any local minimum.

Data Range#

$1 \le n \le 300$. The integers in the matrix are within the int range.

Solution#

This problem is similar to the previous one. The query limit also provides a hint: we can traverse the $n$ values in each of $log_2n$ columns. Specifically:

Use binary search to locate a column containing a local minimum, then traverse that column to find the answer. The binary-search condition is determined by comparing the minimum value in a column with the values immediately to its left and right in the same row.

1
// Forward declaration of queryAPI.
2
// int query(int x, int y);
3
// return int means matrix[x][y].
4
class Solution {
5
public:
6
    vector<int> getMinimumValue(int n) {
7
        typedef long long ll;
8
        ll INF = 1e15;
9
        int l,r;l=0;r = n-1;
10

11
        while(l<r){
12
            int mid = l+r>>1;
13
            ll val = INF;
14
            int p=0;
15
            for(int i=0;i<n;i++){
16
                int t = query(i,mid);
17
                if(t < val)
18
                    val = t,p = i;
19
            }
20
            ll lt = mid ? query(p,mid-1):INF;
21
            ll rt = mid+1<n ? query(p,mid+1):INF;
22

23
            if(val<lt && val<rt)
24
                return {p,mid};
25
            if(lt<val)
26
                r = mid - 1;
27
            else
28
                l = mid + 1;
29
        }
30

31
        ll val = INF;int p=0;
32
        for(int i=0;i<n;i++){
33
            int t = query(i,r);
34
            if(t<val)
35
                val = t,p = i;
36
        }
37
        return {p,r};
38

39
    }
40
};

Input Format#

The input contains multiple test cases. Each test case occupies one line and contains two positive integers, $n$ and $m$, where $n$ is the height of the building and $m$ is the number of eggs you currently have. These eggs have the same hardness—that is, when dropped from the same height, either all of them break or none of them do—and $m$ is no greater than $n$.

You may assume that an egg with hardness $x$ will never break when dropped from a height less than or equal to $x$ regardless of how many times it is dropped. An unbroken egg may be reused. However, it will always break when dropped from any height greater than $x$.

For each test case, you may assume that the egg hardness is between $0$ and $n$. In other words, an egg is guaranteed to break when dropped from floor $n+1$.

Output Format#

For each test case, output an integer representing the number of egg drops required in the worst case when using the optimal strategy.

Data Range#

$1 \le n \le 100$,
$1 \le m \le 10$

Sample Explanation#

The optimal strategy is the strategy that minimizes the number of egg drops required in the worst case.

If there is only one egg, you can only begin dropping it from the first floor. In the worst case, the egg’s hardness is 100, so 100 drops are required. With any other strategy, you may be unable to determine the egg’s hardness. For example, if you first drop it from the second floor and it breaks, you cannot determine whether its hardness is 0 or 1. This means that, in the worst case, infinitely many drops would be required, so the answer for the first test case is 100.

Solution#

1
#include<iostream>
2
#include<algorithm>
3
#include<cstring>
4
using namespace std;
5
const int N =110,M=11;
6
int n,m,f[N][M];
7

8
int main(){
9
    while(cin>>n>>m){
10
        for(int i=1;i<=n;i++) f[i][1] = i;
11
        for(int i=1;i<=m;i++) f[1][i] = 1;
12

13
        for(int i=2;i<=n;i++)
14
            for(int j=2;j<=m;j++){
15
                f[i][j] = f[i][j-1];
16
                for(int k=1;k<=i;k++)
17
                    f[i][j] = min(f[i][j],max(f[k-1][j-1],f[i-k][j])+1);
18
            }
19
        cout<<f[n][m]<<endl;
20
    }return 0;
21
}

1
#include<iostream>
2
#include<algorithm>
3
#include<cstring>
4
using namespace std;
5
const int N =110,M=11;
6
int n,m,f[N][M];
7

8
int main(){
9
    while(cin>>n>>m){
10
        for(int i=1;i<=n;i++){
11
            for(int j=1;j<=m;j++)
12
                f[i][j] = f[i-1][j]+f[i-1][j-1]+1;
13

14
            if(f[i][m] >= n){
15
                cout<<i<<endl;
16
                break;
17
            }
18
        }
19
    }return 0;
20
}

Problem Description#

Design a stack that supports operations such as push, pop, and top, and can retrieve the minimum element in O(1) time.

• push(x)–Insert element x into the stack
• pop()–Remove the top element from the stack
• top()–Get the top element
• getMin()–Get the minimum element in the stack

Data Range#

The total number of operation commands is $[0,100]$.

Sample#

1
MStack minStack = new MStack();
2
minStack.push(-1);
3
minStack.push(3);
4
minStack.push(-4);
5
minStack.getM();   --> Returns -4.
6
minStack.pop();
7
minStack.top();      --> Returns 3.
8
minStack.getM();   --> Returns -1.

Solution#

1
class MinStack {
2
public:
3
    /** initialize your data structure here. */
4
    int len;
5
    int a[110],ck[110];
6

7
    MinStack() {
8
        len = a[0] = ck[0] = 0;
9
    }
10

11
    void push(int x) {
12
        a[len] = x;
13
        ck[len] = min(len?ck[len-1]:x,x);
14
        len++;
15
    }
16

17
    void pop() {
18
        len--;
19
    }
20

21
    int top() {
22
        return a[len-1];
23
    }
24

25
    int getMin() {
26
        return ck[len-1];
27
    }
28
};

1
class MinStack {
2
public:
3
    /** initialize your data structure here. */
4
    stack<int> a;
5
    stack<int> ck;
6

7
    MinStack() {
8

9
    }
10

11
    void push(int x) {
12
        a.push(x);
13
        if(ck.empty() || ck.top() >= x)
14
            ck.push(x);
15
    }
16

17
    void pop() {
18
        if(ck.top() == a.top())
19
            ck.pop();
20
        a.pop();
21
    }
22

23
    int top() {
24
        return a.top();
25
    }
26

27
    int getMin() {
28
        return ck.top();
29
    }
30
};

Problem Description#

Given a linked list, output the entry node of its cycle if it contains one.

If it does not contain a cycle, output null.

Data Range#

The range of node val values is $[1,1000]$.
All node val values are distinct.
The linked-list length is $[0,500]$.

Sample#

1
给定如上所示的链表：
2
[1, 2, 3, 4, 5, 6]
3
2
4
注意，这里的2表示编号是2的节点，节点编号从0开始。所以编号是2的节点就是val等于3的节点。
5
则输出环的入口节点3.

Solution#

Since all val values are distinct and their range is only 1000, use an array to record the node corresponding to each previously encountered val. When a recorded val is encountered again, a cycle has been found.

1
class Solution {
2
public:
3
    ListNode *entryNodeOfLoop(ListNode *head) {
4
        ListNode* ck[1010];
5

6
        for(auto p=head;p;p=p->next){
7
            int val = p->val;
8
            if(ck[val])
9
                return ck[val];
10
            ck[val] = p;
11
        }return NULL;
12
    }
13
};