[LC43. 大数乘法]
string multiply(string num1, string num2) {
string res;
int n1 = num1.size(), n2 = num2.size();
int k = n1 + n2 - 2, carry = 0;
vector<int> v(n1 + n2, 0);
for (int i = 0; i < n1; ++i) {
for (int j = 0; j < n2; ++j) {
v[k - i - j] += (num1[i] - '0') * (num2[j] - '0');
}
}
for (int i = 0; i < n1 + n2; ++i) {
v[i] += carry;
carry = v[i] / 10;
v[i] %= 10;
}
int i = n1 + n2 - 1;
while (v[i] == 0) --i;
if (i < 0) return "0";
while (i >= 0) res.push_back(v[i--] + '0');
return res;
}
LC224. Basic Calculator
解题方案 stack
// 只有+，-，(), 非负数
int calc(string str) {
stack<int> s;
int res = 0, flag = 1;
for(int i = 0; i < str.size(); i++) {
int num = 0;
while(isdigit(str[i])) {
num = num * 10 + (str[i++] - '0');
}
res += flag * num;
switch(str[i]) {
case '+': flag = 1; break;
case '-': flag = -1; break;
case '(':
s.push(res); res = 0;
s.push(flag); flag = 1;
break;
case ')':
res *= s.top(); s.pop();
res += s.top(); s.pop();
break;
default: break;
}
}
return res;
}
LC68. Text Justification
解题方案 string
LC388. Longest Absolute File Path
解题方案 string
int lengthLongestPath(string input) {
int res = 0;
istringstream ss(input);
vector<int> m(100, 0); //assume 100 level
string line = "";
while (getline(ss, line)) {
int level = line.find_last_of('\t') + 1;
int len = line.substr(level).size();
if (line.find('.') != string::npos) {
res = max(res, m[level] + len);
} else {
m[level + 1] = m[level] + len + 1;
}
}
return res;
}
LC418. LeetCodeSentence Screen Fitting (lock)
解题方案 string
LC394. Decode String
s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".
解题方案 string
LC529. Minesweeper
Return the board when no more squares will be revealed.
追加问题是如何初始化扫雷地图。 BFS主要是用来扩展’B’用的
class Solution {
public:
vector<vector<char>> updateBoard(vector<vector<char>> &board, vector<int> &click) {
if (board.empty() || board[0].empty()) return {};
int m = board.size(), n = board[0].size();
queue<pair<int, int>> q;
q.emplace(click[0], click[1]);
while (!q.empty()) {
int row = q.front().first, col = q.front().second, cnt = 0; q.pop();
vector<pair<int, int>> neighbors;
if (board[row][col] == 'M') board[row][col] = 'X';
else if (board[row][col] == 'E') {
for (int i = -1; i < 2; i++) {
for (int j = -1; j < 2; j++) {
int x = row + i, y = col + j;
if (x < 0 || y < 0 || x >= m || y >= n) continue;
if (board[x][y] == 'M') ++cnt;
else neighbors.push_back({x, y});
}
}
if (cnt > 0) board[row][col] = cnt + '0';
else {
board[row][col] = 'B';
for (auto a : neighbors) {
q.push(a);
}
}
}
}
return board;
}
};
LC616. Add bold tag in string
给字符串S 和一个关键词集合，要求将每个关键词在 S 中的所有出现都加粗（通过在文本两边添加 和 这两个 HTML tag 的方式），输出 S 被加粗后的 HTML 文本。
If two such substrings overlap, you need to wrap them together by only one pair of closed bold tag. Also, if two substrings wrapped by bold tags are consecutive, you need to combine them.
Example 1:
Input: s = "abcxyz123", dict = ["abc","123"]
Output: "<b>abc</b>xyz<b>123</b>"
Example 2:
Input: s = "aaabbcc", dict = ["aaa","aab","bc"]
Output: "<b>aaabbc</b>c"
Note:
The given dict won't contain duplicates, and its length won't exceed 100.
All the strings in input have length in range [1, 1000].
Solution 1
Use a boolean array to mark if character at each position is bold or not. After that, things will become simple.
public class Solution {
public String addBoldTag(String s, String[] dict) {
boolean[] bold = new boolean[s.length()];
for (int i = 0, end = 0; i < s.length(); i++) {
for (String word : dict) {
if (s.startsWith(word, i)) {
end = Math.max(end, i + word.length());
}
}
bold[i] = end > i;
}
StringBuilder result = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
if (!bold[i]) {
result.append(s.charAt(i));
continue;
}
int j = i;
while (j < s.length() && bold[j]) j++;
result.append("<b>" + s.substring(i, j) + "</b>");
i = j - 1;
}
return result.toString();
}
}
LC734.Sentence Similarity (Lock)
单词相似不满足传递性 解题思路
Solution 1
class Solution {
public:
bool areSentencesSimilar(vector<string>& words1, vector<string>& words2, vector<pair<string, string>> pairs) {
if (words1.size() != words2.size()) return false;
map<string, set<string>> map;
for (pair<string, string> p : pairs)
map[p.first].insert(p.second);
for (int i = 0; i < words1.size(); i++)
if (words1[i] != words2[i] && !map[words1[i]].count(words2[i]) && !map[words2[i]].count(words1[i]))
return false;
return true;
}
};
written by alexander original link here
LC737. Sentence Similarity II (Lock)
解题思路 单词相似度满足传递性，老三样，BFS, DFS, Union Find
Given two sentences words1, words2 (each represented as an array of strings), and a list of similar word pairs pairs, determine if two sentences are similar.
For example, words1 = ["great", "acting", "skills"] and words2 = ["fine", "drama", "talent"] are similar, if the similar word pairs are pairs = [["great", "good"], ["fine", "good"], ["acting","drama"], ["skills","talent"]].
Note that the similarity relation is transitive. For example, if "great" and "good" are similar, and "fine" and "good" are similar, then "great" and "fine" are similar.
Similarity is also symmetric. For example, "great" and "fine" being similar is the same as "fine" and "great" being similar.
Also, a word is always similar with itself. For example, the sentences words1 = ["great"], words2 = ["great"], pairs = [] are similar, even though there are no specified similar word pairs.
Finally, sentences can only be similar if they have the same number of words. So a sentence like words1 = ["great"] can never be similar to words2 = ["doubleplus","good"].
Note:
The length of words1 and words2 will not exceed 1000.
The length of pairs will not exceed 2000.
The length of each pairs[i] will be 2.
The length of each words[i] and pairs[i][j] will be in the range [1, 20].
Solution 1 DFS Build the graph according to the similar word pairs. Each word is a graph node. For each word in words1, we do DFS search to see if the corresponding word is existing in words2. See the clean code below. Happy coding!
class Solution {
public boolean areSentencesSimilarTwo(String[] words1, String[] words2, String[][] pairs) {
if (words1.length != words2.length) {
return false;
}
//Build the graph;
Map<String, Set<String>> pairInfo = new HashMap<>();
for (String[] pair : pairs) {
if (!pairInfo.containsKey(pair[0])) {
pairInfo.put(pair[0], new HashSet<>());
}
if (!pairInfo.containsKey(pair[1])) {
pairInfo.put(pair[1], new HashSet<>());
}
pairInfo.get(pair[0]).add(pair[1]);
pairInfo.get(pair[1]).add(pair[0]);
}
for (int i = 0; i < words1.length; i++) {
if (words1[i].equals(words2[i])) continue;
if (!pairInfo.containsKey(words1[i])) return false;
if (!dfs(words1[i], words2[i], pairInfo, new HashSet<>())) return false; //Search the graph.
}
return true;
}
public boolean dfs(String source, String target, Map<String, Set<String>> pairInfo, Set<String> visited) {
if (pairInfo.get(source).contains(target)) return true;
visited.add(source);
for (String next : pairInfo.get(source)) {
if (!visited.contains(next) && dfs(next, target, pairInfo, visited)) {
return true;
}
}
return false;
}
}
Solution 2 Union Find
class Solution {
public:
bool areSentencesSimilarTwo(vector<string>& words1, vector<string>& words2, vector<pair<string, string>> pairs) {
if (words1.size() != words2.size()) return false;
unordered_map<string, string> m;
for (auto pair : pairs) {
string x = getRoot(pair.first, m), y = getRoot(pair.second, m);
if (x != y) m[x] = y;
}
for (int i = 0; i < words1.size(); ++i) {
if (getRoot(words1[i], m) != getRoot(words2[i], m)) return false;
}
return true;
}
string getRoot(string word, unordered_map<string, string>& m) {
if (!m.count(word)) m[word] = word;
return word == m[word] ? word : getRoot(m[word], m);
}
};
LC684.Redundant Connection
解题报表 Union Find, BFS, DFS
LC297.Serialize and Deserialize Binary Tree
- 采用前序遍历，头是根节点
- 采用前序+中序，重建二叉树
string serialize(TreeNode* root) {
if(!root) return "#";
return to_string(root->val) + " " +serialize(root->left) + " " + serialize(root->rigth);
}
// using istringstream to avoid substr
TreeNode* deserialize(string data) {
istringstream in(data);
return deserialize(in);
}
TreeNode* deserialize(istringstream &in) {
string val;
in >> val;
if (val == "#") return nullptr;
TreeNode *root = new TreeNode(stoi(val));
root->left = deserialize(in);
root->right = deserialize(in);
return root;
}