程序员进阶之算法练习(一)

前言

可能很多移动端编程的同学听到算法就感到恐惧,认为我不会算法也能开发呀。确实,不会算法,也能应对一般的工作。但是和大牛之间的差距就是,可能别人3行代码实现的东西,你却要写10多行,并且性能比别人差。那么,让我们来学习一些算法吧。

算法学习

算法的学习最简单的方式就是多练习,找一个提供算法练习的网站,思考,编码,验证,最后再看看别人的思路。 本系列的题目来自LeetCode。IDE采用的Xcode,笔者使用的是swift

(ps:以下练习中代码实现部分并不是唯一解答方法,仅供参考)

Two Sum

题目链接 题目大意:给定一个整数数组,找出满足两个数字相加 等于 目标数的两个数字的索引,并且返回。 例如:

nums = [2, 7, 11, 15], target = 9 , 因为 nums[0] + nums[1] = target, 所以 return [0, 1]

代码实现:

func twoSum(_ nums:[Int], _ target:Int) -> [Int]? {
    var d = [Int: Int]()
    
    for (i, num) in nums.enumerated(){
        if let sum = d[target - num] {
            return [sum, i]
        }else{
            d[num] = i
        }
    }
    return nil
}

Add Two Numbers

题目链接 题目大意:使用链表实现两个数字相加

例如:

12 + 13 = 25

代码实现:

public class ListNode {
    public var val: Int
    public var next: ListNode?
    public init(_ val: Int) {
        self.val = val
        self.next = nil
    }
}

public class Solution {
    func addTwoNumbers(_ l1:ListNode?, _ l2:ListNode?) -> ListNode? {
        return helper(l1, l2, 0)
    }
    
    func helper(_ l1:ListNode?, _ l2:ListNode?, _ carry: Int) -> ListNode? {
        var p = l1
        var q = l2
        
        if p == nil && q == nil {
            return carry == 0 ? nil: ListNode(carry)
        }
        
        if p == nil && q != nil {
            p = ListNode(0)
        }
        
        if p != nil && q == nil {
            q = ListNode(0)
        }
        
        let sum = (p?.val)! + (q?.val)! + carry
        let curr = ListNode(sum % 10)
        curr.next = helper(p?.next, q?.next, sum/10)
        return curr
    }
}

var l1:ListNode?
var l2:ListNode?

l1 = ListNode(12)
l2 = ListNode(13)

let s = Solution()
let result1 = s.addTwoNumbers(l1, l2)

思路:

按照小学加法原理,从末尾对齐相加,满十进位。技巧在于如何处理不同长度的两个数字,以及进位和最高位的判断。这里对于不同长度的数字,我们通过在较短的数字前面添加零来保证每一位都能相加。主要分为以下3个要点:

  • 全部为nil时,返回进位值;
  • 有一个为nil时,返回不为nil的那个ListNode和进位值相加的结果;
  • 都不为nil时,返回两个ListNode和进位值相加的结果。

Longest Substring Without Repeating Characters

题目链接

题目大意:给定一个字符串,找出其中最长的没有出现重复字符的连续子串的长度。 例如:

"abcabcbb" 最长的不重复字符子串是"abc",长度为3; "bbbbb" 最长的不重复字符子串是"b",长度为1; "pwwkew" 最长的不重复字符子串是"wke",长度为3;

代码实现:

func lengthOfLongestSubstring(_ s:String) -> Int {
    if s.isEmpty {
        return 0
    }
    
    var map = [Character: Int]()
    var result = 0
    var j = 0
    
    for (i, charactor) in s.characters.enumerated() {
        if map.keys.contains(charactor) {
            j = max(j, map[charactor]! + 1)
        }
        
        map[charactor] = i
        result = max(result, i-j+1)
    }
    
    return result
}

思路:

本题目主要有3个注意点:

  1. 最长的;
  2. 连续的;
  3. 没有重复的字符;

致谢

如果发现有错误的地方,欢迎各位指出,谢谢!

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小筱月

各种排序算法

冒泡排序还有一种优化算法,就是立一个flag,当在一趟序列遍历中元素没有发生交换,则证明该序列已经有序

1433
来自专栏zaking's

js算法初窥02(排序算法02-归并、快速以及堆排序)

1713
来自专栏Java面试通关手册

精研3道简单的网易2018校招编程题

下面三道编程题来自网易2018校招编程题,这三道应该来说是非常简单的编程题了,这些题目大家稍微有点编程和数学基础的话应该没什么问题。看答案之前一定要自己先想一下...

1956
来自专栏专注数据中心高性能网络技术研发

[LeetCode]LinkedList主题系列{第2题}

1.内容介绍 本篇文章记录在leetcode中LinkedList主题下面的题目和自己的思考以及优化过程,具体内容层次按照{题目,分析,初解,初解结果,优化解,...

2718
来自专栏武军超python专栏

2018年7月25日python中面向对象编程的练习

今天遇到的新单词: parameter  n参数 IndentationError  n缩进错误 formatting n格式化

3584
来自专栏数据魔术师

基础算法| 常用排序算法小结

日常吹水 说到这个算法, 可能瞬间大家就觉得那些灰机昏膏素什么的比这个生动活泼多了。 那么,正走在算法之路上的你, 是否还在苦苦寻求修仙之路? 是否被各种排序...

3295
来自专栏blackheart的专栏

[程序设计语言]-[核心概念]-03:控制流

0.概述 前面介绍了语言的演进以及一些基础概念后,从本篇开始进入了语言的核心问题中。这一篇讨论的是语言计算模型(大致可以用控制流来表述),大致如下7种: 顺序执...

20910
来自专栏Scott_Mr 个人专栏

程序员进阶之算法练习(一)

3486
来自专栏牛客网

校招面试手撕算法汇总

所有题目都是从面经中提取而来,持续更新。 本人也是菜鸟一枚,帖子也会相应的发布自己对于题目的解法和看法,但是可能想得不够,也希望大家能够一起讨论,一起进步。 1...

39511
来自专栏斑斓

函数式非凡的抽象能力

如果说面向对象思想是物质世界的哲学观,则函数式思想展现的就是纯粹的数学思维了。函数作为一等公民,它不代表任何物质(对象),而仅仅代表一种转换行为。是的,任何一个...

3375

扫码关注云+社区

领取腾讯云代金券