leetcode模拟面试

àì夳堔傛蜴生んèń 2023-07-24 08:13 10阅读 0赞

90分钟3道题

第一题：字符串

/**
 * 给你一个字符串 s，它由数字（'0' - '9'）和 '#' 组成。我们希望按下述规则将 s 映射为一些小写英文字符：
 * 
 * 字符（'a' - 'i'）分别用（'1' - '9'）表示。
 * 字符（'j' - 'z'）分别用（'10#' - '26#'）表示。
 * 返回映射之后形成的新字符串。
 * 
 * 题目数据保证映射始终唯一。
 * 
 * 
 * 
 * 示例 1：
 * 
 * 输入：s = "10#11#12"
 * 输出："jkab"
 * 解释："j" -> "10#" , "k" -> "11#" , "a" -> "1" , "b" -> "2".
 * 示例 2：
 * 
 * 输入：s = "1326#"
 * 输出："acz"
 * 示例 3：
 * 
 * 输入：s = "25#"
 * 输出："y"
 * 
 * 示例 4：
 * 输入：s = "12345678910#11#12#13#14#15#16#17#18#19#20#21#22#23#24#25#26#"
 * 输出："abcdefghijklmnopqrstuvwxyz"
 */
 public class Solution {
 public String freqAlphabets(String s) {
 if (s == null || s.length() == 0) {
 return "";
 }
 StringBuilder stringBuilder = new StringBuilder();
 for (int i = 0; i < s.length(); ) {
 String temp1 = "";
 if (s.length() >= i + 3) {
 temp1 = s.substring(i, i + 3);
 if (temp1.contains("#")) {
 char temp = (char) ((Integer.parseInt(s.substring(i, i + 2)) - 10) + 'j');
 stringBuilder.append(temp);
 i += 3;
 } else {
 temp1 = s.substring(i, i + 1);
 char temp = (char) ((Integer.parseInt(temp1) - 1) + 'a');
 stringBuilder.append(temp);
 i++;
 }
 } else {
 temp1 = s.substring(i, i + 1);
 char temp = (char) ((Integer.parseInt(temp1)-1) + 'a');
 stringBuilder.append(temp);
 i++;
 }
 }
 return stringBuilder.toString();
 }
 
 public static void main(String[] args) {
 String test = "12345678910#11#12#13#14#15#16#17#18#19#20#21#22#23#24#25#26#";
 Solution solution = new Solution();
 System.out.println(solution.freqAlphabets(test));
 }
 
 }

第二题：树

![20200410000406789.png][]

public class TreeNode {
 int val;
 TreeNode left;
 TreeNode right;
 
 TreeNode(int x) {
 val = x;
 }
 }
 
 
 import java.util.ArrayDeque;
 import java.util.ArrayList;
 import java.util.List;
 import java.util.Queue;
 
 /**
 * 给你一棵二叉树，请你返回层数最深的叶子节点的和。
 * 输入：root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
 * 输出：15
 */
 public class Solution {
 public int deepestLeavesSum(TreeNode root) {
 if (root == null) {
 return 0;
 }
 int depth = getMaxDepth(root);
 List<TreeNode> nodes = getDepthNodes(root, depth);
 int res = 0;
 for (TreeNode node : nodes) {
 res += node.val;
 }
 return res;
 }
 
 private int getMaxDepth(TreeNode root) {
 if (root == null) {
 return 0;
 }
 return Math.max(getMaxDepth(root.left), getMaxDepth(root.right)) + 1;
 }
 
 private List<TreeNode> getDepthNodes(TreeNode treeNode, int depth) {
 List<TreeNode> res = new ArrayList<>();
 Queue<TreeNode> queue = new ArrayDeque<>();
 queue.add(treeNode);
 int currentDepth = 0;
 while (!queue.isEmpty()) {
 currentDepth++;
 int currentSize = queue.size();
 boolean isMaxDepth = false;
 if (currentDepth == depth) {
 isMaxDepth = true;
 }
 for (int i = 0; i < currentSize; i++) {
 TreeNode currentNode = queue.poll();
 TreeNode left = currentNode.left;
 TreeNode right = currentNode.right;
 if (left != null) {
 queue.add(left);
 }
 if (right != null) {
 queue.add(right);
 }
 if (isMaxDepth) {
 res.add(currentNode);
 }
 }
 }
 return res;
 }
 
 public static void main(String [] args){
 TreeNode treeNode = new TreeNode(1);
 Solution solution = new Solution();
 System.out.println(solution.deepestLeavesSum(treeNode));
 }
 }

第三题：二叉查找

/**
 * 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：
 * 
 * 每行的元素从左到右升序排列。
 * 每列的元素从上到下升序排列。
 * 示例:
 * 
 * 现有矩阵 matrix 如下：
 * 
 * [
 * [1, 4, 7, 11, 15],
 * [2, 5, 8, 12, 19],
 * [3, 6, 9, 16, 22],
 * [10, 13, 14, 17, 24],
 * [18, 21, 23, 26, 30]
 * ]
 * 给定 target = 5，返回 true。
 * 
 * 给定 target = 20，返回 false。
 */
 public class Solution {
 public boolean searchMatrix1(int[][] matrix, int target) {
 if (matrix == null) {
 return false;
 }
 for (int i = 0; i < matrix.length; i++) {
 for (int j = 0; j < matrix[i].length; j++) {
 if (matrix[i][j] == target) {
 return true;
 }
 }
 }
 return false;
 }
 
 public boolean searchMatrix(int[][] matrix, int target) {
 if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
 return false;
 }
 // 根据二分查找先找到可能存在那一列
 int[] nums0 = new int[matrix[0].length];
 for (int i = 0; i < matrix[0].length; i++) {
 nums0[i] = matrix[0][i];
 }
 int col = getIndex(nums0, target);
 // 再次根据二分查找找到可能存在在哪一行
 int[] nums2 = new int[matrix.length];
 for (int j = 0; j < matrix.length; j++) {
 nums2[j] = matrix[j][col];
 }
 int row = getIndex(nums2, target);
 return matrix[row][col] == target;
 }
 
 private int getIndex(int[] nums, int target) {
 int left = 0;
 int right = nums.length - 1;
 int mid = 0;
 while (left <= right) {
 mid = (left + right) / 2;
 int tem = nums[mid];
 if (tem < target) {
 left = mid + 1;
 } else if (tem > target) {
 right = mid - 1;
 } else {
 return mid;
 }
 }
 if (target < nums[mid]) {
 return mid - 1;
 }
 return mid;
 }
 
 public static void main(String[] agrs) {
 int[][] matrix = {
 {1, 4, 7, 11, 15},
 {2, 5, 8, 12, 19},
 {3, 6, 9, 16, 22},
 {10, 13, 14, 17, 24},
 {18, 21, 23, 26, 30}
 };
 Solution solution = new Solution();
 System.out.println(solution.searchMatrix(matrix, 5));
 System.out.println(solution.searchMatrix(matrix, 20));
 }
 
 }

[20200410000406789.png]: /images/20230528/94afcf715c294dfa8ba8af47161c4723.png