fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. //6. Zigzag Conversion
  4.  
  5. // Строка "PAYPALISHIRING" записывается зигзагообразным образом в заданном количестве строк следующим образом:
  6. // (для лучшей читаемости вы можете отобразить этот шаблон фиксированным шрифтом)
  7. //P   A   H   N
  8. //A P L S I I G
  9. //Y   I   R
  10. // А затем читайте построчно: "PAHNAPLSIIGYIR"
  11. //Напишите код, который будет принимать строку и выполнять это преобразование с учётом количества строк:
  12. class Solution {
  13.     // [code1]
  14.     public String convert(String s, int numRows) {
  15.         // Проверяем тривиальные случаи:
  16.         // если numRows равен 1 или строка короче numRows, возвращаем исходную строку
  17.         if (numRows == 1 || s.length() <= numRows) {
  18.             return s;
  19.         }
  20.  
  21.         // Создаём StringBuilder для каждой строки зигзага
  22.         // Размер массива = минимум между numRows и длиной строки (для экономии памяти)
  23.         // [code2]
  24.         StringBuilder[] rows = new StringBuilder[Math.min(numRows, s.length())];
  25.  
  26.         // Инициализируем каждый элемент массива новым объектом StringBuilder
  27.         for (int i = 0; i < rows.length; i++) {
  28.             rows[i] = new StringBuilder();
  29.         }
  30.         // Инициализируем переменную для отслеживания текущей строки
  31.         // [code3]
  32.         int currentRow = 0;  // Текущая строка, в которую добавляем символ
  33.         boolean goingDown = false;  // Флаг направления движения по зигзагу: вниз или вверх по зигзагу
  34.                                     // Начинаем с false, так как первый символ будет в строке 0
  35.         // Проходим по всем символам исходной строки
  36.         // [code4]
  37.         for (char c : s.toCharArray()) {
  38.             rows[currentRow].append(c);  // Добавляем текущий символ в StringBuilder текущей строки
  39.  
  40.             // Если достигли верхней (0) или нижней (numRows-1) границы,
  41.             // то меняем направлениена противоположное
  42.             if (currentRow == 0 || currentRow == numRows - 1) {
  43.                 goingDown = !goingDown;
  44.             }
  45.  
  46.             // Переходим к следующей строке: увеличиваем currentRow
  47.             // при движении вниз, уменьшаем при движении вверх
  48.             currentRow += goingDown ? 1 : -1;
  49.         }
  50.  
  51.         // Создаём новый StringBuilder формирования  для результата
  52.         // [code5]
  53.         StringBuilder result = new StringBuilder();
  54.  
  55.         // Объединяем все строки в одну результирующую
  56.         // Добавляем содержимое каждого из них в result
  57.         for (StringBuilder row : rows) {
  58.             result.append(row);
  59.         }
  60.  
  61.         return result.toString();  // Преобразуем StringBuilder в String
  62.     }
  63.     // Особенности реализации на Java:
  64.     //StringBuilder вместо String - используем StringBuilder для эффективной конкатенации строк, так как он изменяемый
  65.     //toCharArray() - преобразуем строку в массив символов для удобного итеративного обхода
  66.     //Math.min() - используем для определения размера массива, чтобы избежать создания лишних элементов
  67.     //Сложность алгоритма:
  68.     //Время: O(n), где n - длина строки s. Каждый символ обрабатывается один раз.
  69.     //Память: O(n), так как все символы сохраняются в StringBuilder'ах.
  70.     //Пример работы:
  71.     //Для s = "PAYPALISHIRING", numRows = 3:
  72.     //rows[0] = "PAHN"
  73.     //rows[1] = "APLSIIG"
  74.     //rows[2] = "YIR"
  75.     //Результат: "PAHNAPLSIIGYIR"
  76.     public String convert1(String s, int numRows) {
  77.         // Check trivial cases:
  78.         // If numRows is 1 or string length is less than or equal to numRows, return the original string
  79.         if (numRows == 1 || s.length() <= numRows) return s;
  80.  
  81.         // Create a StringBuilder for each zigzag row
  82.         // Array size = minimum between numRows and string length (for memory efficiency)
  83.         StringBuilder[] rows = new StringBuilder[Math.min(numRows, s.length())];
  84.  
  85.         // Initialize each array element with a new StringBuilder object
  86.         for (int i = 0; i < rows.length; i++) rows[i] = new StringBuilder();
  87.  
  88.         // Initialize variable to track current row
  89.         int currentRow = 0;  // Current row to add character to
  90.         boolean goingDown = false;  // Flag for zigzag direction: down or up
  91.                                     // Start with false as first character will be in row 0
  92.         // Iterate through all characters in the input string
  93.         for (char c : s.toCharArray()) {
  94.             rows[currentRow].append(c);  // Add current character to current row's StringBuilder
  95.  
  96.             // If we reach the top (0) or bottom (numRows-1) boundary,
  97.             // reverse the direction
  98.             if (currentRow == 0 || currentRow == numRows - 1) {
  99.                 goingDown = !goingDown;
  100.             }
  101.  
  102.             // Move to next row: increment currentRow when going down,
  103.             // decrement when going up
  104.             currentRow += goingDown ? 1 : -1;
  105.         }
  106.  
  107.         // Create a new StringBuilder for the result
  108.         StringBuilder result = new StringBuilder();
  109.  
  110.         // Combine all rows into a single result
  111.         // Append each row's content to result
  112.         for (StringBuilder row : rows) result.append(row);
  113.  
  114.         // Convert StringBuilder to String
  115.         return result.toString();
  116.     }
  117.  
  118.     public static void main(String[] args) {
  119.         String s = "PAYPALISHIRING";
  120.         int numRows = 3;
  121.  
  122.         System.out.println(new Solution().convert(s, numRows));
  123.     }
  124. }
Success #stdin #stdout 0.07s 54584KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
PAHNAPLSIIGYIR
https://ideone.com/O4KjVU
language:
Java (HotSpot 12)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!