Algorithm --- 2D array mesh migration (kotlin)

subject

1260. Two dimensional grid migration
      To give you one m That's ok n Two dimensional grid of columns grid And an integer k. You need to grid transfer k Time .

Every time 「 transfer 」 The operation will trigger the following activities ：

be located grid[i][j] The element will be moved to grid[i][j + 1].
be located grid[i][n - 1] The element will be moved to grid[i + 1][0].
be located grid[m - 1][n - 1] The element will be moved to grid[0][0].
Please return k The final result after the migration operation Two dimensional meshes .

Example 1：

Input ：grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1
Output ：[[9,1,2],[3,4,5],[6,7,8]]
Example 2：

Input ：grid = [[3,8,1,9],[19,7,2,5],[4,6,11,10],[12,0,21,13]], k = 4
Output ：[[12,0,21,13],[3,8,1,9],[19,7,2,5],[4,6,11,10]]
Example 3：

Input ：grid = [[1,2,3],[4,5,6],[7,8,9]], k = 9
Output ：[[1,2,3],[4,5,6],[7,8,9]]

Tips ：

m == grid.length
n == grid[i].length
1 <= m <= 50
1 <= n <= 50
-1000 <= grid[i][j] <= 1000
0 <= k <= 100

Solutions

Except for the first Every other bit is set to next Finally, set the last digit of the two digit array to the first digit

resolvent

    fun shiftGrid(grid: Array<IntArray>, k: Int): List<List<Int>> {
    
        val height = grid.size
        var width = if (grid.isNotEmpty()) grid[0].size else 0
        var next = 0
        for (i in 1..k) {
    
            grid.forEachIndexed {
     index, ints ->
                ints.forEachIndexed {
     index2, i ->
                    //
                    if (index == 0 && index2 == 0) {
    
                        next = i
                    } else {
    
                        var temp = i
                        grid[index][index2] = next
                        next = temp
                        if (index == height - 1 && index2 == width - 1) {
    
                            grid[0][0] = next
                        }
                    }
                }
            }
        }

        var result = ArrayList<List<Int>>()

        grid.forEach {
    
            val element = ArrayList<Int>()
            result.add(element)
            it.forEach {
    
                element.add(it)
            }
        }
        return result
    }

Method 2 Convert to a one-dimensional array

    fun shiftGrid(grid: Array<IntArray>, k: Int): List<List<Int>> {
    
        val heightT = grid.size
        var widthT = if (grid.isNotEmpty()) grid[0].size else 0

        var result = ArrayList<ArrayList<Int>>()
        grid.forEach {
    
            val element = ArrayList<Int>()
            result.add(element)
            it.forEach {
     _ ->
                element.add(0)
            }
        }

        grid.forEachIndexed {
     height, ints ->
            ints.forEachIndexed {
     width, i ->
                var newIndex = (height * widthT + width + k) % (heightT * widthT)

                result[newIndex / widthT][newIndex % widthT] = i
            }
        }
        return result
    }

summary

1. It can also be converted to a one-dimensional array

2. Pay attention to... During conversion
var newIndex = (height * widthT + width) + (k % (heightT * widthT))
It can't be written like this Because of this newIndex The array may be out of bounds
For example, a total of 60 A place He was in 59 Let him move 73 According to the above algorithm The new location is 59 + 13 Across the border
Unless you take another mold
var newIndex = ((height * widthT + width) + (k % (heightT * widthT))) % (heightT * widthT)
You should let him move first k Then touch