Problem Description#

Input two integers $n$ and $m$, output an $n$ by $m$ matrix, filling numbers from $1$ to $n \times m$ in a spiral snake pattern.

The exact matrix form can be referenced from the sample.

Input format#

The input consists of a single line containing two integers $n$ and $m$.

Output format#

Output the required matrix.

The matrix has $n$ rows, each row containing $m$ integers separated by spaces.

Constraints#

$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: expected average time complexity is $O(n \log n)$ and expected additional space complexity is $O(\log n)$.

Thought question: If you can only change the structure of the list and cannot modify each node’s val, how would you do it?

Constraints#

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

The data for this problem is completely randomly generated.

Solution#

The approach is basically the same as ordinary quicksort: partition the list into three parts based on a value: less than the value, equal to the value, and greater than the value; recursively quicksort the front and back sections, and then concatenate the three parts 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#

One can observe that when there is a slope, following the direction of the higher point leads to the 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$ pairwise distinct integers.

Define a local minimum as a value that is smaller than all of its adjacent numbers. An adjacent number is one of the four directions (up, down, left, right). Numbers on the border or corner may have fewer than four neighbors.

You must find any local minimum in $O(n \log n)$ time and output its position as its row index and column index.

The matrix is hidden, and you can obtain values via the predefined function query. For example, query(a,b) returns the value at row a, column b.

Notes:

1. Rows and columns are 0-based.
2. The number of query() calls must not exceed $(n + 2) \times \lceil \log_2 n \rceil + n$.
3. The answer is not unique; output any one local minimum’s position.

Data Range#

$1 \le n \le 300$, matrix values fit in int.

Solution#

Similar to the previous problem, and the call limit gives a hint: we can scan n numbers across log2(n) columns. The approach is to binary search for the column containing a local minimum, then scan that column to obtain the answer, where the binary search condition compares the minimum value in a column with its left and right neighbors.

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 consists of multiple test cases, each on one line containing two positive integers $n$ and $m$, where $n$ is the height of the building and $m$ is the number of eggs you have. All eggs have the same hardness (i.e., they either all break or all do not break when dropped from the same height), and $m \le n$.

You may assume the hardness is between $0$ and $n$, i.e., dropping from the $(n+1)$-th floor will certainly break.

Output Format#

For each test case, output a single integer representing the minimum number of egg drops required in the worst case with the optimal strategy.

Data Range#

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

Sample Explanation#

An optimal strategy minimizes the number of drops in the worst case.

If you have only one egg, you can only start from the first floor; in the worst case, the hardness is 100, so you need 100 drops. If you use another strategy, you might not be able to determine the egg hardness (for example, if you drop on the second floor first and it breaks, you cannot determine whether the hardness is 0 or 1), i.e., in the worst case you would need infinitely many drops, 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 push, pop, top, and can retrieve the minimum element in O(1) time.

• push(x) – push element x onto the stack
• pop() – remove the top element
• top() – get the top element
• getMin() – get the minimum element in the stack

Constraints#

Total number of operations in [0,100].

Example#

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, if it contains a loop, output the entry node of the loop.

If there is no loop, output null.

Constraints#

Node val range is [1,1000]. Node values are all distinct. List length is in [0,500].

Sample#

1
Given the linked list as shown above:
2
[1, 2, 3, 4, 5, 6]
3
2
4
Note that 2 denotes the node with index 2, and node indices start at 0. So the node with index 2 has val equal to 3.
5
Then the entry node of the loop is the one with value 3.

Solution#

It turns out that with distinct values and a range up to 1000, you can use an array to record the first node seen for each value. When you visit a value that has already been recorded, you have found the loop.

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
};