Weekly Contest 167

Posted on | In , | |
Words count in article: 590 | Reading time ≈ 3

1290. Convert Binary Number in a Linked List to Integer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    int getDecimalValue(ListNode* head) {
        int ret = 0;
        ListNode* cur = head;
        while(cur != NULL){
            ret = ret * 2 + cur->val;
            cur = cur->next;
        }
        return ret;
    }
};

1291. Sequential Digits

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<int> sequentialDigits(int low, int high) {
        vector<int> ret;
        queue<int> q;
        for(int i=1; i<=9; i++)
            q.push(i);
        
        while(!q.empty()){
            int f = q.front();
            q.pop();
            
            if(f >= low && f <= high){
                ret.push_back(f);
            }
            if(f > high) break;
            if(f % 10 != 9){
                q.push(f*10 + f%10 + 1);
            }
        }
        return ret;
    }
};

1292. Maximum Side Length of a Square with Sum Less than or Equal to Threshold

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
class Solution {
public:
    int maxSideLength(vector<vector<int>>& mat, int target) {
        int max_len = 0;
        for(int i=0; i<mat.size(); i++){
            for(int j=0; j<mat[0].size(); j++){
                if(mat[i][j] > target) continue;
                int cur_sum = 0;
                int cur_len = 1;
                while(true){
                    cur_sum = 0;
                    if(i+cur_len > mat.size()) {cur_len--; break;}
                    if(j+cur_len > mat[0].size()) {cur_len--; break;}
                    for(int ii=i; ii<i+cur_len; ii++){
                        for(int jj=j; jj<j+cur_len; jj++){
                            cur_sum += mat[ii][jj]; 
                        }
                    }
                    //cout << i << " "  << j << " " << mat[i][j] << " " << cur_sum << endl;
                    if(cur_sum < target){
                        cur_len++;
                    }else if(cur_sum == target){
                        break;
                    }else{
                        cur_len--; break;
                    }
                }
                //cout << i << " "  << j << " " << cur_len << endl;
                max_len = max_len > cur_len ? max_len : cur_len;
            }
        }
        return max_len;
    }
};

1293. Shortest Path in a Grid with Obstacles Elimination

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
class Solution {
public:
    int dp[41][41][1601];
    bool vis[41][41];
    int f(vector<vector<int>>& grid, int i, int j, int k){
        int n = grid.size(), m = grid[0].size();
        if(k < 0) return 1e7;
        if(i == n-1 && j == m-1) return 0;
        if(i < 0 || i >= n || j < 0 || j >= m) return 1e7;
        if(dp[i][j][k] != -1) return dp[i][j][k];
        int ans = 1e7;
        if(vis[i][j]) return ans;
        vis[i][j] = 1;
        vector<int> dx = {0, 1, 0, -1};
        vector<int> dy = {1, 0, -1, 0};
        for(int l=0; l<4; l++){
            int x = i+dx[l];
            int y = j+dy[l];
            if(x >= 0 && x < n && y >= 0 && y < m){
                int nk = k;
                if(grid[x][y] == 1) nk--;
                if(nk >= 0) ans = min(ans, f(grid, x, y, nk)+1);
            }
        }
        vis[i][j] = 0;
        return dp[i][j][k] = ans;
    }
    int shortestPath(vector<vector<int>>& grid, int k) {
        memset(dp, -1, sizeof(dp));
        if(grid[0][0] == 1) k--;
        memset(vis, false, sizeof(vis));
        int ans = f(grid, 0, 0, k);
        if(ans >= 1e7) return -1;
        return ans;
    }
};
Donate? comment?