Fork me on GitHub

02. 双指针-有两个输入, 两个都需要遍历完

0 - 算法, 0.0 - 算法模版

正文

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
fun twoPointers(nums1: IntArray, nums2: IntArray) {
    var pointer1 = 0
    var pointer2 = 0

    while (pointer1 < nums1.size && pointer2 < nums2.size) {
        // 处理指针1和指针2对应位置的元素
        // ...

        // 移动指针
        pointer1++
        pointer2++
    }

    // 处理剩余未遍历完的元素
    while (pointer1 < nums1.size) {
        // 处理指针1对应位置的元素
        // ...
        pointer1++
    }

    while (pointer2 < nums2.size) {
        // 处理指针2对应位置的元素
        // ...
        pointer2++
    }
}

03. 滑动窗口

0 - 算法, 0.0 - 算法模版

正文

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
fun slidingWindow(nums: IntArray, k: Int): Int {
    val n = nums.size
    var sum = 0
    var maxSum = 0

    // 计算第一个窗口的和
    for (i in 0 until k) {
        sum += nums[i]
    }

    maxSum = sum

    // 滑动窗口
    for (i in k until n) {
        // 新窗口的和等于之前窗口的和加上新进入窗口的元素，减去滑出窗口的元素
        sum += nums[i] - nums[i - k]
        // 更新最大和
        maxSum = maxOf(maxSum, sum)
    }

    return maxSum
}

04. 构建前缀和

0 - 算法, 0.0 - 算法模版

正文

以下是一个前缀和算法的常见模板：

1
2
3
4
5
6
7
8
9
10
fun prefixSum(nums: IntArray): IntArray {
    val prefixSum = IntArray(nums.size + 1)

    // 计算前缀和数组
    for (i in 1..nums.size) {
        prefixSum[i] = prefixSum[i - 1] + nums[i - 1]
    }
    
    return prefixSum
}

在这个模板中，我们使用一个额外的数组 prefixSum 来存储原始数组 nums 的前缀和。通过遍历原始数组，我们可以计算每个位置的前缀和并存储在 prefixSum 中。

使用前缀和数组 prefixSum，我们可以高效地回答多个查询，例如计算某个区间的和。假设我们需要计算区间 [left, right] 的和，我们可以使用如下方式获取结果：

1
val sum = prefixSum[right + 1] - prefixSum[left

这个计算结果即为原始数组中从位置 left 到位置 right 的元素之和。
请注意，在模板中，前缀和数组 prefixSum 的长度比原始数组 nums 的长度多了一个元素。这是为了方便计算区间和时的边界情况。

05. 高效的字符串构建

0 - 算法, 0.0 - 算法模版

正文

以下是一个高效的字符串构建算法模板：

1
2
3
4
5
6
7
8
9
fun buildString(chars: List<Char>): String {
    val sb = StringBuilder()

    for (ch in chars) {
        sb.append(ch)
    }
    
    return sb.toString()
}

在这个模板中，我们使用 StringBuilder 来构建字符串。StringBuilder 是可变的字符串类，可以高效地进行字符串的拼接操作。

我们通过遍历字符列表 chars，逐个将字符添加到 StringBuilder 中。最后，通过调用 toString() 方法，将 StringBuilder 转换为最终的字符串结果并返回。

使用 StringBuilder 的好处是它避免了在每次拼接字符串时创建新的字符串对象，从而提高了性能和效率。特别是在需要频繁拼接大量字符串的情况下，使用 StringBuilder 可以避免不必要的性能损耗。

使用这个模板，你可以根据具体需求构建字符串。可以根据问题的要求在遍历过程中进行一些字符处理、条件判断等操作。

06. 链表-快慢指针

0 - 算法, 0.0 - 算法模版

正文

在模板中，我们使用两个指针，一个指针每次向后移动一个节点，另一个指针每次向后移动两个节点。如果链表中存在循环，快指针最终会追上慢指针，这样我们就可以判断出链表有循环。如果链表没有循环，快指针会先到达链表的末尾，此时我们就可以判断链表没有循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
fun hasCycle(head: ListNode?): Boolean {
    var slow = head
    var fast = head

    while (fast?.next != null && fast.next?.next != null) {
        slow = slow?.next
        fast = fast.next?.next

        if (slow == fast) {
            return true
        }
    }

    return false
}

08. 找到符合确切条件的子数组数

0 - 算法, 0.0 - 算法模版

正文

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
fun numSubarraysWithSum(nums: IntArray, goal: Int): Int {
    var count = 0
    var total = 0
    var left = 0

    for (right in nums.indices) {
        total += nums[right]

        while (left <= right && total > goal) {
            total -= nums[left]
            left++
        }

        if (total == goal) {
            count++

            // 统计连续的0
            var temp = left
            while (temp <= right && nums[temp] == 0) {
                count++
                temp++
            }
        }
    }

    return count
}

09. 单调递增栈

0 - 算法, 0.0 - 算法模版

正文

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
fun monotonicStack(nums: IntArray): IntArray {
    val stack = mutableListOf<Int>()
    val result = IntArray(nums.size) { -1 }

    for (i in nums.indices) {
        while (stack.isNotEmpty() && stack.last() < nums[i]) {
            stack.removeAt(stack.size - 1)
        }

        // 在这里可以根据题目需求进行处理
        // 例如：找到栈中元素的下一个更大元素
        if (stack.isNotEmpty()) {
            result[i] = stack.last()
        }
        
        stack.add(nums[i])
    }

    return result
}