Leet Code Weekly Contest 265
1. Smallest Index With Equal Value
linear scan.
class Solution
{
public:
int smallestEqual(vector<int>& nums)
{
for (int i = 0; i < nums.size(); i++)
{
if (nums[i] == i % 10)
{
return i;
}
}
return -1;
}
};2. Find the Minimum and Maximum Number of Nodes Between Critical Points
linear scan.
class Solution
{
public:
vector<int> nodesBetweenCriticalPoints(ListNode* head)
{
vector<int> nums;
while (head != NULL)
{
nums.push_back(head->val);
head = head->next;
}
vector<int> indexes;
for (int i = 1; i < nums.size() - 1; i++)
{
if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1])
{
indexes.push_back(i);
}
else if (nums[i] < nums[i - 1] && nums[i] < nums[i + 1])
{
indexes.push_back(i);
}
}
int min_dis = INT_MAX, max_dis = INT_MIN;
for (int i = 0; i + 1 < indexes.size(); i++)
{
min_dis = min(min_dis, indexes[i + 1] - indexes[i]);
max_dis = max(max_dis, indexes[i + 1] - indexes[0]);
}
if (min_dis == INT_MAX)
{
min_dis = -1;
}
if (max_dis == INT_MIN)
{
max_dis = -1;
}
return vector<int>({ min_dis, max_dis });
}
};3. Minimum Operations to Convert Number
The problem can be seen as a shortest-path problem with at most 1001 nodes.Thus we can do a simple BFS. The time complexity is .
class Solution
{
public:
int minimumOperations(vector<int>& nums, int start, int goal)
{
int dist[10001];
for (int i = 0; i <= 1000; i++)
{
dist[i] = INT_MAX;
}
dist[start] = 0;
queue<int> q;
q.push(start);
while (!q.empty())
{
int x = q.front(); q.pop();
for (auto y : nums)
{
vector<int> targets = vector<int>({ x + y, x - y, x ^ y });
for (auto t : targets)
{
if (t == goal)
{
return dist[x] + 1;
}
if (t >= 0 && t <= 1000)
{
if (dist[t] == INT_MAX)
{
dist[t] = dist[x] + 1;
q.push(t);
}
}
}
}
}
if (goal >= 0 && goal <= 1000 && dist[goal] != INT_MAX)
{
return dist[goal];
}
return -1;
}
};4. Check if an Original String Exists Given Two Encoded Strings
Given a string , we can describe a state indicating we first match any chars and then match the rest of string from position . So with two strings and , we can have define a DFS process .
The DFS process is literally easy but consisted of so many differenet cases:
- Both and are at a completed state: true
- One of the states is completed but another not: false
- Both are matching any chars (): cut the first chars.
- One of them are matching any chars ():
- Another string is matching a letter: cut the first one and continue.
- Another string is matching a digit: enumerate all possible lengths.
- None of them are matching any chars ():
- Both are matching letters ( and are letters): try to match and and continue.
- One of them are matching a digit: enumerate all possible lengths.
class Solution
{
public:
inline bool is_end(string &s, int p, int c)
{
return p == s.length() && c == 0;
}
inline bool is_digit(char c)
{
return c >= '0' && c <= '9';
}
inline bool is_letter(char c)
{
return c >= 'a' && c <= 'z';
}
map<pair<pair<int, int>, pair<int, int>>, bool> f;
inline bool dfs(string &s1, string &s2, int p1, int p2, int c1, int c2)
{
pair<pair<int, int>, pair<int, int>> key =
make_pair(make_pair(p1, p2), make_pair(c1, c2));
if (f.find(key) != f.end())
{
return f[key];
}
bool e1 = is_end(s1, p1, c1);
bool e2 = is_end(s2, p2, c2);
if (e1 && e2)
{
return f[key] = true;
}
if (e1 != e2)
{
return f[key] = false;
}
if (c1 > 0 && c2 > 0)
{
return f[key] = dfs(s1, s2, p1, p2, c1 - min(c1, c2), c2 - min(c1, c2));
}
if (c1 > 0)
{
// Here, c2 must be 0 and thus p2 < s2.length
if (is_letter(s2[p2]))
{
return f[key] = dfs(s1, s2, p1, p2 + 1, c1 - 1, 0);
}
else
{
int num = 0;
for (int i = 0; p2 + i < s2.length(); i++)
{
if (!is_digit(s2[p2 + i]))
{
break;
}
num = num * 10 + s2[p2 + i] - '0';
if (dfs(s1, s2, p1, p2 + i + 1, c1, num))
{
return f[key] = true;
}
}
return f[key] = false;
}
}
if (c2 > 0)
{
// Here, c1 must be 0 and thus p1 < s1.length
if (is_letter(s1[p1]))
{
return f[key] = dfs(s1, s2, p1 + 1, p2, 0, c2 - 1);
}
else
{
int num = 0;
for (int i = 0; p1 + i < s1.length(); i++)
{
if (!is_digit(s1[p1 + i]))
{
break;
}
num = num * 10 + s1[p1 + i] - '0';
if (dfs(s1, s2, p1 + i + 1, p2, num, c2))
{
return f[key] = true;
}
}
return f[key] = false;
}
}
// Here, both c1 and c2 must be 0s
if (is_letter(s1[p1]) && is_letter(s2[p2]))
{
return f[key] = (s1[p1] == s2[p2] && dfs(s1, s2, p1 + 1, p2 + 1, 0, 0));
}
if (is_digit(s1[p1]))
{
int num = 0;
for (int i = 0; p1 + i < s1.length(); i++)
{
if (!is_digit(s1[p1 + i]))
{
break;
}
num = num * 10 + s1[p1 + i] - '0';
if (dfs(s1, s2, p1 + i + 1, p2, num, 0))
{
return f[key] = true;
}
}
return f[key] = false;
}
if (is_digit(s2[p2]))
{
int num = 0;
for (int i = 0; p2 + i < s2.length(); i++)
{
if (!is_digit(s2[p2 + i]))
{
break;
}
num = num * 10 + s2[p2 + i] - '0';
if (dfs(s1, s2, p1, p2 + i + 1, 0, num))
{
return f[key] = true;
}
}
return f[key] = false;
}
// Ideally, we should never go here
throw invalid_argument("Sth went wrong");
}
bool possiblyEquals(string s1, string s2)
{
return dfs(s1, s2, 0, 0, 0, 0);
}
};