Mercurial > lbo > hg > juliaplay
view julia/arrays.jl @ 40:5e3662b65004 default tip
Land/water find peak problem
author | Lewin Bormann <lbo@spheniscida.de> |
---|---|
date | Mon, 03 Apr 2023 22:04:42 +0200 |
parents | af82fbc3d6c0 |
children |
line wrap: on
line source
function _longest_increasing_subsequence(v::Vector{Int})::Vector{Int} M = zeros(Int, length(v)) P = zeros(Int, length(v)) Longest = 0 for i = eachindex(v) e = v[i] # Find element in sequence so far that is smaller than current element e. lo, hi = 1, Longest+1 while lo < hi mid = round(Int, floor((lo+hi)/2)) if e < v[M[mid]] hi = mid else lo = mid+1 end end @assert lo == hi P[i] = lo > 1 ? M[lo-1] : -1 M[lo] = i if lo > Longest Longest = lo end end @show P, M # Reconstruct sequence ixs = zeros(Int, 0) i = M[Longest] while i > 0 push!(ixs, v[i]) i = P[i] end reverse!(ixs) ixs end function twosum1(a::Vector{Int}, n::Int)::Tuple{Int,Int} # n² complexity (trivial): for (i,e1) in enumerate(a) for (j,e2) in enumerate(a) if e1+e2 == n return (i,j) end end end return (0,0) end function twosum_linear(a::AbstractVector{T}, s)::Vector{Pair} where {T<:Integer} seen = Set{T}() p = Pair[] for e = a f = s - e if f in seen push!(p, e => f) end push!(seen, e) end p end function twosum2(a::Vector{Int}, n::Int)::Tuple{Int,Int} # More clever? # # 1. sort array; cut off all elements > n. Start from largest leftover number # and smallest one; look for a match: a_ = sort(a) maxix = 1 for (i, e) = enumerate(a_) if e < n maxix = i else break end end a_ = a_[begin:maxix] front, back = 1, length(a_) while front < back while a_[front]+a_[back] < n front += 1 end if a_[front]+a_[back] == n return (front, back) end back -= 1 end nothing end function threesum(a::AbstractVector{T}, s) where {T<:Integer} triples = Tuple[] for e = a f = s - e pairs = twosum_linear(a, f) append!(triples, ((e, p...) for p = pairs)) end triples end function nsum(a::AbstractVector{T}, s, n) where {T<:Integer} if n == 1 tuple.(filter(==(s), a)) elseif n == 2 twosum_linear(a, s) else tuples = Tuple[] for e = a f = s - e append!(tuples, ((e, p...) for p = nsum(a, f, n-1))) end tuples end end function watercontainer(a::Vector{Int}) maxvol = 0 best = (0,0) for lo = 1:length(a) for hi = length(a):-1:lo vol = (hi-lo) * min(a[lo], a[hi]) if vol > maxvol best = (lo, hi) maxvol = vol end end end best, maxvol end function rainwater(a::Vector{Int}) lm, rm = 0, 0 leftmax, rightmax = zeros(Int, length(a)), zeros(Int, length(a)) for (i,e) in enumerate(a) if e > lm lm = e end leftmax[i] = lm end for (i,e) in enumerate(reverse(a)) if e > rm rm = e end rightmax[length(rightmax)-(i-1)] = rm end water = 0 for (i, e) in enumerate(a) water += min(leftmax[i], rightmax[i]) - e end wat end function longest_increasing_subsequence(v::Vector{Int})::Vector{Int} M = zeros(Int, length(v)) # M[L] stores last index of sequence with length L. P = zeros(Int, length(v)) # P[i] stores predecessor of element i in longest sequence. Longest = 0 for i = eachindex(v) # Binary search for position in longest-sequence-so-far lo, hi = 1, Longest+1 while lo < hi mid = round(Int, floor((lo+hi)/2)) if v[i] < v[M[mid]] hi = mid else lo = mid+1 end end @assert lo == hi # Update predecessor of current index. P[i] = lo > 1 ? M[lo-1] : -1 M[lo] = i if lo >= Longest Longest = lo end end # Reconstruct sequence. seq = zeros(Int, Longest) i = M[Longest] for j = Longest:-1:1 seq[j] = v[i] i = P[i] end seq end function longest_common_subsequence(x::Vector{T}, y::Vector{T})::Vector{T} where {T} m, n = length(x), length(y) C = zeros(Int, m+1, n+1) # Not necessary: for i = 1:m C[i,1] = 0 end for j = 1:n C[1,j] = 0 end for i = 1:m for j = 1:n if x[i] == y[j] C[i+1,j+1] = C[i, j] + 1 else C[i+1,j+1] = max(C[i, j+1], C[i+1, j]) end end end # Reconstruct sequence i, j = m, n k = C[m+1, n+1] seq = Vector{T}(undef, k) while k > 0 if C[i,j] + 1 == C[i+1,j+1] seq[k] = x[i] k -= 1 i -= 1 j -= 1 elseif C[i,j+1] == C[i+1,j+1] i -= 1 elseif C[i+1,j] == C[i+1,j+1] j -= 1 end end seq end function lcss_slow_memoize(a::AbstractArray{T}, b::AbstractArray{T}; d::Matrix=fill(0, length(a), length(b)), c::Vector{Vector{T}}=Vector{Vector{T}}())::Vector{T} where {T} if 0 == min(length(a), length(b)) return [] end ck = (length(a), length(b)) if d[ck...] > 0 return c[d[ck...]] end nexts = [lcss_slow_memoize((@view a[i:end]), (@view b[j:end]); d=d, c=c) for i = 2:length(a) for j = 1:length(b)] longest = isempty(nexts) ? [] : nexts[findmax(length, nexts)[2]] if a[begin] == b[begin] r = vcat([a[begin]], longest) push!(c, r) d[length(a),length(b)] = length(c) return r else push!(c, longest) d[length(a),length(b)] = length(c) return longest end end function longest_consecutive_subarray(a::AbstractArray{<:Integer}) isdistinctonly(s) = length(Set(s)) == length(s) L = -1 lix = nothing for i = 1:length(a) for j = i+1:length(a) v = @view a[i:j] if isdistinctonly(v) && maximum(v) - minimum(v) == (j-i) && (j-i+1) > L L = j-i+1 lix = (i, j) end end end end function replace_every_element_with_product_of_every_other_element(a::AbstractArray{<:Integer}) p = prod(a) [p/ae for ae = a] end function max_positive_difference(a::AbstractArray{<:Real}) D = -1 ix = nothing for i = eachindex(a) for j = i:length(a) if a[i] <= a[j] && a[j] - a[i] > D ix = (i, j) D = a[j] - a[i] end end end @show (D, ix) end function max_product_subarray(a::AbstractArray{<:Integer}) lo, hi = -abs(prod(a)), abs(prod(a)) highest = lo for i = eachindex(a) lo_ = lo lo = min(a[i], min(lo * a[i], hi * a[i])) hi = max(a[i], max(hi * a[i], lo_ * a[i])) highest = max(hi, highest) end highest end function longest_continuous_common_sum(x::AbstractArray{Bool}, y::AbstractArray{Bool}) xs = zeros(Int, size(x)) ys = zeros(Int, size(y)) xs[1] = x[1] ys[1] = y[1] for i = 2:length(x) xs[i] = xs[i-1] + x[i] ys[i] = ys[i-1] + y[i] end cl = min(length(x), length(y)) L = 0 @show (xs, ys) for i = 1:cl for j = i+1:cl xsum = xs[j]-xs[i] ysum = ys[j]-ys[i] if xsum == ysum L = max(L, j-i+1) end end end L end function max_stock_profit(prices::AbstractArray{<:Real})::Real start = prices[1] i = 2 profit = 0 while i <= length(prices) if prices[i] >= prices[i-1] i += 1 else profit += prices[i-1] - start start = prices[i] i += 1 end end profit += prices[end] - start profit end function sort_swapped(a::AbstractArray) count = 0 first, second = 0, 0 for i = eachindex(a) if i <= 1 continue end if count == 0 if a[i] < a[i-1] first = i-1 count += 1 end else if a[i] < a[i-1] second = i count += 1 break end end end if second == 0 second = first+1 end a[first], a[second] = a[second], a[first] a end function max_sum_subarray(a::AbstractArray) max_encountered = -10000 current_sum = 0 lo, hi = 1, length(a) for (i, e) = enumerate(a) if e > current_sum+e lo = i end current_sum = max(current_sum+e, e) if current_sum >= max_encountered hi = i end max_encountered = max(max_encountered, current_sum) end max_encountered end """Fisher-Yates""" function shuffle(a::AbstractVector) for i = length(a):-1:1 ix = rand(UInt) % i a[i], a[ix+1] = a[ix+1], a[i] end end function visualizeshuffle(n, m) base = 1:n mat = zeros(Int, n, m) for i = 1:m mat[:,i] .= collect(base) shuffle(@view mat[:,i]) end mat end function kth_smallest(a::AbstractVector{T}, k=3) where {T<:Integer} buf = collect(a[begin:k]) # copy first few elements sort!(buf) fit_in(x) = begin if x >= buf[end] return else i = findnext((>=)(x), buf, 1) if !isnothing(i) buf[i+1:end] = buf[i:end-1] buf[i] = x end end end for i = k+1:length(a) fit_in(a[i]) end buf[end] end function quickselect_partition(a::AbstractVector, i, j) x, y = i-1, j+1 pivix = div(i+j, 2) piv = a[pivix] @show piv while true x += 1 while a[x] < piv x += 1 end y -= 1 while a[y] > piv y -= 1 end if x >= y a[pivix], a[y] = a[y], a[pivix] return y end if a[x] == piv pivix = y elseif a[y] == piv pivix = x end a[x], a[y] = a[y], a[x] end end function quickselect(a::AbstractVector{<:Integer}, k=3, i=1, j=length(a)) # Like quicksort, but keep sorting only half. if i >= j return i end pivix = quickselect_partition(a, i, j) if pivix > k-1 quickselect(a, k, i, pivix) else quickselect(a, k, pivix+1, j) end end # Naive function subarrays_with_sum(a::AbstractVector{<:Integer}, s) running_sum = copy(a) for i = 2:length(a) running_sum[i] = running_sum[i-1] + a[i] end subarrays = Pair[] for i = 1:length(a) for j = i:length(a) if running_sum[j] - running_sum[i] == s push!(subarrays, i+1 => j) end end end subarrays end # https://interviewing.io/questions/find-peak-element function find_peak_element(m::Matrix{Int}) waters = Tuple.(findall((==)(1), m)) up(ix) = (ix) .+ (-1, 0) down(ix) = (ix) .+ (1, 0) left(ix) = (ix) .+ (0, -1) right(ix) = (ix) .+ (0, 1) inbounds(ix) = begin a, b = (ix) a > 0 && b > 0 && a <= size(m, 1) && b <= size(m, 2) end mark(ix, n) = begin if !inbounds(ix) return end if !(ix in waters) if m[ix...] > 0 && m[ix...] <= n return end m[ix...] = n end mark(up(ix), n+1) mark(down(ix), n+1) mark(left(ix), n+1) mark(right(ix), n+1) end for w in waters m[w...] = 0 mark(w, 0) end m end