每次电脑连接校园网都需要输入密码。甚至有时电脑无法自动弹出上网登录界面。因而希望做一个脚本来实现自动登录。

校园网上网原理

设备模仿目标服务器向客户端发送HTTP Redirect,将客户浏览器重定向到一个预先指定的Web服务器。在这个Web服务器的页面上,用户输入账号密码等信息,后台认证通过后,该服务器会向前述设备发送认证通过消息,该设备会建立认证通过表项。下一次客户Internet(不仅仅HTTP,所有)请求过来的时候,查表找到表项后,正常转发。客户即可正常上网了。

相关知识

  • request库

    • Python中可以实现简单的HTTP的模块

    • 基本GET请求

      1
      2
      3
      4
      5
      import requests

      response = requests.get("http://httpbin.org/get")
      # text输出文本内容
      print(response.text)
  • POST请求和GET请求

    • GET请求和POST请求区别在于前者通常是通过url地址,而后者常见的则是form表单请求
  • Tkinter库

    • Python中可以实现简单窗口视窗设计的模块

    • 创建并显示视窗基本写法

      1
      2
      3
      import tkinter as tk  # 在代码里面导入库,起一个别名,以后代码里面就用这个别名
      root = tk.Tk() # 这个库里面有Tk()这个方法,这个方法的作用就是创建一个窗口
      root.mainloop() # 加上这一句,就可以看见窗口了,循环显示窗口

解决方案

安徽大学校园网登录方式为GET请求。IP会随着位置的不同而可能重新分配。

  • 方案一

    • 将下列代码写入html文件并加入开机自启动计划中。

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      <!DOCTYPE html>
      <html lang="en">
      <head>
      <meta charset="UTF-8">
      <meta name="viewport" content="width=, initial-scale=1.0">
      <title>Document</title>
      </head>
      <body>
      <script>
      onload = function(){
      window.open("url", "_self") # url为请求网址
      }
      </script>
      </body>
      </html>
    • 不足:

      • 无法识别当前IP地址,不适用于因为校园内地理位置的改变而改变IP地址的情况。
      • 仅开机时html文件会运行,仅适用于电脑开机时连接校园网情况,不满足连接WiFi时自动输入账号密码的实际需求。
  • 方案二

    • python代码如下:

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      60
      61
      62
      63
      64
      import requests
      import socket
      import re
      import tkinter as tk
      from tkinter import font


      def login(ip, url_cmcc, url):

      url = re.sub(r'\d+\.\d+\.\d+\.\d+&', ip + '&', url, 1)
      url_cmcc = re.sub(r'\d+\.\d+\.\d+\.\d+&', ip + '&', url_cmcc, 1)
      res_cmcc = requests.get(url_cmcc)
      if '"msg":""' in res_cmcc.text:
      res = requests.get(url)
      login_gui(ip, res.text, 0)
      else:
      login_gui(ip, res_cmcc.text, 1)


      def get_ip():
      try:
      s = socket.socket(socket.AF_INET, socket.SOCK_DGRAM)
      s.connect(('8.8.8.8', 80))
      ip = s.getsockname()[0]
      finally:
      s.close()
      return ip


      def login_gui(ip, text, model):

      if model == 1:
      mod = 'cmcc登录'
      else:
      mod = '普通登录'

      root = tk.Tk()
      root.title('校园网登录')
      var = tk.StringVar()
      if '"msg":""' in text:
      var.set('当前设备已登录\nip地址:%s\n%s' % (ip, mod))
      elif r'\u8ba4\u8bc1\u6210\u529f' in text:
      var.set('登录成功\nip地址:%s\n%s' % (ip, mod))
      elif 'bGRhcCBhdXRoIGVycm9y' in text:
      var.set('密码错误\nip地址:%s\n%s' % (ip, mod))
      elif 'aW51c2UsIGxvZ2luIGFnYWluL' in text:
      var.set('其他设备已登录\nip地址:%s\n%s' % (ip, mod))
      else:
      var.set('您可能欠费停机\nip地址:%s\n%s' % (ip, mod))
      lab = tk.Label(root, textvariable=var, font=('Courier', 15), width=20, height=20)
      lab.pack() # 把标签置入root界面布局
      root.geometry("300x200+600+300") # 将窗口移动到新位置(宽度为400,高度为300,上边距为100,左边距为100)
      root.mainloop()


      def main():
      url_cmcc = ''
      url = ''
      ip = get_ip()
      login(ip, url_cmcc, url)


      if __name__ == '__main__':
      main()
    • 可以改进的地方:

      • 可设置自动获取url来保存各个位置的wlan_ac_ip进而便捷地在校园任何地方都能自动连接校园网

      • 可以进一步完善代码关于账号和密码输入部分以便于校园内同学使用

    • 可利用pyinstaller对文件进行打包

      • pyinstaller -F -w main.py

拓展

基本概念

  • 数据:数据是信息的载体,是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据是计算机程序加工的原料。

  • 数据元素、数据项:数据元素是数据的基本单位,通常作为一个整体进行考虑和处理。一个数据元素可由若干数据项组成,数据项是构成数据元素的不可分割的最小单位。

  • 数据结构:相互之间存在一种或多种特定关系的数据元素的集合。

  • 数据对象:具有相同性质的数据元素的集合,是数据的一个子集。

  • 数据类型:一个值的集合和定义在此集合上的一组操作的总称。

    • 原子类型。其值不可再分的数据类型。
    • 结构类型。其值可以再分解为若干成分(分量)的数据类型。
  • 抽象数据类型(Abstract Data Type, ADT):抽象数据组织及与之相关的操作。

    • 原子类型。其值不可分解。
    • 固定聚合类型。其值由确定数目的成分按某种结构组成。
    • 可变聚合类型。其值的成分数目不确定。
  • 多形数据类型:其值的成分不确定的数据类型。

三要素

  • 逻辑结构
    • 集合:各个元素同属一个集合,别无其他关系。
    • 线性结构:数据元素之间是一对一的关系。除了第一个元素,所有元素都有唯一前驱,除了最后一个元素,所有元素都有唯一后继。
    • 树性结构:数据元素之间是一对多的关系。
    • 图状结构(网状结构):数据元素之间是多对多的关系。
  • 物理结构(存储结构)
    • 顺序存储:把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中,元素之间的关系由存储单元的邻接关系来体现。
      • 若采用顺序存储,则各个数据元素在物理上必须是连续的;若采用非顺序存储,则各个数据元素在物理上可以是离散的
      • 数据的存储结构影响存储空间分配的方便程度
      • 数据的存储结构影响对数据运算的速度
    • 链式存储:逻辑上相邻的元素在物理位置上可以不相邻,借助指示元素存储地址的指针来表示元素之间的逻辑关系。
    • 索引存储:在存储元素信息的同时,还建立附加的索引表。索引表中的每项称为索引项,索引项的一般形式是(关键字,地址)。
    • 散列存储:根据元素的关键字直接计算出该元素的存储地址,又称哈希(Hash)存储
  • 数据的运算
    • 施加在数据上的运算包括运算的定义和实现。
    • 运算的定义针对逻辑结构的,指出运算的功能。
    • 运算的实现针对存储结构的,指出运算的具体操作步骤。

算法的基本概念

  • 算法(Algorithm)对特定问题求解步骤的一种描述,它是指令的有限序列,其中的每条指令表示一个或多个操作。
  • 算法的特性
    • 有穷性。一个算法必须总在执行有穷步后结束,且每一步都可在有穷时间内完成。
      • 算法必须是有穷的,而程序可以是无穷的。
    • 确定性。算法中每条指令必须有确切的含义,对于相同的输入只能得出相同的输出
    • 可行性。算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
    • 输入。一个算法有零个或多个输入,这些输入取自于某个特定的对象的集合。
    • 输出。一个算法有一个或多个输出,这些输出是与输入有某种特定关系的量。
  • “好”算法的特质:
    • 正确性。算法应能正确地求解问题。
    • 可读性。算法应具有良好的可读性,以帮助人们理解。
    • 健壮性。输入非法数据时,算法能适当地做出反应或进行处理,而不会产生莫名其妙的输出结果。
    • 高效率低存储量需求
      • 高效率:花的时间少。时间复杂度低。
      • 低存储量需求:不费内存。空间复杂度低。

算法效率的度量

算法的时间复杂度

  • 事先预估算法时间开销T(n)问题规模n的关系(T表示”time”)。
  • 在T(n)中可以只考虑阶数高的部分。
  • 大O表示“同阶”,同等数量级。即:当n趋近于无穷大时,二者之比为常数。
  • 加法规则:T(n) = T1(n)+T2(n) = O(f(n)) + O(g(n)) = O(max(f(n), g(n)))
  • 乘法规则:T(n) = T1(n) * T2(n) = O(f(n)) * O(g(n)) = O(f(n) * g(n))
  • O(n) < O(log2n) < O(n) < O(nlog2n) <O(n^2^) < O(n^3^) < O(2^n^) < O(n!) < O(n^n^)
  • 顺序执行的代码只会影响常数项,可以忽略。只需挑循环中的一个基本操作分析它的执行次数与n的关系即可。如果有多层嵌套循环,只需关注最深层循环循环了几次。
  • 最坏时间复杂度:最坏情况下算法的时间复杂度。
  • 平均时间复杂度:所有输入示例等概率出现的情况下,算法的期望运行时间。
  • 最好时间复杂度:最好情况下算法的时间复杂度。(不常用)

算法的空间复杂度

  • 算法原地工作:算法所需的内存空间为常量。
  • 函数递归调用带来的内存开销:空间复杂度 = 递归调用的深度

算数运算符

  • 运算符 描述 实例
    +
    -
    *
    / 9 / 2 = 4.5
    // 取整除 9 // 2 = 4
    % 取余数 9 % 2 = 1
    ** 2 ** 3 = 8
  • 在Python中*还可以用于字符串,计算结果就是字符串重复指定次数的结果

    1
    2
    In [1]:"-" * 5
    Out[1]"-----"

变量类型

  • 数字型

    • 整型 int

    • 浮点型 float

    • 布尔型 bool

    • True

    • False

    • 复数型 complex

    • 主要用于科学计算,例如:平面场问题、波动问题、电容电感等问题

  • 非数字型

    • 字符串
    • 列表
    • 元组
    • 字典
  • 提示:在Python2.x中,整数还可分为intlong

  • 使用type函数可以查看一个变量类型

    • In [1]: type(name)
  • 字符串之间可以用+进行拼接

    字符串可以和整数使用*重复拼接相同的字符串

    数字型变量和字符串之间不能进行其他运算

变量的输入和输出

  • input()

    • 字符串变量 = input("提示信息:")
    • input()输入的内容都认为是一个字符串
  • 类型转换函数

    • int(x)将x转换为一个整数
    • float(x)将x装换为一个浮点数
  • 变量的格式化输出

    • 格式化字符 含义
      %s 字符串
      %d 有符号十进制整数,%06表示输出的整数显示6位数,不足的地方用0补全
      %f 浮点数,%.02f表示小数点后只显示两位
      %% 输出%
    • print("Name:%s,Age:%d"% (name, age))name变量中为姓名信息,age变量中为年龄信息

    • print("abc", end = "a")在默认情况下,print输出后会自动在末尾添加换行,利用end可用end内容替代换行

    • print("")在一行输出后添加换行

转义字符

  • 转义字符 描述
    \\ 反斜杠符号
    \` 单引号
    \\“ 双引号
    \n 换行
    \t 横向制表符
    \r 回车

函数的基本使用

  • 函数的定义

    1
    2
    3
    def function():
    # 函数内容
    print("hello")
  • 定义的函数只有被调用才会执行

模块

  • 每一个以扩展名.py为结尾的python源文件都是一个模块
  • 导入模块需要import
  • 模块名也是标识符,需要遵循标识符命名规则
  • .pyc表示编译过文件

列表

  • 查看列表List能使用的功能

    • 在ipython3中操作:
    1
    2
    In [1]:name_list.(+tab键)
    name_list.append name_list.count等等
    • 序号 分类 关键字/函数/方法 说明
      1 增加 列表.insert(索引,数据) 在指定位置插入数据
      列表.append(数据) 在末尾追加数据
      列表.extend(列表2) 将列表2的数据追加到列表
      2 修改 列表[索引] = 数据 修改指定索引的数据
      del 列表[索引] 删除指定索引的数据
      列表.remove(数据) 删除第一个出现的指定数据
      列表.pop 删除末尾数据
      列表.pop(索引) 删除指定索引数据
      列表.clear 情空列表
      4 统计 len(列表) 列表长度
      列表.count(数据) 数据在列表中出现次数
      列表.index(数据) 返回数据索引
      5 排序 列表.sort() 升序排序
      列表.sort(reverse=True) 降序排序
      列表.reverse() 逆转,反转
  • 使用del关键字可以从内存中删除变量

  • 关键字后面不需要使用括号,函数需要

  • 迭代循环for num in nums

  • 列表中可以存储不同类型数据

元组

  • Tuple与列表类似,不同之处在于元组的元素不能修改

    • 元组表示多个元素组成的序列
    • 元组在Python开发中有特定的应用场景
  • 用于存储一串信息,数据之间使用,分隔

  • 元组用()定义

  • 元组的索引从0开始

  • 创建空元组()

  • 查看元组能使用的功能方法如列表

  • 可用for in遍历元组

  • 应用场景

    • 函数的参数和返回值
    • 格式化字符串
    • 让列表不可被修改,以保护列表安全
  • list(元组)# 元组转换为列表

    tuple(列表)# 列表转换为元组

字典

  • dictionary(字典)可用于存储多个数据

  • 字典是无序对象合集,列表是有序对象合集

  • 字典用{}定义

  • 字典使用键值对存储数据,键值之间使用分隔

    • key是索引
    • value是数据
    • 键和值之间使用:分隔
    • 键必须是唯一的
    • 值可以取任何数据类型,但键只能使用字符串、数字和元组
  • 举例:

    1
    2
    3
    4
    xiaoming = {"name": "小明",
    "age": 18,
    "gender": True,
    "height": 1.75}
    key value
    name 小明
    age 18
    gender True
    height 1.75
  • 字典取值使用[]

    • 例如:pirnt(["name"])
  • xiaoming["GPA"] = 3.5若key不存在则会新增键值对

  • 查看元组能使用的功能方法如列表

  • for k in xiaoming变量k是键值

  • 使用场景

    • 使用多个键值对存储描述一个物体的相关信息
    • 将多个字典放在一个列表中再进行遍历,再循环体内部针对每一个字典进行相同的处理

字符串

  • 可以用""''定义字符串,使用''往往用于定义字符串内有""的情况

    • str2 = 'my name is "logo"'
  • index("substring")查询子字符串substring不存在代码会报错

  • 判断类型

方法 说明
string.isspace() 若string只包含空格,返回True
sting.isalnum() 若string至少有一个字符并且所以字符或数字返回True
string.isalpha() 若string至少有一个并且所有字符都是字母返回True
string.isdecimal() 若string只包含数字则返回True(全角数字)
string.isdigit() 若string只包含数字则返回True(全角数字,(1),\u00b2
string.isnumeric() 若string只包含数字则返回True(全角数字,汉字数字)
string.istitle() 若string是标题化的(每个单词首字母大写)则返回True
string.islower() 若string中包含至少一个区分大小写的字符,并且所有这些(区分大小写的)字符都是小写,则返回True
string.isupper() 若string中包含至少一个区分大小写的字符,并且所有这些(区分大小写的)字符都是大写,则返回True
  • 查找和替换
方法 说明
string.startswith(str) 若string以str开头则返回True
string.endwith(str) 若string以str结尾则返回True
string.find(str,start=0,end=len(string)) str在 string的start到end中则返回索引值,否则返回-1
string.rfind(str,start=0,end=len(string)) 类似find()函数,从右边开始
string.index(str,start=0,end=len(string)) find()类似,但是str不在string中会报错
string.rindex(str,start=0,end=len(string)) 类似于index(),从右边开始
string.replace(old_str,new_str,num=string.count(old)) 把string中old_str替换为new_str,若num指定,则替换不超过num
  • 大小写转换
方法 说明
string.capitalize() 把字符串第一个字符大写
string.title() 把字符串每个单词首字母大写
string.lower() 转换string所有大写字母为小写
string.upper() 转换string所有小写字母为大写
string.swapcase() 翻转string中的大小写
  • 去除空白字符
方法 说明
string.lstrip() 截掉 string 左边(开始)的空白字符
string.rstrip() 截掉 string 右边(末尾)的空白字符
string.strip() 截掉 string 左右两边的空白字符
  • 拆分和连接
方法 说明
string.partition(str) 把字符串 string 分成一个 3 元素的元组 (str前面, str, str后面)
string.rpartition(str) 类似于 partition() 方法,不过是从右边开始查找
string.split(str="", num) str 为分隔符拆分 string,如果 num 有指定值,则仅分隔 num + 1 个子字符串,str 默认包含 ‘\r’, ‘\t’, ‘\n’ 和空格
string.splitlines() 按照行(‘\r’, ‘\n’, ‘\r\n’)分隔,返回一个包含各行作为元素的列表
string.join(seq) 以 string 作为分隔符,将 seq 中所有的元素(的字符串表示)合并为一个新的字符串
  • 切片 方法适用于 字符串列表元组
    • 切片 使用 索引值 来限定范围,从一个大的 字符串切出 小的 字符串
    • 列表元组 都是 有序 的集合,都能够 通过索引值 获取到对应的数据
    • 字典 是一个 无序 的集合,是使用 键值对 保存数据
    • nums_str[开始索引:结束索引:步长]
    • 注意
      • 指定的区间属于 左闭右开[开始索引, 结束索引) => 开始索引 >= 范围 < 结束索引
      • 起始 位开始,到 结束位的前一位 结束(不包含结束位本身)
      • 从头开始,开始索引 数字可以省略,冒号不能省略
      • 到末尾结束,结束索引 数字可以省略,冒号不能省略
      • 步长默认为 1,如果连续切片,数字和冒号都可以省略
    • 索引的顺序和倒序
      • 在 Python 中不仅支持 顺序索引,同时还支持 倒序索引,步长为-1
      • 所谓倒序索引就是 从右向左 计算索引
        • 最右边的索引值是 -1,依次递减

公共方法

  • 内置函数
函数 描述 备注
len(item) 计算容器中元素个数
del(item) 删除变量 del 有两种方式
max(item) 返回容器中元素最大值 如果是字典,只针对 key 比较
min(item) 返回容器中元素最小值 如果是字典,只针对 key 比较
cmp(item1, item2) 比较两个值,-1 小于/0 相等/1 大于 Python 3.x 取消了 cmp 函数

注意

  • 字符串 比较符合以下规则: “0” < “A” < “a”
  • 切片

    描述 Python 表达式 结果 支持的数据类型
    切片 “0123456789”[::-2] “97531” 字符串、列表、元组
    • 切片 使用 索引值 来限定范围,从一个大的 字符串切出 小的 字符串
    • 列表元组 都是 有序 的集合,都能够 通过索引值 获取到对应的数据
    • 字典 是一个 无序 的集合,是使用 键值对 保存数据
  • 运算符

    运算符 Python 表达式 结果 描述 支持的数据类型
    + [1, 2] + [3, 4] [1, 2, 3, 4] 合并 字符串、列表、元组
    * [“Hi!”] * 4 [‘Hi!’, ‘Hi!’, ‘Hi!’, ‘Hi!’] 重复 字符串、列表、元组
    in 3 in (1, 2, 3) True 元素是否存在 字符串、列表、元组、字典
    not in 4 not in (1, 2, 3) True 元素是否不存在 字符串、列表、元组、字典
    > >= == < <= (1, 2, 3) < (2, 2, 3) True 元素比较 字符串、列表、元组

    注意

    • in 在对 字典 操作时,判断的是 字典的键
    • innot in 被称为 成员运算符
  • 成员运算符

    成员运算符用于 测试 序列中是否包含指定的 成员

    运算符 描述 实例
    in 如果在指定的序列中找到值返回 True,否则返回 False 3 in (1, 2, 3) 返回 True
    not in 如果在指定的序列中没有找到值返回 True,否则返回 False 3 not in (1, 2, 3) 返回 False

    注意:在对 字典 操作时,判断的是 字典的键

  • 完整的 for 循环语法

    • Python 中完整的 for 循环 的语法如下:
1
2
3
4
5
for 变量 in 集合:

循环体代码
else:
没有通过 break 退出循环,循环结束后,会执行的代码

应用场景

  • 迭代遍历 嵌套的数据类型时,例如 一个列表包含了多个字典

  • 需求:要判断 某一个字典中 是否存在 指定的 值

    • 如果 存在,提示并且退出循环

    • 如果 不存在,在 循环整体结束 后,希望 得到一个统一的提示

LINUX 上的 Shebang 符号(#!)

  • #!这个符号叫做 Shebang 或者 Sha-bang
  • Shebang 通常在 Unix 系统脚本的中 第一行开头 使用
  • 指明 执行这个脚本文件解释程序
  • 使用 Shebang 的步骤
  1. 使用 which 查询 python3 解释器所在路径
1
$ which python3
  1. 修改要运行的 主 python 文件,在第一行增加以下内容
1
#! /usr/bin/python3
  1. 修改 主 python 文件 的文件权限,增加执行权限
1
$ chmod +x cards_main.py
  1. 在需要时执行程序即可
1
./cards_main.py

有些事情我今天没去做,明天更不会做。
有些书我这个月没读,下个月更不会读。
有些目标我今年没达成,明年更不会达成。
有些成功我年轻没取得,年老也不会实现。

  • 世界缓慢地持续旋转,而人们都活在梦中。
  • 正因为不能称心如意,人生才有意思。
  • 我们大家都在持续失去种种宝贵的东西——宝贵的机会和可能性,无法挽回的感情。这是生存的一个意义。但我们的脑袋里——我想应该是脑袋里——有一个将这些作为记忆保存下来的小房间。肯定是类似图书馆书架的房间。而我们为了解自己的心的正确状态,必须不断制作那个房间用的检索卡。也需要清扫、换空气、给花瓶换水。换言之,你势必永远活在你自身的图书馆里。
  • 于是我们领教了世界是何等凶顽,同时又得知世界也可以变得温存和美好。
  • 某种情况下,命运这东西类似不断改变前进方向的局部沙尘暴。你变换脚步力图避开他,不料沙尘暴就像配合你似的同样变换脚步。不知有多少人曾在那里流血,你本身也会流血。温暖的鲜红的血。你将双手接血。那既是你的血,又是别人的血。不过有一点是清楚的:从沙尘暴中逃出的你已不再是跨入沙尘暴时的你。是的,这就是所谓沙生暴的含义。
  • 纵使那样,也就是说纵使你的选择和努力注定徒劳无益,你也仍然绝对是你,不是你以外的什么。你正在作为你自己而向前迈进,毫无疑问,不必担心。
  • 就经验性来说,人强烈追求什么的时候,那东西基本上是不来的, 而当你极力回避它的时候,它却自然找到头上。
  • 不是人选择命运,而是命运选择人。

461.Hamming Distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, return the Hamming distance between them.

Example 1:

1
2
3
4
5
6
7
Input: x = 1, y = 4
Output: 2
Explanation:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑
The above arrows point to positions where the corresponding bits are different.

Example 2:

1
2
Input: x = 3, y = 1
Output: 1

位运算:

时间复杂度:O(log⁡C),本题中logC = log2^31

空间复杂度:O(1)

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int hammingDistance(int x, int y) {
int ans = 0;
while(x > 0 || y > 0) {
if((x & 1) != (y & 1))ans++;
x >>= 1;
y >>= 1;
}
return ans;
}
};
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
int hammingDistance(int x, int y) {
int s = x ^ y, ret = 0;
while (s) {
ret += s & 1;
s >>= 1;
}
return ret;
}
};

内置位运算:

时间复杂度:O(1)

空间复杂度:O(1)

1
2
3
4
5
6
class Solution {
public:
int hammingDistance(int x, int y) {
return __builtin_popcount(x ^ y);
}
};

Brian Kernighan 算法:

时间复杂度:O(log⁡C),本题中logC = log2^31

空间复杂度:O(1)

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
int hammingDistance(int x, int y) {
int s = x ^ y, ret = 0;
while (s) {
s &= s - 1;
ret++;
}
return ret;
}
};

459.Repeated Substring Pattern

Given a string s, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together.

Example 1:

1
2
3
Input: s = "abab"
Output: true
Explanation: It is the substring "ab" twice.

Example 2:

1
2
Input: s = "aba"
Output: false

Example 3:

1
2
3
Input: s = "abcabcabcabc"
Output: true
Explanation: It is the substring "abc" four times or the substring "abcabc" twice.

枚举法:

时间复杂度:O(n^2)

空间复杂度:O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
bool repeatedSubstringPattern(string s) {
int n = s.size();
for (int i = 1; i * 2 <= n; ++i) {
if (n % i == 0) {
bool match = true;
for (int j = i; j < n; ++j) {
if (s[j] != s[j - i]) {
match = false;
break;
}
}
if (match) {
return true;
}
}
}
return false;
}
};

字符串匹配:

1
2
3
4
5
6
class Solution {
public:
bool repeatedSubstringPattern(string s) {
return (s + s).find(s, 1) != s.size();
}
};

KMP算法:

时间复杂度:O(n)

空间复杂度:O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
bool kmp(const string& query, const string& pattern) {
int n = query.size();
int m = pattern.size();
vector<int> fail(m, -1);
for (int i = 1; i < m; ++i) {
int j = fail[i - 1];
while (j != -1 && pattern[j + 1] != pattern[i]) {
j = fail[j];
}
if (pattern[j + 1] == pattern[i]) {
fail[i] = j + 1;
}
}
int match = -1;
for (int i = 1; i < n - 1; ++i) {
while (match != -1 && pattern[match + 1] != query[i]) {
match = fail[match];
}
if (pattern[match + 1] == query[i]) {
++match;
if (match == m - 1) {
return true;
}
}
}
return false;
}

bool repeatedSubstringPattern(string s) {
return kmp(s + s, s);
}
};

优化:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
bool kmp(const string& pattern) {
int n = pattern.size();
vector<int> fail(n, -1);
for (int i = 1; i < n; ++i) {
int j = fail[i - 1];
while (j != -1 && pattern[j + 1] != pattern[i]) {
j = fail[j];
}
if (pattern[j + 1] == pattern[i]) {
fail[i] = j + 1;
}
}
return fail[n - 1] != -1 && n % (n - fail[n - 1] - 1) == 0;
}

bool repeatedSubstringPattern(string s) {
return kmp(s);
}
};

当我跑5km时,前1km是毫无压力的,因为刚刚开始跑,感觉不到累。
最后500米也是可以肆无忌惮地冲刺的,因为我知道跑完这500米完就可以休息了,不用担心接着跑会坚持不下来。
而中间的3.5km是十分枯燥的,总是在思考还有多久能休息,再跑心脏会不会承担不了等等问题。可能会感觉到喘不过来气,可能会想要放弃,可能会感觉看不见终点在哪里。

人生也是如此,绝大多数光景我们都在这3.5km中活着,眼前只有一个不太真实可触的目标,身体十分疲惫,心理也承担着巨大的压力。感觉一直在做事情,却难以接近那个遥不可及又充满神秘的未来。

困难的地方在于我们只能也必须跑下去,幸运的地方在于我们还可以跑下去,并且有人到达过终点。

在这个世界上没有绝对的好人,也没有绝对的坏人。
在一个长的时间限度内,你好事比坏事做的多就是好人,坏事做得比好事多也就成了坏人。
所以不必自困于过去的遗憾,做到今天的自己问心无愧就好。
但行好事耳。

455.Assign Cookies

Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie.

Each child i has a greed factor g[i], which is the minimum size of a cookie that the child will be content with; and each cookie j has a size s[j]. If s[j] >= g[i], we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.

Example 1:

1
2
3
4
5
Input: g = [1,2,3], s = [1,1]
Output: 1
Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3.
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
You need to output 1.

Example 2:

1
2
3
4
5
Input: g = [1,2], s = [1,2,3]
Output: 2
Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2.
You have 3 cookies and their sizes are big enough to gratify all of the children,
You need to output 2.

排序法:

时间复杂度:O(nlogn+mlogm)
空间复杂度:O(logn+logm)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
int ans = 0;
sort(s.begin(), s.end());
sort(g.begin(), g.end());
for (int i = s.size() - 1; i >= 0; i--) {
int j = g.size() - 1;
for (; j >= 0; j--) {
if (s[i] >= g[j]) {
ans++;
g[j] = INT_MAX;
break;
}
}
}
return ans;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int m = g.size(), n = s.size();
int count = 0;
for (int i = 0, j = 0; i < m && j < n; i++, j++) {
while (j < n && g[i] > s[j]) {
j++;
}
if (j < n) {
count++;
}
}
return count;
}
};