发表于 | 分类于

剑指Offer 18. 删除链表的节点

给定单链表的头指针和一个要删除的节点值，定义一个函数删除该节点。返回删除后的链表的头节点。

1
2
3
输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
1
2
3
输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution
{
    public ListNode deleteNode(ListNode head, int val)
    {
        if(head == null)
        {
            return head;
        }
        if(head.val = val)
        {
            return head.next;
        }
        ListNode pre = null;
        ListNode cur = head;
        
        while(cur.val != val)
        {
            pre = cru;
            cru = cru.next;
        }
        pre.next = cru.next;
        return head;
    }
}

发表于 | 分类于

Leetcode 206

反转一个单链表。

1
2
3
4
5
6
7
8
9
public class ListNode
{
    int val;
    ListNode next;
    public ListNode(int val)
    {
        this.val = val;
    }
}
1
2
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

遍历法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution
{
    public ListNode reverseList(ListNode head)
    {
        if(head == null || head.next == null)
        {
            return head;
        }
        ListNode pre = null;
        ListNode cur = head;
        
        while(cur != null)
        {
            ListNode temp = cur.next;
            
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solutin
{
    public ListNode reverseList(ListNode head)
    {
        if(head == null || head.next == null)
        {
            return head;
        }
        
        ListNode newNode = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newNode;
    }
}

发表于 | 分类于

队列

队列是一个有序列表，可以用数组或是链表来实现；遵循先入先出的原则。

数组模拟队列：

  1. maxSize 为队列的最大容量；2. 队列的输入、输出从前后端处理的，因此需要两个变量front和rear。

存入队列的思路分析：

  1. 将尾指针往后移：rear+1，当front == rear 空

  2. 当尾指针real小于队列的最大值maxSize-1，可将数据存入rear所指的数组元素中，否则无法存入数据 rear == maxSize -1 队列满。

阅读全文 »

发表于 | 分类于

第五章 继承

本章将学习面向对象程序设计的另外一个基本概念：继承(inheritance)。继承的基本思想是，可以基于已有的类创建新的类。继承已存在的类就是复用(继承)这些类的方法，而且可以增加一些新的方法和字段，使新类能够适应新的情况。这是Java程序设计中的一项核心技术。

另外，本章还阐述了反射(reflection)的概念。反射是指在程序运行期间更多地了解类及其属性的能力。反射是一个功能强大的特性，不过，不可否认它也相当复杂。

继承主要解决的问题就是：共性抽取。

5.1 类、超类和子类

回忆一下在前一章中讨论过的Employee类。假设你在某个公司工作，这个公司里的经理的待遇与普通员工的待遇存在着一些差异。不过，他们之间也存在着很多相同的地方，例如，他们都领取薪水。只是普通员工在完成本职任务之后仅领取薪水，而经理在完成了预期的业绩之后还能得到奖金。这种情形下就需要使用继承。为什么呢？因为需要为经理定义一个新类Manager，并增加一些新功能。但可以重用Employee类中已经编写的部分代码，并保留原来Employee类中的所有字段。从理论上讲，在Manager与Employee之间存在着明显的“is-a”关系，每个经理都是一个员工：“is-a”关系是继承的一个明显特征。

5.1.1 定义子类

可以如下继承Employee类来定义Manager类，这里使用关键字extends表示继承。

1
2
3
4
public class Manager extends Employee
{
    added methods and fields
}

关键字extends表明正在构建的新类派生于一个已经存在的类。这个已存在的类称为超类(superclass)、基类(base class)

或父类(parent class)；新类称为子类(subclass)、派生类(derived class)或孩子类(child class)。

尽管Employee类是一个超类，但并不是因为它优于子类或者拥有比子类更多的功能。实际上恰恰相反，子类比超类拥有更多的功能。

继承关系的特点：

  • 子类可以拥有父类的内容
  • 子类还可以拥有自己专有的内容

直接通过子类对象访问成员变量：等号左边是谁，就优先用谁，没有则向上找。

间接通过成员方法访问成员变量：方法属于谁，就优先用谁，没有则向上找。

区分子类方法中重名的三种变量：

  • 局部变量： 直接写
  • 本类的成员变量：this.成员变量名

  • 父类的成员变量：super.成员变量名

阅读全文 »

发表于 | 分类于

第四章 对象与类

4.1 面向对象程序设计概述

面向对象程序设计(object-oriented programming，OOP)；面向对象的程序是由对象组成的，每个对象包含对用户公开的特定功能部分和隐藏的实现部分。程序中的很多对象来自标准库，还有一些自定义的。

面向对象三大特征：封装、继承、多态。

4.1.1 类

类(class)是构造对象的模板或蓝图。由类构造(construct)对象的过程称为创建类的实例(instance)。

封装(encapsulation)是处理对象的一个重要概念。从形式上看，封装就是将数据和行为组合在一个包中，并对对象的使用者隐藏具体的实现方式。对象中的数据称为实例字段(instance field)，操作数据的过程称为方法(method)。

实现封装的关键在于，绝对不能让类中的方法直接访问其他类的实例字段。程序只能通过对象的方法与对象数据进行交互。封装给对象赋予“黑盒”特征，这是提高重用性和可靠性的关键。

在扩展一个已有的类时，这个扩展后新类具有被扩展的类的全部属性和方法。你只需要在新类提供适用于这个新类的新方法和数据字段就可以了。通过扩展一个类来建立另外一个类的过程称为继承(inheritance)。

4.1.2 对象

对象的三个主要特性：

  • 对象的行为(behavior)，可以完成哪些操作，或者可以对对象应用哪些方法。
  • 对象的状态(state)，当调用那些方法时，对象会如何相应。
  • 对象的标识(identity)，如何区分具有相同行为与状态的不同对象。

4.1.3 识别类

4.1.4 类之间的关系

在类之间，最常见的关系有：

  • 依赖(dependence)(“uses-a”)
  • 聚合(aggregation)(“has-a”)

  • 继承(inheritance)(“is-a”)

阅读全文 »

发表于 | 分类于

第三章 Java的基本程序设计结构

3.1 一个简单的Java应用程序

3.2 注释

3.3 数据类型

3.3.1 整型

3.3.2 浮点类型

三个特殊的浮点类型：

  • 正无穷大 (Double.POSITIVE_INFINITY)以及相应的Float类型
  • 负无穷大(Double.NEGATIVE_INFINITY)以及相应的Float类型
  • NaN (Double.NaN)以及相应的Float类型

检测一个特定值是否等于Double.NaN:

1
if (x == Double.NaN)// is never true
1
if(Double.isNaN(X))

浮点数不适用于无法接受舍入误差的金融计算，可以使用BigDecimal类。

3.3.3 char类型

3.3.4 Unicode和char类型

3.3.5 boolean类型

3.4 变量与常量

3.4.1 声明变量

3.4.2 变量初始化

3.4.3 常量

可以利用关键字final 指示常量。关键字final表示这个变量只能被赋值一次，一旦被赋值之后就不能够再更改了；常量使用全大写。

当希望某个常量可以在一个类的多个方法中使用，通常将这些常量称为类常量（class constant）；可以使用static final设置一个常量；类常量的定义位于main方法的外部，在同一个类的其他方法也可以使用这个常量。若一个常量被声明为public，那么其他类的方法也可以使用这个常量。

3.4.4 枚举类型

变量的取值只有在一个有限的集合内。

1
2
enum Size {SMALL,MEDIUM,LARGE,EXTRA_LARGE};
Size s = Size.MEDIUM;

Size类型的变量只能存储这个类型声明中给定的某个枚举值，或是特殊值null。

阅读全文 »

发表于 | 分类于

稀疏数组(sparsearray)

当一个数组大部分元素为0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。

稀疏数组的处理方法是：

  • 记录数组一共有几行几列，有多少个不同的值
  • 把具有不同值的元素的行及列值记录在一个小规模的数组中，从而缩小程序的规模。

二维数组转稀疏数组思路：

  1. 遍历原始的二维数组，得到有效数据的个数sum；

  2. 根据sum创建稀疏数组sparseArr int[sum + 1][3]；

  3. 将二维数组的有效数据存入到稀疏数组。

稀疏数组转二维数组：

  1. 点读取稀疏数组的第一行，创建原始的二维数组，比如上面的chessArr2 = int[11][11]；

  2. 读取稀疏数组后面的几行数据，并赋给原始的二维数组。

阅读全文 »

发表于 | 分类于

曲率公式：

$k = \frac {|y’’|}{(1+y’^2)^{\frac{3}{2}}}$

曲率及曲率半径的定义

对于一条曲线来说我们可以研究其曲率。通常来想，以一条连续光滑的曲线上无限接近的两个点为端点的一弧线总可以视为是某个圆上的一段弧（可以简单的认为曲率半径在连续光滑的曲线上不会发生突变，所以在某点的无穷小领域内曲率半径可以作为一个常量）。而这个圆的半径就被定义为曲线在这一点的曲率半径，而曲率则被定义为曲率半径的倒数。

那么如何求曲率的半径呢？我们可以回想一下刚接触到弧度制的时候是怎么定义弧度的。弧度是圆弧长与该圆半径的比值，即$\alpha = \frac{S}{R}$；显然当$S=2\pi R$即整个圆周长时弧度为$2\pi$。

那么显然曲率半径很自然的可以定义为$R=\frac{dS}{d\alpha}$，即无穷小的一段弧长与其相对应的弧度的比值。

阅读全文 »

发表于 | 分类于

1.WiFi名字的由来

WIFI（Wireless Fidelity，无线保真）听起来有点像是HIFI（High-Fidelity，高保真），然后制定无线技术的组织就借用这种深入人心的发音方式取名为WIFI，纯粹就是为了好记。

2.WiFi的频率，信道，调制方式

WiFi的频段：例如$ 2.4GHz $，并不指的是一个特定的频率，而是一个范围。

  • $ 2.4GHz $，指的是:$2.4GHz \sim 2.4835GHz$

  • $ 5GHz $，指的是:$5.15GHz \sim 5.85GHz$

阅读全文 »

发表于 | 分类于

1.什么是无线电波？

无线电波是一种电磁波。低频的无线电波不能穿越大气层，只能在地面传播；而高频的无线电波可以穿透大气层的电离层，例如：X光可以穿透人体，生成X光影像；伽马射线产生的电离辐射，就是核武器的杀伤手段之一。不同频率的无线电波表现出来的性质不一样，其实就是一种东西都是电磁波。

2.无线电波的信道。

生活中常用的无线电波主要在几千Hz~300GHz。根据频率的高低被国际电信联盟（Internationals Telecommunication Union,ITU）规定出各种专用的通信频率，也叫做信道。专业信道涵盖的业务范围特别广，例如：海上移动通信业务，AM广播，FM广播，无线电视广播，太空对地通信，GPS卫星通信服务，深空研究通信，卫星时间校准服务，卫星广播业务服务。

阅读全文 »