Обнулить окружающие элементы в матрице, когда вы найдете нулевое значение

Пожалуйста, можете ли вы предложить лучше / Оптимизировано логика или код для вопроса. Когда вы находите нулевое значение в матрице, просили сделать этот элемент суммой его верхнего, нижнего, левого, правого значения и сделать нулевыми верхний, нижний, левый и правый элементы. Я предполагаю, что предоставленная матрица имеет как минимум 2 строки и 2 столбца, но если вы можете опубликовать код для любого типа матрицы, это будет очень полезно. Я полностью прокомментировал код для легкого понимания, просто скопировать и вставить это в редакторе и настроить значения матричной переменной в основной функции программы.


import java.util.ArrayList;

public class Main {
    static void MakeSurroundingElementsZero(int i,int j,int[][]matrix){
        //when the element is not on the boundary of matrix.means it has
        // all surrounding elements
        if(i >0 && i < matrix.length-1 && j >0 && j < matrix[i].length-1){
             matrix[i][j-1]=matrix[i][j+1]=matrix[i-1][j]=matrix[i+1][j]=0;
        }
        //when it is in the first row
        else if(i ==0){
            // when it is not the first or last element in the first row
            if(j >0 && j < matrix[i].length-1){
                 matrix[i][j+1]=matrix[i][j-1]=matrix[i+1][j]=0;
            }
            //when it is the first element of the first row
            else if(j ==0){
                 matrix[i][j+1]=matrix[i+1][j]=0;
            }
            // when it is the last element of the first row
            else{
                matrix[i][j-1]=matrix[i+1][j]=0;
            }
        }
        //when the element is present in the last row
        else{
            //element not the last or the first in the last row
            if (j >0 && j < matrix[i].length-1 ){
                matrix[i][j+1]=matrix[i-1][j]=matrix[i][j-1]=0;
            }
            //first element in the last row
            else if (j==0){
                matrix[i-1][j]=matrix[i][j+1]=0;
            }
            //last element of the last row
            else{
                matrix[i][j-1]=matrix[i-1][j]=0;
            }
        }
    }
    static void addElements(int i,int j,int[][]matrix){
        //when the element is not on the boundary of matrix.means it has
        // all surrounding elements
        if(i >0 && i < matrix.length-1 && j >0 && j < matrix[i].length-1){
            matrix[i][j] = matrix[i][j-1]+matrix[i][j+1]+matrix[i-1][j]+matrix[i+1][j];
        }
        //when it is in the first row
        else if(i ==0){
            // when it is not the first or last element in the first row
            if(j >0 && j < matrix[i].length-1){
                matrix[i][j] = matrix[i][j+1]+matrix[i][j-1]+matrix[i+1][j];
            }
            //when it is the first element of the first row
            else if(j ==0){
                matrix[i][j] = matrix[i][j+1]+matrix[i+1][j];
            }
            // when it is the last element of the first row
            else{
                matrix[i][j] = matrix[i][j-1]+matrix[i+1][j];
            }
        }
        //when the element is present in the last row
        else{
            //element not the last or the first in the last row
            if (j >0 && j < matrix[i].length-1 ){
                matrix[i][j] = matrix[i][j+1]+matrix[i-1][j]+matrix[i][j-1];
            }
            //first element in the last row
            else if (j==0){
                matrix[i][j]= matrix[i-1][j]+matrix[i][j+1];
            }
            //last element of the last row
            else{
                matrix[i][j] = matrix[i][j-1]+matrix[i-1][j];
            }
        }
    }
    static void MakeZeroes(int[][] matrix) {
        ArrayList<Integer[]> zeroElements = new ArrayList<Integer[]>();
        for (int i = 0;i < matrix.length;i++) {
            for(int j = 0;j < matrix[i].length;j++){
                //checking each element for zero value
                if(matrix[i][j] == 0){
                    addElements(i,j,matrix);
                    //store it as we haven't made the surrounding elements zero yet

                    Integer[] zeroelem = {i,j};
                    zeroElements.add(zeroelem);

                }
            }
        }
        //finally, make surrounding elements zero
        for (int i = 0;i<zeroElements.size();i++){

                MakeSurroundingElementsZero(zeroElements.get(i)[0],zeroElements.get(i)[1],matrix);

        }
    }
    public static void main(String[] args) {
        int[][] matrix = {{2,0,4,0},
                          {5,9,7,9},
                          {2,0,8,0}};
        MakeZeroes(matrix);
        for (int i =0;i < matrix.length;i++){
            for (int j = 0; j < matrix[i].length;j++){
                System.out.print(matrix[i][j]+" ");
            }
            System.out.println();
        }


    }
}

Мой подход заключается в следующем: —

  • Перейти к каждому элементу.
  • Проверьте, равно ли оно нулю.
  • Если ноль, то проверьте, где находится этот элемент, полностью ли внутри матрицы или на границе.
  • Добавьте соответственно элементы вокруг этого элемента с нулевым значением.
  • Сохраните индекс этого нулевого элемента в ArrayList.
  • Выполните цикл ArrayList, чтобы обнулить окружающие элементы.

4 ответа
4

    }
    //when it is in the first row
    else if(i ==0){

Пожалуйста, не делай этого. Да, языки C-стиля поддерживают произвольное количество пробелов (включая комментарии) между } и else. Компилятор будет доволен этим. Но разделение конца предыдущего блока и кода, который сообщает вам, что следующий блок является частью той же структуры, только усложняет задачу. Это значительно упрощает следующему человеку, редактирующему код, выполнение чего-то вроде

    } else {
        // do something here
    }
    //when it is in the first row
    else if(i ==0){

Что может вызвать ошибку компилятора или, что еще хуже, может переместить ваш else if в другую структуру управления.

Языки C-стиля не различаются между окончанием блока и окончанием управляющей структуры. Так что, пожалуйста, помогите читателям, всегда сохраняя } и else как можно ближе. Если не на одной строке (что я лично предпочитаю), то хотя бы на соседних строках. Код, который выполняет одно действие, хотя кажется, что он выполняет другое, может быть невероятно трудным для отладки.

    Подходящая абстракция

    Пожалуйста, используйте пробелы. Позвольте IDE переформатировать ваш код.

    Смещения соседей могут быть элементами из {(1, 0), (-1, 0), (0, 1), (0, -1)}.

    Например:

    private static final int[] UP = {-1, 0};
    private static final int[] DOWN = {1, 0};
    private static final int[] LEFT = {0, -1};
    private static final int[] RIGHT = {0, 1};
    // Num Pad orientaton:
    // 7 8 9
    // 4 5 6
    // 1 2 3
    private static final int[][] NEIGHBORS7 = {DOWN, RIGHT};
    private static final int[][] NEIGHBORS8 = {DOWN, LEFT, RIGHT};
    private static final int[][] NEIGHBORS9 = {DOWN, LEFT};
    private static final int[][] NEIGHBORS4 = {UP, DOWN, RIGHT};
    private static final int[][] NEIGHBORS5 = {UP, DOWN, LEFT, RIGHT};
    private static final int[][] NEIGHBORS6 = {UP, DOWN, LEFT};
    private static final int[][] NEIGHBORS1 = {UP, RIGHT};
    private static final int[][] NEIGHBORS2 = {UP, LEFT, RIGHT};
    private static final int[][] NEIGHBORS3 = {UP, LEFT};
    
    int[][] neighbors(int i, int j, int[][] matrix) {
        if (i == 0) {
            if (j == 0) return NEIGHBORS7;
            if (j == matrix[0].length - 1) return NEIGHBORS9;
            return NEIGHBORS8;
        }
        if (i == matrix.length - 1) {
            if (j == 0) return NEIGHBORS1;
            if (j == matrix[0].length - 1) return NEIGHBORS3;
            return NEIGHBORS2;
        }
        if (j == 0) return NEIGHBORS4;
        if (j == matrix[0].length - 1) return NEIGHBORS6;
        return NEIGHBORS5;
    }
    
    for (int[] neighborIJ: neighbors(i, j, matrix)) {
        int nI = i + neighborIJ[0];
        int nJ = j + neighborIJ[1];
        ...
    }
    

    Лучше указать доступных соседей из каждой точки и пройтись по ним, чтобы принять их значения.

    Итак, две абстракции: предоставить соседей для обхода. И сосед как смещение, не рассчитываемый заново для каждого (i, j).

    Это даст меньше кода, меньше ветвей, поэтому сбои будут обнаружены быстрее.

    Стиль Java

    Тогда есть:

        ArrayList<Integer[]> zeroElements = new ArrayList<Integer[]>();
    

    который должен быть

        List<int[]> zeroElements = new ArrayList<>();
    

    То есть:

    • программа против интерфейсов, наиболее общий код таким образом;
    • использовать алмазный оператор <>;
    • int[] это класс тоже можно использовать как универсальный тип.

    Украшение

    Вместо того

    System.out.print(matrix[i][j]+" ");
    

    форматированный выглядит лучше, когда в суммах больше цифр:

    System.out.printf("%3d ", matrix[i][j]);
    

    Алгоритмические вопросы

    Вы собираете кандидатов, а затем производите суммирование / накопление значений.

    Если суммируется один кандидат, то два других соседних кандидата могут больше не быть кандидатами или получить разные суммы. Воруют у соседских кандидатов.

    Вероятно, это делается так, как если бы один кандидат суммировался, его соседи автоматически становились равными нулю, а значит, и кандидат тоже.

    • Помимо написания «сосед» или «сосед», если хотите, мне действительно не нравятся идентификаторы, названные с использованием счетчика, например NAYBOURS7 если быть честным. Что означает это число?

      — Маартен Бодевес

    • @MaartenBodewes Я пытался американизировать британского соседа. Нумерация — это одна цифровая клавиатура 789 в верхней строке, затем 456 в середине и 123 внизу. Подумал добавить комментарий, но не хотел растягивать ответ. Я исправлю написание

      — Юп Эгген

    • Да, я предполагал, что это неправильный перевод. Когда дело доходит до орфографии в США, я сам разбираюсь: P NEIGHBORS5 хотя, наверное, сегодня вечером за мной поохотится.

      — Маартен Бодевес

    • @MaartenBodewes, твое имя кажется Фламиш, мое голландское, соседи, так сказать. Я подумал, что вспомню более крупное различие, чем цвет / цвет, но это должно было быть другое слово.

      — Юп Эгген

    • Похоже, он из Гронингена, а сейчас я живу в Харлеме. Есть даже верфь под названием «Bodewes» в Нидерландах одного далекого родственника. Это не такое уж редкое имя, как вы могли подумать.

      — Маартен Бодевес

    Есть кое-что, что вы узнаете во время программирования, это то, что вложенность (наличие нескольких условий / циклов внутри друг друга) затрудняет чтение кода. В этом случае он также способствует повторению кода, чего мы обычно стараемся избегать.

    Давайте сначала посмотрим на MakeSurroundingElementsZero. Цель этой функции довольно ясна, хорошее название. Хотя что-то можно было бы улучшить: действительно ли это весь район или действительно только непосредственно прилегающие элементы? Например, это результат:

    [1, 2, 3]
    [4, 0, 6]
    [7, 8, 9] 
    

    Должен быть первый результат или второй?

    [1, 0, 3]
    [0, 20, 0]
    [7, 0, 9]
    

    или

    [0, 0, 0]
    [0, 40, 0]
    [0, 0, 0]
    

    Глядя на ваш код, кажется, что первый ответ правильный, но из описания проблемы не ясно. В обработке изображений для такого типа окрестностей есть название: 4-соседнее и 8-соседнее. 4-сосед представляет первый пример, а 8-сосед — второй. Что ж, теперь, когда это прояснилось, вперед!

    Что касается самого кода: когда я работаю с алгоритмами, моя уловка состоит в том, чтобы попытаться придумать самый простой способ объяснить алгоритм и начать с него. В этом случае мы хотим сделать значения позиций left, right, up, down нулевыми, если они находятся в пределах нашей матрицы.

    Итак, у нас есть следующие позиции: [i - 1, j], [i + 1, j], [i, j - 1], [i, j + 1] и мы хотим обнулить их, если это возможно:

    static void MakeSurroundingElementsZero(int i, int j, int[][] matrix){
        if (i - 1 > 0) {
            matrix[i-1][j] = 0;
        }
        if (i + 1 < matrix[i].length) {
            matrix[i+1][j] = 0;
        }
        if (j - 1 > 0) {
            matrix[i][j-1] = 0;
        }
        if (j + 1 < matrix[j].length) {
            matrix[i][j+1] = 0;
        }
    }
    

    Этот код проверяет, можно ли установить для 4 соседей ноль, и делает это. Это также намного проще, чем то, что вы написали, но оно выполняет свою работу. Главный вывод из этого состоит в том, что вы должны попытаться разложить большие проблемы на более мелкие, где решение всех мелких проблем берет на себя решение большой.

    То же самое и с addElements функция. Мы можем использовать практически тот же код. Однако я ввел переменную с именем sumOfNeighbors. При работе с матрицами полезно использовать переменные, потому что вся индексация загромождает код и затрудняет чтение. Используя переменную, мы можем точно определить, что мы делаем, и затем присвоить sumOfNeighbors значение в центральной ячейке:

    static void addElements(int i,int j,int[][]matrix){
        int sumOfNeighbors = 0
    
        if (i - 1 > 0) {
            sumOfNeighbors += matrix[i-1][j];
        }
        if (i + 1 < matrix[i].length) {
            sumOfNeighbors += matrix[i+1][j];
        }
        if (j - 1 > 0) {
            sumOfNeighbors += matrix[i][j-1];
        }
        if (j + 1 < matrix[j].length) {
            sumOfNeighbors += matrix[i][j+1];
        }
    
        matrix[i][j] = sumOfNeighbors;
    }
    

    Как отметил @Joop Eggen в своем ответе, есть крайний случай, который не рассматривается в вашем описании проблемы.

    Что происходит в этом сценарии?

    [1,2,3,4]
    [5,0,0,6]
    [7,8,9,10]
    

    Если результат будет:

    [1,0,0,4]
    [0,15,18,0]
    [7,0,0,10]
    

    или

    [1,0,0,4]
    [0,0,33,0]
    [7,0,0,10]
    

    или

    [1,0,0,4]
    [0,33,0,0]
    [7,0,0,10]
    

    Возможно, у вас нет ответа на этот вопрос, но при программировании также важно учитывать крайние случаи!

    В общем, ваш код действительно был не так уж плох, но вам нужно взглянуть на проблему в голове (или на бумаге), прежде чем писать код, чтобы упростить ее, чтобы вы могли написать лучший код 🙂

    Да, IEatBagels, в моем коде много недоработок, сейчас я понял. Можете ли вы сказать мне, это проблема начального уровня, я имею в виду, что как новичок я должен был решить этот вопрос с учетом всех крайних случаев. Мне все еще интересно, какой может быть правильный код для этого — Что может понять новичок

    — Арьяман

    Конкретный стиль:

    1. множественные назначения в одной строке только труднее читать, это не сделает ваш код быстрее;
    2. слишком мало пробелов:
      • после запятой;
      • окружающие задания с использованием =;
      • окружающие операторы, такие как +;
      • после int[][] массив типа массивов;
      • перед открывающими скобками и после закрывающих скобок;
      • после else;
    3. MakeZeroes не использует соглашение о кодировании Java для запуска методов с маленькой буквы.

    Обратите внимание, что (2) можно получить, просто используя средство форматирования для вашего кода, на случай, если вы не хотите явно вводить каждое пространство. Таким образом, вы получаете удобство и хорошо отформатированный / читаемый код.


    Специфические для программирования:

    1. есть код копирования / вставки при присвоении нулю, а при суммировании это общий красный флаг;
    2. вы используете индексацию для ArrayList пока вы последовательно просматриваете индексы при установке значений. Для этого вы должны использовать итератор или, в более общем смысле, для каждого построить.

    Конкретный дизайн:

    1. i а также j (обычно используются для циклов) используются вместо, например, x а также y, обычно используется для координат;
    2. addElements(i,j,matrix) называется в MakeZeroes что полностью противоречит принципу наименьшего удивления;
    3. Main это, конечно, не очень хорошее название класса;
    4. (второстепенный): я обычно использую таблицу в качестве начального параметра, но если бы это было поле, возможно, это вообще не было параметром.

    Дизайн был бы намного проще, если бы вы создали Position класс. Это позволило бы вам создавать функции для проверки правильности позиции (вы можете быть поражены, сколько 0 и такие литералы вдруг больше не нужны). Если вы хотите сохранить места, которые должны быть нулевыми, тогда вы можете просто сохранить Position вместо другого массива.


    Я также рекомендую вам создать Matrix или Table класс сортов. Это позволит вам убедиться, что поле представляет собой красивую таблицу — в настоящее время размеры массива в массив вполне мог быть другим. Обычно вы используете классы для инкапсуляции данных и предотвращения достижения вашей программой недопустимого состояния.


    Вместо того, чтобы отслеживать все нулевые значения, вы также можете создать копию матрицы и немедленно выполнить операции, используя данные исходной матрицы. Это, конечно, имеет тот недостаток, что вам требуется память для двух матриц, но вам нужно пройти по матрице только один раз, и вы можете вычислить и / или обнулить значения напрямую. Кроме того, список целочисленных массивов также довольно дорог.

    Однако это скорее альтернатива, чем критика, ваш текущий дизайн довольно приличный.

    Обратите внимание, что вы можете получить повторяющиеся позиции, которые обнулены, поэтому вы также можете использовать Set позиций. Но учтите, что для этого нужно иметь право equals а также hashCode функциональность — легко создается с помощью записывать для Position (Java 14 и новее).


    Еще один продвинутый прием — использовать перечисления для получения позиций относительно другой позиции.

    Например, вы можете использовать

    enum Neighbor {
        NORD, EAST, SOUTH, WEST;
    }
    

    или даже параметризованный

    enum Neighbor {
        NORD(0, -1), EAST(1, 0), SOUTH(0, 1), WEST(-1, 0);
    
        private Neighbor(deltaX, deltaY) {
            ...
        }
    
        ...
    }
    

    Это все здорово, но для новичка это большая работа. Следовательно, вот шаблон, с которым можно поиграть:

    
    public static record Position(int x, int y) {
        Position getNeighbor(Neighbor neighbor) {
            return new Position(this.x + neighbor.getDeltaX(), this.y + neighbor.getDeltaY());
        }
    }
    
    public static record Dimensions(int width, int height) {}
    
    
    public enum Neighbor {
        NORTH(0, -1), EAST(1, 0), SOUTH(0, 1), WEST(-1, 0);
    
        private int deltaX;
        private int deltaY;
    
        private Neighbor(int deltaX, int deltaY) {
            this.deltaX = deltaX;
            this.deltaY = deltaY;
            
        }
        
        public int getDeltaX() {
            return deltaX;
        }
        
        public int getDeltaY() {
            return deltaY;
        }
    }
    
    public static class Matrix implements Cloneable {
        private int[][] matrix;
        private Dimensions dimensions;
        
        public Matrix(int[][] initialMatrix) {
            this.dimensions = new Dimensions(initialMatrix[0].length, initialMatrix.length);
         
            // clones 2-dimensional array and checks row size
            this.matrix = initialMatrix.clone();
            for (int y = 0; y < dimensions.height(); y++) {
                int[] row = initialMatrix[y];
                if (row.length != dimensions.width()) {
                    throw new IllegalArgumentException("Row " + y + " is not of the same width as the preceding rows");
                }
                this.matrix[y] = row.clone();
            }
        }
                
        public boolean isValid(Position pos) {
            return pos.x >= 0 && pos.x < dimensions.width() && pos.y >= 0 && pos.y < dimensions.height();
        }
        
        public void set(Position pos, int value) {
            assert isValid(pos);
            matrix[pos.y()][pos.x()] = value;
        }
        
        public int get(Position pos) {
            assert isValid(pos);
            return matrix[pos.y()][pos.x()];
        }
        
        public Matrix clone() {
            return new Matrix(matrix);
        }
        
        public Dimensions getDimensions() {
            return dimensions;
        }
    }
    

    Это весь код, который вы можете написать, даже не глядя на фактические необходимые вычисления. Наличие базового набора классов и методов действительно может помочь вам сосредоточиться на проблеме. Вы можете скопировать / вставить его в альтернативный Main класс. Можно использовать Neighbor.values() чтобы перебрать всех соседей.

    • Действительно мелочи: public enum Neighbor достаточно (неявно статический), и private final int deltaX; — затем может использовать public без геттеров. record Position хорошая идея / лучшая абстракция.

      — Юп Эгген

    • Вы конечно правы насчет enum по умолчанию статичен, поскольку компилятор создает отдельные файлы классов для каждого enum пример. Однако я не понимаю, как я могу использовать этот факт, чтобы ввести значение const для каждого экземпляра класса изнутри enum Технические характеристики. Если я не ошибаюсь, приведенный выше трюк взят из книги Джошуа «Эффективная Java». В моем случае сосед родственник на позицию, так Position это основная идея, а Neighbor усиливает это как new Position(oldPos.x() - 1, oldPos.y()) на мой вкус слишком загадочно.

      — Маартен Бодевес



    Добавить комментарий

    Ваш адрес email не будет опубликован. Обязательные поля помечены *