Skip to content

Latest commit

 

History

History
4729 lines (3756 loc) · 112 KB

readme.md

File metadata and controls

4729 lines (3756 loc) · 112 KB
Raw

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);