知名互联网公司校招中常见的算法题（19-20）

本是古典何须时尚 2024-03-22 13:26 44阅读 0赞

##  ##

#### 题目19：Z 字形变换 ####

题目描述：

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

解决思路：

我们可以用一个二维数组来模拟 Z 字形变换的过程。我们先用一个变量来记录当前行数和方向，然后遍历字符串，将每个字符加入对应的行中，直到遍历完整个字符串。

代码实现：

public String convert(String s, int numRows) {
      if (numRows == 1) {
          return s;
      }
      char[][] matrix = new char[numRows][s.length()];
      int row = 0;
      int col = 0;
      int direction = 1;
      for (char c : s.toCharArray()) {
          matrix[row][col] = c;
          row += direction;
          if (row == numRows - 1 || row == 0) {
              direction *= -1;
          }
          col += 1;
      }
      StringBuilder sb = new StringBuilder();
      for (int i = 0; i < numRows; i++) {
          for (int j = 0; j < s.length(); j++) {
              if (matrix[i][j] != 0) {
                  sb.append(matrix[i][j]);
              }
          }
      }
      return sb.toString();
    }

题目20：最长回文子串

题目描述：

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

解决思路：

我们可以用动态规划的思想来解决这个问题。我们用一个二维数组 dpi 来表示字符串从 i 到 j 是否为回文串。初始时，dpi = true；当 s\[i\] == s\[j\] 时，如果 j-i <= 2，那么 dpi = true；否则，dpi = dpi+1。

代码实现：

public String longestPalindrome(String s) {
      int n = s.length();
      boolean[][] dp = new boolean[n][n];
      int maxLen = 1;
      int start = 0;
      // Initialize dp array
      for (int i = 0; i < n; i++) {
          dp[i][i] = true;
      }
      for(int j = 1; j < n; j++) {
    for (int i = 0; i < j; i++) {
    if (s.charAt(i) == s.charAt(j)) {
    if (j - i <= 2) {
    dp[i][j] = true;
    } else {
    dp[i][j] = dp[i+1][j-1];
    }
    } else {
    dp[i][j] = false;
    }
          if (dp[i][j] && j - i + 1 > maxLen) {
              maxLen = j - i + 1;
              start = i;
          }
      }
    }
    return s.substring(start, start + maxLen);
    }

以上是关于常见算法题的解决思路、代码实现以及实际案例的详细讲解。如果您想深入了解更多算法知识，可以参考上面的参考文献和代码实现。希望本文能够对大家在准备互联网公司的校招面试过程中有所帮助。