目录
68. 文本左右对齐 Text Justification 🌟🌟🌟
67. 二进制求和 Add Binary
给你两个二进制字符串，返回它们的和（用二进制表示）。
输入为 非空 字符串且只包含数字 1 和 0。
示例 1:
输入: a = "11", b = "1" 输出: "100"
示例 2:
输入: a = "1010", b = "1011" 输出: "10101"
提示：
- 每个字符串仅由字符
'0'或'1'组成。 1 <= a.length, b.length <= 10^4- 字符串如果不是
"0"，就都不含前导零。
代码1：
fn add_binary(a: &str, b: &str) -> String {
let (n, m) = (a.len(), b.len());
let (a, mut b) = if n < m {
(b, a)
} else {
(a, b)
};
let padding = "0".repeat(n - m);
let temp = padding + b;
b = &temp;
let mut res = vec![b'0'; n + 1];
let mut carry = 0;
for i in (0..n).rev() {
let sum = carry + a.as_bytes()[i] - b'0' + b.as_bytes()[i] - b'0';
res[i + 1] = sum % 2 + b'0';
carry = sum / 2;
}
if carry > 0 {
res[0] = b'1';
String::from_utf8(res).unwrap()
} else {
String::from_utf8(res[1..].to_vec()).unwrap()
}
}
fn main() {
println!("{}", add_binary("11", "1"));
println!("{}", add_binary("1010", "1011"));
}代码2：
fn add_binary(a: &str, b: &str) -> String {
let mut n = a.len() as i32 - 1;
let mut m = b.len() as i32 - 1;
let mut carry = 0;
let mut res = String::new();
while n >= 0 || m >= 0 || carry > 0 {
if n >= 0 {
carry += a.chars().nth(n as usize).unwrap() as i32 - '0' as i32;
n -= 1;
}
if m >= 0 {
carry += b.chars().nth(m as usize).unwrap() as i32 - '0' as i32;
m -= 1;
}
res = (carry % 2).to_string() + &res;
carry /= 2;
}
res
}
fn main() {
println!("{}", add_binary("11", "1"));
println!("{}", add_binary("1010", "1011"));
}输出：
100
10101
68. 文本左右对齐 Text Justification
给定一个单词数组 words 和一个长度 maxWidth ，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。
你应该使用 “贪心算法” 来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。
要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。
文本的最后一行应为左对齐，且单词之间不插入额外的空格。
注意:
- 单词是指由非空格字符组成的字符序列。
- 每个单词的长度大于 0，小于等于 maxWidth。
- 输入单词数组
words至少包含一个单词。
示例 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 "
]
解释: 注意最后一行的格式应为 "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 " ]
提示:
1 <= words.length <= 3001 <= words[i].length <= 20words[i]由小写英文字母和符号组成1 <= maxWidth <= 100words[i].length <= maxWidth
代码：
pub fn full_justify(words: Vec<String>, max_width: i32) -> Vec<String> {
let mut ans = Vec::new();
let mut right = 0;
let n = words.len();
while right < n {
let left = right;
let mut sum_len = 0;
while right < n && sum_len + words[right].len() + right - left <= max_width as usize {
sum_len += words[right].len();
right += 1;
}
if right == n {
let s = words[left..].join(" ");
ans.push(s.clone() + &" ".repeat(max_width as usize - s.len()));
} else {
let num_words = right - left;
let num_spaces = max_width as usize - sum_len;
if num_words == 1 {
ans.push(words[left].to_owned() + &" ".repeat(num_spaces));
} else {
let avg_spaces = num_spaces / (num_words - 1);
let extra_spaces = num_spaces % (num_words - 1);
let mut s1 = String::new();
for i in left..left+extra_spaces+1 {
s1 += &words[i];
s1 += &" ".repeat(avg_spaces + 1);
}
let mut s2 = String::new();
for i in left+extra_spaces+1..right {
s2 += &words[i];
if i < right - 1 {
s2 += &" ".repeat(avg_spaces);
}
}
ans.push(s1 + &" ".repeat(avg_spaces) + &s2);
}
}
}
ans
}
fn main() {
let words: Vec<String> = vec!["This", "is", "an", "example", "of", "text", "justification."]
.iter()
.map(|s| s.to_string())
.collect();
let max_width = 16;
for line in full_justify(words.clone(), max_width) {
println!("{}", line);
}
println!();
let words: Vec<String> = vec!["What", "must", "be", "acknowledgment", "shall", "be"]
.iter()
.map(|s| s.to_string())
.collect();
for line in full_justify(words.clone(), max_width) {
println!("{}", line);
}
println!();
let words: Vec<String> = vec!["Science", "is", "what", "we", "understand", "well", "enough", "to", "explain", "to", "a", "computer.", "Art", "is", "everything", "else", "we", "do"]
.iter()
.map(|s| s.to_string())
.collect();
let max_width = 20;
for line in full_justify(words.clone(), max_width) {
println!("{}", line);
}
}输出：
69. x 的平方根 Sqrt x
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
输入：x = 4 输出：2
示例 2：
输入：x = 8 输出：2 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
提示：
0 <= x <= 2^31 - 1
代码1：暴力枚举
fn my_sqrt(x: i32) -> i32 {
let mut i = 0;
while i * i <= x {
i += 1;
}
i - 1
}
fn main() {
println!("{}", my_sqrt(4));
println!("{}", my_sqrt(8));
println!("{}", my_sqrt(122));
}
代码2：牛顿迭代法
fn my_sqrt(x: i32) -> i32 {
if x == 0 {
return 0;
}
let mut x0 = x as f64;
let eps = 1e-6;
loop {
let x1 = 0.5 * (x0 + (x as f64) / x0);
if (x1 - x0).abs() < eps {
break;
}
x0 = x1;
}
x0 as i32
}
fn main() {
println!("{}", my_sqrt(4));
println!("{}", my_sqrt(8));
println!("{}", my_sqrt(122));
}
代码3： 二分查找
fn my_sqrt(x: i32) -> i32 {
let mut left = 1;
let mut right = x.max(1);
while left <= right {
let mid = left + (right - left) / 2;
if mid * mid == x {
return mid;
} else if mid * mid < x {
left = mid + 1;
} else {
right = mid - 1;
}
}
left - 1
}
fn main() {
println!("{}", my_sqrt(4));
println!("{}", my_sqrt(8));
println!("{}", my_sqrt(122));
}输出：
2
2
11
🌟 每日一练刷题专栏 🌟
✨ 持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！
☸ 主页：https://hannyang.blog.csdn.net/