#2022小米编程大赛题解

class Solution {
    fun oddString(words: Array<String>): String {
        fun simply(str: String): String {
            val sb = StringBuilder(str)
            val minChar = sb.min()!!
            for (i in sb.indices) {
                sb[i] = ((sb[i] - minChar).toInt() + 'a'.toInt()).toChar()
            }
            return sb.toString()
        }

        var ans = ""
        val strMap = HashMap<String, Int>()
        for (str in words) {
            val sStr = simply(str)
            strMap[sStr] = strMap.getOrDefault(sStr, 0) + 1
        }
        for (str in words) {
            val sStr = simply(str)
            if (strMap[sStr] == 1) {
                ans = str
                break
            }
        }
        return ans
    }
}

class Solution {
    fun twoEditWords(queries: Array<String>, dictionary: Array<String>): List<String> {
        fun diff(a: String, b: String): Int {
            var cnt = 0
            for (i in a.indices) {
                if (a[i] != b[i]) {
                    cnt++
                }
            }
            return cnt
        }

        val ans = ArrayList<String>()
        for (qur in queries) {
            for (dict in dictionary) {
                if (diff(qur, dict) <= 2) {
                    ans.add(qur)
                    break
                }
            }
        }
        return ans
    }
}

class Solution {
    fun destroyTargets(nums: IntArray, space: Int): Int {
        val destroyCntMap = HashMap<Long, Long>()
        val destroyHead = HashMap<Long, Long>()
        var minNum = -1L
        var maxDestroyCnt = 0L
        nums.sort()
        for (x in nums) {
            val cur = x.toLong() % space
            if (destroyCntMap[cur] != null) {
                destroyCntMap[cur] = destroyCntMap.getOrDefault(cur, 0) + 1
            } else {
                destroyCntMap[cur] = 1L
                destroyHead[cur] = x.toLong()
            }
            val curDestroyCnt = destroyCntMap[cur]!!
            if (curDestroyCnt > maxDestroyCnt) {
                minNum = destroyHead[cur]!!
                maxDestroyCnt = curDestroyCnt
            } else if (curDestroyCnt == maxDestroyCnt) {
                minNum = Math.min(minNum, destroyHead[cur]!!)
            }
        }

        return minNum.toInt()
    }
}

class Solution {
    fun secondGreaterElement(nums: IntArray): IntArray {
        val n = nums.size
        val ans = IntArray(n) {
            -1
        }
        val stack1 = LinkedList<Int>()
        val stack2 = TreeMap<Int, ArrayList<Int>>()
        for (i in 0 until n) {
            while (stack2.isNotEmpty() && stack2.firstKey() < nums[i]) {
                val firstEntry = stack2.firstEntry()
                for (j in firstEntry.value) {
                    ans[j] = nums[i]
                }
                stack2.remove(firstEntry.key)
            }
            while (stack1.isNotEmpty() && nums[stack1.peekLast()] < nums[i]) {
                val removed = stack1.removeLast()
                stack2.getOrPut(nums[removed]) { ArrayList<Int>() }.add(removed)
            }
            stack1.addLast(i)
        }

        return ans
    }
}

class Solution {
    fun averageValue(nums: IntArray): Int {
        return nums.filter { it % 3 == 0 && it % 2 == 0 }.average().toInt()
    }
}

class Solution {
    fun mostPopularCreator(creators: Array<String>, ids: Array<String>, views: IntArray): List<List<String>> {
        val creatorViewsMap = TreeMap<String, Long>()
        val creatorVideoMap = TreeMap<String, ArrayList<Pair<String, Int>>>()
        val n = creators.size
        for (i in 0 until n) {
            creatorViewsMap[creators[i]] = creatorViewsMap.getOrDefault(creators[i], 0L) + views[i]
            creatorVideoMap.getOrPut(creators[i]) { ArrayList() }.add(ids[i] to views[i])
        }
        val ans = ArrayList<List<String>>()
        var maxView = 0L
        val maxViews = ArrayList<Map.Entry<String, ArrayList<Pair<String, Int>>>>()
        for ((creator, view) in creatorViewsMap.entries) {
            if (maxView < view) {
                maxView = view
                maxViews.clear()
                maxViews.add(creatorVideoMap.ceilingEntry(creator))
            } else if (maxView == view) {
                maxViews.add(creatorVideoMap.ceilingEntry(creator))
            }
        }
        for (entry in maxViews) {
            ans.add(listOf(entry.key,
                entry.value.sortedWith(compareByDescending<Pair<String, Int>> { it.second }.thenBy { it.first })
                    .first().first
            )
            )
        }

        return ans
    }
}

class Solution {
    fun makeIntegerBeautiful(n: Long, target: Int): Long {
        val nStr = n.toString()
        val numSum = nStr.map { it - '0' }.sum()
        if (numSum <= target) {
            return 0
        }
        var ans = Long.MAX_VALUE
        var sum = 1
        for (i in nStr.indices) {
            if (sum > target) {
                break
            }
            var x = 0L
            for (j in i until nStr.length) {
                x = x * 10 + (9 - (nStr[j] - '0'))
            }
            x++
            ans = Math.min(ans, x)
            sum += (nStr[i] - '0')
        }

        return ans
    }
}

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun treeQueries(root: TreeNode?, queries: IntArray): IntArray {
        if (root == null) {
            return intArrayOf()
        }

        class TreeNodeHolder(val value: Int, val level: Int) {
            var left: TreeNodeHolder? = null
            var right: TreeNodeHolder? = null
            var maxDepth = 0
        }

        val rootNode = TreeNodeHolder(root.`val`, 0)

        val valueToTreeNodeMap = HashMap<Int, TreeNodeHolder>()
        val levelToTreeNodeListMap = TreeMap<Int, ArrayList<TreeNodeHolder>>()
        fun buildTree(curNode: TreeNodeHolder, treeNode: TreeNode, level: Int): Int {
            valueToTreeNodeMap[curNode.value] = curNode
            levelToTreeNodeListMap.getOrPut(level) { ArrayList() }.add(curNode)
            var maxDepth = level
            if (treeNode.left != null) {
                curNode.left = TreeNodeHolder(treeNode.left!!.`val`, level + 1)
                maxDepth = Math.max(maxDepth, buildTree(curNode.left!!, treeNode.left!!, level + 1))
            }
            if (treeNode.right != null) {
                curNode.right = TreeNodeHolder(treeNode.right!!.`val`, level + 1)
                maxDepth = Math.max(maxDepth, buildTree(curNode.right!!, treeNode.right!!, level + 1))
            }
            curNode.maxDepth = maxDepth
            return maxDepth
        }

        val maxDepth = buildTree(rootNode, root, 0)
        rootNode.maxDepth = maxDepth

        val ans = IntArray(queries.size)
        for (i in queries.indices) {
            val removeTreeNode = valueToTreeNodeMap[queries[i]]!!
            var depth = removeTreeNode.level - 1
            for (node in levelToTreeNodeListMap[removeTreeNode.level]!!) {
                if (node.value == queries[i]) {
                    continue
                }
                depth = Math.max(depth, node.maxDepth)
            }

            ans[i] = depth
        }

        return ans
    }
}