claytonjwong

//
// BUBBLE-SORT
//
// loop-invariant:
//
// the right-most i elements are the largest i elements in A[0:N), 0<=i<N
// sorted in ascending order
//
void bubble_sort1(vector<int>& A){
    bool swapped;

claytonjwong

template< typename T >
class Solution
{
    using Vector = vector< T >;
    using Iter = typename Vector::iterator;

    Vector go( Vector&& A )
    {
        auto N{ A.size() };
        if( N < 2 ) return A;

claytonjwong

2-Dimensional Arrays

How to create and initialize 2D arrays of integers with:

• M rows
• N columns
• X initial value

C

• Designated-Inits

int dp[M][N] = { [0 ... M-1] = { [0 ... N-1] = X } };

claytonjwong

/*
 * Javascript version of C++ equal_range via lower_bound and upper_bound
 *
 * Gist: https://gist.github.com/claytonjwong/53bd1c1489b12eccad176addb8afd8e0
 */

let lowerBound = (A, T) => {
    let N = A.length,
        i = 0,
        j = N;

claytonjwong

/*

Heap Property:

* MinHeap: For every object x, the key of x is <= the keys of its children
* MaxHeap: For every object x, the key of x is >= the keys of its children

----------------------------------------------------------------------------------------------------

Insert:

claytonjwong

/*
 * Kotlin version of C++ equal_range via lower_bound and upper_bound
 *
 * Gist: https://gist.github.com/claytonjwong/2f9c3b33f8697d77a1d442006d4947d6
 */

fun lowerBound(A: IntArray, target: Int): Int {
    val N = A.size
    var i = 0
    var j = N

claytonjwong

let permutations = A => {
    let N = A.length;
    let perms = [];
    let go = (i = 0) => {
        if (i == N) {
            perms.push([...A]);
            return;
        }
        for (let k = i; k < N; ++k) {
            [A[i], A[k]] = [A[k], A[i]];

claytonjwong

fun permutations(A: IntArray): Array<IntArray> {
    var N = A.size
    var perms = mutableListOf<IntArray>()
    fun go(i: Int = 0) {
        if (i == N) {
            perms.add(A.copyOf())
            return
        }
        for (k in i until N) {
            A[i] = A[k].also{ A[k] = A[i] }

claytonjwong

//
// Recursively change each node of the linked list such that next
// is the last node seen during a linear scan of the linked list.
//
class Solution {
public:
    using fun = function<ListNode*(ListNode*, ListNode*)>;
    ListNode* reverseList(ListNode* head) {
        fun go = [&](auto node, auto last) {
            auto next = node->next;

claytonjwong

#
# Recursively change each node of the linked list such that next
# is the last node seen during a linear scan of the linked list.
#
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        def go(node = head, last = None):
            next = node.next
            node.next = last
            if not next: