算法进修Day-34

二进制求和

难度：简单
题目要求：
给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。

示例1

输入：a = “11”, b = “1”
输出：“100”

示例2

输入：a = “1010”, b = “1011”
输出：“10101”

题解

用 $inde{x}_1$ 和 $inde{x}_2$ 分别表示二进制整数 $a$ 和 $b$ 遍历到的下标，用 $carry$ 表示进位值，初始时 $inde{x}_1$ 和 $inde{x}_2$ 分别指向整数 $a$ 和 $b$ 的最大下标，$carry=0$。使用字符串保存两个二进制整数之和的每一位，计算过程中依次将每一位结果拼接到字符串的末尾

当 $inde{x}_1\ge 0,inde{x}_2\ge 0,carry\ne 0$ 三个条件中至少有一个成立，对于每一位，执行如下操作

• 记 $digi{t}_1$ 和 $digi{t}_2$ 分别为 $a[inde{x}_1]$ 和 $b[inde{x}_2]$对应的数字，如果 $inde{x}_1<0$，则 $digi{t}_1=0$，如果 $inde{x}_2<0$ 则 $digi{t}_2=0$
• 计算 $sum=digi{t}_1+digi{t}_2+carry$，则两个二进制整数之和的当前位置的值为 $sum\%2$，进位值 $\frac{sum}{2}$，将 $sum\%2$ 拼接到字符串末尾，将 $carry$ 更新为 $\frac{sum}{2}$
• 将 $inde{x}_1$ 和 $inde{x}_2$ 分别向左移动一位

操作结束之后，将字符串翻转之后得到两个二进制整数之和

想法代码

using System.Text;public class Solution
{public static void Main(string[] args){Solution solution = new Solution();string a = "11";string b = "1";string res = solution.AddBinary(a, b);Console.WriteLine(res);}public string AddBinary(string a, string b){StringBuilder sb = new StringBuilder();int index1 = a.Length - 1, index2 = b.Length - 1;int carry = 0;while (index1 >= 0 || index2 >= 0 || carry != 0){int digit1 = index1 >= 0 ? a[index1] - '0' : 0;int digit2 = index2 >= 0 ? b[index2] - '0' : 0;int sum = digit1 + digit2 + carry;sb.Append(sum % 2);carry = sum / 2;index1--;index2--;}StringBuilder sb2 = new StringBuilder();for (int i = sb.Length - 1; i >= 0; i--){sb2.Append(sb[i]);}return sb2.ToString();}
}

68.文本左右对齐

难度：困难
题目要求：
给定一个单词数组 words 和一个长度 maxWidth ，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。

你应该使用 “贪心算法” 来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。

要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。

文本的最后一行应为左对齐，且单词之间不插入额外的空格。

示例1

输入：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 "
]

示例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 "
]

题解

遍历单词数组，对于每个单词 $word$，尝试将 $word$ 拼接到当前行的末尾，如果当前行已经有单词则需要添加一个空格将单词分隔，考虑将 $word$ 拼接到当前行的末尾之后，当前行的宽度。

如果当前行的宽度不超过 $maxWidth$，则将 $word$拼接到当前行的末尾。

如果当前行的宽度超过 $maxWidth$，则不能将 $word$ 拼接到当前行的末尾，当前行的单词添加完毕。此时需要将当前行的单词重新排版使得单词之间的空格均匀分配，将重新排版之后的当前行添加到结果中，然后将 $word$ 填入新的一行。重新排版当前行的做法如下。

如果当前行只有一个单词，则将该单词左对齐，然后在右侧添加空格直到当前行有 $maxWidth$ 个字符。

如果当前行有至少两个单词，则根据单词数量计算间隔数量，根据单词长度之和计算空格数量，将空格均匀分配在每个间隔中，满足左侧间隔的空格数大于等于右侧间隔的空格数。

遍历单词数组结束之后，需要将剩余的单词填入末尾行。由于末尾行左对齐且相邻单词之间只有一个空格，因此将末尾行的单词使用一个空格分隔的方式依次拼接，然后在右侧添加空格直到末尾行有 $maxWidth$ 个字符。

想法代码

using System.Text;public class Solution
{public static void Main(string[] args){Solution solution = new Solution();string[] words = { "This", "is", "an", "example", "of", "text", "justification." };int maxWidth = 16;IList<string> res = solution.FullJustify(words, maxWidth);foreach (var word in res){Console.WriteLine(word);}}public IList<string> FullJustify(string[] words, int maxWidth){IList<string> justification = new List<string>();IList<string> line = new List<string>();int lineWidth = 0;int wordsCount = words.Length;for (int i = 0; i < wordsCount; i++){string word = words[i];int newLength = lineWidth + (lineWidth > 0 ? 1 : 0) + word.Length;if (newLength <= maxWidth){lineWidth = newLength;}else{string justifiedLine = JustifyLine(line, lineWidth, maxWidth);justification.Add(justifiedLine);line.Clear();lineWidth = word.Length;}line.Add(word);}string justifiedLastLine = JustifyLastLine(line, maxWidth);justification.Add(justifiedLastLine);return justification;}public string JustifyLine(IList<string> line, int lineWidth, int maxWidth){StringBuilder sb = new StringBuilder();sb.Append(line[0]);int lineWords = line.Count;int splits = lineWords - 1;if (splits == 0){while (sb.Length < maxWidth){sb.Append(" ");}}else{int spaces = maxWidth - (lineWidth - splits);int quotient = spaces / splits, remainder = spaces % splits;for (int i = 1; i < lineWords; i++){int currSpaces = quotient + (i <= remainder ? 1 : 0);for (int j = 0; j < currSpaces; j++){sb.Append(" ");}sb.Append(line[i]);}}return sb.ToString();}public string JustifyLastLine(IList<string> line, int maxWidth){StringBuilder sb = new StringBuilder();sb.Append(line[0]);int lineWords = line.Count;for (int i = 1; i < lineWords; i++){sb.Append(" ");sb.Append(line[i]);}while (sb.Length < maxWidth){sb.Append(" ");}return sb.ToString();}
}