I always wondered about how to parse and execute complex numeric expressions, even though i did that my programming language agaram , i did that in a very different way ( using recursion ). So the problem statement here wants us to implement a program which parses the numeric expression. The expression consists of integers and operators ('+', '-', '*', '/') separated by some number of spaces and they guarantee that the expression would be valid.
LC trick to parse number from a list of characters
Lets say you have a string "leet23code" and you want to parse the characters as number 23, and you are not allowed to typecast after collecting the complete number "23" as string.
Its not really a trick but its just a nice way to build the number from string.
The obvious way to do this is by multiplying the position of digit in number and adding it, for example 23 can be represented as
(2 * 10 ^ 1 ) + (3 * 10 ^ 0)
we would need to keep track of the power of 10 to build the number
something like
power = 0
my_number = 0
for c in s:
if c.isnumeric():
my_number += int(c) + 10 * power
power += 1
This is nice and easy to understand, but there is even a better trick than this
def parse_number(self, s):
my_number = 0
for c in s:
if c.isnumeric():
my_number = my_number * 10 + int(c)
return my_number
This reduces the need for keeping track of power, because we knew power is incremented every time.
Swim in rising water - Dijsktra optimization
Problem statement:
You are given an n x n integer matrix grid where each value grid[i][j] represents the elevation at that point (i, j).
The rain starts to fall. At time t, the depth of the water everywhere is t.
You can swim from a square to another 4-directionally adjacent square
if and only if the elevation of both squares individually are at most t. You can swim infinite distances in zero time. Of course, you must stay within the boundaries of the grid during your swim.
Return the least time until you can reach the bottom right square (n - 1, n - 1) if you start at the top left square (0, 0).
Network Delay Time - Djikstra Algorithm
Problem Statement:
You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target.
We will send a signal from a given node k. Return the minimum time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.
Valid sudoku
I have never played sudoku before even though i like analyzing chess games and love to play chess, i couldnt convince myself that sudoku is interesting for one valid reason, to solve it you need to bruteforce :-) That means no logic or strategy involved. Anyway the leetcode problem i decided to solve is about validating sudoku, i already solved this before with the help of youtube video, now i am going to try to solve it by myself
Next greater element
I came across an interesting problem today, give a list of numbers n1 to n10, we need to return an array which will have the next greater element for each number
for example, for input N = [...some numbers..] with length L
we need to return
A = [a1....some numbers..] with length same as N
where A[i] can be zero if there are no greater elements after N[i], if there is a greater element we need to get the first instance of greater element and put it in answer array A
The simple solution requires bruteforcing, that is for every element i, we need to iterate through input array in range [i+1, L], this takes O(n ^ 2) time.
Leetcode grind, new mile stone
I hit the 200 mark :-)
at this point i am feeling quite confident with graph and backtracking concepts, but lacking in 2D dp problems. Moving forward i am planning to complete neetcode 150, then switch to Grokking the coding interview patterns, the target is 500 :-)
I would also need to get rid of this mental block where i ignore the bruteforce solutions without even trying to apply them, i lost 2 questions in the contest due to that :facepalm: