发表更新LeetCode / 算法12 分钟读完 (大约1774个字)

LeetCode-16

934. 最短的桥

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
53
54
55
56
class Solution {
public:

    int indexMap[105][105] = {0}; //岛屿点，对应一个岛
    int n;
    int edgex[105*105] = {0};
    int edgey[105*105] = {0};
    int edgei[105*105] = {0};
    int edgej[105*105] = {0};
    int edgecount = 0;
    int edgeicount = 0;
    int shortestBridge(vector<vector<int>>& grid) {
        n = grid.size();
        int islandCount = 0;
        int p1x,p1y;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == 1 && indexMap[i][j] == 0) {
                    ++islandCount;
                    dfs(grid, i, j, islandCount);
                }
            }
        }
        int min=INT_MAX;
        for(int i = 0; i < edgecount; i++) {
            for(int j = 0; j < edgeicount; j++) {
                int path = abs(edgex[i]-edgei[j]) + abs(edgey[i] - edgej[j]) - 1;
                if(min >= path) {
                    min = path;
                }
            }
        }
        return min;
    }
    void dfs(vector<vector<int>>& grid, int x, int y, int index) {
        if(x < 0 || y < 0 || x >= n || y >= n) return;
        if(indexMap[x][y] != 0 || grid[x][y] != 1) return;
        indexMap[x][y] = index;
        bool flag = (y-1 >= 0 && grid[x][y-1] == 0) || (y+1 < n && grid[x][y+1] == 0) || (x+1 < n && grid[x+1][y] == 0) || (x-1 >= 0 && grid[x-1][y] == 0);
        dfs(grid, x, y-1, index);
        dfs(grid, x, y+1, index);
        dfs(grid, x+1, y, index);
        dfs(grid, x-1, y, index);
        if(flag) {
            if(indexMap[x][y]==1) {
                edgex[edgecount]=x;
                edgey[edgecount]=y;
                edgecount++;
            } else if(indexMap[x][y]==2) {
                edgei[edgeicount]=x;
                edgej[edgeicount]=y;
                edgeicount++;
            }
        }
    }
};

和之前写的一道题有点像，827. 最大人工岛
827. 最大人工岛我先dfs找到所有连通子图和包围岛的0点，然后找这些点中有无同时包围多个岛的，把他们的面积加起来取最大值

这道题也可以使用相同的方法，找到每个岛屿的边界点，然后计算边界点的距离(只有两个岛，两个岛之间肯定是可以连通的，且不管使用那条途径，最短距离一定是 $ abs(x_1 - x_2) + abs(y_1-y_2)-1 $)

看答案

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
class Solution {
public:
    void dfs(int x, int y, vector<vector<int>>& grid, queue<pair<int, int>> &qu) {
        if (x < 0 || y < 0 || x >= grid.size() || y >= grid[0].size() || grid[x][y] != 1) {
            return;
        }
        qu.emplace(x, y);
        grid[x][y] = -1;
        dfs(x - 1, y, grid, qu);
        dfs(x + 1, y, grid, qu);
        dfs(x, y - 1, grid, qu);
        dfs(x, y + 1, grid, qu);
    }

    int shortestBridge(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<vector<int>> dirs = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    queue<pair<int, int>> qu;
                    dfs(i, j, grid, qu);
                    int step = 0;
                    while (!qu.empty()) {
                        int sz = qu.size();
                        for (int i = 0; i < sz; i++) {
                            auto [x, y] = qu.front();
                            qu.pop();
                            for (int k = 0; k < 4; k++) {
                                int nx = x + dirs[k][0];
                                int ny = y + dirs[k][1];
                                if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
                                    if (grid[nx][ny] == 0) {
                                        qu.emplace(nx, ny);
                                        grid[nx][ny] = -1;
                                    } else if (grid[nx][ny] == 1) {
                                        return step;
                                    }
                                }
                            }
                        }
                        step++;
                    }
                }
            }
        }
        return 0;
    }
};
阅读更多
发表更新LeetCode / 算法11 分钟读完 (大约1618个字)

LeetCode-14

927. 三等分

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
53
54
class Solution {
public:
    vector<int> threeEqualParts(vector<int>& arr) {
        int sum = countOne(arr);
        int len = arr.size();
        if(sum % 3 != 0) {
            return {-1,-1};
        }
        if(sum == 0) {
            return {0, len -1};
        }

        int p1,p2,p3;
        p1 = p2 = p3 = 0;
        int i = 0;
        int cur = 0;
        while(i < len) {
            if(arr[i] == 1) {
                if(cur == 0) {
                    p1 = i;
                } else if(cur == sum/3) {
                    p2 = i;
                } else if(cur == 2*sum/3) {
                    p3 = i;
                }
                cur++;
            }
            i++;
        } //把1平均分成3份，p1 p2 p3分别找到三段的第一个1的位置
        // printf("%d %d %d\n", p1, p2, p3);
        int x = p1,y = p2,z = p3;
        int farclen = len - p3;
        if(p1 + farclen > p2 || p2 + farclen > p3) {
            return {-1, -1};
        }
        while(x < p2 && y < p3 && z < len) {
            if(arr[x] != arr[y] || arr[y] != arr[z]) {
                return {-1, -1};
            }
            x++;y++;z++;
        }
        // printf("%d %d %d\n", x, y, z);
        return {p1+farclen-1, p2+farclen};
    }
    int
     countOne(vector<int>& arr) {
        int count = 0;
        for(int a : arr) {
            count += a;
        }
        return count;
    }
};

难，看懂解析思路后才写出来的

刚开始的思路是找0，把1分成了n段，取n/3 , 2n/3和 n段后面的0，然后向右移动双指针比较

后来发现有超级长的输入，超时了

解析的思路与我刚好相反，先数1的个数，如果是0或者不能被3整除，说明不能分成三段

1的个数为n，找到第0 n/3 2n/3个1，记为p1, p2, p3

p3到后末尾的长度就是三个子串的长度，如果p1 或 p2 + 字串长度分别大于p2 p3，说明无解

然后向后比较，若后面的数完全相同则有解

阅读更多
发表更新LeetCode / 算法17 分钟读完 (大约2568个字)

LeetCode-13

1640. 能否连接形成数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    bool canFormArray(vector<int>& arr, vector<vector<int>>& pieces) {
        int arr_map[105] = {0};
        int len_arr = arr.size();
        for(int i = 0; i < len_arr; i++) {
            arr_map[arr[i]] = i+1;
        }
        int pie_len = pieces.size();
        for(int i = 0; i < pie_len; i++) {
            int i_len = pieces[i].size();
            int diff = arr_map[pieces[i][0]];
            if(diff == 0) {
                return false;
            }
            for(int j = 1; j < i_len; j++) {
                if(diff != arr_map[pieces[i][j]] - j) {
                    return false;
                }
            }
        }
        return true;
    }
};

4ms，和最快的思路刚好相反，用map存储arr的index，最快的思路是反过来，用map存一个piece的第一个index

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    bool canFormArray(vector<int>& arr, vector<vector<int>>& pieces) {
        int arr_map[105] = {0};
        int len_arr = arr.size();
        int pie_len = pieces.size();
        for(int i = 0; i < pie_len; i++) {
            arr_map[pieces[i][0]] = i+1;
        }
        int i = 0;
        while(i < len_arr) {
            int row = arr_map[arr[i]];
            if(row == 0) return false;
            vector<int>& subv = pieces[row-1];
            int i_len = subv.size();
            for(int j = 0; j < i_len; j++, i++) {
                if(arr[i] != subv[j]) {
                    return false;
                }
            }
        }
        return true;
    }
};

707. 设计链表

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
struct List {
    List *next;
    int val;
    List(int val0, List* next0 = nullptr):val(val0), next(next0) {}
};

class MyLinkedList {
private:
    List *root;
    List *tail;
    int size;
    inline List* getNode(int& index) {
        List *move = root;
        while(index > 0 && move->next != nullptr) {
            move = move->next;
            index--;
        }
        return move;
    }
public:
    MyLinkedList() {
        root = new List(0);
        tail = root;
        size = 0;
    }
    
    int get(int index) {
        List *move = getNode(index);
        return (move->next == nullptr) ? -1 : move->next->val;
    }
    
    void addAtHead(int val) {
        List* node = new List(val, root->next);
        root->next = node;
        if(root == tail) {
            tail = node;
        }
        size++;
    }
    
    void addAtTail(int val) {
        List* node = new List(val, tail->next);
        tail->next = node;
        tail = node;
        size++;
    }
    
    void addAtIndex(int index, int val) {
        List *move = getNode(index);
        if(index > 0) {
            return;
        }
        List* node = new List(val, move->next);
        move->next = node;
        if(move == tail) {
            tail = node;
        }
        size++;
    }
    
    void deleteAtIndex(int index) {
        List *move = getNode(index);
        List *target = move->next;
        if(target != nullptr)  {
            move->next = target->next;
            if(target == tail) {
                tail = move;
            }
            delete target;
            size--;
        }
    }
};
阅读更多
发表更新LeetCode / 算法29 分钟读完 (大约4309个字)

LeetCode-15

904. 水果成篮

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
class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int len = fruits.size();
        vector<int> v(len);
        int i = 0;
        int cur = fruits[i];
        i++;
        int max_diff = 1;
        int typea = fruits[0], typeb = -1, typec = -1;
        vector<int> last(len+1);
        int curr = 0;
        int j = 1;
        while(j < len) {
            while(j < len && fruits[j] == fruits[curr]) {
                j++;
            }
            last[j] = curr;
            curr = j;
            j++;
        }
        while(i < len) {
            int diff = 1;
            typeb = typec = -1;
            while(i < len) {
                if(fruits[i] != typea && fruits[i] != typeb) {
                    if(typeb == -1) {
                        typeb = fruits[i];
                    } else if(typec == -1) {
                        typec = fruits[i];
                    }
                }
                if(typec == -1) {
                    diff++;
                } else {
                    break;
                }
                i++;
            }
            max_diff = diff > max_diff ? diff : max_diff;
            if(i-1 >= 0 && i < len){
                typea = fruits[i-1];
                i = last[i]+1;
            }
        }
        return max_diff;
    }
};

想法很简单，就是从左往右遍历，数当前遇到了几种水果，当遇到第三种水果后，更新一下装入水果的最大值，三种水果记录为typea, typeb, typec
然后回溯，找到前一个节点在左侧最后一个typea后第一次出现的位置（其实也是typea最后出现的位置的后两个位置）

优化(空间，放弃last数组)

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
class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int len = fruits.size();
        vector<int> v(len);
        int i = 0;
        int cur = fruits[i];
        i++;
        int max_diff = 1;
        int typea = fruits[0], typeb = -1, typec = -1;
        while(i < len) {
            int diff = 1;
            typeb = typec = -1;
            int lasta = i-1, lastb = 0;
            while(i < len) {
                if(fruits[i] != typea && fruits[i] != typeb) {
                    if(typeb == -1) {
                        typeb = fruits[i];
                    } else if(typec == -1) {
                        typec = fruits[i];
                    }
                }
                if(fruits[i] == typea) {
                    lasta = i;
                } else if(fruits[i] == typeb) {
                    lastb = i;
                }
                if(typec == -1) {
                    diff++;
                } else {
                    break;
                }
                i++;
            }
            max_diff = diff > max_diff ? diff : max_diff;
            if(i-1 >= 0 && i < len){
                if(fruits[i-1] == typea) {
                    i = lastb + 2;
                } else if(fruits[i-1] == typeb) {
                    typea = typeb;
                    i = lasta + 2;
                }
                // printf("%d, %d, %d\n", i, lasta, lastb);
            }
        }
        return max_diff;
    }
};

1441. 用栈操作构建数组

阅读更多
发表更新LeetCode / 算法11 分钟读完 (大约1600个字)

LeetCode-10

2020-07-25

Z 字形变换

AC代码

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
class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows <= 1) {
            return s;
        }
        int n = s.size();
        string temp[numRows];
        int t_numRows = 0;
        int p = 0;
        while(p < n) {
            while(p < n && t_numRows < numRows) {
                temp[t_numRows] += s[p];
                p++;
                t_numRows++;
            }
            t_numRows = numRows -2;
            while (p < n && t_numRows > 0) {
                temp[t_numRows] += s[p];
                p++;
                t_numRows--;
            }
        }
        string res;
        for(int i = 0 ; i < numRows; i++) {
            res = res + temp[i];
        }
        return res;
    }
};

优化思路

  1. 两层while循环多次判断p<n,效率底下，实际上只需要当t_numRows==0或t_numRows==numRows-1时改变方向即可

  2. 实际上需要的string数组长度是min(n, numRows)

    优化代码

    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:
     string convert(string s, int numRows) {
         if (numRows <= 1) {
             return s;
         }
         int n = int(s.size());
         int len = min(numRows, n);
         vector<string> temp(len);
         int t_numRows = 0;
         bool goingDown = false;
         for(int i = 0; i < n; i++) {
             temp[t_numRows] += s[i];
             if (t_numRows == 0 || t_numRows == numRows-1) {
                 goingDown = !goingDown;
             }
             t_numRows += goingDown ? 1 :-1;
         }
         string res;
         for (int i = 0; i < len; i++) res += temp[i];
         return res;
     }
    };

    再次优化

    可以直接找新旧数列的数字关系，直接计算

    优化代码

    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
    class Solution {
    public:
     string convert(string s, int numRows) {
         if (numRows <= 1) {
             return s;
         }
         int len_s = int(s.size());
         int unit =(2*numRows-2);
         int n = len_s/unit;
         int remain = len_s%unit;
         string res(len_s, 0);
         for (int i = 0; i < len_s; i++) {
             int p = 0;
             if (i%unit == 0) {
                 p = i/unit+1;
             } else {
                 int r = i%unit + 1,c = i/unit+1;
                 if (r > numRows) {
                     r = unit-r+2;
                     p = 1;
                 } else if (r == numRows) {
                     p = 1-c;
                 }
                 p += n + (n*2)*(r-2) + 2*(c-1) + min(r-1, remain)+1;
                 if (remain > numRows) {
                     p += max(r-(unit-remain+2),0);
                 }
             }
             res[p-1] = s[i];
         }
         return res;
     }
    };

    最终成绩

    执行用时：8 ms, 在所有 C++ 提交中击败了98.89%的用户

    内存消耗：7.7 MB, 在所有 C++ 提交中击败了100.00%的用户

阅读更多
发表更新LeetCode / 算法9 分钟读完 (大约1344个字)

LeetCode-11

2020-07-27

55. 跳跃游戏

思路

  1. 对nums数组，令nums[i] += i,这样表示i位置最远可以走到的距离

  2. 算法

    从i = 0开始
    对于当前i，可以从0走到nums[i]，选取0-nums[i]的最大值，如果最大值大于等于n-1，则可以到达最后，若小于，重复这个步骤，除非i=最大值，则不能到达最后

  3. 为了降低时间复杂度，创建一个数组v，v[i] = max(nums[k]), k = 0,1,…,i

AC代码

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
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = int(nums.size());
        for(int i = 0; i < n; i++) {
            nums[i] += i;
        }
        vector<int> v;
        int max = nums[0];
        for(int i = 0; i < n; i++) {
            if (nums[i] > max) {
                max = nums[i];
            }
            v.push_back(max);
        }
        int i = 0;
        while (i != v[i]) {
            i = v[i];
            if (i >= n-1) {
                return true;
            }
        }
        return false || n == 1;
    }
};
阅读更多
发表更新LeetCode / 算法13 分钟读完 (大约1995个字)

LeetCode-1

1.两数之和

AC代码

思路

  • 刚开始就是用双层for循环写，然后秉承着谦虚的态度看了题解，发现真的有O(N)的算法一遍哈希表。

  • 主要就是利用map建立从数到数组下标的map，然后每次计算出target-nums[i]的值，然后看map里面有对应的下标，有的话就输出，没有就继续。

  • map的值为0时，如何区分stl的map知识有限，如何判断0是数组里面没有这个数还是查询的引索为0呢？只要储存的时候下标+1，用的时候减一就行了，这样map值为0，一定是没有这个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ans;
        map<int, int> m;
        for (int i = 0; i < nums.size(); i++) {
            int pos = target - nums[i];
            if (m[pos] != 0 && m[pos] != i + 1) {
                pos = m[pos] - 1;
                ans.push_back(pos > i ? i : pos);
                ans.push_back(pos < i ? i : pos);
                break;
            }
            m[nums[i]] = i + 1;
        }
        return ans;
    }
};

2. 两数相加

阅读更多
发表更新LeetCode / 算法9 分钟读完 (大约1381个字)

LeetCode-2

20. 有效的括号

思路

  1. 创建一个栈
  2. 遍历字符串
    1. 如果是左半部分，把这个字符压栈
    2. 如果是右半部分，先看一下栈顶元素和它是否配对，如果配对，弹栈，不配对，结束，返回false
  3. 字符串遍历结束后，看栈是否已经空了，如果没空，说明左右括号数量不对应false

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
static const auto __ = []() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	return nullptr;
}();
class Solution {
public:
    bool isValid(string s) {
        int p[128] = {0};
        p['('] = ')'; p[')'] = 0;
        p['['] = ']'; p[']'] = 0;
        p['{'] = '}'; p['}'] = 0;
        stack<char> sta;
        for (int i = 0; i < s.length(); i++) {
            if (p[s[i]]) {
                sta.push(s[i]);
            } else {
                if (sta.empty() || p[sta.top()] != s[i]) return false;
                sta.pop();
            }
        }
        return sta.empty();
    }
};

26. 删除排序数组中的重复项

阅读更多
发表更新LeetCode / 算法15 分钟读完 (大约2270个字)

LeetCode-3

58. 最后一个单词的长度

AC代码

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int lengthOfLastWord(string s) {
        reverse(s.begin(), s.end());
        stringstream ss(s);
        string buf;
        ss >> buf;
        reverse(buf.begin(), buf.end());
        return buf.length();
    }
};
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int lengthOfLastWord(string s) {
        int count = 0;
        for (int i = s.length() -1 ; i >= 0; i--) {
            if (s[i] != ' ')count++;
            else if (count > 0) break;
        }
        return count;
    }
};

66. 加一

思路

阅读更多
发表更新LeetCode / 算法23 分钟读完 (大约3490个字)

LeetCode-4

172. 阶乘后的零

思路

把2，5的倍数拆成2，5，数5的个数（2一定比5多），这样5一定和2配对，所以5的个数就是末尾0的个数

AC代码

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int trailingZeroes(int n) {
        int ans = 0;
        while (n) {
            n /= 5;
            ans += n;
        }
        return ans;
    }
};
1
2
3
4
5
6
class Solution {
public:
    int trailingZeroes(int n) {
        return n == 0 ? 0 : n/5 + trailingZeroes(n / 5);
    }
};
阅读更多
关注我

链接

分类

最新文章

归档

标签

6.8242
Android1
Android FrameWork1
Android 高级开发瓶颈突破系列课11
Android-官方文档1
Android-官方源码6
Android面试查漏补缺2
C/C++1
Flutter1
Java基础 字节码2
Kotlin-Android21
Kotlin-Android 实习25
LeetCode45
LeetCode 1013
LeetCode周赛1
Linux/UNIX系统编程手册38
OI KIWI2
OS4
PAT-(Advanced-Level)-Practice2
PAT-(Basic-Level)-Practice44
blockchain1
fedfab13
gallery1
geth1
git1
gradle1
hexo2
linux2
misc1
projects1
shell2
刷题2
动态规划1
多线程1
排序1
数据库2
牛客2
算法43
×