https://leetcode.com/contest/weekly-contest-314/problems/the-employee-that-worked-on-the-longest-task/
For a problem #1, this one took me longer than expected – about a full ten minutes. I was trying to do things quickly and golf-y, but eventually had to cut my time losses and implement it a more straightforward way.
We assume the task 0 is best, then process each of the other logs calculating
the duration spent on that task as dur. If dur is longer than our currently
known longest duration, we replace our “best so far” and continue. If dur is
equal, we also want to replace our “best so far” if the employee id is lower
(this is specified in the problem statement.)
from typing import List
class Solution:
def hardestWorker(self, n: int, logs: List[List[int]]) -> int:
mx = logs[0][1]
mxidx = logs[0][0]
for idx in range(1, len(logs)):
dur = logs[idx][1] - logs[idx-1][1]
if dur > mx or (dur == mx and logs[idx][0] < mxidx):
mx = dur
mxidx = logs[idx][0]
return mxidx
https://leetcode.com/contest/weekly-contest-314/problems/find-the-original-array-of-prefix-xor/
This problem look daunting at first, but it’s rather simple once you see the trick.
The value at index idx in output pref is the xor of everything arr[0:idx]
so get the original value of arr[idx] we can do arr[0:idx] ^ arr[0:(idx-1)]
(where arr[a:b] is the xor of everything in that slice.) The second value is
pref[idx-1].
from typing import List
class Solution:
def findArray(self, pref: List[int]) -> List[int]:
return [pref[0]] + [ pref[idx-1] ^ pref[idx] for idx in range(1, len(pref))]
https://leetcode.com/contest/weekly-contest-314/problems/using-a-robot-to-print-the-lexicographically-smallest-string/
I found this problem to be more difficult than problem #4, so skipped it and came back to it after completing #4. It took me 9 submissions to get the answer correct, but did not get any TLE.
My original thinking was:
s. That needs to be emitted first, so grab everything
in s up to that char and emit that substring reversedWe can do this efficiently by sweeping backwards through s, adding an index to
a stack/list/deque when the char at current index is less than (or equal to! but
I didn’t realize this until a later submission failed) the previous item added
to the stack/list/deque. Then we process the items off the deque backwards, to
process the smallest item first, then the next smallest thing that was after
that one, etc.
This works for the sample cases, but after submitting found test cases where it
does not work. For these, we have to consider using the buffer t to store
particularly high characters and not emitting them until the right time while
processing later chunks.
This can be done with the while t... loop while we process the chunks. It’s a
bit messy so I won’t elaborate, and I’m not fully convinced it’s sound but it
passed all the cases and was accepted.
from collections import deque
class Solution:
def robotWithString(self, s: str) -> str:
t = ''
r = ''
nextchoice = deque([])
nextchoice.append(len(s)-1)
idx = len(s)-2
while idx >= 0:
if s[idx] <= s[nextchoice[-1]]:
nextchoice.append(idx)
idx -= 1
# print(nextchoice)
prv = 0
for idx in reversed(nextchoice):
while t and t[0] <= s[idx]:
r += t[0]
t = t[1:]
# print(s, r, t)
t = s[prv:idx][::-1] + t
r += s[idx]
prv = idx + 1
return r + t
https://leetcode.com/contest/weekly-contest-314/problems/paths-in-matrix-whose-sum-is-divisible-by-k/
Reading this question, I recalled a similar problem from an ICPC contest at CSUS asking to count the number of paths going right/down with obstacles on certain tiles.
The solution for that one was to set the # of ways on the target position to 1, and then bubble out from there with bottom-up dynamic programming to “push” the “way” out by adding down/right cell values to current cell value until we’ve processed everywhere. Then, we can just look at the source cell knowing it represents all the ways.
This problem requires a similar approach, but I decided that each tile needs k
values – tile t has array of size k where the value with index v on that
array represents the number of ways possible to get from t to that target with
a path that has value v (done modulus k.)
I used java for the convenient allocation of a 3-dimensional array.
class Solution {
private static final int MOD = 1_000_000_000 + 7;
public int numberOfPaths(int[][] grid, int k) {
int rows = grid.length;
int cols = grid[0].length;
int[][][] dp= new int[grid.length][grid[0].length][k];
dp[rows-1][cols-1][grid[rows-1][cols-1] % k] = 1;
for (int r = rows-1; r >= 0; r -= 1) {
for (int c = cols-1; c >= 0; c -= 1) {
int val = grid[r][c];
// If we're not at the bottom, add the values for tile below us
if (r < rows-1) {
for (int nxtval = 0; nxtval < k; nxtval += 1) {
int newval = (val + nxtval) % k;
dp[r][c][newval] += dp[r+1][c][nxtval];
dp[r][c][newval] %= MOD;
}
}
// If we're not at the right, add the values for tile to right of us
if (c < cols-1) {
for (int nxtval = 0; nxtval < k; nxtval += 1) {
int newval = (val + nxtval) % k;
dp[r][c][newval] += dp[r][c+1][nxtval];
dp[r][c][newval] %= MOD;
}
}
}
}
return dp[0][0][0];
}
}