发表于 | 分类于

算法分析

算法的时间复杂度分析

  • 事后分析估算方法：这种统计方法主要是通过设计好的测试程序和测试数据，利用计算机计时器对不同算法编制的程序的运行时间进行比较，从而确定算法效率的高低，但这种方法有很大的缺陷：必须依据算法实现编制好的测试程序，通常需要花费大量的时间和精力，测试完了如果发现测试的是非常糟糕的算法，那么之前所做的事情就全部白费了，并且不同的测试环境(硬件设备)的差别导致测试的结果差异也很大。

  • 事前分析估算方法：在计算机程序编写前，根据统计方法对算法进行估算，经过总结，一个高级语言编写的程序在计算机上运行所消耗的时间取决于下列因素：

    • 算法采用的策略与方案；
    • 编译产生的代码质量；
    • 问题的输入规模(输入量的多少)
    • 机器执行指令的速度

    由此可见，抛开与计算机硬件、软件有关因素，一个程序运行的时间依赖于算法的好坏与问题的输入规模。如果算法固定，那么算法的执行时间就只和问题的输入规模有关系了。

    我们研究算法复杂度，侧重的是当输入规模不断增大时，算法的增长量的一个抽象，而不是精确地定位需要执行多少次，因为如果是这样的话，我们又得考虑回编译器优化等问题，容易主次颠倒。我们分析一个算法的运行时间，最重要的就是把核心操作的次数和输入规模关联起来。

阅读全文 »

发表于 | 分类于

硬核显示技术

显示器的原理

目前最普及的商用显示器技术从技术原理上分成两大类：

  • 液晶显示器LCD(Liquid Crystal Display)
  • 有机发光半导体OLED(Organic Light-emitting Diode)
  • CRT显像管显示器(太过久远，略)

目前这两类显示器的显示原理都是基于通过三基色组合成像素点的光学原理。像素点非常微小并且非常密集人眼视距在正常的范围是看不到像素点的。LCD和OLED组成最小发光单元的原理却有着本质上的不同。

阅读全文 »

发表于 | 分类于

第九章 集合

9.1 Java集合框架

9.1.1 集合接口与实现分离

与现代的数据结构类库的常见做法一样，Java集合类库也将接口(interface)与实现(implementation)分离。下面利用我们熟悉的数据结构——队列(Queue)来说明是如何分离的。

队列接口指出可以在队列的尾部添加元素，在队列的头部删除元素，并且可以查找队列中元素的个数。当需要收集对象，并按照“先进先出”方式检索对象时就应该使用队列。

队列接口的最简形式可能类似下面这样：

1
2
3
4
5
6
public interface Queue<E>
{
    void add(E element);
    E remove();
    int size();
}

这个接口并没有说明是如何实现的。队列通常有两种实现方式”一种是使用循环数组；另一种是使用链表。

阅读全文 »

发表于 | 分类于

HTML和CSS

1.B/S软件的结构

JAVASE C/S Client/Server

B/S Browser/Server

image-20201123150000522

阅读全文 »

发表于 | 分类于

Collection框架

Collection

阅读全文 »

发表于 | 分类于

第八章 泛型程序设计

8.1 为什么要使用泛型程序设计

泛型程序设计(generic programming)意味着编写的代码可以对多种不同类型的对象重用。例如，你并不希望为收集String和File对象分别编写不同的类。实际上，也不需要这样做，因为一个ArrayList类就可以收集任何类的对象。这就是泛型程序设计的一个例子。

实际上 ，在Java有泛型类之前已经有一个ArrayList类。下面来研究泛型程序设计的机制是如何演变的，另外还会介绍这对用户和实现者来说意味着什么。

8.1.1 类型参数的好处

在Java中增加泛型类之前，泛型程序设计是用继承实现的。ArrayList类只维护一个Object引用的数组：

1
2
3
4
5
6
7
public class ArrayList
{
    private Object[] elementData;
    ...;
    public Object get(int i){...}
    public void add(Object o){...}
}

这两种方法存在两个问题。当获取一个值时必须进行强制类型转换。

1
2
ArrayList files = new ArrayList();
String filename = (String)files.get(0);

此外，这里没有错误检查。可以向数组列表中添加任何类的值。

1
files.add(new File("..."));

对于这个调用，编译器和运行都不会错。不过在其他地方，如果将get的结果强制类型转换转换为String类型，就会产生一个错误。

泛型提供了一个更好的解决方案：参数类型(type parameter)。ArrayList类有一个类型参数用来指示元素的类型：

1
ArrayList<String> files = new ArrayList<String>();

这使得代码具有更好的可读性。人们一看就知道这个数组列表中包含的是String对象。

编译器也可以充分利用这个类型信息。调用get的时候，不需要进行强制类型转换。编译器知道返回值类型为String，而不是Object：

1
String filename = files.get(0);

编译器还知道ArrayList\的add方法有一个类型为String的参数，这比有一个Object类型的参数要安全得多。现在，编译器可以检查，防止你插入错误类型得对象。例如，以下语句

1
files.add(new(File("...")));//can only add String objects to an Arraylist<String>

是无法通过编译得。不过，出现编译错误要比运行时出现类得强制类型转换异常好得多。

这正是类型参数得魅力所在：他们会让你的程序更易读，也更安全。

阅读全文 »

发表于 | 分类于

第七章 异常、断言和日志

7.1 处理错误

假设在一个Java程序运行期间出现了一个错误。这个错误可能由于文件包含错误信息，或者网络连接出现问题造成的，也有可能是因为使用了无效的数组下标，或者试图使用一个没有被赋值的对象引用而造成的。用户期望在出现错误时，程序能够采取合理的行为。如果由于出现错误而使得某些操作没有完成，程序应该：

  • 返回到一种安全状态，并能够让用户执行其他的命令；或者
  • 允许用户保存所有工作的结果，并以妥善的方式终止程序。

为了能够处理程序中的异常情况，必须考虑到程序中可能会出现的错误和问题。那么需要考虑哪些问题呢？

  • 用户输入错误
  • 设备错误
  • 物理限制
  • 代码错误

正如第五章中所提到的那样，在Java中，如果某个方法不能采用正常的途经完成它的任务，可以通过另外一个路径退出方法。在这种情况下，方法并不返回任何值，而是抛出(throw)一个封装了错误信息的对象。需要注意的是，这个方法将会立刻退出，并不返回正常值。此外，也不会从调用这个方法的代码继续执行，取而代之的是，异常处理机制开始搜索能够处理这种异常状况的异常处理器(exception handler)。

异常有自己的语法和特定的继承层次结构。下面首先介绍语法，然后给出有效地使用这种语言特性的技巧。

阅读全文 »

发表于 | 分类于

链表

链表的定义

链表是物理存储单元上非连续、非顺序的存储结构，它由一个个结点，通过指针来联系起来，其中每个结点都包括数据和指针。

image-20201027082655248

链表的非连续，非顺序，对应数组的连续、顺序，来看一个例子：整型数组1，2，3，4在内存中是如何表示的

image-20201027082807682

可以看到数组的每个元素都是连续紧邻分配的，这叫连续性，同时由于数组的元素占用的大小是一样的，在Java中int型大小固定为4个字节，所以如果数组的起始位置是100，由于这些元素在内存中都是连续紧邻分配的，大小也一样，可以很容易地找出数组中任意一个元素的位置，比如数组中的第三个元素起始地址为100+2*4=108，这就叫顺序性。查找的时间复杂度是O(1)，效率很高！

阅读全文 »

发表于 | 分类于

第六章 接口、lambda表达式与内部类

到目前为止，你已经学习了Java中面向对象编程的核心思想：类和继承。本章将介绍几种常用的高级技术。尽管这些内容可能不太容易理解，但一定要掌握，以完善你的Java工具箱。首先介绍第一种技术，即接口(interface)，接口用来描述类应该做什么，而不指定他们具体应该如何做。一个类可是实现(implement)一个接口或多个接口。有些情况可能要求符合这些接口，只要有这种要求，就可以实现了这个接口的类(及实现类)的对象。了解接口以后，再继续介绍lambda表达式，这是一种很简洁的方法，用来创建可以在将来某个时间点执行的代码块。通过使用lambda表达式，可以用一种精巧而简洁的方式表示使用回调或可变行为的代码。

接下来，我们将讨论内部类(inner class)机制。理论上讲，内部类有些复杂，内部类定义在另外一个类的内部，它们的方法可以访问包含它们的外部类的字段。内部类技术在设计具有相互协作关系的类集合时很有用。

在本章的最后还将介绍代理(proxy)，这是一种实现任意接口的对象。代理是一种非常专业的构造工具，可以用来构建系统级的工具。第一次阅读本书时可以先跳过那一节。

6.1 接口

6.1.1 接口的概念

在Java程序设计语言中，接口不是类，而是对希望符合这个接口的类的一组需求。

我们经常听到服务提供商这样说：“如果你的类符合某个特定接口，我们就会履行这项服务。”下面给出一个具体示例。Array类中的sort方法承诺可以对对象数组进行排序，但要求满足下面这个条件：对象所属的类实现Comparable接口。

1
2
3
4
public interface Comparable
{
    int compareTo(Object other);
}

这说明，任何实现Comparable接口的类都需要包含compapreTo方法，这个方法有一个Object参数，并且返回一个整数。

接口中的所有方法都是自动public方法。因此，在接口中声明方法时，不必提供关键字public。

当然，这个接口还有一个没有明确说明的附加要求：在调用x.compareTo(y)的时候，这个compareTo方法必须确实能够比较两个对象，并返回比较结果，即x和y哪一个更大 。当x小于y时返回一个负数；当x等于y时，返回0；否则返回一个正数。

上面这个接口只有一个方法，而有些接口可能包含多个方法。稍后可以看到，接口还可以定义常量。不过，更重要的是要知道接口不能提供什么。接口绝不会有实例字段，在Java8之前，接口绝对不会实现方法。

提供实例字段和方法实现的任务应该由实现接口的那个类来完成。因此，可以将接口看成是没有实例字段的抽象类。但是这两个概念还是有一定区别的，稍后将会给出i详细的解释。

现在，假设希望使用Arrays类的sort方法对Employee对象数组进行排序，Employee类就必须实现Comparable接口。

阅读全文 »

发表于 | 分类于

删除链表中的节点_237

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为要被删除的节点。

image-20201025185014252

1
2
3
4
5
6
7
8
输入：head = [4,5,1,9], node = 5
输出：[4,1,9]
解释：给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
    
输入：head = [4,5,1,9], node = 1
输出：[4,5,9]
解释：给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

1
2
3
4
5
6
7
8
class Solution
{
    public void deleteNode(ListNode node)
    {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

思路分析：将要被删除节点的下一个节点的数据赋值给当前节点，将当前节点的next指向下一节点的next(跳过下一节点)。