Skip to content

entendre1/algo

BranchesTags
 
 

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

1,012 Commits
code
code
 
 
company
company
 
 
dp
dp
 
 
freq
freq
 
 
misc.txt
misc.txt
 
 
readme.md
readme.md
 
 

Repository files navigation

list






arr

out_loop (many cycles); in_loop (1 cycle); big 2 side, down; small 2 side, up

out_loop (many cycles); in_loop (1 cycle); big 2 side, down; small 2 side, up


intersection(1_ele_in_another) -> unique(set); unique(set) -> intersection(1_ele_in_another);

[1, 1, 1] and [1, 1] -> [1, 1]-> [1]; intersection -> unique
[1, 1, 1] and [1, 1] -> [1, 1] -> [1]; unique -> intersection
[1, 1, 1] and [1, 1] -> [1, 1]-> [1]; unique -> intersection





1 loop, 2_same_kind_var track pureness

[1, 2, 3], good; [3, 2, 1], good; [2, 2, 2], good; [1, 2, -100, 100], bad
  • EG
  • 1, 2, 3, pure (1 loop, 2_same_kind_var track pureness)
  • 3, 2, 1, prue (..)
  • 2, 2, 2, pure (..)
  • [1, 2, -100, 100], !pure (..)
  • SUMMA
  • loop eles
  • if asc + desc set, !pure (1 loop, 2_same_kind_var track pureness)
  • if asc set, pure (..)
  • if desc set, pure (..)
  • if asc + desc !set, !touch, equal (..)
  • https://leetcode.com/problems/monotonic-array


slide_window_avoid_rest_ops

slide_window_avoid_rest_ops; res == 1; i < a.len - len VS a[i+len]; sorted, a[i] == start_val, a[i+len] == end_val, start_val == end_val
  • EG
  • [1, 2, 2, 6, 6, 6, 6, 7, 10], len = 9, quarter_len = 9/4 -> floor(2.25) = 2;
  • ceil(2.25) = 3, 3*4_quarter = 12_too_big
  • SUMMA
  • len = a.len / 4 (floor)
  • single_loop(i=0; i < a.len - len; ..); (i < a.len - len VS a[i+len])
  • if a[i] == a[i + len], re a[i]; (sorted, a[i] == start_val, a[i+len] == end_val, start_val == end_val)
  • https://leetcode.com/problems/element-appearing-more-than-25-in-sorted-array
slide_window_avoid_rest_ops; max_in_slide_win; i_diff_spd_pt_same_start; j_diff_spd_pt_same_end; sum == curr_win_size_in_val, plus ns[j] == extend_win_right; end-start, affect curr_win_size_in_len; sum == curr_win_size_in_val, minus ns[j] == shrink_win_left;
  • EG
  • [2, 3, 4, 1, 5], k = 3; e.g. [2, 3, 4] or [2, 4, 1] or [4, 1, 5]; max = 4+1+5=10
  • SUMMA
  • i_diff_spd_pt_same_start
  • j_diff_spd_pt_same_end
  • outloop (j < len)
  • sum = sum + ns[j] (sum == curr_win_size_in_val, plus ns[j] == extend_win_right)
  • if end - start = k-1 (end-start, affect curr_win_size_in_len)
  • ma = ma(ma, sum) (update_max)
  • sum = sum - ns[i] (sum == curr_win_size_in_val, minus ns[j] == shrink_win_left)
  • end_if, ++j (extend_win_right)
  • re max / k
  • https://leetcode.com/problems/maximum-average-subarray-i


?

greedy, sort, group_2


ele === index; mark_num

[2, 5, 3, 1, 1] (missing 4); ind = ele - 1; [2-1(ind), 5-1(ind), 3-1(ind), 1-1(ind), 1-1(ind)]; [-2, -5, -3, x, -1]; ele = ind + 1; ele === ind; mark_num


arr_full_sum(sort) - arr_actual_sum(sort)

missing_1_num; [3, 0, 1] -> [0, 1, 3] (2 missing) -> [0, 1, 2, 3] (full); diff = 0, 1, 2, 3 - 0, 1, 3


loop_eles + build hash / sort_then_middle

[2, 3, 1, 1, 1] -> [1, 1, 1, 2, 3]; vote_algo; same_ele_vote, diff_ele_vote_cancel, vote_exhaust_new_major
  • EG
  • SUMMA
  • vote_algo
  • major = ns[0]; counter = 1; (1st_ele major)
  • loop ele (i=1)
  • if c === 0; major = n[i], c=1 (vote_exhaust_new_major)
  • if major === ns[i]; ++c (same_ele_vote)
  • else --c (diff_ele_vote_cancel)
  • https://leetcode.com/problems/majority-element


flow_down (priority queue like)

[1, 1, 2, 2, 3, 3] -> 1 is 3rd max; (1) flow_down (priority queue like) (2) priority queue
[3,6,1,0], 6 (>= 2 * everyone); (1) flow_down (priority queue like) (2) priority queue
[3,4,5,2], max prod of 2 num, 4*5=20; (1) flow_down (priority queue like) (2) priority queue
[10, -1, -2, -3] -> 10 * (-2) * (-3); +, +, + VS +max, -, -
top 5 subject scores for each student; [[1, 91], [1, 92], [2, 81], [1, 60]] -> [[1, 91], [1, 92], [1, 60], [2, 81]]; prepare before (hash) + flow_down
kth largest element; priority queue (find insert posi, shift_left)





non_decrease_arr; (1)left_before_edge; (2)too_low, i-1, i, i+1; (3)too_high, i-2, i; (4)right_edge

non_decrease_arr; (1)left_before_edge; (2)too_low, i-1, i, i+1; (3)too_high, i-2, i; (4)right_edge
  • EG
  • SUMMA
  • i=0
  • [0(i_no_i-1), 1, 2, 3, 4], 5pt
  • i=1
  • [1, -100(i_look_back, drop, out_of_trend_low), 2, 3, 4], 5pt; (left_before_edge)
  • i=2
  • [1, 2, -100(i, drop, out_of_trend_low), 3, 4], 5pt; (too_low; i-1, i, i+1)
  • i=3
  • [1, 2, 100(out_of_trend_high), 3(i, drop), 4], 5pt; (too high; i-2, i)
  • .....
  • i=len-2
  • [1, 2, 3, -100(i, drop, out_of_trend_high), 4], 5pt; (too low; i-1, i, i+1)
  • i=len-1
  • [1, 2, 3, 4, -100(i, drop, i_last)], 5pt; (right_edge)
  • https://leetcode.com/problems/non-decreasing-array





INVERSE_QUESTION; when saying true, false, yes, no; inverse

INVERSE_QUESTION; matrix; most re_fail, else re_true; 2_ele_diag, upto_2nd_last
  • EG
  • SUMMA
  • INVERSE_QUESTION; most re_fail, else re_true
  • loop(i=0; i<=len-2; ..) (normal_scan_loop, 2_ele_diag, upto_2nd_last)
  • loop(j=0; j<=len-2; ..) (normal_scan_loop, 2_ele_diag, upto_2nd_last)
  • if ma[i][j] !== ma[i+1][j+1] re_fail (INVERSE_QUESTION, most re_fail)
  • https://leetcode.com/problems/toeplitz-matrix





backward

10 -> B or 11 -> B; 0 -> A; 0_end; backward + seq_1s
  • EG
  • 10 -> B or 11 -> B; 0 -> A; 0_end
  • [0(end)], t
  • [0, 0(end)], t
  • [1, 0(end)], f
  • [0, 0, 0(end)], t; (0 + 0_end, because 1 uses 1st 0)
  • [0, 1, 0(end)], f; (odd_sequence_1s)
  • [1, 0, 0(end)], t; (0 + 0_end)
  • [1, 1, 0(end)], t; (even_seq_1s)
  • [0, 0, 0, 0(end)], t; (0 + 0_end)
  • [0, 0, 1, 0(end)], f; (odd_seq_1s)
  • [0, 1, 0, 0(end)], t; (0 + 0_end)
  • [1, 0, 0, 0(end)], t; (0 + 0_end)
  • [0, 1, 1, 0(end)], t; (even_seq_1s)
  • SUMMA
  • loop(i=len-2; ns[i]!==0 && i>=0; --i); ignore_ending_0
  • backward; count_seq_1s; odd_seq_1s false; even_seq_1s true;
  • https://leetcode.com/problems/1-bit-and-2-bit-characters
n1: [1, 2, 3, 4(end_m_r), 0, 0(end_w)]; n2: [2, 2(end_n_r)]; backward, 1_write, 2_reads
  • EG
  • SUMMA
  • end_write, end_m_read, end_n_read (1_write, 2_reads)
  • while(n>=0) (scan_from_right)
  • n1[end_w--] = n1[end_m_r] > n2[end_n_r] ? n1[end_m_r--] (1_write, 2_reads)
  • n1[end_w--] = n1[end_m_r] <= n2[end_n_r] ? n2[end_n_r--] (1_write, 2_reads)
  • https://leetcode.com/problems/merge-sorted-array
backward, IGNORE_CARRY (9) or ADD_ONE (0, 1, 2..8)
  • EG
  • SUMMA
  • backward loop eles
  • if ds[i] === IGNORE_CARRY (9); ds[i] = 0; con_loop
  • if ds[i] === ADD_ONE (0, 1, 2..8); ds[i]++; return
  • end_loop, prepend 1; e.g. 999, con_loop
  • https://leetcode.com/problems/plus-one


curr_ele = max(..rest_arr)

curr_ele = max(..rest_arr)


parity (2_things)

parity (2_things); [2, 2, 2, 3, 3]; even_to_even; odd_to_odd; even_to_odd; odd_to_even
  • EG
  • posi = [2, 2, 2, 3, 3]; posi 1 == 0 chip; posi 2 == 3 chips; posi 3 == 2 chips
  • odd_to_odd, even_to_even, cost 0; odd_to_even, even_to_odd, cost 1
  • SUMMA
  • loop eles
  • if odd, ++odd
  • if even, ++even
  • end_loop;
  • if odd == arr.len, re 0; (odd_to_odd, cost 0)
  • if even == arr.len, re 0; (even_to_even, cost 0)
  • else re min(odd, even) (e.g. [2, 2, 2, 3, 3], 3 less moves)
  • https://leetcode.com/problems/minimum-cost-to-move-chips-to-the-same-position





when_same_flip_both, when_diff_do_nothing

1, 0 -> 0, 1 -> 1, 0 -> when_diff_do_nothing; 1, 1 -> 1, 1 -> 0, 0 -> when_same_flip_both;




transpose matrix -> (i, j) swap (j, i)

transpose matrix -> (i, j) swap (j, i)


outloop(row_1D_arr_slot_xxx); inloop(col_1D_arr_slot_xxx); row_1D_arr_slot_xxx X col_1D_arr_slot_xxx -> 2D

outloop(row_1D_arr_slot_acc); inloop(col_1D_arr_slot_acc); row_1D_arr_slot_acc x col_1D_arr_slot_acc -> 2D
  • EG
  • method 1: do_row, do_col; do_row, do_col
  • ind: [[0_row, 1_col], [1_row, 1_col]]
  • 0 0 -> 1 1 -> 1 2 ==> 1 2 -> 1 3
  • 0 0 -> 0 0 -> 0 1 ==> 1 2 -> 1 3
  • method 2: do_row, do_row; do_col, do_col
  • ind: [0_row, 1_row]
  • 0 0 -> 1 1 -> 1 1
  • 0 0 -> 0 0 -> 1 1
  • ind: [1_col, 1_col]
  • 0 0 -> 0 1 -> 0 2
  • 0 0 -> 0 1 -> 0 2
  • merge_2
  • do_row, do_col; do_row, do_col ===> do_row, do_row; do_col, do_col
  • SUMMA
  • single_loop(income_ind_arr)
  • row_1D_arr_slot_acc
  • col_1D_arr_slot_acc
  • outloop(row_1D_arr_slot_acc)
  • inloop(col_1D_slot_acc)
  • if (row_1D_arr_slot_acc[i] + col_1D_slot_acc[j]) % 2 == 0, ++counter
  • https://leetcode.com/problems/cells-with-odd-values-in-a-matrix
outloop(row_1D_arr_slot_max, move_down); inloop(col_1D_arr_slot_min, move_right); row_1D_arr_slot_max x col_1D_arr_slot_min -> 2D
  • EG matrix: 1, 2, 3, 4 5, 6, 7, 8 9, 10, 11, 12
  • outloop(row_1D_arr_slot_max, move_down)
  • inloop(col_1D_arr_slot_min, move_right)
  • row_1D_arr_max = [1, 2, 3, 4] -> [5, 6, 7, 8] -> [9, 10, 11, 12]
  • col_1D_arr_min = [1, 5, 9] -> [1, 5, 9] -> [1, 5, 9] -> [1, 5, 9]
  • 1D x 1D = outloop(row_1D_arr_slot_max) x inloop(col_1D_arr_slot_min)
  • res = [9], cross_over
  • SUMMA
  • outloop(row_1D_arr_slot_max, move_down)
  • inloop(col_1D_arr_slot_min, move_right)
  • row_1D_arr_max[i] = ma(matrix[i][j], ma[i]) (slot_not_finish)
  • col_1D_arr_min[j] = mi(matrix[i][j], mi[j]) (slot_finish)
  • outloop(row_1D_arr_slot_max)
  • inloop(col_1D_arr_slot_min)
  • if ma[i] == mi[j], arr.push (row_1D_arr_slot_max x col_1D_arr_slot_min -> 2D)
  • https://leetcode.com/problems/lucky-numbers-in-a-matrix


sorted_desc_matrix, row_desc, col_desc; top_left_big, bottom_right_small; row_ind_go_up,col_above_same_or_behind

sorted_desc_matrix, row_desc, col_desc; top_left_big, bottom_right_small; row_ind_go_up,col_above_same_or_behind




2D -> 1D -> 2D

2D -> 1D -> 2D; 1D[i_total] = 2D[i_total / w][i_total % w]; 2D[i][j] = 1D[r * w + c];

  • EG

  • SUMMA

  • 2D -> 1D -> 2D; a_old[i_total / old_w][i_total % old_w] -> a_mid[i_total = i_total = r * width + c] -> a_new[i_total / new_w][i_total % new_w]

  • old_w * old_h === new_w * new_h;

  • loop(i_total=0; i < old_w * old_h; ..); 2D -> 1D; a_old[i_total / old_w][i_total % old_w] -> a_mid[i_total = r * width + c]

  • a_new[i_total / new_w][] = a_old[i_total / old_w][i_total % old_w]

  • https://leetcode.com/problems/reshape-the-matrix

2D -> 1D -> 2D; 1D[i_total] = 2D[i_total / w][i_total % w]; 2D[i][j] = 1D[r * w + c];
  • EG
  • SUMMA
  • 2D -> 1D; loop(i=0; i<m*n; ..); a_mid[i_total] = a_old[i_total / old_w][i_total % old_w];
  • shift; loop(i=0; i<m*n; ..); a_new_1D[(i_total + k) % len] = a_mid[i_total];
  • 1D -> 2D; in_loop, out_loop; a_new_2D[i][j] = a_new_1D[i * width + j];
  • https://leetcode.com/problems/shift-2d-grid
2D -> 1D; 1D[i_total] = 2D[i_total / w][i_total % w]; 2D[i][j] = 1D[r * w + c];
  • EG
  • SUMMA
  • [ r:[0, 1, 2], [3, 4, 5], [6, 7, 8], c:[0, 3, 6], [1, 4, 7], diag[2, 5, 8], [0, 4, 8], [2, 4, 6] ] (3_win)
  • loop input_arr (fill_tic_tac)
  • a_mid[ c * width + r ] = (i_A_OR_B % 2) + 1; (2D -> 1D; a_old[r][c] -> a_mid[ c * width + r])
  • loop win
  • if a_mid[ win[i][0] ] == a_mid[ win[i][1] ] == a_mid[ win[i][2] ] && not_eq_zero (3_win)
  • either re 'A' or 'B'
  • end_loop; input_arr.len === 9 re 'DRAW'; else 'PENDING'
  • https://leetcode.com/problems/find-winner-on-a-tic-tac-toe-game





count(full || b_eof) VS out_req_left

read_4_char api func; count(full || b_eof); out_req_left == out_req_n_char - total_acc;





rm_1_item; (len_reduce, --i && ++i_back_to_top)

rm vowel in str; splice; (len_reduce, --i && ++i_back_to_top)
[-1, -1, 0, 1, 1, 2, 2] -> [-1, 0, 1, 2];
ip addr, 123.41.51.61 -> 123[.]41[.]51[.]61; insert "[" start, insert "]" end





what_diff_type_pt? (1) i_slow_pt_diff, j_fast_pt_diff(LOOK_BACK); (2) i_same_spd_pt_diff, j_same_spd_pt_diff(i_start + len); (3) i_same_spd_pt_diff, j_same_spd_pt_diff(tracking_var); (4) i_diff_spd_pt_same, j_diff_spd_pt_same(????);

i_same_spd_pt_diff, j_same_spd_pt_diff(tracking_var); "ab" VS "ba" (A_can_swap)
  • EG
  • abc VS ab; diff_len, A_cannot_swap
  • aab VS aab; same_and_dup, A_can_swap "aa"
  • ab VS ba; i_same_spd_pt_diff, j_same_spd_pt_diff(tracking_var)
  • SUMMA
  • if diff_len, A_cannot_swap, re f
  • if same_and_dup, A_can_swap, re t
  • else i_same_spd_pt_diff, j_same_spd_pt_diff(tracking_var);
  • e.g. ab VS ba; var1 = [a, b], var2 = [b, a]
  • if var1[0] == var2[1] && var1[1] == var2[0]
  • https://leetcode.com/problems/buddy-strings





in_loop; prefix_reduce_1_char; compare_with_input_word

in_loop(non_found_prefix_loop); prefix_reduce_1_char; compare_with_input_word
["cool", "lock", "cook"]; cook as common; cool vs lock -> co (ol); co vs cook -> co(); if_common, rm from input_word; if_non_common, rm from common
  • EG
  • SUMMA
  • arr[0] as common (global)
  • out_loop (i=1, i<len) (outloop_each_word)
  • in_loop(loop_each_char_in_common)
  • (1)
  • vertical compare
  • common: aac; first_a stay; for next input_word (global)
  • input: abc; first_a gone; next_common_char won't check again
  • (2)
  • vertical compare
  • common: xy; first_x gone; next input_word won't use (global)
  • input: abc; first_a stay; next_common_char may hit
  • in_summary; if_common, rm from input_word; if_non_common, rm from common
  • https://leetcode.com/problems/find-common-characters


vertical_compare

[1, 1, 4, 2, 1, 3] -> min_move_become_sort -> [1, 1, 1, 2, 3, 4]





compare(sb 1 group || b 1 group) / in_hash(sb 1 group || b 1 group)

IVIV(roman) -> IV(s, s+1) -> compare(sb 1 group || b 1 group); i(start), i(start+1), j(x, end), j(x, end-1); i move right; access_hash
  • EG
  • IVIV -> (sb)(sb) -> (IV)(IV)
  • VIVI -> (b)(sb)(b, end) -> (V)(IV)(I)
  • SUMMA => sb 1 group, b 1 group
  • build HASH (from Q, has all combo)
  • loop chars
  • curr = h[i], next = h[i+1] (LOOK_AHEAD, i_stay)
  • if curr >= next, b 1 group
  • else next < curr, sb 1 group, fast_forward
  • else the_end_char
  • https://leetcode.com/problems/roman-to-integer
IVIV(roman) -> IV(s, s+1) -> in_hash(sb 1 group || b 1 group); i(start), i(start+1), j(x, end), j(x, end-1); i move right; access_hash
  • EG
  • IVIV -> (in_h)(in_h) -> (IV)(IV)
  • VIVI -> (in_h)(in_h)(in_h) -> (V)(IV)(I)
  • SUMMA => h[ s[i] + s[i+1] ] (LOOK_AHEAD, i_stay)
  • build HASH (from Q, has all combo)
  • loop chars
  • if h[ s[i] + s[i+1] ], fast_forward
  • else 1_char_acc
  • https://leetcode.com/problems/roman-to-integer


loop 1 -> 1000; loop a -> b; xxxx; (natural_bottom_up)

a2 in a1; a1 follows a2 order; res build_from_ground
  • EG
  • a1: [3, 4, 1, 1, 2, 2]
  • a2: [1, 2]
  • h: {3:1, 4:1, 1:2, 2:2} (build_knowledge)
  • out: [1, 1, 2, 2, 3, 4]
  • SUMMA
  • ..
  • ..
  • loop 0->1000 (e.g. loop 1 -> 1000 or loop a -> z, natural_bottom_up)
  • use all freq
  • res.push(build_from_ground)
  • https://leetcode.com/problems/relative-sort-array
[1,1,4,2,1,3] -> how_many_move -> [1, 1, 1, 2, 3, 4]; natural_bottom_up + consume_hash === input_arr_len
  • EG
  • [1,1,4,2,1,3] -> how_many_move -> [1, 1, 1, 2, 3, 4] (sort)
  • SUMMA
  • hash 0, 1, 2, 3 -> 100 (natural_bottom_up)
  • out_loop 1 -> 100 (natural_bottom_up)
  • input_arr_ind = 0 (global)
  • i === height
  • in_loop( (hash[i]--) > 0); (natural_bottom_up + consume_hash === input_arr_len)
  • input_arr[ input_arr_ind ] !== i_height; res++; e.g. input_arr[1] may == input_arr[100], beause dup
  • https://leetcode.com/problems/height-checker
missing_positive_num; hash_prepare + bottom_up + fill_gap_in_hash
missing_positive_num; hash_prepare + bottom_up + fill_gap_in_hash
missing_positive_num; positive_uniq + find_gap_in_input


LOOK_BACK, LOOK_SELF, LOOK_AHEAD

place flower in pot_array
  • EG
  • [1,0,0,0,0,0,1], k = 2 -> [1,0,0(1),0,0(1),0,1]
  • SUMMA
  • if fb[i-1] = 1, skip (LOOK_BACK)
  • if fb[i] = 1, skip (LOOK_SELF)
  • if fb[i+1] = 1, skip (LOOK_AHEAD)
  • after_all, ++counter
  • end_loop, counter >= k?
  • https://leetcode.com/problems/can-place-flowers


LOOK_BACK(same OR inc; i=1)

find_word_segment; letter space == word_segment; i-1, i(LOOK_BACK, i_move);
[5, 37, 12, 5] -> rank: [1, 3, 2, 1]; LOOK_BACK, when_same_rank_stay, when_diff_rank_inc


build_from_ground_rearrange (a_i + a_j VS res_i + res_j)

a2 in a1; a1 follows a2 order; res build_from_ground_rearrange(i_hash_fill_res + j_natural_bottom_up_fill_res VS res_ind )
  • EG
  • a1: [3, 4, 1, 1, 2, 2]
  • a2: [1, 2]
  • h_a1: {3:1, 4:1, 1:2, 2:2}
  • out: [1, 1, 2, 2, 3, 4]
  • SUMMA
  • h_a1
  • loop a2 (a1 follows a2 order)
  • use h_a1 to print freq (i_hash_fill_res)
  • res.push
  • end_loop, reset freq
  • loop 0->1000 (e.g. loop 1 -> 1000 or loop a -> z; j_natural_bottom_up_fill_res)
  • use all freq
  • res.push
  • https://leetcode.com/problems/relative-sort-array
build_from_ground_rearrange(i_big_fill_res, i_small_fill_res VS res_ind); [-4(i_start), -3, 1, 2(j_big)] -> [1, 4, 9, 16];
  • EG
  • sort + -; big head?, big tail?
  • why push big -> small?
  • if small to big, e.g. [-4(i_small), -3, 1, 2(j_big)] -> [2^2, 1^2, -3^2, ..] (wrong)
  • push big -> small
  • [-4(i_small), -3, 1, 2(j_big)] -> [1, 4, 9, 16];
  • SUMMA
  • res = [], ind = j_end;
  • i_small, j_big
  • loop(i <= j)
  • if ns[i]^2 > ns[j]^2, res[ind--](can be arr / hash) = ns[i]^2; (i_big_fill_res; res_ind)
  • if ns[i]^2 <= ns[j]^2, res[ind--](can be arr / hash) = ns[j]^2 (i_small_fill_res; res_ind)
  • https://leetcode.com/problems/squares-of-a-sorted-array


rewind

110#11#12# -> (1)(10#)(11#)(12#) -> ajkl


find_word_segment; feature represent entire;

find_word_segment; feature represent entire (letter space == word_segment);


build_hash_freq, --hash_freq[n]

chars build words; can "atach" build "cat", "dog", "xxxxx" each time?
1st unique char in str; hash_freq, lookup_in_order
aaabb, build_palindrome; a:3 (odd), b:2 (even); hash_freq, take_all_even
hash; max(...arr)


hash[ str(complex_ele) ]; dp(same_var_curr) = dp(same_var_prev) + x

[[1,2],[2,1],[3,4],[5,6]] -> [[1,2],[1, 2],[3,4],[5,6]] 1 pair; hash[ str(complex_ele) ]; dp(same_var_curr) = dp(same_var_prev) + x
  • EG
  • n=1, a -> 0
  • n=2, aa -> a(a) -> 1 pair (0_dp + 1_last_few_num)
  • n=3, aaa -> a(aa) -> 3 pairs (1_dp + 2_last_few_num)
  • n=4, aaaa -> a(aaa) -> 6 pairs (3 + 3)
  • n=5, aaaaa -> a(aaaa) -> 10 pairs (6 + 4)
  • so dp[n] = dp[n-1] + (n-1) ==> dp(same_var_curr) = dp(same_var_prev) + (n-1)
  • SUMMA
  • e.g. [[1,2],[2,1],[3,4],[5,6]]
  • loop ele
  • hash[str(ele)] (stringify_for_complex_ele)
  • if hash[n] > 1, use dp(same_var_curr) = dp(same_var_prev) + (n-1)
  • https://leetcode.com/problems/number-of-equivalent-domino-pairs


prebuild hash_init_posi / build hash_init_posi along (met / !met) / update hash_init_posi along (met / !met) / build hash_init_posi along (met_the_other / !met_the_other)

cal total distance; prebuild hash_init_posi;
  • EG
  • keyboard: abcdefghijklmnopqrstuvwxyz, word: cba, that is 1 keyboard position (a-z)
  • keyboard: pqrstuvwxyzabcdefghijklmno, word: pom, that is another keyboard position (p-o)
  • SUMMA
  • prebuild hash posi
  • loop chars (e.g. cba)
  • LOOK_BACK(i=1); dist = h[i] - h[i-1]; res = res + dist
  • https://codedestine.com/single-row-keyboard-string-problem
max distance; build hash_init_posi along (met / !met);
2 same num distance <= k; update hash_init_posi along (met / !met)


one pass; hash_obj(freq, distance); sudden_meet_condi, update_freq, update_distance

[1,2,1,2,1,3,3,2]; {1:3, 2:3, 3:2}; 1 and 2 same max_freq, but 1 is shorter dist; (1) one pass; hash_obj: {freq, distance}; sudden_meet_condi(freq > max_freq || freq == max_freq), update_freq, update_distance


1_tracking_var, 2_tracking_var, 3_tracking_var, etc

ns: [a, b, c, d, b]; w0=b, w1=d
2_tracking_var, minFreq, minDistance
3_tracking_var, m0, m1, m2
5_tracking_var, ma0, ma1, ma2, mi0, mi2


hash, sort_hash, rev_sort_hash

aaabbbccc -> (abc)(cba)(abc)(cba) -> (inc)(desc)(inc)(desc); hash, sort_hash, rev_sort_hash


nums -> digi_sum_prepare_hash -> group_sum

[1, 2, 11, 12]_num -> [1, 2, 2, 3]_digi_sum_prepare_hash -> [1, 2, 2, 3]_group_sum; nums -> digi_sum_prepare_hash -> group_sum


indexOf === lastIndexOf, only_1_no_repeat

1st unique char in str; indexOf === lastIndexOf, only_1_no_repeat


split(/+s/), set

mails_in_arr (split, set); rm dot, rm chars after '+'
, -> _ (maintain segment); trim_head_tail, split(/+s/)
  • EG
  • _abc_d,e,f_g_ -> _abc_d_e_f_g_(maintain segment) -> abc_d_e_f_g(trim_head_tail, split(/+s/)) -> [abc, d, e, f, g]
  • SUMMA
  • , -> _ (maintain segment)
  • trim_head_tail, split(/+s/)
  • build_hash, to freq
  • https://leetcode.com/problems/most-common-word/
morse code hash, use_set


mod_to_use, contain

ele + 1; mod_to_use, contain
2*ele; mod_to_use, contain
2*ele, ele/2; mod_to_use, contain


up_ups || up_lows || low_lows

CHINA || China || china -> up_ups, up_lows, low_lows
  • EG
  • SUMMA
  • re CHINA || China || china
  • loop chars
  • re up_ups(w) || up_lows(w) || low_lows(w);
  • up_ups == up?(w[0]) && up?(w[i], loop)
  • up_lows == up?(w[0]) && low?(w[i], loop)
  • low_lows == low?(w[0]) && low?(w[i], loop)
  • https://leetcode.com/problems/detect-capital


query_arr(like_2D), words_arr(like_2D); query_smallest_dist_arr, word_smallest_dist_arr; in_loop, out_loop

query_arr(like_2D), words_arr(like_2D); query_smallest_dist_arr, word_smallest_dist_arr; in_loop, out_loop
  • EG
  • qs -> [aza, bab]; ws -> [czzc, ddz]
  • qs1 -> [3_a_dist, 1_a_dist]; ws1 -> [4_c_dist, 2_d_dist]
  • res -> [1, 2]
  • 3_a_dist < 4_c_dist(*), 3_a_dist > 2_d_dist(x), so 1)
  • 1_a_dist < 4_c_dist(*), 1_a_dist < 2_d_dist(*), so 2)
  • SUMMA
  • qs_sort, find_smallest, a[0]
  • ws_sort, find_smallest, a[0]
  • dist = lastInd(a[0]) - ind(a[0]) + 1
  • qs1 -> [3_a_dist, 1_a_dist]; ws1 -> [4_c_dist, 2_d_dist]
  • out_loop, in_loop; qs1[0], qs1[1] stay
  • https://leetcode.com/problems/compare-strings-by-frequency-of-the-smallest-character


outloop, inloop

outloop, inloop; use_up single def_num, 3999 -> 2999 -> 1999 -> 999 -> 99 -> 9 -> 0 === (MMM)(CM)(?)(?)
  • EG
  • 3999 -> 2999 -> 1999 -> 999 -> 99 -> 9 -> 0
  • SUMMA
  • def_num (hash)
  • const h = { 1: "I", 4: "IV", .. 9: "IX", .. 90: "XC", ... 900: "CM" 1000: "M" }
  • hash -> arr -> rev
  • outloop: loop each def_num
  • inloop: use_up single def_num, move next
  • num -> roman, build str
  • https://leetcode.com/problems/integer-to-roman
aaAaA (rm Aa) -> aaA (rm aA) -> a (rm nothing, stop);
abcabc -> a VS b(len_1) -> ab VS ca(len_2) -> abc VS abc(len_3); pick pattern_len stable, rest move
  • EG
  • ..
  • SUMMA
  • len = 6, half_len = 3
  • abcabc (len_1(stable), OUTLOOP)
  • a VS b, a VS c, a VS a, a VS b, a VS c (slide_char, INLOOP)
  • abcabc (len_2(stable), OUTLOOP)
  • ab VS ca, ab VS bc (slide_char, INLOOP)
  • abcabc (len_3(stable), OUTLOOP)
  • abc VS abc (slide_char, INLOOP)
  • outloop: pattern
  • inloop: move pattern
  • https://leetcode.com/problems/repeated-substring-pattern


orig structure -> new structure

"aabc", [ab, bc]; aabc; (orig ab -> new 11; orig bc -> new 11)
LLLLRRRR, (-1)(-1)(-1)(-1)(+1)(+1)(+1)(+1); (orig L, R -> new -1, +1)
++vertical, --vertical; ++horizontal, --horizontal; (orig v -> new +1, -1; orig h -> new +1, -1)


slide_word (loop_word, slide_word, substring_equal)

"aabc", [ab, bc]; aabc; slide_word (loop_word, slide_word, substring_equal)
ababa, [aba, ab] -> [(0, 2), (2, 4)...]; slide_word (loop_word, slide_word, substring_equal)


build_knowledge

build_knowledge(# shift); backward; i_read, i_write_almost;
  • EG
  • SUMMA
  • [0(0, sh=0), 0(1, sh=1), 0(2, sh=2), 0(3, sh=3), 1(4)], len = 5;
  • shift(prev_0s) + ind < len ===> 2 + 2 = 4 < 5
  • shift(prev_0s) + ind < len ===> 3 + 3 = 6 > 5 (build_knowledge, # shift)
  • loop_stop, sh == 3 (1 extra)
  • loop(i=i-1; sh>0 ..) (backward)
  • if i+sh < len (avoid 1 extra); read i, write i+sh (normal, i_read, i_write_almost)
  • if a[i] == 0; read i, write i+(--sh) (dup 0, i_read, i_write_almost)
  • https://leetcode.com/problems/duplicate-zeros/discuss/312743/JavaC%2B%2B-O(n)-or-O(1)
a2 in a1; a1 follows a2 order; res build_from_ground


largest is uncommon

largest uncommon, abcde..... z VS abc, largest


get_all_substring

get_all_substring
  • EG
  • SUMMA
  • e.g. "abc"
  • loop (i start; small)
  • subloop (j end; big; i j cross over)
  • sub(i, j)


loop ele, subloop eles

["mass","as","hero","superhero"], inside_ele substring ["as","hero"]; loop ele, subloop eles


sort(other_attr ? other_attr : default_attr)

sort(other_attr ? other_attr : default_attr); sort -> slice -> map
  • EG
  • SUMMA
  • [[1,0,0,0], [1,1,1,1], [1,0,0,0], [1,0,0,0]]
  • res = [[1_count, 0_ind], [4, 1], [1, 2], [1, 3]]
  • res.sort(other_attr ? other_attr : default_attr);
  • res.sort.slice.map: sort(other_attr ? other_attr : default_attr) -> slice_portion -> map_sub_attr)
  • https://leetcode.com/problems/the-k-weakest-rows-in-a-matrix
ababa, [aba, ab] -> [(0, 2), (2, 4)...]; slide_word (loop_word, slide_word, substring_equal)


small_var (maintain meaning), big_var (maintain meaning)

ABABAB(3*AB), ABAB(2*AB), gcd = AB; AAAA - AAA(rm_prefix) = A; AAA - A(rm_prefix) = A
  • EG
  • (ab)abab vs ab, ababab.sub(ab.len) == abab; abab vs ab
  • (ab)ab vs ab, abab.sub(ab.len) == ab; ab vs ab
  • ab vs ab, ab.sub(ab.len) == ''; gcd
  • SUMMA
  • long - short, keep going
  • recur
  • (1) long_var (maintain meaning) > short_var (maintain meaning); (2) false_case( !abab.sub(ab) ); (3) good_case( s1 there, s2 == '' ); (4) con( (ab)ab, ab )
  • https://leetcode.com/problems/greatest-common-divisor-of-strings
abc12; abc long, 12 short; (bs)(bs)(b) -> (a1)(b1)c
  • EG
  • SUMMA
  • get_letter_arr(split, filter, isNaN), get_num_arr(split, filter, isNaN)
  • big_var (maintain meaning) > small_var (maintain meaning)
  • (bs)(bs)(b), bs + bs + extra
  • (bs)(bs), bs + bs + no_extra
  • arr.pop_end()
  • https://leetcode.com/problems/reformat-the-string

to_num VS to_char, get distance

Hello -> hello





special case 1st, then normal case

110#11#12# -> (1)(10#)(11#)(12#) -> s.replace(/10#/) -> special 1st, (1)jkl -> ajkl





greatest common divisor (gcd)

keep long_before_short; long_has_no_short; short_full_consumed; gcd_recur_rm_common
  • EG
  • AAAA - AAA = A;
  • AAA - A = AA;
  • AA - A = A;
  • A - A = 0 (done)
  • SUMMA
  • gcd_recur
  • if short_str.len > long_str.len (keep short_before_long)
  • if long.index(short) === 0, re ''; (long_has_no_short)
  • if short.len === 0, re big; (short full consumed)
  • else gcd( long.substr(short), short ); (gcd_recur_rm_common)
  • https://leetcode.com/problems/greatest-common-divisor-of-strings
keep start_before_end; curr_res in total_res, when_condi; total_res_with_loop; part_cycle = curr_res; rest_part_cycle = tot_res - curr_res
  • EG
  • [1_distance, 2_d, 3_d, 4_d]; 1_ind -> 2_ind, 2_distance
  • SUMMA
  • if start_ind > end_ind; swap; keep_1_direction_cycle
  • loop eles
  • if i >= start_ind(0_ind) && i < dest_ind(1_ind); res = res + dist[i] (curr_res in total_res, when_condi)
  • tot = tot + dist[i] (total_res_with_loop)
  • end_loop; part_of_cycle = curr_res; rest_part_of_cycle = tot_res - curr_res
  • https://leetcode.com/problems/distance-between-bus-stops
another gcd, [1,1,2,2,2,2] -> [1, 1], [2, 2], [2, 2]




DP

https://leetcode.com/discuss/general-discussion/491522/dynamic-programming-questions-thread





misc dp

each digit as group; double digit as group

1D; 1,2,3 -> ABC (each digit as group), 12,3 -> KC (double digit as group); num_combo
  • dp[i] === AT this ele (num_char), FINAL num_combo
  • init side === 1 (num_combo_1D; flow down)
  • loop ele (num_char)
  • curr_digit (0 skip; 1 good flow down)
  • curr_digit in 1->9(single_char); dp[i] = dp[i-1](curr digit flow down);

  • p_digit + curr_digit (undef_0 skip; undef_1 skip; "12" good flow)
  • p_digit + curr_digit in 10->26(double_char); dp[i] = dpi + i>=2 ? dp[i-2](2 digit flow down)
  • SUMMRY
  • curr_digit, done; p_digit + curr_digit, done
  • https://leetcode.com/problems/decode-ways


dp[i] = dp[i_prev] + sth

  • dp[i] = dp[i_prev] + curr_ele
  • dp[i] = dp[i_prev] + func(curr_ele)
  • dp[i] = reset + curr_ele
aaabc -> aaa_3_char, aa_2_char, a_1_char, b_1_char, c_1_char -> 3+2+1+1+1=8; dp[i]_curr_freq = dp[i-1]_prev_freq + dp[i]_curr_freq
N = 12; 1 -> 0(0), 2 -> 5(1), 3 -> x(0)... 10 -> 10(0), 11 -> 11(0), 12 -> 15; contain [3, 4, 7], then*all_fail; contain [2, 5, 6, 9], then_give_1

  • EG

  • mycount

  • 0 1 2 3 4 5 6 7 8 9 10 11 12 13 (each_num)

  • 0 1 5 x x 2 9 x 8 6 10 11 12 1x (e.g. 2 -> 5, 180 degrees)

  • 0 0 1 0 0 1 1 0 0 1 00 00 01 00 (contain [3, 4, 7], then_all_fail; contain [2, 5, 6, 9], give_1)

  • double_digits

  • 14 -> 1(1)4(x) -> 0 (contain [3, 4, 7], then_all_fail)

  • 20 -> 2(1)0(0) -> 1 (contain [2, 5, 6, 9], give_1)

  • 22 -> 2(1)2(1) -> 1 (......)

  • SUMMA

  • contain [3, 4, 7], then_all_fail

  • contain [2, 5, 6, 9], then_give_1

  • single_loop(i=1; i<=N...)

  • DP_EXPLAIN

  • dp_slot == N+1

  • dp[N+1].fill(0)

  • i == curr_input_num

  • dp[i] == curr_rotate_addup

  • i-1 == prev_input_num

  • dp[i-1] == prev_rotate_addup

  • dp[i] = dp[i-1] + mycount(i)

  • https://leetcode.com/problems/rotated-digits





building matrix

diff types of init side

fake_top_left_all_empty

00000 0 0 0 0

fake_top_1_val

01000 0 0 0 0

fake_left_1_val

00000 1 0 0 0

fake_top_vals

11111 0 0 0 0

fake_left_vals

10000 1 1 1 1

fake_top_left_vals

11111 1 1 1 1

physi_1_1_val

00000 01 0 0 0

physi_top_vals

00000 01111 0 0 0

physi_left_vals

00000 01 01 01 01

physi_top_left_vals

00000 01111 01 01 01

fake_top_left_vals

11111 1 1 1 1

1D/2D; physi_1_1_val; top_contrib, left_contrib; num_combo(add)/min/max

2D; physi_1_1_val; top_contrib, left_contrib; num_combo(add)/min/max
  • n+1, m+1 size
  • dp[i][j] => AT THIS row, AT THIS col, FINAL num_combo
  • init side => physi_1_1_val(num_combo) || fake_top_1_val || fake_left_1_val;
  • loop row (n)
  • loop col (m)
  • dp[i][j] = dp[i-1]j + dp[i]j-1; add
  • re dp[n][m]
  • https://leetcode.com/problems/unique-paths/
1D; physi_1_1_val; top_contrib, left_contrib; num_combo(add)
  • m+1 size
  • dp[i] => AT THIS col, FINAL num_combo
  • init side => physi_1_1_val(num)combo
  • loop row (n)
  • loop col (m)
  • dp[j] = dp[j](top; press_row) + dp[j-1](left, press_row)
  • re dp[m]
  • https://leetcode.com/problems/unique-paths/
2D; physi_1_1_val; top_contrib, left_contrib, obstacle; num_combo(add)
  • n+1, m+1 size
  • dp[i][j] => AT this row, AT this col, FINAL num_combo
  • init side => physi_1_1_val(num_combo); dp[1][1] == 1 || 0 (dep obstacle); init_in_loop
  • loop row (n)
  • loop col (m)
  • if obstacle, dp[i][j] = 0 (self no)
  • else no obstacle, dp[i][j] = dp[i-1]j + dp[i]j-1;
  • re dp[n][m]
  • https://leetcode.com/problems/unique-paths-ii/
1D; physi_1_1_val; top_contrib, left_contrib, obstacle; num_combo(add)
  • m+1 size
  • dp[j] => AT this col, FINAL num_combo
  • init side => physi_1_1_val(num_combo); dp[1] == 1 || 0 (dep obstacle); init_in_loop
  • loop row (n)
  • loop col (m)
  • if obstacle, dp[j] = 0 (self no)
  • else no obstacle, dp[j] = dp[j](top; press_row) + dp[j-1](left; press_row);
  • re dp[m]
  • https://leetcode.com/problems/unique-paths-ii/
2D; physi_1_1_val; top_contrib, left_contrib; min_path
  • n+1, m+1 size
  • dp[i][j] => AT this col, AT this row, FINAL min_path
  • init side => during_loop
  • loop row (n)
  • loop col (m)
  • if 1st row, dp[i][j] = dp[i]j-1 + grid[i-1][j-1]
  • if 1st col, dp[i][j] = dp[i-1]j + grid[i-1][j-1]
  • else dp[j] = MIN(dp[i]j-1, dp[i-1]j) + grid[i-1][j-1]
  • https://leetcode.com/problems/minimum-path-sum/
1D; physi_1_1_val; top_contrib, left_contrib; min_path
  • m+1 size
  • dp[i][j] => AT this col, AT this row, FINAL min_path
  • init side => during_loop
  • loop row (n)
  • loop col (m)
  • if 1st row, dp[j] = dp[j-1](left; press_row) + grid[i-1][j-1]
  • if 1st col, dp[j] = dp[j](top; press_row) + grid[i-1][j-1]
  • else dp[j] = MIN(dp[j-1](left; press_row), dp[j](top; press_row)) + grid[i-1][j-1]
  • https://leetcode.com/problems/minimum-path-sum/
2D; trangle to square DP; head + content + tail
  • EG
  • rowNum = 4, so [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1]]
  • SUMMA
  • dp[i][j] => i at this rowNum, i=0, i<=rowNum-1;
  • dp[i][j] => j at this content, j=1(avoid head), j<i(avoid tail);
  • dp[i][j] => res
  • out_loop rowNum
  • pa = [] (build_1D)
  • in_loop content (avoid head / tail)
  • pa[i] = [] (build_2D); pa[i][0] = 1(start)
  • pa[i][j] = pa[i-1]j-1 + pa[i-1]j
  • pa[i][i] = 1(end)
  • https://leetcode.com/problems/pascals-triangle
2D; fake_top_left_vals; bottom_up, bottom_contrib, bottom_right_contrib; min_path
  • n, m size (dp_size == ma_size)
  • dp[i-1][j] => AT this col, AT this row, FINAL min_path
  • init side => fill_bottom_row
  • loop row (bottom_up; i=n-1(ele); i>=0(ele))
  • loop col (bottom_forward; j=0; j>=i(j+1))
  • dp[i-1][j] = MIN(dp[i-1][j], dp[i-1][j+1]) + grid[i-1]j
  • re dp[0][0]
  • https://leetcode.com/problems/triangle
1D; fake_top_left_vals; bottom_up, bottom_contrib, bottom_right_contrib; min_path
  • m size
  • dp[j] => AT this col, FINAL min_path
  • init side => fill_bottom_row
  • loop row (bottom_up; i=n-1(ele); i>=0(ele))
  • loop col (bottom_forward; j=0; j>=i(j+1))
  • dp[j] = MIN(dpj, dpj+1) + grid[i-1][j]
  • re dp[0]
  • https://leetcode.com/problems/triangle/






3 loops; dp_3D; dimensions; multi_tar; max_combo

3 loops; dp_3D; NO_ORDER ele, reach tar_n, tar_m; max_combo
  • n+1, m+1, z+1 size
  • dp[k][i][j] === AT this ele, AT this tar_m, AT this tar_n, FINAL max_combo
  • init side === 0 (max_nopress, so 0s; below_val)
  • loop ele (forward, NO_ORDER)
  • loop tar_m (forward)
  • loop tar_n (forward)
  • direction
  • j >= zero && k >= one, dp[k][i][j] = ma( dp[i-1][j][k](top, ele_1st), 1 + dp[i-1][j-zero][k-one](diag, init_noval, val(1)) )
  • else, dp[k][i][j] = dp[i-1][j][k](top, ele_1st)
  • https://leetcode.com/problems/ones-and-zeroes/

3 loops; dp_2D, press_ele; dimensions; num_combo(add)

3 loops; dp_2D, press_ele; n dice, n face (ORDER ele), reach tar; num_combo(add)
  • n+1, m+1 size
  • 3D; dp[dice][face][tar] => AT this dice, AT this face, AT this tar, FINAL num_combo(add)
  • 2D, press_ele; dp[i][j] => AT this dice, AT this tar, FINAL num_combo(add)
  • init side => physi_1_1_val (num_combo_press, so 1; below_noval)
  • loop dice (forward)
  • loop tar (forward; ORDER, 1+2, 2+1, diff)
  • loop face (forward; ele)
  • direction
  • j>=k, dp[i][j] = dp[i][j](orig, tar_1st, ORDER; press_ele) + dp[i][j-k(face)](left, num_combo; press_ele) % module;
  • SUMMARY
  • loop1, loop2, loop3 ORDER_DIFF dp[3][2][1]
  • https://leetcode.com/problems/number-of-dice-rolls-with-target-sum


num breaks into sub_num; product, square, formular_etc; max/min

1D; 1 num breaks sub nums; NO_ORDER ele, reach tar; max_product
  • m+1 size
  • dp[j] => AT this num, FINAL max_product
  • init side => 1 (multiply 1)
  • loop ele (forward; NO_ORDER, 12, 21, same)
  • loop tar (forward; dp_ind_constraint)
  • direction
  • dp[j] = MAX(dp[j](top, ele*1st; press*ele), dp[j-i](diag, init_x_formu_var; press_ele; x+y=tar) * i(x*y = max_product)), no_inject_vs
  • https://leetcode.com/problems/integer-break
1D; squares_addup_num; ORDER ele; reach tar; min_combo
  • m+1 size
  • dp[i] => AT this num, FINAL min_combo
  • init side => 0 (min_press, so 0; below_val)
  • loop tar (forward; ORDER? 1^2 + 2^2, affect_next_diff)
  • loop ele (forward; dp_ind_constraint)
  • direction
  • mi = mi( mi, dp[i-j*j](diag, init_noval, val(1); press_ele; x^2+y^2 = tar) + 1 ), inject_vs
  • end_loop_up_dp
  • https://leetcode.com/problems/perfect-squares


cut a rod, dp_recal_constraint

1D; cut a rod, unit_len_value, n*unit_len_value; ORDER ele; reach tar; max_val


(a+b) - (c+d)

2D; NO_ORDER ele (cancel out); reach gen_tar(2d_forward_tar); min_diff(condi)
  • transfer: (a + b) - (c + d), (totTar - aTar) - aTar === diff; ha = sum / 2
  • n+1, ha+1 size
  • dp[i][j] === AT this ele, AT this tar, FINAL condi
  • init side == fake_left_vals (condi_nopress, so trues; below_noval)
  • loop ele (forward; NO_ORDER)
  • loop ha (forward)
  • direction
  • dp[i][j] = dp[i-1][j](top, ele_1st) || dp[i-1][j-i](diag, condi; x+y=ha); ma VS j(sub_tar), inject_vs
  • https://leetcode.com/problems/last-stone-weight-ii/
1D; NO_ORDER ele; (canncel out); reach gen_tar(1d_gen_tar_backward); min_diff
1D; NO_ORDER ele; (add -/+); reach gen_tar(1d_gen_tar_backward); num_combo(add)
1D; backward, curr_overwrite, prev_nochange
  • EG
  • SUMMA
  • dp[0] = 1 (start)
  • dp[i+1] = 1 (push_new_end)
  • dp[j] => j at this num; j=i(backward, 2nd_last), j>0(avoid_head)
  • dp[j] => res
  • out_loop numRow (top -> bottom)
  • dp[0] = 1 (start)
  • dp[i+1] = 1 (push_new_end)
  • in_loop #; j=i(backward, curr_overwrite, prev_nochange; 2nd_last), j>0(avoid_head)
  • dp[j] = dpj-1 + dpj
  • https://leetcode.com/problems/pascals-triangle-ii


child chars(ele); parent chars(tar); action; condi

2D; child chars(ele); parent chars(tar); chop_char_subseq; condi
  • n+1, m+1 size
  • dp[i][j] => AT this child_char; AT this parent_char; FINAL condi(chop_char_subseq);
  • init side => fake_top_vals (each_child_use_diag)
  • loop child (child_1st, each_child_use_diag)
  • loop parent
  • direction
  • if, dp[i][j-1](left, each_child_use_diag) == true, dp[i]j = true
  • if, dp[i-1][j-1](diag, each_child_use_diag) == true && c[i] == p[j](char == char), dp[i]j = true
  • https://leetcode.com/problems/is-subsequence/
1D; child chars(ele); parent chars(tar); child_build_parent; condi
  • m+1 size
  • dp[i] === AT str posi; FINAL condi(from question)
  • init side === true (condi_press, so true; below_noval)
  • loop parent (parent_1st, child_build_parent)
  • loop child
  • direction
  • dp[i] = ( dp[i](orig, tar_1st, ORDER; press_child) || ( dp[i - w_l](left, p_w + c_w == f_w; press_child; w_l + rest = fw_l) && s.sub == w(word_match) ) )
  • https://leetcode.com/problems/word-break


ele; addup to tar; loop_ele, loop_tar; num_combo/min/max

2D; NO_ORDER ele; addup to tar; num_combo(add) (vs min_num_combo)
  • n+1, m+1 size
  • dp[i][j] === AT this ele, AT this tar, FINAL num_combo
  • init side => fake_left_vals (num_combo_nopress, so 1s; below_noval)
  • loop ele (forward; NO_ORDER)
  • loop tar (forward)
  • direction
  • j>=i(w), dp[i][j] = dp[i-1][j](top, ele_1st) + dp[i][j-i(ele)](left, num_combo_left)
  • else, dp[i][j] = dp[i-1]j
  • https://leetcode.com/problems/coin-change-2/
1D; NO_ORDER ele; addup to tar; num_combo(add) (vs min_num_combo)
  • m+1 size
  • dp[j] === AT this tar, FINAL num_combo
  • init side === 1 (num_combo_press, so 1; below_noval)
  • loop ele (forward; NO_ORDER, 1+2, 2+1, same)
  • loop tar (forward, dp_ind_constraint)
  • direction
  • dp[j] = dp[j](top, ele_1st; press_ele) + dp[j-i(ele)](left, num_combo_left; press_ele; x+y=tar);
  • https://leetcode.com/problems/coin-change-2/
2D; NO_ORDER ele; addup to tar; min_num_combo (vs num_combo)
  • n+1, m+1 size
  • dp[i][j] === AT this ele, AT this tar, FINAL min_num_combo
  • init side === 0 (min_nopress, so 0s; below_val)
  • loop ele (forward)
  • loop tar (forward)
  • direction
  • j>=i(w): dp[i][j] = mi( dp[i-1][j](top, ele_1st, NO_ORDER), 1 + dp[i][j-i(ele)](left, num_combo_left) )
  • else: dp[i][j] = dp[i-1][j]
  • https://leetcode.com/problems/coin-change/
1D; NO_ORDER ele; addup to tar; min_num_combo (vs num_combo)
  • m+1 size
  • dp[j] => AT this num, FINAL min_num_combo/-1
  • init side => 0 (min_press, so 0; below_val)
  • loop ele (forward; NO_ORDER, 1+2, 2+1, same)
  • loop tar (forward; dp_ind_constraint, j=w; j<=t)
  • direction
  • dp[j] = MIN(dp[j](top, ele_1st, NO_ORDER; press_ele), 1 + dp[j-i(ele)](left, num_combo_left; press_ele; x+y=tar) )
  • https://leetcode.com/problems/coin-change/


2_start, 2_ending

1D; min_cost_climb; 2_start, 2_ending
  • EG
  • SUMMA
  • dp[i] => i, at each index
  • dp[i] => dp[i], cost so far
  • dp[i-1] => prev_step_1, acc_cost
  • dp[i-2] => prev_step_2, acc_cost
  • dp[x-y] => none
  • dp[0] => init, start_0 (2_start)
  • dp[1] => init, start_1 (2_start)
  • ns[i] => ele, curr_cost
  • loop eles (i=2, i<len)
  • dp[i] = mi(dp[i-1], dp[i-2])(2_start) + ns[i]
  • re mi(dp[len-1], dp[len-2]) (2_ending)
  • https://leetcode.com/problems/min-cost-climbing-stairs
climb, draw_the_tree_cache
  • EG
  • climb, take_1_step or take_2_step
  • SUMMA
  • draw_the_tree_cache
  • init:
  • recur_cache VS dp_arr
  • dp[0]: when_tar_exhaust
  • single_loop:
  • recur_func VS dp_func
  • sub_tars contrib top_tar; count = count + recur(sub_tar)_abstract_return
  • sub_tars_cache
  • https://leetcode.com/problems/climbing-stairs
climb, draw_the_tree_dp
  • EG
  • climb, take_1_step or take_2_step
  • SUMMA
  • draw_the_tree_dp
  • init:
  • dp_arr VS recur_cache
  • dp[0]: when_tar_exhaust
  • outloop:
  • bottom -> top VS top -> bottom -> slow_cover_top
  • inloop:
  • dp_func VS recur_func
  • sub_tars contrib top_tar: dp[tar] = dp[tar-ns[0]] + dp[tar-ns[1]] + dp[tar-ns[2]]... -> dp[tar] = dp[tar]_acc_inloop + dp[tar-ns[i]];
  • avoid_ind_overconsume
  • https://leetcode.com/problems/climbing-stairs























=============================================================================

dp (real_understanding)

dp, order !important (ele -> tar)

arr*to_2_equal_sum_part; order !important (ele -> tar)
  • EG
  • SUMMA
  • method 1:
  • draw_the_tree_no_cache
  • knapsack recur; recur_as_loop_i
  • method 2:
  • draw_the_tree_2d_cache
  • knapsack recur, recur_as_loop_i
  • method 3:
  • 2d_cache
  • same as above, 2d_cache(dp[i][tar] == dp[tar][i])
  • method 4:
  • 2d_cache
  • combination_sum recur, no recur_as_loop_i
  • method 5:
  • 2d_cache
  • tar -> ele (order important; want_more dp[..][len])
  • ele -> tar (order !important; want_less dp[..][j-1]; loop_order_can_swap) <--
  • method 6:
  • 2d_cache
  • tar -> ele (order important; want_more dp[..][len]) <--
  • ele -> tar (order !important; want_less dp[..][j-1]; loop_order_can_swap)
  • method 7:
  • 1d_cache
  • backward_loop, use_prev_dp; forward_loop, overwritten_prev_dp
  • see my solution: https://leetcode.com/submissions/detail/468284357
  • https://leetcode.com/problems/partition-equal-subset-sum





dp, order important (tar -> ele)

combo_sum_4; order_important (tar -> ele)
  • EG
  • SUMMA
  • method 1:
  • draw_the_tree_no_cache(timeout); recur_abstract_return
  • method 2:
  • 1d_cache
  • draw_the_tree_cache; recur_abstract_return
  • method 3:
  • 2d_cache
  • tar -> ele (order important; want_more, dp[..][j-1]) <--
  • ele -> tar (order !important; want_less, dp[..][len]; loop_order_can_swap) x
  • method 4:
  • 1d_cache
  • forward_loop, no_overwritten_prev_dp (dp[..][len])
  • method 5:
  • 1d_cache
  • backward_loop, use_prev_dp
  • my solution: https://leetcode.com/submissions/detail/468503374/
  • https://leetcode.com/problems/combination-sum-iv
buy sell stock k_tran = unlimit; recur == dp, some_param == dp_ind, ele == ele





curr = (con_subarray || startover_subarray) + ele

max_subarray; curr = (con_subarray || startover_subarray) + ele
buy_low_sell_high_once;





brute_force; all_step map 2D dp;

find palindrome in substr; brute_force; all_step map 2D dp;





brute_force; at curr_i, look left, look right

how many < curr_i; brute_force; at curr_i, look left, look right





2pt (i_start, j_end)

reverse group eles in arr; build_fresh; easier
trap rain water; max_hold_most_water (left), max_hold_most_water (right)
rev_each_word, keep space; i_start, j_end; rev_a_word
even num on left, odd num on right; skip_loop (hit odd), skip_loop (hit even), swap; even_left, odd_right (in place)
even num on left, odd num on right; build_fresh, i_write (start), j_write (end), n_read; left_partition_even, right_partition_odd (fresh)
is palindrome; i_start == j_end, cross; brute_force





2pt, i_start, j_start

even num at even ind, odd num at odd ind; build_fresh (easier), i_write (start), j_write (start), n_read; even at even, odd at odd





2pt, i_start, j_start (extending)

subarray_sum == k (+); i_start, j_start (extending); range
consecutive chars len >= 3; i_start, j_start (extending); range





2pt, i_end, j_end (extending)

count last word len; 2pt, i_end, j_end (extending)





2pt (i, i+len)

rev str in k; 0->k rev, k->2k no; question_ask
[1, 2, 3, 4] -> [2, 4, 4, 4]; one 2, then three 4; i = i+2_len (question_show)
[2, 3, 1, 1, 1] -> [1, 1, 1, 2, 3]; i, i+len/2 (i vs i+len/2, then slide)
[2, 3, 1, 1, 1] -> [1, 1, 1, 2, 3]; i, i+len/2 (i vs i+len/2, then slide)





2pt (no-check-self, 2_loop)

longest substr palindrome; 2pt (no-check-self, 2_loop)





2pt (lo -> small, hi -> large)

IDID, pool: [0, 1, 2, 3, 4_len] -> [0_I, 4_D, 1_I, 3_D, 2_last]; lo -> small, hi -> large





3pt (i_start, j_end-1, k_end*; look for large)

find how many ele_1 + ele_2 == ele_3; i_start + j_end-1 == k_end* (look for large)
in arr, a^2 + b^2 == c^2; i_start + j_end-1 == k_end* (look for large)





3pt (i_start*, i_start+1, j_end; make it small)

3sum, ele_1 + ele_2 + ele_3 == 0; i_start* + i_start+1 + j_end == 0 (make it small)





3pt (i*, i+1, i+2_con)

local_inv == global_inv; i*, i+1, i+2_con; question_ask





3pt (i-2, i-1, i*; backward)

[1, 3, 5, 4, 4] -> 1, 3, 5 (all_odd); i-2, i-1, i*





3pt (i-1, i*, i+1; mid)

zig zag; [1, 2, 3, 4, 5] -> [1, 3_max, 2, 5_max, 4]; i-1, i, i+1; i max swap; max_top
a?c -> abc, fill ? so no repeat (consecutive); i-1, i*, i+1; inc "a" to 26 char;
a?c -> abc, fill ? so no repeat (consecutive); i-1, i*, i+1; inc "a" to "c";





4pt (i_start, i_start+1, j_end-1, j_end ===> i_start, j_end-1 OR i_start+1, j_end)

if not palindrome, rm 1 char; i_start, i_start+1, j_end-1, j_end ===> i_start, j_end-1 OR i_start+1, j_end





i_stable, j_loop, exhaust

find minimum platforms (train start, end time); cross_compare; deakin_experience
0011 -> 01, 0011 (2 count); i_stable, j_loop, exhaust; i_start, j_end (check valid)





instead of count same_type, count as go; eventually add up

aaaba; "a" 4, "aa" 2, "aaa" 1, "b" 1, so 8; i_stable, j_loop, exhaust (instead of count same_type, count as go)





brute_force; i_stable, j_stable, k_loop

3sum_less_k, count; i_stable, j_stable, k_loop





brute_force; efficiency, no-met-skip

longest substr palindrome; brute_force; efficiency, no-met-skip





skip_loop

skip_loop (space, then char)

skip_loop (space, then char)
  • EG
  • SUMMA
  • ...
skip_loop (space, then dot)





skip_loop (i_start, j_end)

skip_loop (i_start, hit a e i o u; j_end, hit a e i o u)
skip_loop (i_start, hit letter; j_end, hit letter)





skip_loop (up_hill, down_hill)

valid mountain; skip_loop (up), skip_loop (up, backward); form mountain
buy low (down_hill), sell high (up_hill);





gap

[1, 2, 3, 4, 5, 10, 100, 1000], lo=5, hi=10 -> missing_range, [6->9]; gap -> missing_range





find consecutive; (i_start, j_end) vs (either con or reset); both can work






what does "sort" mean?

[3, 3, 3, 1, 1, 1, 2, 2, 2]; sort -> curr_ind === how many smaller than you
[100, 99, 1, 2] -> [1, 2, 99, 100]; sort -> neighbour shortest





deal with left, deal with right;

curr rating high > neighbours --> left neighbours, right neighbours; curr i
  • EG
  • SUMMA
  • curr rating high > neighbours --> left neighbours (look_back, preserve prev), right neighbours (look_back, preserve prev); curr i max
  • https://leetcode.com/problems/candy
trap rain water; max_hold_water (brute_force, left), max_hold_water (brute_force, right); curr i
trap rain water; max_hold_water (dp left), max_hold_water (dp right); curr i
curr i > left, curr i < right; left_max (dp left), right_max (dp right); curr i





brute_force; dp[ind][can_buy][tran] = buy or no_action; dp[ind][can_buy][tran] = sell or no_action; k_tran = 1, 2, k, unlimit

dp[ind][can_buy][tran] = buy or no_action; dp[ind][can_buy][tran] = sell or no_action; k_tran = 1
dp[ind][can_buy][tran] = buy or no_action; dp[ind][can_buy][tran] = sell or no_action; k_tran = 2
dp[ind][can_buy][tran] = buy or no_action; dp[ind][can_buy][tran] = sell or no_action; k_tran = k
dp[ind][can_buy] = buy or no_action; dp[ind][can_buy] = sell or no_action; k_tran = unlimit (no care)





combo_sum; (1) i (2) i+1 (3) i+1 && len (4) draw_the_tree

combo_sum; (1) i (2) i+1 (3) i+1 && len (4) draw_the_tree

combo_sum_1; i
combo_sum_2; i+1
combo_sum_3; i+1 && len
combo_sum_4; draw_the_tree


3sum_less_k (count); k_stable; i, j meet
3sum_less_k (count); k_stable; i, j meet
3sum_less_k (absolute_distance); k_stable; i, j meet





j_read (explode), i_write (move forward); build_from_ground

reverse words in str; rev_whole, rev_each, no_space; whole then small_modify
reverse words in str; rev_whole, rev_each, no_space; whole then small_modifya good __ example " -> "example good a"; rev_whole, rev_each_word, no_extra_space
[1, 1, 2, 2, 3, 3] (sort) -> [1, 2, 3]; i_write (correct_posi), j_read (explode)
rm ele, [3, 2, 2, 3] -> [x, 2, 2, x]; i_write (correct_posi), j_read (explode)
move zeros to end, [0,1,0,3,12] -> [1, 3, 12, 0, 0]; i_write (correct_posi), j_read (explode)
ns1 = [5, 6, 0, 0, 0], m = 2, ns2 = [1, 2, 3], n = 3 -> [1, 2, 3, 5, 6]; i_read (explode), j_read (explode), k_write (correct_posi)





rm 2 chars, new dup;

"abba" -> "aa" -> ""; rm 2 chars, new dup; j_read (explode), i_write (back / forward); build_from_ground
"abba" -> "aa" -> ""; rm 2 chars, new dup; redo
"abba" -> "aa" -> ""; rm 2 chars, new dup; stack (close ele move together)





greedy

[2, 3]_child, [1, 10]_cookie; sort; can this cookie feed this child?





ind = num % len

distribute candy; candy_n = 10, [1, 2, 3]_order -> [5, 2, 3]; ind = num % len; distribute





is_palindrome (1) compare now (2) compare later (final == final)

is_palindrome; abba; (1) compare now
is_palindrome; 121 -> 121; (2) compare later (final == final)





palindr subseq (start, end same; non-con), rm 1 go

rm palindr subseq until ""; palindr subseq (start, end same; non-con), rm 1 go





palindrome 2 sides + mid;

find palindrome in substr; palindrome 2 sides + mid;





prev_digit = input / 10; curr_digit = input % 10;

sum of min num; prev_digit = input / 10; curr_digit = input % 10; brute_force





len / num = each, len % num = remain;

" this is a sentence " -> "this is a sentence__"; len / num = each, len % num = remain; combine_words





full_len - ind == rest_len

12345678 -> 12.345.678; full_len - ind == rest_len; rest_len % 3 == 0





chg_sth, become_old_question

3sum; ele + 2sum_hash_prev (chg_sth, become_old_question)
3sum_less_k; ele + 2sum_less (chg_sth, become_old_question)
2part_equal; half_sum + combination_sum_2; (chg_sth, become_old_question)





inverse_question; when saying true, false, yes, no; inverse

local_inv_num == global_inv_num; means only local_inv exist (inverse_question)





slide_window

longest no repeated, "abcbk" -> chop "abc" -> "bk"; brute_force, str_tmp (indexOf), income_char dup?
longest no repeated, "abcbk" -> chop "abc" -> "bk"; brute_force, hash (unique), income_char dup?
longest no repeated, "abcbk" -> chop "abc" -> "bk"; tmp_str (indexOf), right_end bit by bit, left_end indexOf reduce
(1) all_the_way: [1, 2, 3, 4], k = 10; (2) presum: [1, 2, 3, 4], k = 9; tmp_arr, right_end bit by bit, left_end loop reduce
[1, 2, 3, 7, 5], tar = 12; tmp_sum, right_end bit by bit, left_end loop reduce
longest no repeated, "abcbk" -> chop "abc" -> "bk"; right_end bit by bit, left_end hash reduce
[1, 2, 3, 4], k = 10, product < 10; [1], [1, 2], [2], etc; slide_win, right_end bit by bit, left_end loop reduce;
[1,7,3,6,5,6], left_win = 11, pivot = 6, right_win = 11, left_win == right_win;
list
https://www.1point3acres.com/bbs/thread-678970-1-1.html





2_sort_subarr

2_sort_subarr

merge 2_sort_arr; i_forward_backward (r), j_forward_backward (r), k_forward_backward (w)
sqt sort_arr; 2_sort_subarr; i_f_b (r), j_f_b (r), k_f_b (w)





hash (what the truth?)

  • EG
  • SUMMA
    1. past, inject
    1. freq





hash (freq)

[0, 1, 0, 2, 1] -> [0, 0, 1, 1, 2]; no sort, hash (freq), build_from_groud





hash (met_before)

"gfg" -> "gf", rm duplicated; hash (met_before)





hash (1 to 1, 2 hash)

aba -> dog cat dog (good); aba -> dog cat cat (bad); 1 to 1, 2 hash





set (unique)

set (unique)
  • EG
  • SUMMA





set (set1.size == set2.size)

aba -> dog cat cat (bad); set (set1.size == set2.size)





max represent entire subarr

[1, 2, 17, 1, 2], 17 is leader >= everything at right; max represent entire subarr
[2,3,5,1,3]_candy, extra = 3; a[i] + extra > max; max represent entire subarr
global_inv_num == local_inv_num; next_each....; max represent entire subarr





suggest while typing

suggest while typing; each_char == level_of_filter
suggest while typing; s.startsWith (prefix)
suggest while typing; ind causes l, r to bound (binary search)





binary search

search_insert_position; binary search (outbound vs inbound)
find square root of 8; ind*ind is square
is 16 a perfect square; ind*ind is square
[g, g, g, g, b, b, b] -> left most vs right most
pick > guess or pick < guess; ~= first bad version
2sum (sorted); ele_i = tar - ns[i] (arr1 binary_search arr2, l_dynamic, r_dynamic)
2sum (sorted); ele_i = tar - ns[i] (arr1 binary_search arr2, 2sum)
arr1, arr2, find intersection eles, unique; (unique, binary search left most)
arr1, arr2, find intersection eles, repeated; (brute_force, binary search left most)
[0, 1, 2_pivot, 3, 4] -> shift left [2, 3, 4, 0, 1] -> shift right [3, 4, 0, 1, 2];
binary search unknown size; step*2





limited ele -> build_from_groud

sort [0, 0, 2, 2, 1, 1] (only 0, 1, 2) -> [0, 0, 1, 1, 2, 2]; limited_ele -> build_from_ground





equal k problem

[-2, -1, 0, 4, 1, 2], find all subarr == k; brute_force, single_ele is subarr, extend is subarr
[-2, -1, 0, 4, 1, 2], find all subarr == k; 2_diff: pre_sum_2 - pre_sum_1 = tar
2sum (once out); 2_sum: ele_2 + ele_1 = tar; hash (direct_prev) -> hash (related_prev)
2sum (repeated, find all pair); brute_force
2sum (repeated, find all pair); hash (direct_prev) -> has (related_prev)
2sum (repeated, find distinct pair); i_start, j_end + skip_loop (remove repeated)
2sum (repeated, find distinct pair); a+a = tar (a once) OR a+b = tar (a many times, but b once), hash (freq)
2sum (less than k, return max sum); 2pt, i and j meet





ind = presum diff; ind = presum%mod

tar = 7, [0, 7, 8], how_many = tar?; all_the_way vs hash(ind = presum_diff); hash(set 1/+1)
tar = 7, [0, 7, 8], max_len (== tar); all_the_way vs hash(ind = presum_diff); hash (posi)
mod = 7, [0, -7, -8], how_many%7?; all_the_way vs hash(ind = presum%mod); hash (set 1/+1)
mod = 7, [0, 7, 8], >= 2 ele % 7?; all_the_way vs hash(ind = presum%mod); hash(posi)
[3, 1, 2, 5, 3], k = 3_odd -> [1, 1, 0, 1, 1], k = 3; all_the_way vs hash(ind = presum_diff); hash(set 1/+1)
[0, 1, 1, 0, 1], k_sum = 3; all_the_way vs hash(ind = presum diff); hash(set 1/+1)
https://leetcode.com/discuss/general-discussion/563022/prefix-sum-problems
DC leetcode 3, 300
other lists: https://github.com/CyC2018/CS-Notes/blob/master/notes/Leetcode%20%E9%A2%98%E8%A7%A3%20-%20%E7%9B%AE%E5%BD%95.md





comparator; (1) a_sub vs b_sub (sub) (2) a vs b (individual) (3) ab vs ba (combo)

["dig1 8 1 5 1", "let1 art can"]; "8 1 5 1" vs "art can"; a_sub vs b_sub (sub)
[1, 20, ...] -> 120 vs 201; ab vs ba (combo)





char in substr, substr in sentence

code and shopping vcart; char in substr (order), substr in sentence (order, gap)





slide (exhaust), then extend (match)

code and shopping vcart; slide (exhaust), then extend (match);
find substr in sentence; slide (exhaust), then extend (match)





is myself part of others (include self)?

is substr of another string; is myself part of others (include self)?





(1) 1 on 1 exact_match (2) extend_match (3) false

abc (i) -> long press -> aaabbbccc (j); (1) 1 on 1 exact_match (2) extend_match (3) false





partition

++++ -> [--++, +--+, ++--], combo#; partition, i, i+1, partition





look_back






look_forward






continue (reaching), reset (reached)

aabbccc, max = 3; continue (leading_char), reset (diff_char)
[1, 2, 3, 6, 6] -> [1, 2, 3], [6], [6]; continue (!part_sum), reset (part_sum)
APAPLLL, 2A (non-con) or 3L (con), no award; single_loop, continue (LLL), reset (LLA)
[1, 2, 3, 1], 1->2->3 inc, max_freq=3; continue (inc), reset (desc)
count and say, 21 -> 1211; continue (past vs curr), reset (past, curr, curr_tobe_past)





income_ele chg internal_ele prop (odd/even)

income_ele chg internal_ele prop (odd/even)





direct_cancel (...)

is anagram; direct_cancel (vertical, similar_but_diff_posi)
n = 5 -> [-2, -1, 0, 1, 2]; n = 4 -> [-2, -1, 1, 2]; direct_cancel (horizontal, similar_but_diff_posi)
s1 = cba, s2 = abcabc, build s1 from s2; direct_cancel (diff_pool_size, similar_but_diff_posi)





delay_cancel (eventuall_balance, similar_but_diff_posi)

is anagram; delay_cancel (eventuall_balance, similar_but_diff_posi)
[a, b], [c, d], [b, c] -> sort [a, b], [b, c], [c, d]; delay_cancel ([in, out], similar_but_diff_posi)
baabb -> abbba; palin (odd) -> cancel -> 1 left; palin (even) -> cancel -> 0 left





greedy_cancel

RLLRRL -> RLLR + RL, res = 2; or RLLRRL -> RL + LR + RL, res = 3 (max); greedy_cancel (similar_but_diff_posi)





moving -> coordinate

NESWW (north, east, south, ...), cross any point; moving -> coordinate
robot at (0, 0), UULDDR (up, up, left...), back to (0, 0); moving -> coordinate





symmetric

00011 -> 0011, 01, total = 2; 0(0011) min_symmetric





treeMap (static)

treeMap (static)





treeMap (keep injecting)

treeMap (keep injecting)





my-calendar

intersect formular (3 mid block)
intersect formular (top + bottom block);
my-calendar-0 (count === 1, single booking)
  • EG
  • SUMMA
  • just fyi
my-calendar-i (count >= 2, double booking)
my-calendar-ii (count >= 3, tripple booking)
  • EG
  • SUMMA
  • method 1:
  • 1st_booking (mem1), 2nd_booking (mem2, do_merge), 3rd_booking (tripple booking); 3 mid block
  • each mem hold all income; each mem represents own state
  • method 2:
  • treeMap (keep injecting); inject (no_matter), good_keep, bad_out
  • https://leetcode.com/problems/my-calendar-ii
my-calendar-iii (count >= k, k booking);





meeting room

meeting room 1 (mini_platform); treeMap (static)
meeting room 2 (mini_platform), what is min room needed? treeMap (static)
meeting room 3 (my calendar 1, 2, 3); treeMap (keep injecting)





minimum platform / car_pooling; treeMap (static)

minimum platform; treeMap (static)
bus, [persons, start_time, end_time], counter = 4; treeMap (static)





overlap (become 1, with_merge)

[[1, 3], [2, 6], [8, 10], [15, 18]] -> [[1, 6], [8, 10], [15, 18]]; overlap (become 1, with_merge)





overlap (become 1, with_small)

[[1, 2], [1, 3], [2, 3], [3, 4]] -> [[1, 2], [2, 3], [3, 4]]; (become 1, with_small)
shooting balloon; overlap (become 1, with_small)





min is max strength

LOOnBALxBALLpOOn; h {b:3, a:3, l:3, o:3, n:3} -> h {b:3, a:3, l:3/2, o:3/2, n:1}, so 1; min is strength (min is strength)
LOOnBALxBALLpOOn; h {b:3, a:3, l:3, o:3, n:3} -> h {b:2, a:2, l:1, o:1, n:2}, so 1; min is strength (rm_same_time)





swap, then equal

candy swap; swap, then equal





straight line slope; dy / dx = (y1 - y) / (x1 - x)

straight line slope; dy / dx = (y1 - y) / (x1 - x)
[0, 100] -> [0, 1]; diag to hor / ver (diag cover hor / ver); then straight_line; shortest;





sort

bubble_sort

example 1; 1 iteration, push 1 bubble to end
  • 1 iteration, push 1 bubble to end
example 2; if anything not sort, bubble continue
  • if anything not sort, bubble continue





backtrack

i vs (i+? and res_inds);

  • i vs (i and res_inds);
  • i vs (i+1 and res_inds);
  • i vs (0 and res_inds);
combo_sum_1; i vs (i and res_inds);
  • EG
  • combo_sum_1, ns = [2,3,6,7], tar = 7, res = [[2,2,3],[7]]
  • SUMMA
  • sort_rm_dup
  • bt(final_res, tmp_arr, ns_orig, curr_i, tar)
  • recur_stop_check: tar_reach || tar_overconsume
  • recur:
  • single_loop (i vs i and res_inds)
  • before_op, look_back, sort_rm_dup
  • tmp_arr_new = tmp_arr.concat(ns[i]) (concat)
  • bt (tar_desc) (0_repeat_entire_x; i-1_x; i_no_repeat + include_self; i+1_miss_self_x)
  • https://leetcode.com/problems/combination-sum
combo_sum_2; i vs (i+1 and res_inds);
  • EG
  • combo_sum_2; ns = [2,5,2,1,2], tar = 5, res = [[1,2,2], [5]];
  • SUMMA
  • sort_rm_dup
  • bt(final_res, tmp_arr, ns_orig, curr_i, tar)
  • recur_stop_check: tar_reach || tar_overconsume
  • recur:
  • single_loop (i vs i+1 and res_inds)
  • tmp_arr_new = tmp_arr.concat(ns[i]) (concat)
  • bt_recur_abstract_return(tar_desc) (0_repeat_entire_x; i-1_x; i_repeat_self_x; i+1_avoid_self + res)
  • https://leetcode.com/problems/combination-sum-ii
combo_sum_3; i vs (i+1 and res_inds);
  • EG
  • combo_sum_3; ns = [1, 2, 3, ... 9], k_len = 3, tar = 7, res = [[1,2,4];
  • SUMMA
  • sort_rm_dup
  • ns_orig = [1, 2, 3, 4, 5, 6, 7, 8, 9] (new_part)
  • bt(final_res, tmp_arr, ns_orig, curr_i, tar)
  • recur_stop_check: tar_reach + len_reach || tar_overconsume or len_overconsume
  • recur:
  • single_loop (i vs i+1 and res_inds)
  • tmp_arr_new = tmp_arr.concat(ns[i]) (concat)
  • bt_recur_abstract_return(tar_desc) (0_repeat_entire_x; i-1_x; i_repeat_self_x; i+1_avoid_self + res)
  • https://leetcode.com/problems/combination-sum-iii
combo_sum_4; i vs (i+1 and res_inds);

About

No description, website, or topics provided.

Resources

Readme
Activity

Stars

0 stars

Watchers

0 watching

Forks

0 forks
Report repository

Releases

No releases published

Packages

No packages published

Languages

  • JavaScript 100.0%