Input: n = 1
Output: true
Explanation: 2^0 = 1

class Solution {
    fun isPowerOfTwo(n: Int): Boolean {
        if (n == 0) return false
        val x = n.toLong()
        return (x and -x) == x
    }
}

Input: n = 1
Output: 10

class Solution {
    fun knightDialer(n: Int): Int {
        val MOD = 1000000007
        val moves = arrayOf(
            intArrayOf(4, 6),
            intArrayOf(6, 8),
            intArrayOf(7, 9),
            intArrayOf(4, 8),
            intArrayOf(0, 3, 9),
            intArrayOf(),
            intArrayOf(0, 1, 7),
            intArrayOf(2, 6),
            intArrayOf(1, 3),
            intArrayOf(2, 4)
        )
        
        var dp = IntArray(10) { 1 }
        
        for (step in 1 until n) {
            val newDp = IntArray(10)
            for (i in 0 until 10) {
                for (move in moves[i]) {
                    newDp[move] = (newDp[move] + dp[i]) % MOD
                }
            }
            dp = newDp
        }
        
        return dp.fold(0) { acc, count -> (acc + count) % MOD }
    }
}

Input: file = "abc", n = 4 Output: 3
buf после вызова должен содержать "abc".

class Solution {
    fun read(buf: Array<Char>, n: Int): Int {
        var copiedChars = 0
        var readChars = 4
        val buf4 = Array(4) { ' ' } 

        while (copiedChars < n && readChars == 4) {
            readChars = read4(buf4)

            for (i in 0 until readChars) {
                if (copiedChars == n) {
                    return copiedChars
                }
                buf[copiedChars] = buf4[i]
                copiedChars++
            }
        }
        return copiedChars
    }

    private fun read4(buf4: Array<Char>): Int {
        return 0
    }
}

Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

class Solution {
    fun generate(numRows: Int): List<List<Int>> {
        val triangle = mutableListOf<List<Int>>()

        for (rowNum in 0 until numRows) {
            val row = MutableList(rowNum + 1) { 0 }
            row[0] = 1
            row[row.lastIndex] = 1

            for (j in 1 until row.size - 1) {
                row[j] = triangle[rowNum - 1][j - 1] + triangle[rowNum - 1][j]
            }

            triangle.add(row)
        }

        return triangle
    }
}

Input: n = 4
Output: [2,1,4,3]

class Solution {
    fun beautifulArray(n: Int): IntArray {
        return construct(n).toIntArray()
    }
    
    private fun construct(n: Int): List<Int> {
        if (n == 1) return listOf(1)
        val odd = construct((n + 1) / 2).map { 2 * it - 1 }
        val even = construct(n / 2).map { 2 * it }
        return odd + even
    }
}

Input: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","good"],["fine","good"],["drama","acting"],["skills","talent"]]
Output: true

fun areSentencesSimilar(sentence1: Array<String>, sentence2: Array<String>, similarPairs: List<List<String>>): Boolean {
    if (sentence1.size != sentence2.size) {
        return false
    }
    
    val graph = mutableMapOf<String, MutableList<String>>()
    for (pair in similarPairs) {
        val (x, y) = pair
        graph.computeIfAbsent(x) { mutableListOf() }.add(y)
        graph.computeIfAbsent(y) { mutableListOf() }.add(x)
    }
    
    fun dfs(word1: String, word2: String, visited: MutableSet<String>): Boolean {
        if (word1 == word2) {
            return true
        }
        visited.add(word1)
        for (neighbor in graph[word1].orEmpty()) {
            if (neighbor !in visited && dfs(neighbor, word2, visited)) {
                return true
            }
        }
        return false
    }
    
    for (i in sentence1.indices) {
        if (sentence1[i] != sentence2[i]) {
            if (!dfs(sentence1[i], sentence2[i], mutableSetOf())) {
                return false
            }
        }
    }
    
    return true
}

Input: dominoes = ".L.R...LR..L.."
Output: "LL.RR.LLRRLL.."

class Solution {
    fun pushDominoes(dominoes: String): String {
        val N = dominoes.length
        val indexes = mutableListOf(-1)
        val symbols = mutableListOf('L')
        
        for (i in dominoes.indices) {
            if (dominoes[i] != '.') {
                indexes.add(i)
                symbols.add(dominoes[i])
            }
        }
        
        indexes.add(N)
        symbols.add('R')
        
        val ans = dominoes.toCharArray()
        for (idx in 0 until indexes.size - 1) {
            val i = indexes[idx]
            val j = indexes[idx + 1]
            val x = symbols[idx]
            val y = symbols[idx + 1]
            if (x == y) {
                for (k in i + 1 until j) {
                    ans[k] = x
                }
            } else if (x == 'R' && y == 'L') {
                for (k in i + 1 until j) {
                    if (k - i == j - k) {
                        ans[k] = '.'
                    } else if (k - i < j - k) {
                        ans[k] = 'R'
                    } else {
                        ans[k] = 'L'
                    }
                }
            }
        }
        
        return String(ans)
    }

Input: nums = [3,5,2,6], k = 2
Output: [2,6]
Explanation: Among the set of every possible subsequence: {[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]}, [2,6] is the most competitive.

class Solution {
    fun mostCompetitive(nums: IntArray, k: Int): IntArray {
        val queue = ArrayDeque<Int>()
        var additionalCount = nums.size - k
        
        for (num in nums) {
            while (queue.isNotEmpty() && queue.last() > num && additionalCount > 0) {
                queue.removeLast()
                additionalCount--
            }
            queue.addLast(num)
        }
        
        return queue.take(k).toIntArray()
    }
}

Input: accounts = [[1,2,3],[3,2,1]]
Output: 6
Explanation:
1st customer has wealth = 1 + 2 + 3 = 6
2nd customer has wealth = 3 + 2 + 1 = 6
Both customers are considered the richest with a wealth of 6 each, so return 6.

class Solution {
    fun maximumWealth(accounts: Array<IntArray>): Int {
        var maxWealthSoFar = 0
        
        for (account in accounts) {
            var currCustomerWealth = account.sum()
            maxWealthSoFar = maxOf(maxWealthSoFar, currCustomerWealth)
        }
        
        return maxWealthSoFar
    }
}

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], labels = "abaedcd"
Output: [2,1,1,1,1,1,1]
Explanation: Node 0 has label 'a' and its sub-tree has node 2 with label 'a' as well, thus the answer is 2. Notice that any node is part of its sub-tree.
Node 1 has a label 'b'. The sub-tree of node 1 contains nodes 1,4 and 5, as nodes 4 and 5 have different labels than node 1, the answer is just 1 (the node itself).

class Solution {
    private fun dfs(node: Int, parent: Int, adj: Map<Int, List<Int>>, labels: CharArray, ans: IntArray): IntArray {
        val nodeCounts = IntArray(26)
        nodeCounts[labels[node] - 'a'] = 1

        adj[node]?.forEach { child ->
            if (child != parent) {
                val childCounts = dfs(child, node, adj, labels, ans)
                for (i in 0 until 26) {
                    nodeCounts[i] += childCounts[i]
                }
            }
        }

        ans[node] = nodeCounts[labels[node] - 'a']
        return nodeCounts
    }

    fun countSubTrees(n: Int, edges: Array<IntArray>, labels: String): IntArray {
        val adj = mutableMapOf<Int, MutableList<Int>>()
        edges.forEach { edge ->
            adj.computeIfAbsent(edge[0]) { mutableListOf() }.add(edge[1])
            adj.computeIfAbsent(edge[1]) { mutableListOf() }.add(edge[0])
        }

        val ans = IntArray(n)
        dfs(0, -1, adj, labels.toCharArray(), ans)
        return ans
    }
}

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.

class Solution {
    fun eraseOverlapIntervals(intervals: Array<IntArray>): Int {
        intervals.sortBy { it[1] }
        var ans = 0
        var k = Int.MIN_VALUE
        
        for (interval in intervals) {
            val x = interval[0]
            val y = interval[1]
            if (x >= k) {
                k = y
            } else {
                ans++
            }
        }
        
        return ans
    }
}

Input: data = [1,0,1,0,1]
Output: 1
Explanation: There are 3 ways to group all 1's together:
[1,1,1,0,0] using 1 swap.
[0,1,1,1,0] using 2 swaps.
[0,0,1,1,1] using 1 swap.
The minimum is 1.

class Solution {
    fun minSwaps(data: IntArray): Int {
        val ones = data.sum()
        var cnt_one = 0
        var max_one = 0
        var left = 0
        var right = 0

        while (right < data.size) {
            cnt_one += data[right]
            right += 1
            if (right - left > ones) {
                cnt_one -= data[left]
                left += 1
            }
            max_one = Math.max(max_one, cnt_one)
        }
        return ones - max_one
    }
}

Input: s = "abc", k = 2
Output: 1

class Solution {
    fun minChangesToMakePalindrome(s: String, k: Int): Int {
        val n = s.length

        fun minChangeToPalindrome(i: Int, j: Int): Int {
            var changes = 0
            var i = i
            var j = j
            while (i < j) {
                if (s[i] != s[j]) {
                    changes++
                }
                i++
                j--
            }
            return changes
        }

        val dp1 = Array(n) { IntArray(n) }
        for (length in 1..n) {
            for (i in 0..n - length) {
                val j = i + length - 1
                dp1[i][j] = minChangeToPalindrome(i, j)
            }
        }

        val dp2 = Array(n + 1) { IntArray(k + 1) { Int.MAX_VALUE } }
        dp2[0][0] = 0

        for (i in 1..n) {
            for (kk in 1..k) {
                for (j in 0 until i) {
                    dp2[i][kk] = minOf(dp2[i][kk], dp2[j][kk - 1] + dp1[j][i - 1])
                }
            }
        }

        return dp2[n][k]
    }
}

Input
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []]
Output
[null, 1, 3, 2, 2, 3]

Explanation
Solution solution = new Solution([1, 2, 3]);
solution.getRandom(); // return 1
solution.getRandom(); // return 3
solution.getRandom(); // return 2
solution.getRandom(); // return 2
solution.getRandom(); // return 3
// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.

class ListNode(var `val`: Int) {
    var next: ListNode? = null
}

class Solution(head: ListNode?) {
    private val range = mutableListOf<Int>()

    init {
        var current = head
        while (current != null) {
            range.add(current.`val`)
            current = current.next
        }
    }

    fun getRandom(): Int {
        val pick = (0 until range.size).random()
        return range[pick]
    }
}

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4

class Solution {
    fun shortestPalindrome(s: String): String {
        val n = s.length
        val rev = s.reversed()
        for (i in 0 until n) {
            if (s.substring(0, n - i) == rev.substring(i)) {
                return rev.substring(0, i) + s
            }
        }
        return ""
    }
}

Input: n = 4  
Output: "1211"  

class Solution {
    fun countAndSay(n: Int): String {
        var s = "1"
        for (i in 2..n) {
            var t = ""
            val regex = Regex("(.)\\1*")
            regex.findAll(s).forEach { match ->
                t += "${match.value.length}${match.value[0]}"
            }
            s = t
        }
        return s
    }
}

Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2
Output: 0.25000
Explanation: There are two paths from start to end, one having a probability of success = 0.2 and the other has 0.5 * 0.5 = 0.25.

class Solution {
    fun maxProbability(n: Int, edges: Array<IntArray>, succProb: DoubleArray, start: Int, end: Int): Double {
        val maxProb = DoubleArray(n)
        maxProb[start] = 1.0

        for (i in 0 until n - 1) {
            var hasUpdate = false
            for (j in edges.indices) {
                val u = edges[j][0]
                val v = edges[j][1]
                val pathProb = succProb[j]
                if (maxProb[u] * pathProb > maxProb[v]) {
                    maxProb[v] = maxProb[u] * pathProb
                    hasUpdate = true
                }
                if (maxProb[v] * pathProb > maxProb[u]) {
                    maxProb[u] = maxProb[v] * pathProb
                    hasUpdate = true
                }
            }
            if (!hasUpdate) {
                break
            }
        }

        return maxProb[end]
    }
}