All posts for the month April, 2024

common string

Find longest common string between strA and strB
for each char in strA, we find its location in strB.
This is a 2D array, strA at row -1, strB at colum -1, e.g. eab
We use colum major, with subarray being one colum.

See findCommonStrUtil. We could initialize all to 0 first, or initialize along the way.
For each common char, e.g. b:b, it number means the longest common ending at b.
    it's its upper-left + 1, here is a:a + 1  = 2
e.g.
            a b c
        e   0 0 0
        a   1 0 0
        b   0 2 0
Notes: suffix tree can also do it, but overkill.
Download: http://riowing.net/p/wp/string.cpp

Rotate Vector

meRotateVectorUtilInplace(vector& aInput, int iSteps)
is to rotate to the right iSteps, in place
for Input: 1 2 3 4 5 6 7 8 9
the last 3 spots are used as buffer, which keeps replacing the left first 3, then second 3… by swap.
we swap pDst and pSrc, pDst is on the left, pSrc start with 7, the start of buffer. we swap until end().
on next round, we just move pSrc back to the start of buffer, which is pHead, the start of buffer.
pDst reaching start of buffer means we are done, like the 3d from last.
when only portion of buffer is move to the left, due to pDst has been to close to buffer, we shrink the buffer and keep going, buy setting hHead.

Input: with iSteps 2 : 1 2 3 4 5
    aInput: 4 5 3 1 2
    pSrc reset to 1
    only portion of buffer is used, reset pHead, the start of shinked buffer, to 2
    aInput: 4 5 1 2 3
    pSrc reset to 3
    output: 4 5 1 2 3
    started i = 3

Input: with iSteps 3 : 1 2 3 4 5
    only portion of buffer is used, reset pHead, the start of shinked buffer, to 5
    aInput: 3 4 5 2 1
    pSrc reset to 1
    aInput: 3 4 5 1 2
    pSrc reset to 2
    output: 3 4 5 1 2

Download: http://riowing.net/p/wp/SpiralMatrix.cpp

rotate matrix

Rotate to the right here. Done in two ways.

leet46RotateImageUtil reposition 4 elements:
always x becomes y, y becomes last – y. [x,y]->[last-y,x]
always [i][j] going to [j][n – i – 1]. start with filling i,j with [n – j – 1][i]

leet46RotateImageUtilFlip
flip horizontally. loop the left half of the matrix
midX = iSizeX / 2 < midX is right for both even and odd number of colums, swap i and iSizeX – 1 – i
flip diagonal to the lower right. loop the upper left half, for row, it’s j < iSizeY – i so that for first colum, we want the bottom element.
swap [j][i] and [iSizeX – 1 – i][iSizeX – 1 – j]
note swap [x,y] and [y,x] is for flipping to the lower left.

Download: http://riowing.net/p/wp/SpiralMatrix.cpp

by Rio Wing on April 14, 2024 • Permalink

Posted in algo

Tagged matrix

Posted by Rio Wing on April 14, 2024

https://riowingwp.wordpress.com/2024/04/14/rotate-matrix/

TicTacToe

The goal of CTicTacToe is to check if:
1. the move is legal
2. winner declared

Key data:
CBoard is an union for easier access to bits and check the value of the whole number.
The board is 3×3. total 18 bits, 9 bits for one player
e.g. maBoards[0] has bitset<9> to track one player.
All 8 winning patterns pre-calculated in maWinningPatterns[8]
check winner by bit AND & maBoards[] and maWinningPatterns[] equals to maWinningPatterns[]
for each move to be legal, maBoards[ePlayer].maBitsStatus[iIndex] has to be 0

Rio Wing's Tech Blog

All posts for the month April, 2024

common string

Rotate Vector

rotate matrix

TicTacToe

Recent Posts

Archives

Categories