Following the previous articles — Week 1/5 and Week 2/5, we will continue diving into iOS technical interview preparation with the third week of the 30-day code challenge.

在之前的文章( 第1/5周和第2/5周)之后 ，我们将在30天代码挑战的第三周继续深入研究iOS技术面试准备。

Developers who would like to practice by themselves, feel free to take advantage of my Github repo, which includes solutions and unit tests for the 30-day code challenge.

想要自己练习的开发者可以随时使用我的Github存储库 ， 其中包括针对30天代码挑战的解决方案和单元测试。

The below topics are the 7 programming questions of the week that we are going to cover in this article.

以下主题是我们将在本文中讨论的一周中的七个编程问题。

Product of Array Except Self (Solution)

阵列的产品，除非自 ( 解决方案 )

Valid Parenthesis String (Solution) 🥇

有效括号字符串 ( 解决方案 )🥇

Number of Islands (Solution) 🥈

岛数 ( 解 )🥈

Minimum Path Sum (Solution)

最小路径总和 ( 解 )

Search in Rotated Sorted Array (Solution) 🥉

搜索旋转排序数组 ( 解决方案 )🥉

Construct Binary Search Tree from Preorder Traversal (Solution)

从预遍历构造二叉搜索树 ( 解决方案 )

Leftmost Column with at Least a One (Solution)

至少有一个左列 ( 解决方案 )

(🥇 🥈 🥉 indicate writer’s selection of high-frequency interview questions.)

( 🥉 表示作者选择了高频访谈问题。)

阵列除自身的乘积 (Product of Array Except Self)

Description: Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i]

描述 ：给定一个阵列nums n个整数的，其中n> 1时 ，返回一个数组output ，使得output[i]是等于所有的元素的乘积nums除了nums[i]

Example 1Input: [1, 2, 3, 4, 5]Output: [120, 60, 40, 30, 24]Example 2Input: [0, 1, 2, 3, 4]Output: [24, 0, 0, 0]

One way to simplify the problem and save the runtime is to get the product of the entire array then divide it by each element to get the output for each of them. However, there are some edge cases we have to handle. First, if the array contains one zero, the outputs will all be zero except the one for that zero in the array. Furthermore, if the array has more than one zeros, it is obvious that all outputs become zero. Taking these two additional cases into account, we are ready for the solution.

简化问题并节省运行时间的一种方法是获取整个数组的乘积，然后将其除以每个元素，以获取每个数组的输出。 但是，我们必须处理一些极端情况。 首先，如果数组包含一个零 ，则输出将全部为零，除了数组中该零的一个。 此外，如果数组具有多个零 ，则所有输出都将变为零。 考虑到这两种其他情况，我们已准备好解决方案。

func productExceptSelf(_ nums: [Int]) -> [Int] { var foundFirstZero = false var total = 1 for num in nums { if !foundFirstZero && num == 0 { foundFirstZero = true } else { total = total * num } } var output = [Int]() if foundFirstZero && total == 0 { return Array(repeating: 0, count: nums.count) } for num in nums { if foundFirstZero { if num == 0 { output.append(total) } else { output.append(0) } } else { output.append(total/num) } } return output }

Time complexity: O(N). Since we loop through the entire array twice independently, the runtime is O(2N). I note it as O(N) after leaving out the constants.

时间复杂度： O(N) 。 由于我们独立遍历整个数组两次，因此运行时间为O(2N) 。 省略常数后，我将其记为O(N) 。

有效的括号字符串 (Valid Parenthesis String)

🥇 Writer’s selection of the week

🥇 作家的每周精选

Description: Given a string containing only three types of characters: “(“, “)” and *️⃣ (= “*”), write a function to check whether this string is valid. We define the validity of a string by these rules:

说明：给定一个仅包含三种类型的字符的字符串：“ ( “，” ) “和*️⃣(=” * “)，编写一个函数来检查此字符串是否有效。 我们通过以下规则定义字符串的有效性：

Any left parenthesis “(“ must have a corresponding right parenthesis “)”.

任何左括号“ ( ”必须具有相应的右括号“ ) ”。

Any right parenthesis “)“ must have a corresponding left parenthesis “(”.

任何右括号“)“必须有一个对应的左括号‘(’。

“(“ must go before the corresponding “)“.

“ (必须在相应的“ )之前”。

*️⃣ could be treated as a single “)“ or a single “(” or an empty string.

*️⃣可视为单个“)“或单一‘(’或空字符串。

An empty string is also valid

空字符串也有效 Example 1 Input: "(*)"Output: TrueExample 2Input: "(*))"Output: True

Dealing with parenthesis questions, the first data structure that comes to my mind is a Stack because of its LIFO (last in, first out) feature. Thankfully, we don’t have to implement Stack in Swift since its Array already provides operation functions such as removeLast(), append(), and lastIndex(of:) that allows it to behave like a Stack.

在处理括号问题时，我想到的第一个数据结构是Stack，因为它具有LIFO ( 后进 先出 )功能。 值得庆幸的是，我们不必在Swift中实现Stack，因为它的Array已经提供了操作功能，例如removeLast()，append()和lastIndex(of :) ，使其可以像Stack一样工作。

Initially, when we iterate over the array, we push a “(” to the stack for each “(”. On the other hand, when we see “)”, we pop an element from the stack to check whether it is a “(” that matches the “)”.

最初，当我们迭代阵列上，我们推“(”到堆叠为每个“(”。在另一方面，当我们看到“)”，我们从栈中弹出的元件，以检查它是否是一个“ (匹配“” ) 。

Nonetheless, this question introduces another character * that can serve as either “(” or “)”, which makes it a bit different. Ideally, we can still handle all incoming “)” by checking if there are available “(” or *️⃣ to match. Pop “(” or *️⃣ if either of them exists in the stack. Otherwise, return false since the input can be therefore confirmed invalid.

但是，这个问题引入了另一个可以用作“ ( ”或“” )的字符* ，这使它有些不同。 理想情况下，我们仍然可以处理所有来电“)”由是否有可“(”或检查*️⃣相匹配。啪“(”或*️⃣如果其中一方在堆栈中存在。否则，返回false，因为输入可以因此被确认无效。

So far we’ve done with all “)” from the input. There is one last step for the validation process that we have to cope with the remaining “(” and *️⃣ in the stack. To do the task, I pop elements from the stack and examine them one by one. We can return false if it’s a “(” since there’s no “)” or *️⃣ on its right side that can match it. Otherwise, if the popped element is a *️⃣, we want to see whether there is “(” existing in the stack. If there is, remove it. If not, return true as it means there are only *️⃣s left in the stack.

到目前为止，我们已经与所有完成的“)”从输入。 验证过程的最后一步是我们必须处理堆栈中剩余的“ ( ”和*️⃣。要完成此任务，我从堆栈中弹出元素并逐个检查它们。如果返回，则返回false这是一个“(”因为没有“)”或*️⃣在其右侧，可以与之匹敌。否则，如果弹出的元素是*️⃣，我们想看看是否有“(”现有的堆栈，如果如果没有，返回true，因为这意味着堆栈中只剩下*️⃣。

func checkValidString(_ s: String) -> Bool { var stack = [Character]() for c in s { if c == "(" || c == "*" { stack.append(c) } else { if let idx = stack.lastIndex(of: "(") { stack.remove(at: idx) } else if let idx = stack.lastIndex(of: "*") { stack.remove(at: idx) } else { return false } } } while stack.last != nil { let last = stack.removeLast() if last == "(" { return false } else if last == "*" { if let idx = stack.lastIndex(of: "(") { stack.remove(at: idx) } else { return true } } } return stack.isEmpty }

We need a step-by-step analysis to get the estimate of time complexity considering that we use quite a few Swift Array operation functions. First of all, let’s say the input string has a length of N. Theoretically, the length of the stack is ≤ N. Assume the worst case that will make the stack as large as the input string, the function lastIndex(of:) and remove() both take O(N). As a result, the first for-loop takes roughly O(N²). In a similar way for the second while-loop, where we pop each element from the stack and perform function lastIndex(of:) on the stack, the runtime is consequently O(N²) for the worst case. In conclusion, it takes O(N²) for the entire solution.

考虑到我们使用了许多Swift Array操作函数，我们需要分步进行分析以获得时间复杂度的估算值。 首先，假设输入字符串的长度为N。 从理论上讲，在堆栈的长度≤ñ。 假定最坏的情况会使堆栈与输入字符串一样大，函数lastIndex(of :)和remove()都采用O(N) 。 结果，第一个for循环大约需要O(N²) 。 在用于第二while循环类似的方式，在这里我们从栈中弹出每个元素和在堆栈上执行功能的lastIndex的(的:)，运行时因此是O(N²)为最坏的情况。 总之，整个解决方案需要O(N²) 。

Although this solution is not the most efficient one, I’ve added a couple of rules to break out loops if a determinant factor is found, which makes it faster than 91% of Swift entries on LeetCode. Just FYI, you can find other efficient solutions that apply dynamic programming or greedy algorithm here.

尽管此解决方案不是最有效的解决方案，但我添加了一些规则，可以在发现决定因素的情况下打破循环，这比LeetCode上Swift条目的91％更快。 仅供参考，您可以在此处找到其他应用动态编程或贪婪 算法的有效解决方案。

岛屿数 (Number of Islands)

🥈 Writer’s selection of the week

🥈 作家的每周精选

Description: Given a 2D grid map of “1”s (land) and “0”s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.

描述 ：给定2D栅格地图，“陆地”和“ 0 ”(水)分别为“ 1 ”和“ 0 ”(水)。 岛屿被水包围，是通过水平或垂直连接相邻的土地而形成的。

Example 1Input:1 1 1 1 01 1 0 1 01 1 0 0 00 0 0 0 0Output: 1Example 2Input:1 1 0 0 01 1 0 0 00 0 1 0 00 0 0 1 1Output: 3

Instead of just finding all “1”s, we want to be able to mark all consecutive “1”s as one island. In other words, we want to merge all adjacent “1”s so they will only be counted once as an island. Speaking of finding all adjacent elements, Depth-First Search (DFS) would be a suitable algorithm to get the job done.

我们希望不仅能够找到所有的“ 1 ”，而且希望能够将所有连续的“ 1 ”标记为一个岛。 换句话说，我们希望合并所有相邻的“ 1 ”，因此它们将仅被算作一个岛。 说到查找所有相邻元素， 深度优先搜索 ( DFS )将是完成工作的合适算法。

Basically, we traverse through the entire grid. Whenever there is a “1” we find in the grid, we increment the count by one. Additionally, and most importantly, we have to go through all adjacent elements and see if there’re any “1”s. If there are, change all adjacent “1”s to “0”s so they won’t be counted again. The concept is implemented in the following solution.

基本上，我们遍历整个网格。 只要在网格中找到“ 1 ”，我们就将计数加一。 另外，最重要的是，我们必须遍历所有相邻的元素，看看是否有“ 1 ”。 如果有，请将所有相邻的“ 1 ”更改为“ 0 ”，这样就不会再次计数。 该概念在以下解决方案中实现。

func numIslands(_ grid: [[Character]]) -> Int { var count = 0 var matrix = grid for x in 0..<matrix.count { for y in 0..<matrix[x].count { if matrix[x][y] == "1" { count += 1 findAdjacentIslands(x, y, &matrix) } } } return count } func findAdjacentIslands(_ x: Int, _ y: Int, _ matrix: inout [[Character]]) { matrix[x][y] = "0" if x + 1 < matrix.count, matrix[x + 1][y] == "1" { findAdjacentIslands(x + 1, y, &matrix) } if y + 1 < matrix[x].count, matrix[x][y + 1] == "1" { findAdjacentIslands(x, y + 1, &matrix) } if y - 1 >= 0, matrix[x][y - 1] == "1" { findAdjacentIslands(x, y - 1, &matrix) } if x - 1 >= 0, matrix[x - 1][y] == "1" { findAdjacentIslands(x - 1, y, &matrix) } }

Time complexity: O(NM). Let’s assume the input grid has N rows and M columns. We need to go over each element in the grid in order to determine how many islands are there. Therefore the runtime it takes is O(N * M).

时间复杂度： O(NM) 。 假设输入网格具有N行和M列。 我们需要遍历网格中的每个元素，以确定其中有多少个岛。 因此，运行时间为O(N * M) 。

最小路径总和 (Minimum Path Sum)

Description: Given a grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. You can only move either down or right at any point in time.

描述 ：给定一个充满非负数的网格，找到从左上到右下的路径，该路径将沿其路径的所有数字的总和最小化 。 您只能在任何时间点上下移动。

Example Input:[ [1, 3, 1], [1, 5, 1], [4, 2, 1]]Output: 7The path 1 -> 3 -> 1 -> 1 -> 1 has the minimum sum.

One intuitive idea to solve the problem is to do it recursively. Beginning from top-left, we continue comparing the value of the right and bottom. Even the current right value is less than the bottom one, it doesn’t mean going towards the right will result in the minimum sum eventually. Therefore, we have to repeat the process and consider all cases while moving the start point all the way down to bottom-right to get the desired output. Nevertheless, this way is too inefficient to get the work done within the time limit.

解决问题的一种直观想法是递归执行。 从左上角开始，我们继续比较右下角的值。 即使当前的权利值小于最低值，也并不意味着向右行最终将导致最小的总和。 因此，我们必须重复该过程并考虑所有情况，同时将起点一直向下移动到右下角以获得所需的输出。 但是，这种方法效率太低，无法在规定的时间内完成工作。

We have to devise another way that not only utilizes the concept of the recursive method but also has a compelling runtime.

我们必须设计出另一种方法，该方法不仅利用递归方法的概念，而且具有引人注目的运行时。

Take the below input as an example, the minimal sum derived is 3. First of all, I want to introduce a term — then-minimum sum, which defines the minimum value accumulated until the current element.

以下面的输入为例，得出的最小和为3 。 首先，我想介绍一个术语- 然后最小和 ， 它定义了直到当前元素为止累积的最小值。

Let’s count it step by step, starting from top-left, the then-minimum sum at top-left is 1. Continuing going down to bottom-left position, we will find the then-minimum sum is 2 since the path it goes through is 1 -> 1. On the other hand, the then-minimum sum is 4 at the top-right position while it goes from 1 to 3. At the bottom-right, we have two choices to calculate the then-minimal sum, one is from its top (then-min sum 4) and the other one is from its left side (then-min sum 2). We simply select the left side one given its smaller value. Lastly, add up its value to the bottom-right one to get the final minimum sum.

让我们从左上角开始逐步计算， 然后左上角的最小和为1 。 继续下降到左下角的位置，我们将发现那么最小和为2，因为它经过的路径是1-> 1 。 另一方面， 右上角 的最小和为4 ，而从1到3 。 在右下角，我们有两个选择来计算那么最小和 ，一个是从顶部算起的( 那么最小和4 )。 另一个是从左侧开始的 ( 然后是最小总和2 )。 我们只选择左侧一个较小的值。 最后，将其值加到右下角的值以得到最终的最小和。

Input[ [1, 3], [1, 1]]Then-minimum grid[ [1, 4], [2, 3]]

Applying the rule we found above, we create a new grid that copies the input one. Iterating over it, we compare the top and left value for each element before adding either of which to get the then-min sum. In the end, we will find the minimum path sum at the bottom-right of the grid.

应用上面发现的规则，我们创建了一个新的网格来复制输入内容。 对其进行迭代，我们比较每个元素的顶部和左侧的值，然后再添加其中的任何一个以获取then-min总和 。 最后，我们将在网格的右下角找到最小路径总和。

This is a dynamic programming approach that tries to solve the subproblem of the recursive method in a more elegant way. The full solution is shown below.

这是一种动态编程方法，试图以一种更优雅的方式解决递归方法的子问题。 完整的解决方案如下所示。

func minPathSum(_ grid: [[Int]]) -> Int { var matrix = grid for i in 0..<grid.count { for j in 0..<grid[i].count { if i > 0 && j > 0 { matrix[i][j] += min(matrix[i-1][j], matrix[i][j-1]) } else if i > 0 { matrix[i][j] += matrix[i-1][j] } else if j > 0 { matrix[i][j] += matrix[i][j-1] } } } return matrix[matrix.count - 1][matrix[0].count - 1] }

Time complexity: O(NM) given an input grid of N rows and M columns.

时间复杂度： O(NM)给定N行和M列的输入网格。

在旋转排序数组中搜索 (Search in Rotated Sorted Array)

🥉 Writer’s selection of the week

🥉 作家的每周精选

Description: Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. You are given a target value to search. If it is found in the array return its index, otherwise return -1.

说明 ：假设以升序排序的数组以您不知道的某个枢轴旋转。 将为您提供要搜索的目标值。 如果在数组中找到它，则返回其索引，否则返回-1 。

Note: You may assume no duplicate exists in the array. Your algorithm’s runtime complexity must be in the order of O(log N).

注意：您可以假定阵列中不存在重复项。 算法的运行时复杂度必须为O(log N)的量级。

Example 1Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 0Output: 4Example 2Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 3Output: -1

Since one hard requirement is to solve the problem in O(log N), we have to be careful with our design. Apparently, a loop-through solution won’t work considering it will at least take O(N).

由于解决O(log N)中的问题是一项艰巨的要求，因此我们必须谨慎设计。 显然，考虑到它至少需要O(N)，因此无法通过环通解决方案。

What do you think of when a problem that limits your runtime to O(log N) in the “search” context? Binary Search Algorithm.

当在“ 搜索 ”上下文中将运行时间限制为O(log N)的问题时，您怎么看？ 二进制搜索算法 。

For a normal sorted array, we can easily adapt a binary search algorithm to find our target in O(log N). However, we are told that the input array is rotated at once. Therefore, we need to make some changes in the interval-dividing logic. Similar to a normal binary search, we still have to decide which interval we want to perform a further search given start, mid, and end as dividing points.

对于普通的排序数组，我们可以轻松地采用二进制搜索算法来在O(log N)中找到目标。 但是，我们被告知输入数组立即旋转。 因此，我们需要对间隔划分逻辑进行一些更改。 与普通的二进制搜索相似，我们仍然必须确定要在开始间隔， 中间间隔和结束间隔作为分割点的情况下执行进一步搜索的间隔。

First of all, we need to know which interval the target is more likely to fall into. Take [4, 5, 6, 7, 0, 1, 2] with target 0 as an example, the beginning start is 4, mid is 7, and end is 2. If mid is larger than start, it means the first half of the entire array is not rotated. In that case, we can determine if the target falls into that first half. It turns out to be no, then we set start to mid + 1 and continue to the next round search.

首先，我们需要知道目标更可能落入哪个区间。 取〔4，5，6，7，0，1，2]靶0为例，刚开始起动是4， 中间是7，和端部 2。 如果mid大于start ，则表示整个数组的前半部分不旋转。 在这种情况下，我们可以确定目标是否落入了前一半。 结果为no ，然后将start设置为mid +1 ，然后继续进行下一轮搜索。

In another example of [3, 4, 0, 1, 2] with a target of 4, the beginning start is 3, mid is 0, and end is 2. In this case, mid is smaller than start, which indicates the second half of the array is in the right order. We then focus on the second half and see whether the target is in the range from mid to end. The answer is negative, thus we set end to mid -1 and proceed to the next round.

在另一示例[3，4，0，1，2]为4靶，开头开始为3， 中间是0，并且结束是2。 在这种情况下， mid小于start ，这表示数组的后半部分顺序正确。 然后，我们专注于下半年看到目标是否在范围从中期 结束 。 答案是否定的 ，因此我们将结尾定在-1中，然后进行下一轮。

I only discuss two of the seven cases to handle in our version of binary search. The solution provided shows all the cases with comments explaining them.

我只讨论在我们的二进制搜索版本中要处理的七个案例中的两个。 提供的解决方案显示所有案例，并附带注释以解释它们。

func search(_ nums: [Int], _ target: Int) -> Int { guard nums.count > 0 else { return -1 } var start = 0 var end = nums.count - 1 while start <= end { let mid = start + (end - start) / 2 let midVal = nums[mid] if target == midVal { // The target is found. return mid } else if target == nums[start] { // The target is found. return start } else if target == nums[end] { // The target is found. return end } else if midVal > nums[start] { // If it falls into this condition, it means the first half of // the array is not rotated. Therefore, we can decide if the // target falls into the first half or not. if target < midVal, target > nums[start] { end = mid - 1 } else { start = mid + 1 } } else { // If it falls into this condition, it means the second half of // the array is not rotated. Thus, we can decide whether the // target is in the second half or not. if target > midVal, target < nums[end] { start = mid + 1 } else { end = mid - 1 } } } return -1 }

Time complexity: O(log N) since the way we handle it is similar to the binary search algorithm, which divides the array by half repeatedly until we can decide whether the target is in the array.

时间复杂度： O(log N)，因为我们处理它的方式类似于二进制搜索算法，该算法将数组重复除半，直到我们可以确定目标是否在数组中。

从预遍历构造二叉搜索树 (Construct Binary Search Tree from Preorder Traversal)

Description: Return the root node of a binary search tree that matches the given preorder traversal.

描述 ：返回与给定的遍历遍历匹配的二叉搜索树的根节点。

Note: A binary search tree is a binary tree where for every node, any descendant of node.left has a value less than node.val, and any descendant of node.right has a value greater than node.val.

注：二叉搜索树是二叉树，其中每一个节点，node.left的任何后代有一个值小于node.val和node.right的任何后代具有值大于node.val。

Example 1Input: [8, 5, 1, 7, 10, 12]Output: [8, 5, 10, 1, 7, null, 12] 8 / \ 5 10 / \ \1 7 12

In a preorder traversal, the root node always comes first, then the left descendants, and lastly the right descendants. According to the definition in the note, the first value after the index 0 that has a larger value than the index 0 value is considered to be the root of all right descendants. Besides, the subarray between index 0 and the right root are all left descendants with their root at the start index of the subarray. Afterward, we just need to recursively repeat the process until there is no subarray we can extract from the input. Here’s the solution.

在预遍历中 ，根节点始终首先出现，然后是左后代，最后是右后代。 根据注释中的定义，索引0之后的第一个值(其值大于索引0的值)被视为所有后代的根。 此外，索引0和右根之间的子数组都是左后代 ，其根在子数组的起始索引处。 之后，我们只需要递归地重复该过程，直到没有可以从输入中提取的子数组为止。 这是解决方案。

func bstFromPreorder(_ preorder: [Int]) -> TreeNode? { guard preorder.count > 0 else { return nil } return bstFromPreorder(preorder, 0, preorder.count - 1) } private func bstFromPreorder(_ preorder: [Int], _ start: Int, _ end: Int) -> TreeNode? { let root = TreeNode(preorder[start]) if start + 1 <= end, preorder.count > 1 { var rightRootIdx = -1 for idx in start+1...end { if preorder[idx] > preorder[start] { rightRootIdx = idx break } } if rightRootIdx == start + 1 { root.right = bstFromPreorder(preorder, rightRootIdx, end) } else if rightRootIdx == -1 { root.left = bstFromPreorder(preorder, start + 1, end) } else { root.right = bstFromPreorder(preorder, rightRootIdx, end) root.left = bstFromPreorder(preorder, start + 1, rightRootIdx - 1) } } return root }

Time complexity: O(N²). As we iterate over the entire input array, it takes O(N). In our recursive method, we run a linear search to find the root of the right descendants, where it roughly takes another O(N) in the worst case. This might not be the fastest solution to the problem. What do you think we can optimize the solution? While iterating over the input is inevitable, I am thinking the linear search part probably can be improved. Well, I’ll leave it to you to do the optimization then.

时间复杂度： O(N²) 。 当我们遍历整个输入数组时，它需要O(N) 。 在我们的递归方法中，我们运行线性搜索以找到右后代的根，在最坏的情况下它大约需要另一个O(N) 。 这可能不是解决问题的最快方法。 您认为我们可以优化解决方案什么？ 虽然迭代输入是不可避免的，但我认为线性搜索部分可能会得到改善。 好吧，我将留给您进行优化。

最左边的列至少有一个 (Leftmost Column with at Least a One)

Description: A binary matrix means that all elements are 0 or 1. For each individual row of the matrix, this row is sorted in non-decreasing order.

描述 ：二进制矩阵表示所有元素均为0或1 。 对于矩阵的每个单独行，该行均以非降序排序。

Given a row-sorted binary matrix binaryMatrix, return the leftmost column index with at least a 1 in it. If such an index doesn’t exist, return -1.

给定行排序的二进制矩阵binaryMatrix，返回最左边的列索引，其中至少包含1 。 如果这样的索引不存在，则返回-1 。

Available APIs to access Binary Matrix.

可用API访问Binary Matrix。

BinaryMatrix.get(x, y) returns the element of the matrix at index (x, y).

BinaryMatrix.get(x, y)返回索引为( x ， y )的矩阵元素。

BinaryMatrix.dimensions() returns 2 elements [m, n], which means the matrix is m * n.

BinaryMatrix.dimensions()返回2个元素[ m ， n ]，这意味着矩阵为m * n 。

Submissions making more than 1000 calls to BinaryMatrix.get will be disqualified. Also, any solutions that attempt to circumvent the judge will result in disqualification.

提交超过1000次 BinaryMatrix.get调用的提交将被取消资格。 同样，任何试图绕开法官的解决方案都将导致取消资格。

Example 1Input: [ [0, 0], [1, 1]]Output: 0Example 2Input: [ [0, 0], [0, 1]]Output: 1Example 3Input: [ [0, 0, 0, 1], [0, 0, 1, 1], [0, 1, 1, 1]]Output: 1

Don’t be frightened of the lengthy description of the problem. The solution isn’t as hard as you thought. Let me give you a start point, think about we go from top-right and go all the way toward bottom-left if there are 1s along the path. The basic idea can be designed into a three-phase decision making that reduces our API use.

不要对冗长的问题描述感到恐惧。 解决方案并不像您想的那么难。 让我给您一个起点，考虑一下如果路径上有1 s，我们将从右上角一直走到左下角。 可以将基本思想设计成三个阶段的决策，以减少我们对API的使用。

阶段1。 (Phase 1.)

Go toward the left as much as we can if there is 1 on our way. If there’s no 1, go Phase 2. Record the current leftmost value.

如果途中有1 ，则尽可能向左走。 如果没有，请进入第2阶段 。 记录当前最左边的值。

阶段2。 (Phase 2.)

Go down one row and see if there is any 1. If there is, back to Phase 1. Otherwise, keep going down to another row. Go to Phase 3 until there are no other rows.

向下走一排，看看是否有1个 。 如果存在，请返回到阶段1 。 否则，请继续向下移动到另一行。 转到阶段3，直到没有其他行。

第三阶段 (Phase 3.)

Return the current leftmost value.

返回当前最左边的值。

Following these three phases of logic design, we can avoid redundant API calls while getting the leftmost 1 throughout the matrix. See the full solution in the following.

遵循逻辑设计的这三个阶段，我们可以避免冗余API调用，同时在整个矩阵中获得最左边的 1 。 请参阅下面的完整解决方案。

func leftMostColumnWithOne(_ binaryMatrix: BinaryMatrix) -> Int { let dim = binaryMatrix.dimensions() var x = 0 var y = dim[1] - 1 var currentLeftMost = -1 while x < dim[0], y >= 0 { if y - 1 >= 0 && binaryMatrix.get(x, y - 1) == 1 { y -= 1 currentLeftMost = y } else if x + 1 < dim[0] { x += 1 } else { return binaryMatrix.get(x, y) == 1 ? y : currentLeftMost } } return -1 }

Time complexity: O(N+M) for the worst case of a binary matrix with N rows and M columns. One of the worst cases happens when the first a couple of rows are all 0s except the last row contains full of 1s. In that case, we go all the way down to the last row then go to the leftmost position to get the desired output.

时间复杂度：对于具有N行和M列的二进制矩阵，最坏的情况是O(N + M) 。 最坏的情况之一发生在前几行都为0 s之外，而最后一行包含1 s时。 在这种情况下，我们一直向下到最后一行，然后转到最左边的位置以获得所需的输出。

You’re killing it! Week 3 is done. Developers who want the source code and unit tests for the challenge, you can download them from my Github. Feel free to contribute to my Github or to send me an email if you have questions.

你要杀了它！ 第三周完成。 需要挑战的源代码和单元测试的开发人员，可以从我的Github下载。 如有疑问，请随时为我的Github贡献力量或给我发送电子邮件。

翻译自: https://medium.com/swlh/ios-interview-prep-guide-30-day-code-challenge-in-swift-week-3-5-463f9bb8c4f5

相关资源：微信小程序源码-合集6.rar