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、二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

  1. 对于该题的最近的公共祖先定义:对于有根树T的两个节点p、q,最近公共祖先LCA(T,p,q)表示一个节点x,满足x是p和q的祖先且x的深度尽可能大。在这里,一个节点也可以是它自己的祖先.
  2. 二叉搜索树是若它的左子树不空,则左子树上所有节点的值均小于它的根节点的值; 若它的右子树不空,则右子树上所有节点的值均大于它的根节点的值
  3. 所有节点的值都是唯一的。
  4. 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)
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 203,324评论 5 476
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,303评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 150,192评论 0 337
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,555评论 1 273
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,569评论 5 365
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,566评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,927评论 3 395
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,583评论 0 257
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,827评论 1 297
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,590评论 2 320
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,669评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,365评论 4 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,941评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,928评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,159评论 1 259
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,880评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,399评论 2 342

推荐阅读更多精彩内容