Huawei code test

2016 机考 test 1

老师想知道从某某同学当中，分数最高的是多少，现在请你编程模拟老师的询问。当然， 老师有时候需要更新某位同学的成绩. 输入描述: 输入包括多组测试数据。 每组输入第一行是两个正整数N和M（0 < N <= 30000,0 < M < 5000）,分别代表学生的数目和操作的数目。 学生ID编号从1编到N。 第二行包含N个整数，代表这N个学生的初始成绩，其中第i个数代表ID为i的学生的成绩 接下来又M行，每一行有一个字符C（只取‘Q’或‘U’），和两个正整数A,B,当C为’Q’的时候, 表示这是一条询问操作，他询问ID从A到B（包括A,B）的学生当中，成绩最高的是多少 当C为‘U’的时候，表示这是一条更新操作，要求把ID为A的学生的成绩更改为B。 输出描述: 对于每一次询问操作，在一行里面输出最高成绩.

示例1
输入
5 7
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 4 5
U 2 9
Q 1 5
输出
5
6
5
9

pub fn input() -> String {
let mut input = String::new();
std::io::stdin().read_line(&mut input).unwrap();
input.trim().to_string()
}
pub fn input_split() -> Vec<String> {
let mut input = String::new();
std::io::stdin().read_line(&mut input).unwrap();
input
.split_whitespace()
.map(|s| s.to_string())
.collect::<Vec<_>>()
}
pub fn huawei_2016_1() {
let f = input_split();
let n = &f[0].parse::<i32>().unwrap();
let m = &f[1].parse::<i32>().unwrap();
let mut id = input_split();
let mut a = vec![];
for _ in 0..m.to_owned() {
a.push(input_split());
}
for line in a.iter() {
let q = &line[0];
let a = &line[1].parse::<i32>().unwrap().to_owned();
let b = &line[2].parse::<i32>().unwrap().to_owned();
if q == "U" {
let a = a.to_owned() as usize;
let b = b.to_owned() as usize;
if let Some(elem) = id.get_mut(a - 1) {
*elem = b.to_string();
}
// println!("{:?}", id);
} else if q == "Q" {
if b > a {
let a = a.to_owned() as usize - 1;
let b = b.to_owned() as usize - 1;
let stu = id
.get(a..=b)
.unwrap()
.iter()
.map(|s| s.parse::<i32>().unwrap())
.collect::<Vec<_>>();
println!("{}", stu.into_iter().max().unwrap());
} else if a > b {
let a = a.to_owned() as usize - 1;
let b = b.to_owned() as usize - 1;
let stu = id
.get(b..=a)
.unwrap()
.iter()
.map(|s| s.parse::<i32>().unwrap())
.collect::<Vec<_>>();
println!("{}", stu.into_iter().max().unwrap());
}
}
}
}
fn main(){
huawei_2016_1();
}

HJ17 坐标移动

开发一个坐标计算工具， A表示向左移动，D表示向右移动，W表示向上移动，S表示向下移动。从（0,0）点开始移动，从输入字符串里面读取一些坐标，并将最终输入结果输出到输出文件里面。

输入：
合法坐标为A(或者D或者W或者S) + 数字（两位以内）
坐标之间以;分隔。
非法坐标点需要进行丢弃。如AA10;  A1A;  $%$;  YAD; 等。
下面是一个简单的例子 如：
A10;S20;W10;D30;X;A1A;B10A11;;A10;
处理过程：
起点（0,0）
+   A10   =  （-10,0）
+   S20   =  (-10,-20)
+   W10  =  (-10,-10)
+   D30  =  (20,-10)
+   x    =  无效
+   A1A   =  无效
+   B10A11   =  无效
+  一个空 不影响
+   A10  =  (10,-10)
结果 （10， -10）

pub fn input() -> String {
let mut input = String::new();
std::io::stdin().read_line(&mut input).unwrap();
input.trim().to_string()
}
pub fn huawei_2016_2() {
/*
HJ17 坐标移动
*/
fn contains_muti_letter(s: String) -> bool {
let mut count = 0;
for c in s.chars() {
if !c.is_digit(10) {
count += 1;
}
}
if count >= 2 {
return true;
} else {
return false;
}
}
let f = input();
let f_vec = f
.split(";")
.filter(|s| !s.is_empty())
.map(|s| {
let mut s = s.to_string();
if contains_muti_letter(s.to_string()) {
s = "".to_string();
}
s
})
.collect::<Vec<_>>();
let mut pos = (0, 0);
for i in 0..f_vec.len() {
if let Some(num) = &f_vec[i].split("A").last() {
if let Ok(n) = num.parse::<i32>() {
pos.0 = pos.0 - n;
}
}
if let Some(num) = &f_vec[i].split("D").last() {
if let Ok(n) = num.parse::<i32>() {
pos.0 = pos.0 + n;
}
}
if let Some(num) = &f_vec[i].split("W").last() {
if let Ok(n) = num.parse::<i32>() {
pos.1 = pos.1 + n;
}
}
if let Some(num) = &f_vec[i].split("S").last() {
if let Ok(n) = num.parse::<i32>() {
pos.1 = pos.1 - n;
}
}
}
println!("{},{}", pos.0,pos.1);
}
fn main(){
huawei_2016_2();
}

HJ20 密码验证合格程序

密码要求: 1.长度超过8位 2.包括大小写字母.数字.其它符号,以上四种至少三种 3.不能有长度大于2的包含公共元素的子串重复 （注：其他符号不含空格或换行） 数据范围：输入的字符串长度满足 1≤n≤100

输入：
021Abc9000
021Abc9Abc1
021ABC9000
021$bc9000
输出：
OK
NG
NG
OK

Rust

#![allow(unused)]
fn main() {
pub fn huawei_2016_3() {
/*
HJ20 密码验证合格程序
*/
fn input() -> String {
let mut input = String::new();
std::io::stdin().read_line(&mut input).unwrap();
input.trim().to_string()
}
//是否公共元素的子串重复
fn repeat(f: &str) -> bool {
let mut vec = vec![];
for i in 0..f.len() - 2 {
let sub = f
.chars()
.map(|s| s.to_string())
.collect::<Vec<_>>()
.get(i..i + 3)
.unwrap()
.to_vec()
.join("")
.to_string();
if vec.contains(&sub) {
return false;
} else {
vec.push(sub);
}
}
true
}
fn valid(f: &str) -> &str {
let mut re = "";
let mut char_up = 0;
let mut char_low = 0;
let mut char_digit = 0;
let mut char_other = 0;
for c in f.chars() {
if (c as i32 >= 65 && c as i32 <= 90) {
char_up += 1;
} else if (c as i32 >= 97 && c as i32 <= 122) {
char_low += 1;
} else if (c as i32 >= 48 && c as i32 <= 57) {
char_digit += 1;
} else {
char_other += 1;
}
}
let mut num = 0;
let types = vec![char_up, char_low, char_digit, char_other];
for t in &types {
if t >= &1 {
num += 1;
}
}
// println!("{:?}", &types);
//三个条件
let reqire1 = f.len() >= 8;
let reqire2 = num >= 3;
let reqire3 = repeat(&f);
// println!("{}-{}-{}", reqire1, reqire2, reqire3);
if (reqire1 && reqire2 && reqire3) {
re = "OK";
} else {
re = "NG";
}
re
}
use std::io::{self, *};
fn run() {
let stdin = io::stdin();
unsafe {
for line in stdin.lock().lines() {
let f = line.unwrap();
println!("{}", valid(&f));
}
}
}
run();
}
}

JavaScript

const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
rl.on('line', function (line) {
const repeat = (str) => {
let len = str.length - 2;
let vec = [];
for (let i = 0; i < len; i++) {
const sub = str.substring(i, i + 3);
if (vec.indexOf(sub) >= 0) {
return false;
} else {
vec.push(sub);
}
}
return true;
};
function validate(str) {
let valid = "NG"
let validStr = str.length > 8
let validRepeat = repeat(str)
let validTypes = types(str)
if (validStr && validRepeat && validTypes) {
valid = "OK"
}
return valid
}
console.log(validate(line));
function types(str) {
let num = 0
if (/[a-z]/.test(str)) {
num++
}
if (/[A-Z]/.test(str)) {
num++
}
if (/[0-9]/.test(str)) {
num++
}
if (/[^0-9a-zA-Z]/.test(str)) {
num++
}
return num >= 3
}
});

HJ26 字符串排序

编写一个程序，将输入字符串中的字符按如下规则排序。 规则 1 ：英文字母从 A 到 Z 排列，不区分大小写。 如，输入： Type 输出： epTy 规则 2 ：同一个英文字母的大小写同时存在时，按照输入顺序排列。 如，输入： BabA 输出： aABb 规则 3 ：非英文字母的其它字符保持原来的位置。 如，输入： By?e 输出： Be?y 数据范围：输入的字符串长度满足 \1≤n≤1000

输入：
A Famous Saying: Much Ado About Nothing (2012/8).
输出：
A aaAAbc dFgghh: iimM nNn oooos Sttuuuy (2012/8).

pub fn huawei_2016_4() {
fn valid(f: &str) -> String {
let mut v: Vec<u8> = Vec::from(f);
let mut c: Vec<u8> = Vec::new();
for i in 0..26 {
for j in 0..v.len() {
if ((v[j] == 65u8 + (i as u8)) || (v[j] == 97u8 + (i as u8))) {
c.push(v[j]);
}
}
}
let mut i = 0;
let mut j = 0;
while i < v.len() && j < c.len() {
if (v[i] >= 97 && v[i] <= 122) || (v[i] >= 65 && v[i] <= 90) {
v[i] = c[j];
j += 1;
}
i += 1;
}
let mut re = String::new();
for i in v {
re.push(char::from(i));
}
re
}
fn run() {
use std::io::{self, *};
let stdin = io::stdin();
unsafe {
for line in stdin.lock().lines() {
let f = line.unwrap();
println!("{}", valid(&f));
}
}
}
run();
}
fn main(){
huawei_2016_4();
}

非递增顺序的最小子序列

给你一个数组 nums，请你从中抽取一个子序列，满足该子序列的元素之和 严格 大于未包含在该子序列中的各元素之和。 如果存在多个解决方案，只需返回 长度最小 的子序列。如果仍然有多个解决方案，则返回 元素之和最大 的子序列。 与子数组不同的地方在于，「数组的子序列」不强调元素在原数组中的连续性，也就是说，它可以通过从数组中分离一些（也可能不分离）元素得到。 注意，题目数据保证满足所有约束条件的解决方案是 唯一 的。同时，返回的答案应当按 非递增顺序 排列。

输入：nums = [4,3,10,9,8]
输出：[10,9]
解释：子序列 [10,9] 和 [10,8] 是最小的、满足元素之和大于其他各元素之和的子序列。但是 [10,9] 的元素之和最大。

#![allow(unused)]
fn main() {
impl Solution {
pub fn min_subsequence(nums: Vec<i32>) -> Vec<i32> {
if nums.len() == 1 || nums.clone().into_iter().all(|x| nums[0] == x) {
return nums;
}
let mut v: Vec<(&[i32], &[i32])> = vec![];
let mut n = nums.clone();
n.sort();
for i in 1..n.len() {
v.push(n.split_at(i))
}
let mut re = vec![];
for vv in &v {
if vv.0.into_iter().sum::<i32>() < vv.1.into_iter().sum::<i32>() {
re.push(vv.1.to_vec());
}
}
println!("{:?}", &re);
let mut rr = re.last().unwrap().to_vec();
rr.reverse();
rr
}
}
}

区间列表的交集

给定两个由一些 闭区间 组成的列表，firstList 和 secondList ，其中 firstList[i] = [starti, endi] 而 secondList[j] = [startj, endj] 。每个区间列表都是成对 不相交 的，并且 已经排序 。 返回这 两个区间列表的交集 。 形式上，闭区间 [a, b]（其中 a <= b）表示实数 x 的集合，而 a <= x <= b 。 两个闭区间的 交集 是一组实数，要么为空集，要么为闭区间。例如，[1, 3] 和 [2, 4] 的交集为 [2, 3] 。

输入：firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
输出：[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

#![allow(unused)]
fn main() {
pub fn huawei_2016_5() {
pub struct Solution {}
impl Solution {
pub fn interval_intersection(
first_list: Vec<Vec<i32>>,
second_list: Vec<Vec<i32>>,
) -> Vec<Vec<i32>> {
let mut res = vec![];
let n = first_list.len();
let m = second_list.len();
let mut i = 0;
let mut j = 0;
while (i < n && j < m) {
let left = if first_list[i][0] > second_list[j][0] {
first_list[i][0]
} else {
second_list[j][0]
};
let right = if first_list[i][1] < second_list[j][1] {
first_list[i][1]
} else {
second_list[j][1]
};
if left <= right {
res.push([left, right].to_vec());
}
if first_list[i][1] < second_list[j][1] {
i += 1;
} else {
j += 1;
}
}
res
}
}
fn run() {
let re = Solution::interval_intersection(
[
[0, 2].to_vec(),
[5, 10].to_vec(),
[13, 23].to_vec(),
[24, 25].to_vec(),
]
.to_vec(),
[
[1, 5].to_vec(),
[8, 12].to_vec(),
[15, 24].to_vec(),
[25, 26].to_vec(),
]
.to_vec(),
);
assert_eq!(
[
[1, 2].to_vec(),
[5, 5].to_vec(),
[8, 10].to_vec(),
[15, 23].to_vec(),
[24, 24].to_vec(),
[25, 25].to_vec()
]
.to_vec(),
re
);
}
run();
}
}

区间列表的并集

#![allow(unused)]
fn main() {
pub fn huawei_2016_20() {
pub struct Solution {}
impl Solution {
pub fn interval_intersection(
first_list: Vec<Vec<i32>>,
second_list: Vec<Vec<i32>>,
) -> Vec<Vec<i32>> {
let mut res = vec![];
let n = first_list.len();
let m = second_list.len();
let mut i = 0;
let mut j = 0;
while (i < n && j < m) {
let left = if first_list[i][1] >= second_list[j][0] {
Some(first_list[i][0])
} else {
res.push(first_list[i].to_vec());
res.push(second_list[i].to_vec());
None
};
let right = if first_list[i][1] >= second_list[j][0] {
Some(second_list[i][1])
} else {
None
};
if left <= right {
res.push([left.unwrap(), right.unwrap()].to_vec());
}
if first_list[i][1] <= second_list[j][1] {
i += 1;
} else {
j += 1;
}
}
res.dedup();
res
}
}
fn run() {
let re = Solution::interval_intersection(
[
[0, 2].to_vec(),
[5, 10].to_vec(),
[13, 23].to_vec(),
[24, 25].to_vec(),
]
.to_vec(),
[
[1, 5].to_vec(),
[8, 12].to_vec(),
[15, 24].to_vec(),
[25, 26].to_vec(),
]
.to_vec(),
);
println!("{:?}", re); //[[0, 5], [5, 12], [13, 24], [24, 26]]
}
run();
}
}

合并表记录

数据表记录包含表索引index和数值value（int范围的正整数），请对表索引相同的记录进行合并，即将相同索引的数值进行求和运算，输出按照index值升序进行输出。

输入
4
0 1
0 2
1 2
3 4
输出
0 3
1 2
3 4

pub fn input_num<T>() -> T
where
<T as std::str::FromStr>::Err: std::fmt::Debug,
T: std::str::FromStr,
{
let mut input = String::new();
std::io::stdin().read_line(&mut input).unwrap();
input.trim().to_string().parse::<T>().unwrap()
}
pub fn input_vec_num<T>() -> Vec<T>
where
<T as std::str::FromStr>::Err: std::fmt::Debug,
T: std::str::FromStr,
{
let mut input = String::new();
std::io::stdin().read_line(&mut input).unwrap();
input
.split_whitespace()
.map(|s| s.parse::<T>().unwrap())
.collect::<Vec<T>>()
}
fn merge_map_records() {
let n = input_num::<i32>();
use std::collections::BTreeMap;
let mut v = BTreeMap::new();
for _ in 0..n {
let in_v = input_vec_num::<i32>();
if v.contains_key(&in_v[0]) {
if let Some(vv) = v.get_mut(&in_v[0]) {
*vv = *vv + in_v[1];
}
} else {
v.insert(in_v[0], in_v[1]);
}
}
for (k, v) in &v {
println!("{} {}", k, v);
}
}
fn main() {
merge_map_records();
}

HJ33 整数与IP地址间的转换(ipv4) 原理：ip地址的每段可以看成是一个0-255的整数，把每段拆分成一个二进制形式组合起来，然后把这个二进制数转变成 一个长整数。 举例：一个ip地址为10.0.3.193 每段数字 相对应的二进制数 10 00001010 0 00000000 3 00000011 193 11000001 组合起来即为：00001010 00000000 00000011 11000001,转换为10进制数就是：167773121，即该IP地址转换后的数字就是它了。

输入：
10.0.3.193
167969729
输出：
167773121
10.3.3.193

Rust

pub fn huawei_2016_6() {
fn binary_to_decimal(num: &str) -> Option<i64> {
if num.len() == 0 {
return None;
}
let mut sum = 0;
let vec = num
.chars()
.map(|x| i64::from(x.to_digit(10).unwrap()))
.collect::<Vec<i64>>();
for (index, item) in vec.iter().rev().enumerate() {
sum += i64::pow(2, index as u32) * item;
}
Some(sum)
}
pub fn input_vec_num<T>(split_by: &str) -> Vec<T>
where
<T as std::str::FromStr>::Err: std::fmt::Debug,
T: std::str::FromStr,
{
let mut input = String::new();
std::io::stdin().read_line(&mut input).unwrap();
input
.split(split_by)
.filter(|s| !s.is_empty())
.map(|s| s.trim().to_string())
.map(|s| s.parse::<T>().unwrap())
.collect::<Vec<T>>()
}
pub fn input_num<T>() -> T
where
<T as std::str::FromStr>::Err: std::fmt::Debug,
T: std::str::FromStr,
{
let mut input = String::new();
std::io::stdin().read_line(&mut input).unwrap();
input.trim().to_string().parse::<T>().unwrap()
}
fn ip_to_int() {
let ip = input_vec_num::<i64>(".");
let mut ipb = String::new();
for i in ip.iter() {
let s = format!("{:8b}", i).replace(" ", "0");
ipb.push_str(&s);
}
println!("{}", binary_to_decimal(&ipb).unwrap());
}
fn int_to_ip() {
let num = input_num::<i64>();
let s = format!("{:>032b}", num);
let mut s_vec = vec![];
for i in (0..s.len()).step_by(8) {
s_vec.push(binary_to_decimal(&s[i..i + 8]).unwrap().to_string());
}
println!("{}", s_vec.join("."));
}
ip_to_int();
int_to_ip();
}
fn main(){
huawei_2016_6();
}

Python

def ip_to_int(s):
s = list(map(int, s.split('.')))
s = [bin(i)[2:] for i in s]
s = ''.join([(8-len(i)) * '0' + str(i) for i in s])
print(int(s,2))
def int_to_ip(s):
s = bin(int(s))[2:]
s = (32 - len(s)) * '0' + s
s = [str(int((s[i:i+8]), 2)) for i in range(0,len(s),8)]
print('.'.join(s))
while True:
try:
s = input()
if '.' in s:
ip_to_int(s)
else:
int_to_ip(s)
except:
break

报数游戏

题目描述：约瑟夫环（Josephus）问题是由古罗马的史学家约瑟夫（Josephus）提出的，其表述方式有多种，较典型的一种是： 有ｎ只猴子，按顺时针方向围成一圈选大王（编号从１到ｎ），从第１号开始报数，一直数到ｍ，数到ｍ的猴子退出圈外，剩下的猴子再接着从1 开始报数。就这样，直到圈内只剩下一只猴子时，这个猴子就是猴王，编程求输入ｎ，ｍ后，输出最后猴王的编号。 有n（n<=100）围成一圈，顺序排号（从1排到n）。从第一个人开始报数（从1一直往上报数)，凡报到m及m的倍数或者尾数为m的人退出圈子，问最后留下的是原来第几号的那位？ 输入描述： 输入为两个正整数，第一个<=100，第二个<=9； 输出描述： 输出为一个正整数；

样式输入：
10 3
样式输出：
5

Rust

pub fn huawei_2016_7() {
pub fn input_vec_num<T>(split_by: &str) -> Vec<T>
where
<T as std::str::FromStr>::Err: std::fmt::Debug,
T: std::str::FromStr,
{
let mut input = String::new();
std::io::stdin().read_line(&mut input).unwrap();
input
.split(split_by)
.filter(|s| !s.is_empty())
.map(|s| s.trim().to_string())
.map(|s| s.parse::<T>().unwrap())
.collect::<Vec<T>>()
}
let v = input_vec_num::<i64>(" ");
let mut n = v.get(0).unwrap().to_owned();
let m = v.get(1).unwrap().to_owned();
let mut count = 0;
let mut vec = (1..=n as usize)
.into_iter()
.map(|s| 1 as usize)
.collect::<Vec<_>>();
while n > 1 {
count += 1;
if (count == m || count % m == 0 || count % 10 == m) {
n -= 1;
let i_remove = count % n;
vec[i_remove as usize] = 0;
}
}
let mut res = 0;
for (i, s) in vec.iter().enumerate() {
if *s == 1 {
res = i + 1;
break;
}
}
println!("{}", res);
}
fn main(){
huawei_2016_7();
}

Python

class huawei:
def __init__(self):
self
def huawei_2016_7(self):
li = list(map(int, input().split(" ")))
n = li[0]
m = li[1]
count = 0
l = [1 for i in range(n)]
while n > 1:
count += 1
if count == m or count % m == 0 or count % 10 == m:
n -= 1
i_remove = count % n
l[i_remove] = 0
print(l.index(1)+1)
sol = huawei()
s = sol.huawei_2016_7()

停车位问题

有一横排车位，有至少一个车位停了车，也至少有一个车位没停车。一个车位有车用1表示，无车用0表示。为了避免剐蹭，请为司机规划停在哪个车位，距离其他车中间间隔的车位最远。输入：一组数据，代表目前车位的状态。 输出：当前车辆停车距离其他车辆的最大间距

输入 1 0 0 0 0 1 0 1 0
输出 3
新来的车停在 下标为1或者小标为4的位置，才会出现距离其他车辆最大距离3

Rust

#![allow(unused)]
fn main() {
pub fn huawei_2016_8() {
pub fn input_vec_string(split_by: &str) -> Vec<String> {
let mut input = String::new();
std::io::stdin().read_line(&mut input).unwrap();
input
.split(split_by)
.filter(|s| !s.is_empty())
.map(|s| s.trim().to_string())
.map(|s| s.to_string())
.collect::<Vec<String>>()
}
let v = input_vec_string("1");
let max = v
.iter()
.map(|s| {
s.split(" ")
.filter(|s| !s.is_empty())
.map(|s| s.trim().to_string())
.map(|s| s.to_string())
.collect::<Vec<String>>()
.len()
})
.collect::<Vec<_>>();
println!("{:?}", max.iter().max().unwrap() - 1);
}
}

Python

def huawei_2016_8(self):
nums_input = input().split()
max_ = 0
i = 0
j = 1
while j < len(nums_input):
if nums_input[i] == nums_input[j] == "0":
j += 1
else:
max_ = max([max_, j - i])
i = j
j = j + 1
else:
max_ = max([max_, j - i])
print(max_ - 1)

拼接URL

题目描述：

• 给定一个url前缀和url后缀,通过,分割 需要将其连接为一个完整的url
• 如果前缀结尾和后缀开头都没有/，需要自动补上/连接符
• 如果前缀结尾和后缀开头都为/，需要自动去重
• 约束：不用考虑前后缀URL不合法情况

in:/acm,/bb
out:/acm/bb

in:/abc/,/bcd
out:/abc/bcd

in:,
out:/

#![allow(unused)]
fn main() {
pub fn huawei_2016_9() {
pub fn input_vec_string(split_by: &str) -> Vec<String> {
let mut input = String::new();
std::io::stdin().read_line(&mut input).unwrap();
input
.split(split_by)
.filter(|s| !s.is_empty())
.map(|s| s.trim().to_string())
.map(|s| s.to_string())
.collect::<Vec<String>>()
}
let v = input_vec_string(",");
let v_vec = v
.iter()
.map(|s| {
let res = if s.starts_with("/") && !s.ends_with("/") {
s.to_string()
} else if s.ends_with("/") {
s.as_str()[0..s.len() - 1].to_string()
} else {
format!("/{}", s)
};
res.to_string()
})
.collect::<Vec<_>>();
println!("{:?}", v_vec.join(""));
}
}

最长连续子串

有N个正整数组成的一个序列,给定一个整数sum 求长度最长的的连续子序列使他们的和等于sum 返回次子序列的长度 如果没有满足要求的序列 返回-1

案例1：
输入
1,2,3,4,2
6
输出
3
解析：1,2,3和4,2两个序列均能满足要求
所以最长的连续序列为1,2,3 因此结果为3
示例2：
输入
1,2,3,4,2
20
输出
-1
解释：没有满足要求的子序列，返回-1

#![allow(unused)]
fn main() {
pub fn huawei_2016_10() {
pub fn input_vec_num<T>(split_by: &str) -> Vec<T>
where
<T as std::str::FromStr>::Err: std::fmt::Debug,
T: std::str::FromStr,
{
let mut input = String::new();
std::io::stdin().read_line(&mut input).unwrap();
input
.split(split_by)
.filter(|s| !s.is_empty())
.map(|s| s.trim().to_string())
.map(|s| s.parse::<T>().unwrap())
.collect::<Vec<T>>()
}
pub fn input_num<T>() -> T
where
<T as std::str::FromStr>::Err: std::fmt::Debug,
T: std::str::FromStr,
{
let mut input = String::new();
std::io::stdin().read_line(&mut input).unwrap();
input.trim().to_string().parse::<T>().unwrap()
}
pub fn max_subsequence(nums: Vec<i32>, target: i32) -> isize {
let mut v = vec![];
for i in 0..nums.len() {
let res = &nums.split_at(i);
v.push(res.0.to_vec());
v.push(res.1.to_vec());
}
let mut re = vec![];
for vv in &v {
if vv.iter().sum::<i32>() == target {
re.push(vv.len());
}
}
match re.iter().max() {
Some(r) => *r as isize,
None => -1,
}
}
let nums = input_vec_num::<i32>(",");
let target = input_num::<i32>();
let res = max_subsequence(nums, target);
println!("{}", res);
}
}

求最长子串长度

输入一个字符串，求符合条件的最长子串的长度，符合条件的子串必须且只能包含一个字母（a-zA-Z）,其余部分只能由数字构成

输入：
abc123ABC
输出：
4
解释：最长的连续数字长度为123，随便加上前面或者后面的一个字母，长度即为：4

import re
s = input()
# 通过正则找出所有连续的数字子串（考完之后想了下，其实不如改成双指针遍历的方法去找最长数字子串）
pattern = re.compile(r'\d+')
arr = pattern.findall(s)
if not arr:
print(-1)
else:
max_n = arr[0]
for i in arr:
if len(i) > len(max_n):
max_n = i
index_start = s.index(max_n)
if index_start - 1 >= 0 and s[index_start-1] in "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ":
print(len(max_n)+1)
elif index_start + len(max_n) <= len(s)-1 and s[index_start + len(max_n)] in "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ":
print(len(max_n)+1)
else:
print(-1)
# 此答案用例通过率79%，占用内存超过了限定值

最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
longest_streak = 0
num_set = set(nums)
for num in num_set:
if num - 1 not in num_set:
current_num = num
current_streak = 1
while current_num + 1 in num_set:
current_num += 1
current_streak += 1
longest_streak = max(longest_streak, current_streak)
return longest_streak

求数组中最大N个与与最小N个数的和

输入一个输入和N，求求数组中最大N个与与最小N个数的和，数组需要去重，去重后的输入长度如果不够2*N，则返回 -1 输入描述： 数组个数按空格分割的数组N的值 例1： 输入描述： 5 95 88 83 64 100 2 输出： 342 解释：最大的两个数是：100、95 最小的两个数是：83、64，输出他们的和即可

a = int(input())
b = list(map(int, input().split(' ')))
c = int(input())
bb = sorted(b)
max = 0
min = 0
if len(bb) < c*2:
print(-1)
else:
for i in bb[0:c]:
min += i
for i in bb[-c:]:
max += i
print(max+min)

计算出租车的实际里程

出租车司机自行修改了里程表，导致每次遇到4，就会跳过，比如4–>5、39–>40、400–>500

输入：
5
输出：
4
解释：因为实际里程到4之后，会跳过直接到5，所以里程表显示5的时候，实际里程应该为4
例2：
输入：
15
输出：
13
解释：实际里程到4之后，会跳过直接到5，多了1，到14之后直接跳到了15，又多了1，所以 13 = 15 - 1 - 1

Rust

#![allow(unused)]
fn main() {
pub fn huawei_2016_11() {
pub fn input_num<T>() -> T
where
<T as std::str::FromStr>::Err: std::fmt::Debug,
T: std::str::FromStr,
{
let mut input = String::new();
std::io::stdin().read_line(&mut input).unwrap();
input.trim().to_string().parse::<T>().unwrap()
}
let n = input_num::<i64>();
let mut m = 0;
let mut more = 0;
let s_num = format!("{}", n);
while m < n {
if format!("{}", m).contains("4") {
let this_m = format!("{}", m).replace("4", "5").parse::<i64>().unwrap();
if this_m <= n {
more += this_m - m;
m = this_m;
} else {
break;
}
} else {
m += 1;
}
}
println!("{}", n - more);
}
}

Python

n = int(input())
m = 0
more = 0
while m < n:
# 不知道4会出现在个、十、百、千、万哪儿个位置
if '4' in str(m):
this_m = int(str(m).replace("4", "5"))
if this_m <= n:
more += this_m - m
m = this_m
else:
break
else:
m += 1
print(n-more)

字符串分割

给定非空字符在s，将该字符串分割成一些子串，使每个子串的ASCIIA码值的和均为水仙花数。 1、若分割不成功则返回 0 2、若分割成功且分割结果不唯一则返回-1 3、若分割成功且分割结果唯一，则返回分割后的子串数目 输入描述: 1、输入字符串的最大长度为 200 输出描述:根据题目描述中情况返回相应的结果 备注:“水仙花数”是指一个三位数，每位上数字的立方和等于该数字本身，如 371是“水仙花数”，因为:371=3^3+7^3+1^3。

输入
abc
输出
0

Rust

#![allow(unused)]
fn main() {
pub fn huawei_2016_12() {
pub fn input_string() -> String {
let mut input = String::new();
std::io::stdin().read_line(&mut input).unwrap();
input.trim().to_string()
}
fn is_sxhs(n: i64) -> bool {
// """判断是否为水仙花数"""
if n < 100 || n > 999 {
return false;
}
let a = n % 10;
let b = (n - a) / 10 % 10;
let c = (n - a - b * 10) / 100 % 10;
if n == i64::pow(a, 3) + i64::pow(b, 3) + i64::pow(c, 3) {
return true;
} else {
return false;
}
}
fn partition_sxhs(s: &str) -> isize {
let ascii_v = Vec::from(s);
if ascii_v.len() <= 0 {
return 0;
}
let mut res = vec![];
for i in 1..ascii_v.len() + 1 {
let (vec0, vec1) = ascii_v.split_at(i);
let sum0: i64 = vec0.iter().map(|s| *s as i64).sum();
let sum1: i64 = vec1.iter().map(|s| *s as i64).sum();
if is_sxhs(sum0) {
res.push(vec0.to_vec());
}
if is_sxhs(sum1) {
res.push(vec1.to_vec());
}
}

let re = if res.len() <= 0 {
0
} else if res.len() > 1 {
-1
} else {
res.len() as isize
};
re
}
let s = input_string();
println!("{}", partition_sxhs(&s));
// println!("{}", is_sxhs(371));
}
}

Python

def partition_sxhs(s):
ord_arr = [ord(x) for x in s]
def is_sxhs(n):
"""判断是否为水仙花数"""
if n < 100 or n > 999:
return False
a = n % 10
b = (n - a) // 10 % 10
c = (n - a - b * 10) // 100 % 10
if n == a ** 3 + b ** 3 + c ** 3:
return True
return False
def backtrack(origin_list, tmp_list, result):
"""回溯算法"""
if not origin_list:
result.append(tmp_list[:])
return
for i in range(1, len(origin_list) + 1):
this_list = origin_list[:i]
# 先截取出来一个水仙花数，再递归数组剩余部分
if is_sxhs(sum(this_list)):
tmp_list.append(this_list)
backtrack(origin_list[i:], tmp_list, result)
tmp_list.pop()
tmp_list, result = [], []
backtrack(ord_arr, tmp_list, result)
print(result)
if len(result) == 0:
return 0
elif len(result) > 1:
return -1
elif len(result) == 1:
return len(result[0])
print(partition_sxhs("Gddd$Gddd"))

求解连续数列

已知连续正整数数列{K}=K1,K2,K3…Ki的各个数相加之和为S，i=N(0<S<100000,0<N<100000),求此数列K。 输入描述: 输入包含两个参数，1)连续正整数数列和S，2)数列里数的个数N。 输出描述: 如果有解输出数列K，如果无解输出-1。

输入
525
6
输出
85 86 87 88 89 90

Rust

#![allow(unused)]
fn main() {
pub fn huawei_2016_13() {
fn shulie(s: usize, n: usize) -> Vec<f64> {
let mut arr = vec![0.; n];
let middle = if n % 2 == 0 {
f64::floor((s as f64 / n as f64) + 0.5)
} else {
f64::floor((s as f64 / n as f64))
};
let start = middle - (n as f64 / 2.);
for i in 0..arr.len() {
arr[i] = start + i as f64;
}
if arr[0] <= 0. {
return vec![];
}
arr
}
println!("{:?}", shulie(525, 6));
}
}

Python

import math
def shulie(s, n):
arr = [0] * n
middle = int(s / n + 0.5) if n % 2 == 0 else int(s / n)
start = middle - math.floor(n / 2)
for i in range(len(arr)):
arr[i] = start + i
if arr[0] <= 0:
return -1
return arr
print(shulie(525, 5))

服务器广播

服务器连接方式包括直接相连，间接连接。 A 和 B 直接连接， B 和 c 直接连接，则 A 和 c 间接连接。直接连接和间接连接都可以发送广播。 给出一个 N * N 数组，代表 N 个服务器， matrix[i][j] == 1 ，则代表 i 和 j 直接连接；不等于 1 时，代表 i 和 j 不直接连接。 matrix[i][i]== 1 ，即自己和自己直接连接。 matrix[i][j]==matrix[j][i] 。计算初始需要给几台服务器广播，才可以使侮个服务器都收到广播。

in:
[[1,1,0],[1,1,0],[0,0,1]]
out:
2

def minimal_broadcast(matrix):
n = len(matrix)
stack = []
full_stack = [i for i in range(n)]
iterator_stack = []
res = []
while full_stack:
stack.append(full_stack[0])
minimal_graph = []
while stack:
i = stack.pop(0)
iterator_stack.append(i)
if i in full_stack:
full_stack.pop(full_stack.index(i))
for j in range(n):
if matrix[i][j] == 1:
if j not in stack and j not in iterator_stack:
stack.append(j)
if j not in minimal_graph:
minimal_graph.append(j)
# print(minimal_graph)
res.append(minimal_graph)
# print("*****")
return len(res)

if __name__ == '__main__':
matrix = [[1,1,0], [1,1,1], [0,1,1]]
n = minimal_broadcast(matrix)
print(n)

HJ88 扑克牌大小（玩牌高手）

扑克牌游戏大家应该都比较熟悉了，一副牌由54张组成，含3~A、2各4张，小王1张，大王1张。牌面从小到大用如下字符和字符串表示（其中，小写joker表示小王，大写JOKER表示大王）： 3 4 5 6 7 8 9 10 J Q K A 2 joker JOKER 输入两手牌，两手牌之间用“-“连接，每手牌的每张牌以空格分隔，”-“两边没有空格，如：4 4 4 4-joker JOKER。 请比较两手牌大小，输出较大的牌，如果不存在比较关系则输出ERROR。 基本规则： （1）输入每手牌可能是个子、对子、顺子（连续5张）、三个、炸弹（四个）和对王中的一种，不存在其他情况，由输入保证两手牌都是合法的，顺子已经从小到大排列； （2）除了炸弹和对王可以和所有牌比较之外，其他类型的牌只能跟相同类型的存在比较关系（如，对子跟对子比较，三个跟三个比较），不考虑拆牌情况（如：将对子拆分成个子）； （3）大小规则跟大家平时了解的常见规则相同，个子、对子、三个比较牌面大小；顺子比较最小牌大小；炸弹大于前面所有的牌，炸弹之间比较牌面大小；对王是最大的牌； （4）输入的两手牌不会出现相等的情况。 输入描述： 输入两手牌，两手牌之间用”-“连接，每手牌的每张牌以空格分隔，”-“两边没有空格，如 4 4 4 4-joker JOKER。 输出描述： 输出两手牌中较大的那手，不含连接符，扑克牌顺序不变，仍以空格隔开；如果不存在比较关系则输出ERROR。

输入：
4 4 4 4-joker JOKER
输出：
joker JOKER

dic = {'3': 1, '4': 2, '5': 3, '6': 4, '7': 5, '8': 6,
'9': 7, '10': 8, 'J': 9, 'Q': 10, 'K': 11,
'A': 12, '2': 13, 'joker': 14, 'JOKER': 15}
while True:
try:
s1, s2 = input().split('-')
list1, list2 = s1.split(), s2.split()
if len(list1) == len(list2):
if dic[list1[0]] > dic[list2[0]]:
print(' '.join(list1))
else:
print(' '.join(list2))
elif 'joker JOKER' in s1 or 'joker JOKER' in s2:
print('joker JOKER')
elif len(list1) == 4 and len(set(list1)) == 1:
print(' '.join(list1))
elif len(list2) == 4 and len(set(list2)) == 1:
print(' '.join(list2))
else:
print('ERROR')
except:
break

汽水瓶

某商店规定：三个空汽水瓶可以换一瓶汽水，允许向老板借空汽水瓶（但是必须要归还）。 小张手上有n个空汽水瓶，她想知道自己最多可以喝到多少瓶汽水。 数据范围：输入的正整数满足 \1≤n≤100 注意：本题存在多组输入。输入的 0 表示输入结束，并不用输出结果。 输入描述： 输入文件最多包含 10 组测试数据，每个数据占一行，仅包含一个正整数 n（ 1<=n<=100 ），表示小张手上的空汽水瓶数。n=0 表示输入结束，你的程序不应当处理这一行。 输出描述： 对于每组测试数据，输出一行，表示最多可以喝的汽水瓶数。如果一瓶也喝不到，输出0。

输入：
3
10
81
0
输出：
1
5
40
说明：
样例 1 解释：用三个空瓶换一瓶汽水，剩一个空瓶无法继续交换
样例 2 解释：用九个空瓶换三瓶汽水，剩四个空瓶再用三个空瓶换一瓶汽水，剩两个空瓶，向老板借一个空瓶再用三个空瓶换一瓶汽水喝完得一个空瓶还给老板

use std::io::{self, *};
fn main() {
let stdin = io::stdin();
for line in stdin.lock().lines() {
let ll = line.unwrap();
if &ll == "0" {
break;
}
let mut empty = ll.parse::<i64>().unwrap(); // 空瓶子数量
let mut res = 0; //总共换的瓶子
let mut new_get = 0;
let mut hold = 0;
while empty >= 2 {
//借一瓶 换3个空 get 1瓶 还给老板
if empty == 2 {
empty = 0;
res += 1;
}
//空瓶>=3
else {
new_get = empty / 3; //新得到的瓶子
hold = empty % 3; //手里剩下的
res += new_get; //换来的加到 总换瓶里
empty = new_get + hold; //空瓶等于 = 新得到的+手里剩下的
}
}
println!("{}", res);
}
}

根据身高重建队列

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。 请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
解释：
编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。

Rust

#![allow(unused)]
fn main() {
pub fn huawei_2016_15() {
struct Solution {}
impl Solution {
pub fn reconstruct_queue(people: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
let mut p = people.clone();
p.sort_by_key(|s| (-*s.get(0).unwrap(),*s.get(1).unwrap()));
let mut i = 0;
while i < p.len(){
if i > p[i][1] as usize{
p.insert(p[i][1] as usize, p.get(i).unwrap().to_owned());
p.remove(i+1);
}
i += 1;
}
return p;
}
}
let people = vec![
[7, 0].to_vec(), [4, 4].to_vec(), [7, 1].to_vec(), [5, 0].to_vec(), [6, 1].to_vec(), [5, 2].to_vec()
];
let res = Solution::reconstruct_queue(people);
// [[5, 0], [7, 0], [5, 2], [6, 1], [4, 4], [7, 1]]
println!("{:?}", res);
}
}

Python

def reconstructQueue(people):
people = sorted(people, key=lambda x: (-x[0], x[1]))
i = 0
while i < len(people):
if i > people[i][1]:
people.insert(people[i][1], people[i])
people.pop(i+1)
i += 1
return people
people = [[7, 0], [4, 4], [7, 1], [5, 0], [6, 1], [5, 2]]
# [[5, 0], [7, 0], [5, 2], [6, 1], [4, 4], [7, 1]]
print(reconstructQueue(people))

计算疫情扩散时间

在一个地图中(地图由n*n个区域组成），有部分区域被感染病菌。感染区域每天都会把周围（上下左右）的4个区域感染。 请根据给定的地图计算，多少天以后，全部区域都会被感染。 0表示未感染区域，1表示已经感染区域 例如输入1,0,1,0,0,0,1,0,1，表示地图 1,0,1 0,0,0 1,0,1

输入
1,0,1,0,0,0,1,0,1
输出
2
输入
0,0,0,0
输出
-1
输入
1,1,1,1,1,1,1,1,1
输出
-1

def spread_time(string):
string_list = string.split(",")
length = len(string_list)
if string_list.count("1") == length or string_list.count("0") == length:
return -1
slice = int(pow(length, 0.5))
rank = [string_list[i*slice:(i+1)*slice] for i in range(slice)]
rank1 = [string_list[i*slice:(i+1)*slice] for i in range(slice)]
def spread(rank, rank1):
for i in range(len(rank)):
for j in range(len(rank)):
if rank[i][j] == "1":
continue
if i > 0:
if rank1[i - 1][j] == "1":
rank[i][j] = "1"
if j > 0:
if rank1[i][j - 1] == "1":
rank[i][j] = "1"
if 0 < j < len(rank) - 1:
if rank1[i][j + 1] == "1":
rank[i][j] = "1"
if 0 < i < len(rank) - 1:
if rank1[i + 1][j] == "1":
rank[i][j] = "1"
days = 0
while True:
spread(rank, rank1)
days += 1
list = [j for i in rank for j in i]
print(list)
if [j for i in rank for j in i].count("1") == length:
return days
temp = rank
rank = rank1
rank1 = temp
if __name__ == '__main__':
print(spread_time("1,0,1,0,0,0,1,0,1"))
print(spread_time("1,1,1,1,1,1,1,1,1"))

所有整数的最小和

1.输入字符串s输出s中包含所有整数的最小和， 说明：1字符串s只包含a~z,A~Z,+,-， 2.合法的整数包括正整数，一个或者多个0-9组成，如：0,2,3,002,102 3.负整数，负号开头，数字部分由一个或者多个0-9组成，如-2,-012,-23,-00023 输入描述：包含数字的字符串 输出描述：所有整数的最小和

输入：
bb1234aa
输出
10
输入：
bb12-34aa
输出：
-31
说明：1+2-(34)=-31

package com.amoscloud.newcoder.easy;
import java.util.Scanner;
public class Main96 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String line = in.nextLine();
in.close();
char[] chars = line.toCharArray();
int sum = 0;
for (int i = 0; i < chars.length; i++) {
char c = chars[i];
if (c == '-') {
i++;
int start = i;
while (i < chars.length && Character.isDigit(chars[i])) {
i++;
}
String substring = line.substring(start, i);
if (substring.length() > 0) {
sum -= Integer.parseInt(substring);
}
i--;
continue;
}
if (Character.isDigit(c)) {
sum += Character.digit(c, 10);
}
}
System.out.println(sum);
}
}

分班

幼儿园两个班的小朋友排队时混在了一起,每个小朋友都知道自己跟前面一个小朋友是不是同班,请你帮忙把同班的小朋友找出来 小朋友的编号为整数与前面一个小朋友同班用Y表示不同班用N表示 输入描述： 输入为空格分开的小朋友编号和是否同班标志 比如 6/N 2/Y 3/N 4/Y 表示一共有4位小朋友 2和6是同班 3和2不同班 4和3同班 小朋友总数不超过999 0< 每个小朋友编号 <999 不考虑输入格式错误 输出两行 每一行记录一班小朋友的编号 编号用空格分开并且

1. 编号需要按照大小升序排列，分班记录中第一个编号小的排在第一行
2. 如果只有一个班的小朋友 第二行为空
3. 如果输入不符合要求输出字符串ERROR

输入
1/N 2/Y 3/N 4/Y
输出
1 2
3 4
说明：2的同班标记为Y因此和1同班
3的同班标记位N因此和1,2不同班
4的同班标记位Y因此和3同班

import java.util.ArrayList;
import java.util.Scanner;
import java.util.TreeSet;
public class Main19 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String[] stus = in.nextLine().split(" ");
in.close();
try {
TreeSet<Integer> c1 = new TreeSet<>();
TreeSet<Integer> c2 = new TreeSet<>();
boolean is1 = true;
for (int i = 0; i < stus.length; i++) {
String[] split = stus[i].split("/");
String id = split[0];
String same = split[1];
if (i == 0) {
c1.add(Integer.parseInt(id));
continue;
}
if ("N".equals(same)) is1 = !is1;
(is1 ? c1 : c2).add(Integer.parseInt(id));
}
StringBuilder b1 = new StringBuilder();
for (Integer id : c1) b1.append(id).append(" ");
if (c2.size() > 0) {
StringBuilder b2 = new StringBuilder();
for (Integer id : c2) b2.append(id).append(" ");
if (c1.first() < c2.first()) {
System.out.println(b1.toString().trim());
System.out.println(b2.toString().trim());
} else {
System.out.println(b2.toString().trim());
System.out.println(b1.toString().trim());
}
} else {
System.out.println(b1.toString().trim());
}
} catch (Exception e) {
System.out.println("ERROR");
}
}
}

括号匹配

给定一个字符串，里边可能包含“()“、”[]“、”{}“三种括号，请编写程序检查该字符串中的括号是否成对出现，且嵌套关系正确。 输出： true：若括号成对出现且嵌套关系正确，或该字符串中无括号字符； false：若未正确使用括号字符。 实现时无需考虑非法输入。

输入描述: 输入：字符串 例子：(1+2)/(0.5+1)

输出描述: 输出：true | false 例子：true

输入
(1+2)/(0.5+1)
输出
True

#![allow(unused)]
fn main() {
pub fn huawei_2016_18() {
use std::collections::VecDeque;
let cs = "(1+2)/(0.5+1)".chars().collect::<Vec<_>>();
let mut stack: VecDeque<char> = VecDeque::new();
for c in cs {
if (c == '(' || c == '{' || c == '[') {
stack.push_back(c);
} else {
if c == ')' {
if stack.back().unwrap() == &'(' {
stack.pop_back();
}
}
if (c == '}') {
if (stack.back().unwrap() == &'{') {
stack.pop_back();
}
}
if (c == ']') {
if (stack.back().unwrap() == &'[') {
stack.pop_back();
}
}
}
}
if (stack.is_empty()) {
println!("true");
} else {
println!("false");
}
}
}

打印机任务

某个打印机根据打印机队列执行打印任务，打印任务分为九个优先级，分别用数字1~9表示，数字越大优先级越高。打印机每次从队列头部取出第一个任务A， 然后检查队列余下任务中有没有比A优先级更高的任务，则将任务A放在队列尾部，否则就执行任务A的打印。请编写一个程序，根据输入的打印队列，编出实 际的打印顺序。

输入样例：
9, 3, 5
输出样例：
0, 2, 1

#![allow(unused)]
fn main() {
pub fn huawei_2017_2() {
pub fn input_vec_num<T>(split_by: &str) -> Vec<T>
where
<T as std::str::FromStr>::Err: std::fmt::Debug,
T: std::str::FromStr,
{
let mut input = String::new();
std::io::stdin().read_line(&mut input).unwrap();
input
.split(split_by)
.filter(|s| !s.is_empty())
.map(|s| s.trim().to_string())
.map(|s| s.parse::<T>().unwrap())
.collect::<Vec<T>>()
}
use std::collections::VecDeque;
fn go_print(q: &VecDeque<i64>, target: i64) -> bool {
if q.is_empty() {
return false;
}
if q.len() == 1 {
return true;
}
for v in q.iter() {
if *v > target {
return false;
}
}
true
}
let max = |v: &VecDeque<i64>| {
let res = v.iter().enumerate().max().unwrap();
(res.0, *res.1)
};
let v = input_vec_num::<i64>(",");
let v = vec![9, 3, 5];
let mut vec = vec![];
for vv in v.iter().enumerate() {
vec.push(vv);
}
vec.sort_by_key(|s| s.1);
vec.reverse();
let res = vec.iter().map(|s| s.0).collect::<Vec<_>>();
println!("{:?}", res);
}
}

平安果

给定一个M行N列的矩阵（M*N个格子），每个格子中放着一定数量的平安果。 你从左上角的各自开始，只能向下或者向右走，目的地是右下角的格子。 每走过一个格子，就把格子上的平安果都收集起来。求你最多能收集到多少平安果。

注意：当经过一个格子时，需要一次性把格子里的平安果都拿走。
限制条件：1<N,M<=50；每个格子里的平安果数量是0到1000（包含0和1000）.
输入描述：
输入包含两部分：
第一行M, N
接下来M行，包含N个平安果数量
输出描述：
一个整数
最多拿走的平安果的数量
示例：
输入
2 4
1 2 3 40
6 7 8 90
输出
136

#![allow(unused)]
fn main() {
pub fn huawei_2017_3() {
pub fn input_vec_num<T>(split_by: &str) -> Vec<T>
where
<T as std::str::FromStr>::Err: std::fmt::Debug,
T: std::str::FromStr,
{
let mut input = String::new();
std::io::stdin().read_line(&mut input).unwrap();
input
.trim()
.split(split_by)
.filter(|s| !s.is_empty())
.map(|s| s.trim().to_string())
.map(|s| s.parse::<T>().unwrap())
.collect::<Vec<T>>()
}
let v = input_vec_num::<usize>(" ");
let n = v.get(0).unwrap().to_owned();
let m = v.get(1).unwrap().to_owned();
let mut nums = vec![];
for _ in 0..n {
nums.push(input_vec_num::<usize>(" "));
}
fn get_max(num: Vec<Vec<usize>>) -> usize {
let mut row = num.len();
let mut col = num[0].len();
let mut dp = (0..row)
.into_iter()
.map(|_| vec![0; col])
.collect::<Vec<_>>();
for i in 0..row {
for j in 0..=i {
dp[i][0] += num[j][0];
}
}
for i in 0..col {
for j in 0..=i {
dp[0][i] += num[0][j];
}
}
use std::cmp::max;
for i in 1..row {
for j in 1..col {
dp[i][j] = max(dp[i][j - 1] + num[i][j], dp[i - 1][j] + num[i][j]);
}
}
println!("{:?}", dp);
return dp[row - 1][col - 1];
}
// println!("{:?}", nums);
println!("{}", get_max(nums));
}
}

华为OD机考：素数之积

RSA加密算法在网络安全世界中无处不在，它利用了极大整数因数分解的困难度，数据越大，安全系数越高，给定一个32位正整数，请对其进行因数分解，找出是哪 两个素数的乘积。 PS:示例 n=1*n，不符合题意。1不是素数

#![allow(unused)]
fn main() {
pub fn huawei_2017_4() {
pub fn input_num<T>() -> T
where
<T as std::str::FromStr>::Err: std::fmt::Debug,
T: std::str::FromStr,
{
let mut input = String::new();
std::io::stdin().read_line(&mut input).unwrap();
input.trim().to_string().parse::<T>().unwrap()
}
pub fn is_prime(p: i32) -> bool {
p >= 2 && (2..).take_while(|q| q * q <= p).all(|q| p % q != 0)
}
let mut a = -1;
let mut b = -1;
let num = input_num::<i32>();
for i in 2..=f64::sqrt(num as f64) as i32 {
if is_prime(i) {
if num % i == 0 {
if is_prime(num / i) {
a = i;
b = num / i;
}
}
}
}
println!("{} {}", a, b);
}
}

数字字符串组合倒序

对数字，字符，数字串，字符串，以及数字与字符串组合进行倒序排列。 符号的定义 1.作为连接符使用时作为字符串的一部分，例如“20-years”作为一个整体字符串呈现； 2.连续出现 2 个’及以上时视为字符串间隔符，如“out–standing”中的”–“视为间隔符，是 2 个独立整体字符串”out”和”standing”； 3.除了 1，2 里面定义的字符以外其他的所有字符，都是非法字符，作为字符串的间隔符处理，倒序后间隔符作为空格处理； 4.要求倒排后的单词间隔符以一个空格表示；如果有多个间隔符时，倒排转换后也只允许出现一个字格间隔符：

in:I am an 20-years out--standing @ * -stu- dent
out:['dent', 'stu', 'standing', 'out', '20-years', 'an', 'am', 'I']

import re
s = input().strip()
pattern = re.compile("[a-zA-Z0-9-]+")
res = pattern.findall(s)
# print(res)
new_s = []
for i in res:
if "--" in i:
temp = i.split("--")
for j in temp:
new_s.append(j.strip("-"))
else:
new_s.append(i.strip("-"))
print(new_s[::-1])

俄罗斯套娃信封问题(动态规划)

给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。 当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。 请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。 注意：不允许旋转信封。

输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出：3
解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。
示例 2：
输入：envelopes = [[1,1],[1,1],[1,1]]
输出：1

#![allow(unused)]
fn main() {
impl Solution {
pub fn max_envelopes(nums: Vec<Vec<i32>>) -> i32 {
let mut nums = nums.clone();
nums.sort_unstable_by(|a, b| {
a[0].partial_cmp(&b[0])
.unwrap()
.then(b[1].partial_cmp(&a[1]).unwrap())
});
let mut sub = vec![];
for envelope in &nums {
let (_, h) = (envelope[0], envelope[1]);
let i = sub.binary_search(&h);
let i = match i {
Ok(i) => i,
Err(i) => i,
};
if i == sub.len() {
sub.push(h);
} else {
sub[i] = h;
}
}
sub.len() as i32
}
}
}

叠积木(动态规划)

给出一个列表如[[6,7,],[5,4],[3,2]],表示木块的长和宽，当木块的长和宽不大于另个木块的长和宽时，就可以放在上面，此外数组还可以左右翻转。求最多能搭多少层。 输入描述 一个二维数组，里面是每个积木的长和宽，可以左右翻转 输出描述 最多能搭多少层

#![allow(unused)]
fn main() {
pub fn huawei_2016_19() {
pub fn input_vec_string() -> Vec<Vec<i32>> {
let mut input = String::new();
std::io::stdin().read_line(&mut input).unwrap();
input
.trim()
.replace("[[", "")
.replace("]]", "")
.split("],")
.filter(|s| !s.is_empty())
.map(|s| s.trim().to_string())
.map(|s| s.to_string().replace("[", ""))
.map(|s| {
s.split(",")
.filter(|s| !s.is_empty())
.map(|s| s.trim().to_string())
.map(|s| s.parse::<i32>().unwrap())
.collect::<Vec<_>>()
})
.collect::<Vec<_>>()
}
let numss = input_vec_string();
let mut nums = (0..numss.len())
.into_iter()
.map(|_| vec![0; numss[0].len()])
.collect::<Vec<_>>();
use std::cmp::max;
use std::cmp::min;
for i in 0..nums.len() {
let num1 = numss[i][0];
let num2 = numss[i][1];
nums[i][0] = max(num1, num2); // 大的为长度
nums[i][1] = min(num1, num2); // 小的为宽度
}
nums.sort_by_key(|s| s[0] * s[1]);
println!("{:?}", nums);
let mut sub = vec![];
for envelope in &nums {
let (_, h) = (envelope[0], envelope[1]);
let i = sub.binary_search(&h);
let i = match i {
Ok(i) => i,
Err(i) => i,
};
if i == sub.len() {
sub.push(h);
} else {
sub[i] = h;
}
}
println!("{:?}", sub.len() + 1);
}
}

IPv4地址转换成整数

存在一种虚拟IPv4地址，由4小节组成，每节的范围为0~128，以#号间隔，格式如下： (1~128)#(0~255)#(0~255)#(0~255) 请利用这个特性把虚拟IPv4地址转换为一个32位的整数，IPv4地址以字符串形式给出，要求每个IPvV4地址只能对应到唯一的整数上。 如果是非法IPv4，返回invalid IP。

#![allow(unused)]
fn main() {
pub fn huawei_2016_21() {
pub fn input_vec_num<T>(split_by: &str) -> Vec<T>
where
<T as std::str::FromStr>::Err: std::fmt::Debug,
T: std::str::FromStr,
{
let mut input = String::new();
std::io::stdin().read_line(&mut input).unwrap();
input
.split(split_by)
.map(|s| s.trim().to_string())
.filter(|s| !s.is_empty())
.map(|s| s.trim().to_string())
.map(|s| s.parse::<T>().unwrap())
.collect::<Vec<T>>()
}
fn binary_to_decimal(num: &str) -> Option<i64> {
if num.len() == 0 {
return None;
}
let mut sum = 0;
let vec = num
.chars()
.map(|x| i64::from(x.to_digit(10).unwrap()))
.collect::<Vec<i64>>();
for (index, item) in vec.iter().rev().enumerate() {
sum += i64::pow(2, index as u32) * item;
}
Some(sum)
}
let ip = input_vec_num::<i64>("#");
if ip.len() < 3 {
println!("invalid IP");
}
fn ip_to_int(ip: Vec<i64>) {
let mut ipb = String::new();
for i in ip.iter() {
let s = format!("{:8b}", i).replace(" ", "0");
ipb.push_str(&s);
}
println!("{}", binary_to_decimal(&ipb).unwrap());
}
ip_to_int(ip);
//in:100#101#1#5
//out:1684340997
}
}

HJ21 简单密码

现在有一种密码变换算法。 九键手机键盘上的数字与字母的对应： 1–1， abc–2, def–3, ghi–4, jkl–5, mno–6, pqrs–7, tuv–8 wxyz–9, 0–0，把密码中出现的小写字母都变成九键键盘对应的数字，如：a 变成 2，x 变成 9. 而密码中出现的大写字母则变成小写之后往后移一位，如：X ，先变成小写，再往后移一位，变成了 y ，例外：Z 往后移是 a 。 数字和其它的符号都不做变换。 数据范围： 输入的字符串长度满足 \1≤n≤100 输入描述： 输入一组密码，长度不超过100个字符。 输出描述： 输出密码变换后的字符串

示例1
输入：
YUANzhi1987
复制
输出：
zvbo9441987

pub fn huawei_2016_23() {
pub fn input_vec_string(split_by: &str) -> Vec<String> {
let mut input = String::new();
std::io::stdin().read_line(&mut input).unwrap();
input
.trim()
.split(split_by)
.filter(|s| !s.is_empty())
.map(|s| s.trim().to_string())
.map(|s| s.to_string())
.collect::<Vec<String>>()
}
let mut a = input_vec_string("");
let key = vec![
("abc", 2),
("def", 3),
("ghi", 4),
("jkl", 5),
("mno", 6),
("pqrs", 7),
("tuv", 8),
("wxyz", 9),
];
for (i, aa) in a.iter_mut().enumerate() {
for k in key.iter() {
if k.0.contains(&aa.to_string()) {
aa.clear();
aa.push_str(&k.1.to_string());
}
}
let aa_char = *aa.chars().collect::<Vec<_>>().first().unwrap() as u8;
if aa_char > 65 && aa_char < 90 {
let new_aa_char = aa_char + 33;
aa.clear();
aa.push(new_aa_char as char);
} else if aa_char == 65 {
let new_aa_char = 98_u8;
aa.clear();
aa.push(new_aa_char as char);
} else if aa_char == 90 {
let new_aa_char = 97_u8;
aa.clear();
aa.push(new_aa_char as char);
}
}
println!("{}", a.join(""));
}
fn main(){
huawei_2016_23();
}