Task 1: Zero Matrix
If an element in an M x N matrix is 0, set its entire row and column to 0.
Example Output
Input:
[1, 0, 1]
[1, 1, 1]
Output:
[0, 0, 0]
[1, 0, 1]
Logic
Scan matrix to record row and column indices containing zero, then update target rows and columns.
Perl Solution
ch-1.pl
sub zero_matrix {
my ($matrix) = @_;
my (%rows, %cols);
for my $r (0 .. $#$matrix) {
for my $c (0 .. $#{$matrix->[$r]}) {
if ($matrix->[$r][$c] == 0) { $rows{$r} = $cols{$c} = 1; }
}
}
for my $r (keys %rows) { @{$matrix->[$r]} = (0) x @{$matrix->[$r]}; }
for my $c (keys %cols) { for my $r (0 .. $#$matrix) { $matrix->[$r][$c] = 0; } }
}
Python Solution
ch-1.py
def zero_matrix(matrix: List[List[int]]) -> None:
rows, cols = set(), set()
for r in range(len(matrix)):
for c in range(len(matrix[0])):
if matrix[r][c] == 0:
rows.add(r); cols.add(c)
for r in rows:
for c in range(len(matrix[0])): matrix[r][c] = 0
for c in cols:
for r in range(len(matrix)): matrix[r][c] = 0
Task 2: Reorder List
Reorder linked list L0 -> L1 -> ... -> Ln-1 -> Ln as L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 ...
Example Output
Input: 1 -> 2 -> 3 -> 4 -> 5
Output: 1 -> 5 -> 2 -> 4 -> 3
Logic
Find midpoint of linked list, reverse second half, and interleave nodes from first and second half.
Perl Solution
ch-2.pl
sub reorder_list {
my ($head) = @_;
my @nodes;
my $curr = $head;
while ($curr) { push @nodes, $curr; $curr = $curr->{next}; }
my ($i, $j) = (0, $#nodes);
while ($i < $j) {
$nodes[$i]->{next} = $nodes[$j];
$i++;
break if $i == $j;
$nodes[$j]->{next} = $nodes[$i];
$j--;
}
$nodes[$i]->{next} = undef;
}
Python Solution
ch-2.py
def reorder_list(head: Optional[ListNode]) -> None:
nodes = []
curr = head
while curr:
nodes.append(curr)
curr = curr.next
i, j = 0, len(nodes) - 1
while i < j:
nodes[i].next = nodes[j]
i += 1
if i == j: break
nodes[j].next = nodes[i]
j -= 1
if nodes: nodes[i].next = None