1428. Leftmost Column with at Least a One

LeetCode medium original: C# #csharp #leetcode #matrix #medium #search #sort #string #two-pointers

题目文本会按所选界面语言从俄语翻译；代码保持不变。

LeetCode Static

Строково-отсортированная бинарная матрица означает, что все elementы равны 0 или 1, и каждая 字符串 матрицы отсортирована в неубывающем порядке.

Дана строково-отсортированная бинарная матрица binaryMatrix, return индекс (начиная с 0) самого левого столбца, содержащего 1. Если такого индекса не существует, return -1.

Вы не можете напрямую обращаться к бинарной матрице. Вы можете получить доступ к матрице только через интерфейс BinaryMatrix:

- BinaryMatrix.get(row, col) returns element матрицы с индексом (row, col) (начиная с 0).

- BinaryMatrix.dimensions() returns размеры матрицы в виде списка из 2 elementов [rows, cols], что означает, что матрица имеет размер rows x cols.

Отправки, делающие более 1000 вызовов к BinaryMatrix.get, будут оценены как неправильный ответ. Кроме того, любые решения, пытающиеся обойти проверку, будут дисквалифицированы.

Для пользовательского тестирования вводом будет вся бинарная матрица mat. Вы не будете иметь прямого доступа к бинарной матрице.

示例:

Input: mat = [[0,0],[0,1]]

Output: 1

C# 解法

匹配/原始

public class Solution {
    public int LeftMostColumnWithOne(BinaryMatrix binaryMatrix) {
        IList<int> dimensions = binaryMatrix.Dimensions();
        int rows = dimensions[0];
        int cols = dimensions[1];
        
        int currentRow = 0;
        int currentCol = cols - 1;
        
        while (currentRow < rows && currentCol >= 0) {
            if (binaryMatrix.Get(currentRow, currentCol) == 0) {
                currentRow++;
            } else {
                currentCol--;
            }
        }
        
        return (currentCol == cols - 1) ? -1 : currentCol + 1;
    }
}

C++ 解法

自动草稿，提交前请检查

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int LeftMostColumnWithOne(BinaryMatrix binaryMatrix) {
        vector<int> dimensions = binaryMatrix.Dimensions();
        int rows = dimensions[0];
        int cols = dimensions[1];
        
        int currentRow = 0;
        int currentCol = cols - 1;
        
        while (currentRow < rows && currentCol >= 0) {
            if (binaryMatrix.Get(currentRow, currentCol) == 0) {
                currentRow++;
            } else {
                currentCol--;
            }
        }
        
        return (currentCol == cols - 1) ? -1 : currentCol + 1;
    }
}

Java 解法

匹配/原始

class Solution {
    public int leftMostColumnWithOne(BinaryMatrix binaryMatrix) {
        int rows = binaryMatrix.dimensions().get(0);
        int cols = binaryMatrix.dimensions().get(1);

        int currentRow = 0;
        int currentCol = cols - 1;
    
        while (currentRow < rows && currentCol >= 0) {
            if (binaryMatrix.get(currentRow, currentCol) == 0) {
                currentRow++;
            } else {
                currentCol--; 
            }
        }
    
        return (currentCol == cols - 1) ? -1 : currentCol + 1;
    }
}

JavaScript 解法

匹配/原始

var leftMostColumnWithOne = function(binaryMatrix) {
    const [rows, cols] = binaryMatrix.dimensions();
    let currentRow = 0, currentCol = cols - 1;
    
    while (currentRow < rows && currentCol >= 0) {
        if (binaryMatrix.get(currentRow, currentCol) === 0) {
            currentRow++;
        } else {
            currentCol--;
        }
    }
    
    return (currentCol === cols - 1) ? -1 : currentCol + 1;
};

Go 解法

匹配/原始

func leftMostColumnWithOne(binaryMatrix BinaryMatrix) int {
    dimensions := binaryMatrix.Dimensions()
    rows, cols := dimensions[0], dimensions[1]
    
    currentRow, currentCol := 0, cols - 1
    
    for currentRow < rows && currentCol >= 0 {
        if binaryMatrix.Get(currentRow, currentCol) == 0 {
            currentRow++
        } else {
            currentCol--
        }
    }
    
    if currentCol == cols - 1 {
        return -1
    }
    return currentCol + 1
}

Algorithm

1⃣Инициализируйте указатели на текущую строку и столбец, начиная с верхнего правого угла матрицы.

2⃣Повторяйте поиск до тех пор, пока указатели не выйдут за границы матрицы:

Если текущий element равен 0, сдвигайте указатель строки вниз.

Если текущий element равен 1, сдвигайте указатель столбца влево.

3⃣Если указатель столбца остается на последнем столбце, значит, все elementы матрицы равны 0, и return -1. В противном случае return индекс самого левого столбца с 1.

😎

Vacancies for this task

活跃职位 with overlapping task tags are 已显示.

所有职位

目前还没有活跃职位。