0%

Posted on Edited on In

题目

原题在此

解析

用stack记录出现过的括号, 遇到左括号就入栈括号的位置; 遇到右括号时, 若栈不为空则可构成合法括号, 出栈一个元素; 否则将当前位值标注为待删除. 最后将栈内剩余元素(没有右括号可以匹配的左括号)全部标记待删除. 最后调用string::erase()方法或其他语言的类似方法一次全部删除.

代码

c++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    string minRemoveToMakeValid(string s) {
        stack<int> stk;
        int n = s.size();
        for(int i = 0; i < n; ++i) {
            if(s[i] == '(') stk.push(i);
            if(s[i] == ')') {
                if(stk.empty()) s[i] = '!';
                else stk.pop();
            }
        }
        
        while(!stk.empty()) {
            s[stk.top()] = '!';
            stk.pop();
        }
        
        s.erase(std::remove(s.begin(), s.end(), '!'), s.end());
        return s;
    }
};

Posted on Edited on In

题目

原题在此

解析

  1. 3个能构成1个Slices, 4个能构成1+2个, 5个能构成1+2+3个
  2. 每次比较三个就行, count每次比较成功就+1, 失败就归零.

代码

c++

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& A) {
		int n = A.size(), cnt = 0, res = 0;
		for(int i = 2; i < n; ++i){
			if(A[i] - A[i - 1] == A[i - 1] - A[i - 2]) res += ++cnt;
			else cnt = 0;
		}
		return res;
	}
};

Posted on Edited on In

题目

原题在此

解析

从最宽的开始, 如果比它窄的箱子想装更多水, 就一定要比它高.

代码

c++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxArea(vector<int>& height) {
        int water = 0;
        int i = 0, j = height.size() - 1;
        while (i < j) {
            int h = min(height[i], height[j]);
            water = max(water, (j - i) * h);
            while (height[i] <= h && i < j) i++;
            while (height[j] <= h && i < j) j--;
        }
        return water;
    }
};

Posted on Edited on In

题目

原题在此

解析

  1. letter ^= 32可以切换大小写.
  2. 递归的回溯法可以遍历所以组合.

代码

c++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<string> letterCasePermutation(string S) {
        vector<string> wjl;
        permutation(wjl, S, 0);
        return wjl;
    }
    
private:
    void permutation(vector<string>& wjl, string s, int index) {
        wjl.push_back(s);
        if(index >= s.size()) return;
        
        for(int i = index; i < s.size(); i++) {
            if (isalpha(s[i])) {
                s[i] ^= 32;
                permutation(wjl, s, i + 1);
                s[i] ^= 32;
            }
        }
    }
};

Posted on Edited on In

题目

原题在此

解析

将power 和 index 组成 pair 放入set(set会自己排好序), 然后返回k个index就好.

代码

c++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
        vector<int> res;
        set<pair<int, int>> st;
        for(int i = 0; i < mat.size(); ++i) {
            int o = lower_bound(mat[i].begin(), mat[i].end(), 0, greater<int>()) - mat[i].begin();
            st.insert({o, i});
        }
        
        for(auto it = st.begin(); k > 0; --k) {
            res.push_back(it -> second);
            ++it;
        }
        return res;
    }
};

Posted on Edited on In

题目

原题在此

解析

用dfs解题TLE了, 查了一下并查集的解法, 通过了. 链接在此

代码

c++/dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<int> colors(n, 0);
        for (int i = 0; i < n; ++i)
            if(!colors[i] && !dfs(colors, graph, i, 1)) return false;
                
        return true;
    }
    
    bool dfs(vector<int> colors, vector<vector<int>>& graph, int node, int color) {
        if(colors[node]) return colors[node] == color;
        colors[node] = color;
        for (auto nei : graph[node])
            if (!dfs(colors, graph, nei, -color)) return false;
        
        return true;
    }
};

c++/disjointSet

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
class DisjointSet {
private:
    vector<int> parent;
    vector<int> rank;
    
public:
    DisjointSet(int n) {
        parent = vector<int>(n);
        for(int i = 0; i < n; ++i) parent[i] = i;
        rank = vector<int>(n, 1);
    }
    
    int find(int p) {
        int t = p;
        while(t != parent[t]) t = parent[t];
        parent[p] = t;
        return t;
    }
    
    void unionSet(int a, int b) {
        int sa = find(a), sb = find(b);
        if(sa == sb) return;
        if(rank[sa] < rank[sb]) swap(sa, sb);
        rank[sa] += rank[sb];
        parent[sb] = sa;
    }
};

class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        if(!n) return false;
        DisjointSet ds(n);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < graph[i].size(); ++j) {
                if (ds.find(i) == ds.find(graph[i][j])) return false;
                if (j) ds.unionSet(graph[i][j], graph[i][j - 1]);
            }
        } 
        return true;
    }
};

Posted on Edited on In

题目

原题在此

In an N by N square grid, each cell is either empty (0) or blocked (1).

A clear path from top-left to bottom-right has length k if and only if it is composed of cells C_1, C_2, ..., C_k such that:

  • Adjacent cells C_i and C_{i+1} are connected 8-directionally (ie., they are different and share an edge or corner)
  • C_1 is at location (0, 0) (ie. has value grid[0][0])
  • C_k is at location (N-1, N-1) (ie. has value grid[N-1][N-1])
  • If C_i is located at (r, c), then grid[r][c] is empty (ie. grid[r][c] == 0).
    Return the length of the shortest such clear path from top-left to bottom-right. If such a path does not exist, return -1.

Example 1:
Input: [[0,1],[1,0]]
Output: 2

Example 2:
Input: [[0,0,0],[1,1,0],[1,1,0]]
Output: 4

Note:

  • 1 <= grid.length == grid[0].length <= 100
  • grid[r][c] is 0 or 1

解析

典型的BFS算法, 用queue维护待搜索节点, 搜索过的节点要标注以避免死循环.

代码

c++

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
class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        if(grid.empty() || grid[0][0]) return -1;
        queue<pair<int, int>> q;
        q.push({0,0});
        grid[0][0] = 1;
        int len = 1, n = grid.size();
        vector<int> dir{1,0,-1,0,1,1,-1,-1,1};
        while(!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                auto [x, y] = q.front();
                q.pop();
                if(x == n - 1 && y == n - 1) return len;
                for(int j = 0; j < 8; ) {
                    int row = x + dir[j];
                    int col = y + dir[++j];
                    if(row >= 0 && row < n && col >= 0 && col < n && !grid[row][col]) {
                        q.push({row, col});
                        grid[row][col] = 1;
                    }
                }
            }
            len++;
        }
        return -1;
    }
};

Posted on Edited on In

题目

原题在此

Given a non-negative integer num, return the number of steps to reduce it to zero. If the current number is even, you have to divide it by 2, otherwise, you have to subtract 1 from it.

Example 1:

Input: num = 14
Output: 6

Explanation:
Step 1) 14 is even; divide by 2 and obtain 7.
Step 2) 7 is odd; subtract 1 and obtain 6.
Step 3) 6 is even; divide by 2 and obtain 3.
Step 4) 3 is odd; subtract 1 and obtain 2.
Step 5) 2 is even; divide by 2 and obtain 1.
Step 6) 1 is odd; subtract 1 and obtain 0.

Example 2:
Input: num = 8
Output: 4

Explanation:
Step 1) 8 is even; divide by 2 and obtain 4.
Step 2) 4 is even; divide by 2 and obtain 2.
Step 3) 2 is even; divide by 2 and obtain 1.
Step 4) 1 is odd; subtract 1 and obtain 0.

Example 3:
Input: num = 123
Output: 12

Constraints:
0 <= num <= $10^6$

解析

遍历bits, leading zeros 不算, 其余位是1就加2, 是0就加1.

代码

c++

1

Posted on Edited on In

题目

原题在此

Given two strings s and t , write a function to determine if t is an anagram of s.

Example 1:
Input: s = "anagram", t = "nagaram"
Output: true

Example 2:
Input: s = "rat", t = "car"
Output: false

Note:
You may assume the string contains only lowercase alphabets.

Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case?

解析

统计每个字符的出现次数加入set, 然后比较两set是否相等. 因为输入只包含小写字母, 可用int[26]代替.
py可以直接调用Counter.

代码

py

1
2
3
4
5
6
7
8
class Solution(object):
    def isAnagram(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        return Counter(s) == Counter(t)

c++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.length() != t.length()) return false;
        int n = s.length();
        int counts[26] = {0};
        for (int i = 0; i < n; i++) { 
            counts[s[i] - 'a']++;
            counts[t[i] - 'a']--;
        }
        for (int i = 0; i < 26; i++)
            if (counts[i]) return false;
        return true;
    }
};

Posted on Edited on In

题目

原题在此

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

For example, if there are two nodes X and Y in the original list, where X.random --> Y, then for the corresponding two nodes x and y in the copied list, x.random --> y.

Return the head of the copied linked list.

The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

  • val: an integer representing Node.val
  • random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.

Your code will only be given the head of the original linked list.

Example 1:

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:

Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

Example 3:

Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

Example 4:
Input: head = []
Output: []
Explanation: The given linked list is empty (null pointer), so return null.

Constraints:

  • 0 <= n <= 1000
  • -10000 <= Node.val <= 10000
  • Node.random is null or is pointing to some node in the linked list.

解析