fun backtrack(...) {
    // 检查是否达到结束条件
    if (满足结束条件) {
        // 处理结果
        处理结果
        return
    }

    // 遍历所有可能的选择
    for (选择 in 可选列表) {
        // 做选择
        做选择

        // 进入下一层决策树
        backtrack(...)

        // 撤销选择
        撤销选择
    }
}

fun dp(n: Int, memo: IntArray): Int {
    // 检查是否已经计算过该值
    if (memo[n] != -1) {
        return memo[n]
    }
    
    // 边界条件
    if (n == 0 || n == 1) {
        memo[n] = n
        return n
    }
    
    // 递归计算并保存结果
    memo[n] = dp(n - 1, memo) + dp(n - 2, memo)
    return memo[n]
}

class TrieNode {
    val children = HashMap<Char, TrieNode>()
    var isWord = false
}

class Trie {
    private val root = TrieNode()

    fun insert(word: String) {
        var node = root
        for (char in word) {
            if (!node.children.containsKey(char)) {
                node.children[char] = TrieNode()
            }
            node = node.children[char]!!
        }
        node.isWord = true
    }

    fun search(word: String): Boolean {
        var node = root
        for (char in word) {
            if (!node.children.containsKey(char)) {
                return false
            }
            node = node.children[char]!!
        }
        return node.isWord
    }

    fun startsWith(prefix: String): Boolean {
        var node = root
        for (char in prefix) {
            if (!node.children.containsKey(char)) {
                return false
            }
            node = node.children[char]!!
        }
        return true
    }
}

class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        val hashmap = HashMap<Int, Int>()
        for(i in nums.indices){
            val complement = target - nums[i]
            if(hashmap.containsKey(complement)){
                return intArrayOf(hashmap[complement]!!, i)
            }
            hashmap[nums[i]] = i        
            }
        return intArrayOf()
    }
}

class Solution {
    fun addTwoNumbers(l1: ListNode?, l2: ListNode?): ListNode? {
        // 定义两个指针 p1 和 p2，分别指向两个链表的头节点
        var p1 = l1
        var p2 = l2

        // 定义一个哨兵节点 dummy，作为结果链表的头节点
        val dummy = ListNode(0)
        // 定义一个节点 cur, 作为结果链表的尾节点
        var cur = dummy

        var carry = 0

        while(p1 != null || p2 != null){
            val x = p1?.`val` ?: 0
            val y = p2?.`val` ?: 0
            var sum = x + y + carry
            carry = sum / 10
            sum = sum % 10

            cur?.next = ListNode(sum)

            p1 = p1?.next
            p2 = p2?.next
            cur = cur?.next
        }

        if(carry > 0){
            cur?.next = ListNode(carry)
        }

        return dummy?.next
    }
}

class Solution {
    fun lengthOfLongestSubstring(s: String): Int {
        var maxLen = 0 // 最长不含重复字符子串的长度
        var left = 0 // 窗口左边界
        val map = HashMap<Char, Int>() // 哈希表记录字符最后出现的位置

        for(right in s.indices){
            val char = s[right]

            if(map.containsKey(char) && map[char]!! >= left){
                left = (map[char]?: 0) + 1
            }

            map[char] = right
            maxLen = maxOf(maxLen, right - left + 1)
        }
        return maxLen
    }
}

// 该函数用于在两个已排序整数数组中找到它们的中位数，返回类型为 Double。
fun findMedianSortedArrays(nums1: IntArray, nums2: IntArray): Double {
    // 获取 nums1 和 nums2 的长度。
    val n1 = nums1.size
    val n2 = nums2.size
    // 如果 nums1 的长度大于 nums2，则交换它们，确保 nums1 的长度小于等于 nums2。
    if (n1 > n2) {
        return findMedianSortedArrays(nums2, nums1)
    }  
    // 设置左右指针的初始值。
    var left = 0 // 如果把 num1 和 num2 合并元素重新排序，最左边
    var right = n1 // 如果把 num1 和 num2 合并元素重新排序，相当于 num2 最左边
    // 当左指针小于等于右指针时，执行二分查找。
    while (left <= right) { // 因为 n1 < n2
        // 计算 nums1 中间的索引 i 和 nums2 中间的索引 j。
        val num1HalfIndex = (left + right) / 2 
        val num2HalfIndex = ((n1 + n2 + 1) / 2) - num1HalfIndex  
        // 计算 nums1 和 nums2 的左侧和右侧的最大值和最小值。
        val maxOfNum1SmallRange = if (num1HalfIndex == 0) Int.MIN_VALUE else nums1[num1HalfIndex - 1] // nums1 小区间的最大值
        val minOfNum1BigRange = if (num1HalfIndex == n1) Int.MAX_VALUE else nums1[num1HalfIndex] // nums1 大区间的最小值
        val maxOfNum2SmallRange = if (j == 0) Int.MIN_VALUE else nums2[j - 1] // nums2 小区间的最大值
        val minOfNum2BigRange = if (j == n2) Int.MAX_VALUE else nums2[j] // nums2 大区间的最小值
        // 如果满足条件，则返回中位数。
        if (maxOfNum1SmallRange <= minOfNum2BigRange && maxOfNum2SmallRange <= minOfNumBigRange) { // num1小 < num2大 && num2小 < num1大, 也就是说“小区间都小于大区间”
             return if ((n1 + n2) % 2 == 0) { // 如果 nums1 和 nums2 的长度之和为偶数
                // 则返回左右两侧最大值和最小值的平均值。
                (maxOf(maxOfNum1SmallRange, maxOfNum2SmallRange).toDouble() + minOf(minOfNum1BigRange, minOfNum2BigRange).toDouble()) / 2.0
            } else {
                // 如果 nums1 和 nums2 的长度之和为奇数，则返回左侧最大值。
                maxOf(maxOfNum1SmallRange, maxOfNum2SmallRange).toDouble()
            }
        } else if (maxOfNum1SmallRange > minOfNum2BigRange) { // num1大 < num2小
            // 如果 nums1 的左侧最大值大于 nums2 的右侧最小值，则需要将 num1HalfIndex 向左移动。
          /*
                   left   num1HalfIndex   right
                    |           |           |
                    1 1 1 1 1 1 1 1 1 1 1 1 E
          1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 E
                          |
                     num2HalfIndex
          */
            right = num1HalfIndex - 1
          /*
                    num1HalfIndex 
                   left   |   right
                    |     |     |
                    1 1 1 1 1 1 1 1 1 1 1 1 
          1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 E
                                |
                           num2HalfIndex 
          */
        } else {
        // 如果 nums2 的左侧最大值大于 nums1 的右侧最小值，则需要将 num1HalfIndex 向右移动。
         /*
         left   num1HalfIndex   right
          |           |           |
          1 1 1 1 1 1 1 1 1 1 1 1 E
                  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 E
                                  |
                            num2HalfIndex
         */
            left = num1HalfIndex + 1
         /*
            留给大家画
         */
        }
    }
    // 如果找不到中位数，则返回 0.0。
    return 0.0
}

fun findMedianSortedArrays(nums1: IntArray, nums2: IntArray): Double {
    val n1 = nums1.size
    val n2 = nums2.size
    if (n1 > n2) {
        return findMedianSortedArrays(nums2, nums1)
    }  
    var left = 0
    var right = n1
    while (left <= right) { // 因为 n1 < n2
        val num1HalfIndex = (left + right) / 2 
        val num2HalfIndex = ((n1 + n2 + 1) / 2) - num1HalfIndex  
        val maxOfNum1SmallRange = if (num1HalfIndex == 0) Int.MIN_VALUE else nums1[num1HalfIndex - 1]
        val minOfNum1BigRange = if (num1HalfIndex == n1) Int.MAX_VALUE else nums1[num1HalfIndex]
        val maxOfNum2SmallRange = if (j == 0) Int.MIN_VALUE else nums2[j - 1]
        val minOfNum2BigRange = if (j == n2) Int.MAX_VALUE else nums2[j]
        if (maxOfNum1SmallRange <= minOfNum2BigRange && maxOfNum2SmallRange <= minOfNumBigRange) {
             return if ((n1 + n2) % 2 == 0) {
                (maxOf(maxOfNum1SmallRange, maxOfNum2SmallRange).toDouble() + minOf(minOfNum1BigRange, minOfNum2BigRange).toDouble()) / 2.0
            } else {
                maxOf(maxOfNum1SmallRange, maxOfNum2SmallRange).toDouble()
            }
        } else if (maxOfNum1SmallRange > minOfNum2BigRange) {
            right = num1HalfIndex - 1
        } else {
            left = num1HalfIndex + 1
        }
    }
    return 0.0
}

class Solution {
    fun convert(s: String, numRows: Int): String {
        推出 (numRows < 2) return s
        val rows: MutableList<StringBuilder> = ArrayList()
        for (i in 0 until numRows) rows.add(StringBuilder())
        var i = 0
        var step = -1
        for (c in s.toCharArray()) {
            rows[i].append(c)
            if (i == 0 || i == numRows - 1) step = -step
            i += step
        }
        val res = StringBuilder()
        for (row in rows) res.append(row)
        return res.toString()
    }
}

fun isPrime(n: Int): Boolean {
    if (n <= 1) return false
    for (i in 2 until n) {
        if (n % i == 0) {
            return false
        }
    }
    return true
}

fun countPrimesInArray(arr: IntArray): Int {
    var count = 0
    for (num in arr) {
        if (isPrime(num)) {
            count++
        }
    }
    return count
}

fun main() {
    val arr = intArrayOf(2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)
    println("Count of prime numbers in the array: ${countPrimesInArray(arr)}")
}