文本左右对齐(字符串、模拟)
给定一个单词数组和一个长度 maxWidth，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。 你应该使用“贪心算法”来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。 要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。 文本的最后一行应为左对齐，且单词之间不插入额外的空格。 说明:
- 单词是指由非空格字符组成的字符序列。
- 每个单词的长度大于 0，小于等于 _maxWidth_。
- 输入单词数组 words 至少包含一个单词。
示例: 输入: words = ["This", "is", "an", "example", "of", "text", "justification."] maxWidth = 16 输出: [ "This is an", "example of text", "justification. " ] 示例 2: 输入: words = ["What","must","be","acknowledgment","shall","be"] maxWidth = 16 输出: [ "What must be", "acknowledgment ", "shall be " ] 解释: 注意最后一行的格式应为 "shall be " 而不是 "shall be" 因为最后一行应为左对齐，而不是左右两端对齐，第二行同样为左对齐，这是因为这行只包含一个单词。 示例 3: 输入: 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> ret = new ArrayList<>();
int index = 0;
while (index < words.length) {
int cur = index, len = 0;
while (cur < words.length && len + words[cur].length() + cur - index <= maxWidth) {
len = len + words[cur++].length();
}
cur--;
StringBuilder sb = new StringBuilder();
if (cur == words.length - 1) {
for (int i = index; i <= cur; i++) {
sb.append(words[i]);
if (i < cur) {
sb.append(' ');
}
}
} else {
int base = cur > index ? (maxWidth - len) / (cur - index) : (maxWidth - len);
String baseStr = genSpace(base);
int left = cur > index ? (maxWidth - len) % (cur - index) : 0;
String leftStr = genSpace(base + 1);
for (int i = index; i <= cur; i++) {
sb.append(words[i]);
___________________;
}
}
if (sb.length() < maxWidth) {
sb.append(genSpace(maxWidth - sb.length()));
}
ret.add(sb.toString());
index = cur + 1;
}
return ret;
}
private String genSpace(int n) {
char[] cs = new char[n];
Arrays.fill(cs, ' ');
return new String(cs);
}
}
解答：
if (i < cur) {
sb.append(left > 0 ? leftStr : baseStr);
left--;
}
螺旋矩阵 II(数组、矩阵)
给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
示例 1：
输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]
示例 2：
输入：n = 1
输出：[[1]]
提示：
- 1 <= n <= 20
解答：
package LeetCode;
public class GenerateMatrix {
public int[][] generateMatrix(int n) {
int[][] res = new int[n][n];
if (n == 0) {
return res;
}
int left = 0;
int right = n - 1;
int up = 0;
int down = n - 1;
int i = 1;
while (i <= n * n) {
for (int col = left; col <= right; col++) {
res[up][col] = i;
i++;
}
up++;
if (i <= n * n) {
for (int j = up; j <= down; j++) {
res[j][right] = i;
i++;
}
right--;
}
if (i <= n * n) {
for (int j = right; j >= left; j--) {
res[down][j] = i;
i++;
}
down--;
}
if (i <= n * n) {
for (int j = down; j >= up; j--) {
res[j][left] = i;
i++;
}
left++;
}
}
return res;
}
public static void main(String[] args) {
GenerateMatrix a = new GenerateMatrix();
a.generateMatrix(3);
}
}
二叉树中的最大路径和(树、深度优先搜索)
路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径** 至少包含一个 **节点，且不一定经过根节点。 路径和 是路径中各节点值的总和。 给你一个二叉树的根节点 root ，返回其 最大路径和 。
示例 1：
输入：root = [1,2,3] 输出：6 解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
示例 2：
输入：root = [-10,9,20,null,null,15,7] 输出：42 解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
提示：
- 树中节点数目范围是 [1, 3 * 104]
- -1000 <= Node.val <= 1000
解答：
class Solution {
int maxSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
maxGain(root);
return maxSum;
}
public int maxGain(TreeNode node) {
if (node == null) {
return 0;
}
int leftGain = Math.max(maxGain(node.left), 0);
int rightGain = Math.max(maxGain(node.right), 0);
int priceNewpath = node.val + leftGain + rightGain;
maxSum = Math.max(maxSum, priceNewpath);
return node.val + Math.max(leftGain, rightGain);
}
}
本文内容到此结束了， 如有收获欢迎点赞????收藏????关注✔️，您的鼓励是我最大的动力。 如有错误❌疑问????欢迎各位大佬指出。 主页：共饮一杯无的博客汇总????????
保持热爱，奔赴下一场山海。????????????