本文主要是介绍算法进修Day-34,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
算法进修Day-34
二进制求和
难度:简单
题目要求:
给你两个二进制字符串 a
和 b
,以二进制字符串的形式返回它们的和。
示例1
输入:a = “11”, b = “1”
输出:“100”
示例2
输入:a = “1010”, b = “1011”
输出:“10101”
题解
用 i n d e x 1 index_1 index1 和 i n d e x 2 index_2 index2 分别表示二进制整数 a a a 和 b b b 遍历到的下标,用 c a r r y carry carry 表示进位值,初始时 i n d e x 1 index_1 index1 和 i n d e x 2 index_2 index2 分别指向整数 a a a 和 b b b 的最大下标, c a r r y = 0 carry=0 carry=0。使用字符串保存两个二进制整数之和的每一位,计算过程中依次将每一位结果拼接到字符串的末尾
当 i n d e x 1 ≥ 0 , i n d e x 2 ≥ 0 , c a r r y ≠ 0 index_1\geq 0,index_2\geq 0, carry\neq 0 index1≥0,index2≥0,carry=0 三个条件中至少有一个成立,对于每一位,执行如下操作
- 记 d i g i t 1 digit_1 digit1 和 d i g i t 2 digit_2 digit2 分别为 a [ i n d e x 1 ] a[index_1] a[index1] 和 b [ i n d e x 2 ] b[index_2] b[index2]对应的数字,如果 i n d e x 1 < 0 index_1<0 index1<0,则 d i g i t 1 = 0 digit_1=0 digit1=0,如果 i n d e x 2 < 0 index_2<0 index2<0 则 d i g i t 2 = 0 digit_2=0 digit2=0
- 计算 s u m = d i g i t 1 + d i g i t 2 + c a r r y sum=digit_1+digit_2+carry sum=digit1+digit2+carry,则两个二进制整数之和的当前位置的值为 s u m % 2 sum \%2 sum%2,进位值 s u m 2 \frac{sum}{2} 2sum,将 s u m % 2 sum\%2 sum%2 拼接到字符串末尾,将 c a r r y carry carry 更新为 s u m 2 \frac{sum}{2} 2sum
- 将 i n d e x 1 index_1 index1 和 i n d e x 2 index_2 index2 分别向左移动一位
操作结束之后,将字符串翻转之后得到两个二进制整数之和
想法代码
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 "
]
题解
遍历单词数组,对于每个单词 w o r d word word,尝试将 w o r d word word 拼接到当前行的末尾,如果当前行已经有单词则需要添加一个空格将单词分隔,考虑将 w o r d word word 拼接到当前行的末尾之后,当前行的宽度。
如果当前行的宽度不超过 m a x W i d t h maxWidth maxWidth,则将 w o r d word word拼接到当前行的末尾。
如果当前行的宽度超过 m a x W i d t h maxWidth maxWidth,则不能将 w o r d word word 拼接到当前行的末尾,当前行的单词添加完毕。此时需要将当前行的单词重新排版使得单词之间的空格均匀分配,将重新排版之后的当前行添加到结果中,然后将 w o r d word word 填入新的一行。重新排版当前行的做法如下。
如果当前行只有一个单词,则将该单词左对齐,然后在右侧添加空格直到当前行有 m a x W i d t h maxWidth maxWidth 个字符。
如果当前行有至少两个单词,则根据单词数量计算间隔数量,根据单词长度之和计算空格数量,将空格均匀分配在每个间隔中,满足左侧间隔的空格数大于等于右侧间隔的空格数。
遍历单词数组结束之后,需要将剩余的单词填入末尾行。由于末尾行左对齐且相邻单词之间只有一个空格,因此将末尾行的单词使用一个空格分隔的方式依次拼接,然后在右侧添加空格直到末尾行有 m a x W i d t h 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();}
}
这篇关于算法进修Day-34的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!