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

超、凢脫俗 2024-03-22 13:25 25阅读 0赞

##  ##

题目14：无重复字符的最长子串

题目描述：

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

解决思路：

我们可以用哈希表来解决这个问题。我们用一个哈希表来存储每个字符出现的位置。遍历字符串，如果遇到重复的字符，就更新子串的起始位置为当前重复字符的下一个位置，并更新哈希表中重复字符的位置。同时记录子串的最大长度。

代码实现：

public int lengthOfLongestSubstring(String s) {
      int[] index = new int[128];
      int left = 0;
      int maxLen = 0;
      for (int right = 0; right < s.length(); right++) {
          char c = s.charAt(right);
          left = Math.max(left, index[c]);
          index[c] = right + 1;
          maxLen = Math.max(maxLen, right - left + 1);
      }
      return maxLen;
    }

题目15：旋转图像

题目描述：

给定一个 n × n 的二维矩阵表示一个图像。将图像顺时针旋转 90 度。

解决思路：

我们可以用翻转和转置的方法来解决这个问题。首先，我们将矩阵沿着水平中线进行翻转；然后，将矩阵沿着主对角线进行翻转。这样就得到了顺时针旋转 90 度的矩阵。

代码实现：

public void rotate(int[][] matrix) {
      int n = matrix.length;
      // Flip matrix horizontally
      for (int i = 0; i < n / 2; i++) {
          for (int j = 0; j < n; j++) {
              int temp = matrix[i][j];
              matrix[i][j] = matrix[n - i - 1][j];
              matrix[n - i - 1][j] = temp;
          }
      }
      // Transpose matrix
      for (int i = 0; i < n; i++) {
          for (int j = i + 1; j < n; j++) {
              int temp = matrix[i][j];
              matrix[i][j] = matrix[j][i];
              matrix[j][i] = temp;
          }
      }
    }

题目16：有效的括号

题目描述：

给定一个只包括 '('，')'，'\{'，'\}'，'\['，'\]' 的字符串 s ，判断字符串是否有效。有效字符串需满足：

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

解决思路：

我们可以用栈来解决这个问题。遍历字符串，如果遇到左括号，就将它入栈；如果遇到右括号，就弹出栈顶元素并判断是否匹配。如果不匹配，就返回 false；如果最后栈不为空，也返回 false。

代码实现：

public boolean isValid(String s) {
      Stack<Character> stack = new Stack<>();
      for (char c : s.toCharArray()) {
          if (c == '(' || c == '{' || c == '[') {
              stack.push(c);
          } else {
              if (stack.isEmpty()) {
                  return false;
              }
              char top = stack.pop();
              if ((c == ')' && top != '(') || (c == '}' && top != '{') || (c == ']' && top != '[')) {
                  return false;
              }
          }
      }
      return stack.isEmpty();
    }

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