2022-05 牛客在线编程学习记录
编程语言Swift,仅做个人学习记录，并不对正确性及其他任何情况负责。
1、跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
数据范围：1≤n≤401 \leq n \leq 401≤n≤40
要求：时间复杂度：O(n)O(n)O(n) ，空间复杂度： O(1)O(1)O(1)
如果用递归 这里n越大就会越慢 用迭代(循环)最块
func jumpFloor (_ number : Int) -> Int {
var a = 1
var b = 1
if number < 2 {
return number
}
for _ in 2...number {
let c = a
a = b
b = a + c
}
return b;
}
print(jumpFloor(7)) /// 21
2、牛牛与三角形
给定n个数，返回在所有合法的三角形的组成中，周长最大的三角形的周长减去周长最小的三角形的周长的值。
题目保证每组测试数据中都存在有三个数可以构成三角形，保证答案在int范围内。
时间限制：C/C++ 5秒，其他语言10秒 空间限制：C/C++ 256M，其他语言512M
依次找到最大三角形和最小三角形 最大三角形即倒序遍历
最小三角形则较为麻烦
func formTriangle (_ n: Int, _ a: [Int]) -> Int {
var arr : Array = a;
arr.sort(by: <)
/// 先找最大 判断第一个满足arr[i] < arr[i-1] + arr[i-2]
var maxV = 0;
for i in (2..<arr.count).reversed() {
if arr[i-1] + arr[i-2] > arr[i] {
maxV = arr[i] + arr[i-1] + arr[i-2]
break
}
}
/// 再找最小 从第1个开始遍历直到倒数第二h个
/// 依次将i + x(找到的值) 与 i+1的值进行比较 直到找到最小的值满足 x + i > i+1 并与每一轮找到的最小周长进行对比得到最小值
var minV = Int.max
for i in 1..<arr.count-1 {
let b = arr[i]
let c = arr[i+1]
var left = 0
var right = i
while left < right {
let mid = left + (right - left) / 2
if arr[mid] + b > c {
right = mid
} else {
left = mid + 1
}
}
if left < i && arr[left] + b > c {
minV = min(minV, arr[left] + b + c)
}
}
return maxV - minV
}
print(formTriangle(10,[9,7,7,6,1,9,1,1,10,1])) /// 25
3、名字的漂亮度
给出一个字符串，该字符串仅由小写字母组成，定义这个字符串的“漂亮度”是其所有字母“漂亮度”的总和。
每个字母都有一个“漂亮度”，范围在1到26之间。没有任何两个不同字母拥有相同的“漂亮度”。字母忽略大小写。
给出多个字符串，计算每个字符串最大可能的“漂亮度”。
本题含有多组数据。
数据范围：输入的名字长度满足 1≤n≤10000 1 \le n \le 10000 \ 1≤n≤10000
统计各个字符的出现次数 然后从大到小排序 然后计算结果即可
import Foundation
let num = Int(readLine() ?? "") ?? 0
var strArr: [String] = []
for _ in 0..<num {
strArr.append(readLine() ?? "")
}
func maxDegreeOfStr(_ str: String) -> Int {
var degree = 0
var dict = [Character : Int]()
for c in str {
if let count = dict[c] {
dict[c] = count + 1
} else {
dict[c] = 1
}
}
let times = dict.map{ $0.value }.sorted(by: >);
var singleDegree = 26
for t in times {
degree += t * singleDegree
singleDegree -= 1
}
return degree
}
4、连续子数组的最大和
输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为1。求所有子数组的和的最大值。
要求:时间复杂度为 O(n)，空间复杂度为 O(n)
进阶:时间复杂度为 O(n)，空间复杂度为 O(1)
动态规划 创建一个相同长度的数组 依次与前面的值相加 并存储结果 其中最大值即为解
import Foundation
let line = readLine() ?? ""
let strArr = line.split(separator: ",")
let numArr = strArr.map{Int($0) ?? 0}
func FindGreatestSumOfSubArray ( _ array: [Int]) -> Int {
var dynamicArr = Array.init(repeating: 0, count: array.count);
if array.count == 1 {
return array[0]
}
dynamicArr[0] = array[0];
var maxValue = dynamicArr[0];
for i in 1..<array.count {
dynamicArr[i] = max(dynamicArr[i-1] + array[i], array[i])
maxValue = max(maxValue, dynamicArr[i])
}
return maxValue
}
print(FindGreatestSumOfSubArray(numArr))
5、字符串变形
对于一个长度为 n 字符串，我们需要对它做一些变形。
首先这个字符串中包含着一些空格，就像"Hello World"一样，然后我们要做的是把这个字符串中由空格隔开的单词反序，同时反转每个字符的大小写。
比如"Hello World"变形后就变成了"wORLD hELLO"。
数据范围: 1≤n≤1061\le n \le 10^61≤n≤106 , 字符串中包括大写英文字母、小写英文字母、空格。
进阶：空间复杂度 O(n)O(n)O(n) ， 时间复杂度 O(n)O(n)O(n)
输入描述：
给定一个字符串s以及它的长度n(1 ≤ n ≤ 10^6)
返回值描述：
请返回变形后的字符串。题目保证给定的字符串均由大小写字母和空格构成。
先全部反转 然后找到对应的单词再次翻转 单次遍历大写转小写 小写转大写即可
不可以直接以空格分割数组反转拼接（忽略了连续空格的情况）
import Foundation
let string = readLine() ?? ""
let length = Int(readLine() ?? "") ?? 0
func trans(_ string: String, _ length: Int) -> String {
if length == 0 {
return string
}
let newStr = String(string.reversed())
var startIndex = newStr.startIndex
let endIndex = newStr.endIndex
var formatStr = String()
while let spaceIndex = newStr[startIndex..<endIndex].firstIndex(of: " ") {
formatStr.append(String(newStr[startIndex..<spaceIndex].reversed()) + " ")
startIndex = newStr.index(after: spaceIndex)
}
formatStr.append(String(newStr[startIndex..<endIndex].reversed()))
var finalStr = String()
for str in formatStr {
if str != " " && str >= "A" && str <= "Z" {
finalStr.append(str.lowercased())
} else if str != " " && str >= "a" && str <= "z" {
finalStr.append(str.uppercased())
} else {
finalStr.append(str);
}
}
return finalStr
}
print(trans(string, length))
压栈的思想
func trans(_ s: String, _ n: Int) -> String {
var stack: [String] = []
var str = ""
let s = s + " " // 原字符串默认加" "，避免for循环最后的特别处理
for c in s {
// 以空格为分隔符，区分单词进行压栈
if c == " " {
stack.append(str)
str = ""
} else {
// 识别大小写字母，逐一转换
if c.isLowercase {
str.append(c.uppercased())
} else {
str.append(c.lowercased())
}
}
}
var res = ""
while !stack.isEmpty {
res.append(stack.removeLast() + " ")
}
// 去除最后一个单词后的空格
res.removeLast()
return res
}
6、顺时针打印矩阵
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字
数据范围:
0 <= matrix.length <= 100
0 <= matrix[i].length <= 100
确定边界，以及注意循环结束条件，按照打印顺序走即可
func printMatrix ( _ matrix: [[Int]]) -> [Int] {
var direction = 0;
var result = [Int]()
let i = matrix.count
let j = matrix.first!.count
var left = 0, right = j-1, top = 0, bottom = i-1
while top <= bottom && left <= right {
switch direction {
case 0:
for item in left...right {
result.append(matrix[top][item])
}
top += 1
case 1:
for section in top...bottom {
result.append(matrix[section][right])
}
right -= 1
case 2:
for item in (left...right).reversed() {
result.append(matrix[bottom][item])
}
bottom -= 1
case 3:
for section in (top...bottom).reversed() {
result.append(matrix[section][left])
}
left += 1
default:
break
}
direction += 1
direction = direction % 4
}
return result
}
7、二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
- 对于该题的最近的公共祖先定义:对于有根树T的两个节点p、q，最近公共祖先LCA(T,p,q)表示一个节点x，满足x是p和q的祖先且x的深度尽可能大。在这里，一个节点也可以是它自己的祖先.
- 二叉搜索树是若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值； 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值
- 所有节点的值都是唯一的。
- p、q 为不同节点且均存在于给定的二叉搜索树中。
数据范围:
3<=节点总数<=10000
0<=节点值<=10000
如果给定以下搜索二叉树: {7,1,12,0,4,11,14,#,#,3,5}，如下图:
二叉树.png
func lowestCommonAncestor ( _ root: TreeNode?, _ p: Int, _ q: Int) -> Int {
return process(root, p, q)!.val
}
func process(_ root: TreeNode?, _ p: Int, _ q: Int) -> TreeNode? {
if root == nil || root!.val == p || root!.val == q {
return root
}
let val = root!.val
if val < p && val < q {
return process(root!.right, p, q)
} else if val > p && val > q {
return process(root!.left, p, q)
} else {
return root
}
}
8、取近似值
写出一个程序，接受一个正浮点数值，输出该数值的近似整数值。如果小数点后数值大于等于 0.5 ,向上取整；小于 0.5 ，则向下取整。
数据范围：保证输入的数字在 32 位浮点数范围内
加0.5取整即可
import Foundation
let input = Double(readLine() ?? "") ?? 0
print(Int(input + 0.5))
9、截取字符串
输入一个字符串和一个整数 k ，截取字符串的前k个字符并输出
使用现成的系统方法即可
let line = readLine() ?? ""
let cutNum = Int(readLine() ?? "") ?? 0
print(line.substring(to: line.index(line.startIndex, offsetBy: cutNum)))
10、输入n个整数，输出其中最小的k个
输入n个整数，找出其中最小的k个整数并按升序输出
let arr1 = (readLine() ?? "").components(separatedBy: " ")
let totalNum = Int(arr1.first!) ?? 0
let outputNum = Int(arr1.last!) ?? 0
let numStrArr = (readLine() ?? "").components(separatedBy: " ")
var numArr = [Int]()
for item in numStrArr {
numArr.append(Int(item) ?? 0)
}
let result = numArr.sorted(by: <)
if outputNum < totalNum && totalNum == result.count {
for num in 0..<outputNum {
print(result[num], terminator: " ")
}
} else {
print("out of Range")
}
11、 输入整型数组和排序标识，对其元素按照升序或降序进行排序
输入整型数组和排序标识，对其元素按照升序或降序进行排序
根据输入调用排序函数即可
let totalNum = Int(readLine() ?? "")
let numArr = (readLine() ?? "").components(separatedBy: " ")
let desc = Int(readLine() ?? "")
var handleArr = [Int]()
numArr.forEach({ item in
handleArr.append(Int(item) ?? 0)
})
if desc == 1 {
handleArr.sorted(by: >).forEach { num in
print(num, terminator: " ")
}
} else {
handleArr.sorted(by: <).forEach { num in
print(num, terminator: " ")
}
}
12、字符串最后一个单词的长度
计算字符串最后一个单词的长度，单词以空格隔开，字符串长度小于5000
（注：字符串末尾不以空格为结尾）
let strArray = (readLine() ?? "").components(separatedBy: " ")
let lastStrCount = strArray.last?.count ?? 0
print(lastStrCount)
13、 计算某字符出现次数
写出一个程序，接受一个由字母、数字和空格组成的字符串，和一个字符，然后输出输入字符串中该字符的出现次数。（不区分大小写字母）
因为不区分大小写，所以全部转为小写，然后循环一次 使用字典，以字符为键保存出现次数 最后根据字符获取对应的次数即可 （也可只保存目标字符串数量，其他字符忽略）
let inputStr = readLine() ?? ""
let char = Character((readLine() ?? "").lowercased())
var charDic = [Character : Int]()
inputStr.lowercased().forEach { str in
if charDic.keys.contains(str) {
charDic[str]! += 1;
} else {
charDic[str] = 1;
}
}
print(charDic[char] ?? 0)
