【LeetCode 随笔】面试经典 150 题【中等＋困难】持续更新中。。。

🌈你好呀！我是 山顶风景独好
💝欢迎来到我的博客，很高兴能够在这里和您见面！
💝希望您在这里可以感受到一份轻松愉快的氛围！
💝不仅可以获得有趣的内容和知识，也可以畅所欲言、分享您的想法和见解。
🚀 欢迎一起踏上探险之旅，挖掘无限可能，共同成长！

12.【中等】整数转罗马数字

七个不同的符号代表罗马数字，其值如下：

罗马符号	数值
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

组合符号	数值	示例
IV	4	1 (I) 减去 1 (V) 的值
IX	9	1 (I) 减去 10 (X) 的值
XL	40	10 (X) 减去 1 (L) 的值
XC	90	10 (X) 减去 100 © 的值
CD	400	100 © 减去 1 (D) 的值
CM	900	100 © 减去 1000 (M) 的值

罗马数字是通过添加从最高到最低的小数位值的转换而形成的。将小数位值转换为罗马数字有以下规则：

• 如果该值不是以 4 或 9 开头，请选择可以从输入中减去的最大值的符号，将该符号附加到结果，减去其值，然后将其余部分转换为罗马数字。
• 如果该值以 4 或 9 开头，使用 减法形式，表示从以下符号中减去一个符号，例如 4 是 5 (V) 减 1 (I): IV ，9 是 10 (X) 减 1 (I)：IX。仅使用以下减法形式：4 (IV)，9 (IX)，40 (XL)，90 (XC)，400 (CD) 和 900 (CM)。
• 只有 10 的次方（I, X, C, M）最多可以连续附加 3 次以代表 10 的倍数。你不能多次附加 5 (V)，50 (L) 或 500 (D)。如果需要将符号附加4次，请使用 减法形式。

给定一个整数，将其转换为罗马数字。

示例 1：

• 输入：num = 3749
• 输出： “MMMDCCXLIX”
• 解释：
  3000 = MMM 由于 1000 (M) + 1000 (M) + 1000 (M)
  700 = DCC 由于 500 (D) + 100 © + 100 ©
  40 = XL 由于 50 (L) 减 10 (X)
  9 = IX 由于 10 (X) 减 1 (I)
  注意：49 不是 50 (L) 减 1 (I) 因为转换是基于小数位

---

示例 2：

• 输入：num = 58
• 输出：“LVIII”
• 解释：
  50 = L
  8 = VIII

class Solution {  // 定义罗马数字中每个符号对应的整数值  int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};  // 定义罗马数字符号  String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};  // 将整数转换为罗马数字的方法  public String intToRoman(int num) {   StringBuffer roman = new StringBuffer();  // 遍历每个罗马数字符号和对应的整数值  for (int i = 0; i < values.length; ++i) {  int value = values[i];  String symbol = symbols[i];  // 当整数值大于等于当前罗马数字符号对应的整数值时  while (num >= value) {  // 减去该罗马数字符号对应的整数值  num -= value;  // 在字符串中添加对应的罗马数字符号  roman.append(symbol);  }  // 如果整数已经为0，则提前退出循环  if (num == 0) {  break;  }  }  // 返回构建的罗马数字字符串  return roman.toString();  }  
}

151.【中等】反转字符串中的单词

• 给你一个字符串 s ，请你反转字符串中 单词 的顺序。
• 单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
• 返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
• 注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 2：

• 输入：s = " hello world "
• 输出：“world hello”
• 解释：反转后的字符串中不能存在前导空格和尾随空格。

---

示例 3：

• 输入：s = “a good example”
• 输出：“example good a”
• 解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

解题思路：

• 倒序遍历字符串 sss ，记录单词左右索引边界 iii , jjj 。
• 每确定一个单词的边界，则将其添加至单词列表 resresres 。
• 最终，将单词列表拼接为字符串，并返回即可。

class Solution {  public String reverseWords(String s) {  // 删除字符串s的首尾空格  s = s.trim();  // 初始化j为字符串s的最后一个字符的索引，i也为最后一个字符的索引，用于后续从后向前遍历  int j = s.length() - 1, i = j;  // 创建一个StringBuilder对象res，用于构建结果字符串  StringBuilder res = new StringBuilder();  // 当i大于等于0时，继续遍历  while (i >= 0) {  // 从后向前遍历，找到单词的起始位置（即首个不是空格的字符）  while (i >= 0 && s.charAt(i) != ' ') i--;  // 将从i+1到j的子字符串（即一个单词）添加到结果中，并在其后添加一个空格  // 注意：i+1是单词的起始位置，j+1会超出范围，因此使用j  res.append(s.substring(i + 1, j + 1) + " ");  // 跳过单词间的空格，继续寻找下一个单词的起始位置  while (i >= 0 && s.charAt(i) == ' ') i--;  // 更新j为下一个单词的尾字符索引  j = i;  }  // 将StringBuilder对象res转换为字符串，并删除结果字符串的首尾空格，然后返回  return res.toString().trim();  }  
}

6.【中等】Z 字形变换

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

• 比如输入字符串为 “PAYPALISHIRING” 行数为 3 时，排列如下：
  
• 之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：“PAHNAPLSIIGYIR”。

请你实现这个将字符串进行指定行数变换的函数：

示例 ：

• 输入：s = “PAYPALISHIRING”, numRows = 4
• 输出：“PINALSIGYAHRPI”
• 解释：
  

class Solution {  public String convert(String s, int numRows) {  // 如果numRows小于2，说明无需转换，直接返回原字符串  if(numRows < 2) return s;  // 创建一个ArrayList，用于存储每一行的StringBuilder对象  List<StringBuilder> rows = new ArrayList<StringBuilder>();  // 初始化每一行的StringBuilder对象  for(int i = 0; i < numRows; i++) rows.add(new StringBuilder());  // i表示当前字符应该放在哪一行  // flag表示i的移动方向，初始化为-1表示向下移动  int i = 0, flag = -1;  // 遍历字符串s中的每一个字符  for(char c : s.toCharArray()) {  // 将字符添加到对应的行中  rows.get(i).append(c);  // 如果当前行是第一行或者最后一行，则改变移动方向  if(i == 0 || i == numRows - 1) flag = - flag;  // 根据flag的值更新i的值，实现Z字形遍历  i += flag;  }  // 创建一个StringBuilder对象res，用于构建结果字符串  StringBuilder res = new StringBuilder();  // 遍历所有行，将每一行的内容添加到res中  for(StringBuilder row : rows) res.append(row);  // 将res转换为字符串并返回  return res.toString();  }  
}

68.【困难】文本左右对齐

• 给定一个单词数组 words 和一个长度 maxWidth ，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。
• 你应该使用 “贪心算法” 来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ’ ’ 填充，使得每行恰好有 maxWidth 个字符。
• 要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。
• 文本的最后一行应为左对齐，且单词之间不插入额外的空格。

注意:

• 单词是指由非空格字符组成的字符序列。
• 每个单词的长度大于 0，小于等于 maxWidth。
• 输入单词数组 words 至少包含一个单词。

示例 :

• 输入:words = [“Science”,“is”,“what”,“we”,“understand”,“well”,“enough”,“to”,“explain”,“to”,“a”,“computer.”,“Art”,“is”,“everything”,“else”,“we”,“do”]，maxWidth = 20
• 输出:
  [
  “Science is what we”,
  “understand well”,
  “enough to explain to”,
  “a computer. Art is”,
  “everything else we”,
  "do "
  ]

class Solution {// 主要方法，用于实现单词的完全对齐功能public List<String> fullJustify(String[] words, int maxWidth) {List<String> ans = new ArrayList<String>(); // 初始化结果列表int right = 0, n = words.length; // 初始化指向当前行第一个单词的指针（right）及单词总数（n）// 循环处理每一行，直到所有单词被分配while (true) {int left = right; // 当前行的第一个单词在 words 的位置int sumLen = 0; // 统计这一行单词长度之和// 找出当前行可以容纳的单词，确保单词总长度加上空格不超过 maxWidthwhile (right < n && sumLen + words[right].length() + right - left <= maxWidth) {sumLen += words[right++].length(); // 累加单词长度并移动右指针}// 如果右指针到达末尾，说明处理的是最后一行if (right == n) {StringBuffer sb = join(words, left, n, " "); // 将剩余单词左对齐拼接，单词间单空格sb.append(blank(maxWidth - sb.length())); // 在行末填充空格以达到 maxWidthans.add(sb.toString()); // 添加到结果列表并返回return ans;}// 计算当前行的单词数和所需空格数int numWords = right - left;int numSpaces = maxWidth - sumLen;// 如果当前行只有一个单词，左对齐并在后面填充空格if (numWords == 1) {StringBuffer sb = new StringBuffer(words[left]);sb.append(blank(numSpaces)); // 在单词后添加足够的空格ans.add(sb.toString());continue;}// 多单词行处理int avgSpaces = numSpaces / (numWords - 1); // 平均每个空格数量int extraSpaces = numSpaces % (numWords - 1); // 额外的空格// 拼接单词，先拼接带有额外空格的单词，再拼接其余单词StringBuffer sb = new StringBuffer();sb.append(join(words, left, left + extraSpaces + 1, blank(avgSpaces + 1))); sb.append(blank(avgSpaces)); // 添加平均数量的空格sb.append(join(words, left + extraSpaces + 1, right, blank(avgSpaces)));ans.add(sb.toString()); // 添加到结果列表}}// 辅助方法，生成指定数量的空格字符串public String blank(int n) {StringBuffer sb = new StringBuffer();for (int i = 0; i < n; ++i) {sb.append(' ');}return sb.toString();}// 辅助方法，使用指定分隔符连接 words 中指定范围的单词public StringBuffer join(String[] words, int left, int right, String sep) {StringBuffer sb = new StringBuffer(words[left]);for (int i = left + 1; i < right; ++i) {sb.append(sep);sb.append(words[i]);}return sb;}
}

167.【中等】两数之和 II - 输入有序数组

• 给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。
• 以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
• 你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
• 你所设计的解决方案必须只使用常量级的额外空间。

public int[] twoSum(int[] numbers, int target) {  // 初始化两个指针，一个指向数组的开头，一个指向数组的末尾  int i = 0;  int j = numbers.length - 1;  // 当两个指针没有相遇时，执行循环  while (i < j) {  // 计算当前两个指针所指向的元素之和  int sum = numbers[i] + numbers[j];  // 如果和小于目标值，则移动左指针向右  if (sum < target) {  i++;  }   // 如果和大于目标值，则移动右指针向左  else if (sum > target) {  j--;  }   // 如果和等于目标值，则返回两个指针的索引（注意这里索引从1开始，所以加1）  else {  return new int[]{i+1, j+1};  }  }  // 如果循环结束仍未找到满足条件的两个数，则返回{-1, -1}  return new int[]{-1, -1};  
}