Home Tags Posts tagged with "数组"

数组

0 15

好久之前就了解过动态数组了,这次自己来实现一个。

先上代码

    /**
     * 实现一个动态数组
     *
     * @author 杨深建
     */
public class ArrayImpl<T> implements ArrayInterface<T> {

    private int size; // 表示的是数组的大小
    private T[] data; // 定义一个数组

    public ArrayImpl(int capciaty) {
        data = (T[]) new Object[capciaty]; // 创建一个数组
        size = 0;
    }

    public ArrayImpl() {
        this(10);
    }

    /**
     * 获取数组的容量
     *
     * @return
     */
    @Override
    public int getCapciaty() {
        return data.length;
    }

    /**
     * 获取数组的大小
     *
     * @return
     */
    @Override
    public int getSize() {
        return size;
    }

    /**
     * 判断数组是否为空
     *
     * @return
     */
    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 向数组的指定位置添加元素。
     *
     * @param index
     * @param element
     */
    @Override
    public void add(int index, T element) {
        // 1、判断index 是否合法。
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("index  is  illegal");
        }
        // 2、判断是否为满
        if (size == data.length) {
            resize(size*2);  //进行扩容操作
        }
        // 3、进行插入操作,数据迁移
        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }
        // 4、进行赋值插入
        data[index] = element;
        // 5、元素个数加1
        size++;
    }

    /**
     * 进行扩容操作
     * @param i
     */
    private void resize(int index) {
        T  [] data2=(T[]) new  Object[index];
        for(int i=0;i<size;i++){  //进行赋值操作
            data2[i]=data[i];
        }
        data=data2;
    }

    /**
     * 在数组的头部插入元素
     */
    @Override
    public void addFirst(T element) {
        add(0, element);
    }

    /**
     *
     * 在数组中的尾部插入元素
     */
    @Override
    public void addLast(T element) {
        add(size, element);
    }

    /**
     * 获取index索引位置的元素
     *
     * @param index
     * @return
     */
    @Override
    public T get(int index) {
        // 1、判断index 是否合法。
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("index  is  illegal");
        }
        return data[index];
    }

    /**
     * 修改index索引位置的元素为e
     *
     * @param index
     * @param element
     */
    @Override
    public void set(int index, T element) {
        // 1、判断index 是否合法。
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("index  is  illegal");
        }
        data[index] = element;
    }

    /**
     * 显示所有的数组元素
     */
    @Override
    public void print() {
        for (int i = 0; i < size; i++) {
            System.out.println(data[i]);
        }
    }

    /**
     * 查找数组中是否有元素e
     */
    @Override
    public boolean contains(T e) {
        for (int i = 0; i < size; i++) {
            if (e.equals(data[i])) {
                return true;
            }
        }
        return false;
    }

    /**
     * 查找数组中元素e所在的索引,如果不存在元素e,则返回-1
     */
    @Override
    public int find(T e) {
        for (int i = 0; i < size; i++) {
            if (e.equals(data[i])) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 从数组中删除index位置的元素, 返回删除的元素
     */
    @Override
    public T remove(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("index  is  illegal");
        }
        T res = data[index]; // 获取结果
        for (int i = index + 1; i < size; i++) {
            data[i - 1] = data[i]; // data[index]
        }
        size--;  //进行元素个数-1
        if(size == data.length/4 && data.length/2!=0)  resize(data.length/2);  //如果元素的个数小于容量的1/4 ,我们就进行缩容操作 到容量的1/2
        return res;
    }

    /**
     * 从数组中删除第一个元素, 返回删除的元素
     */
    @Override
    public T removeFirst() {
        T res = remove(0);
        return res;
    }

    /**
     * 从数组中删除最后一个元素, 返回删除的元素
     */

    @Override
    public T removeLast() {
        T res = remove(size - 1);
        return res;
    }

    /**
     * 从数组中删除元素e
     */
    @Override
    public void removeElement(T element) {
        int index = find(element);
        if (index != -1) {
            remove(index);
        }
    }

    @Override
    public String toString() {
        //使用 线程不安全的StringBuilder 效率更高
        StringBuilder res = new StringBuilder();
        res.append(String.format("Array: size = %d , capacity = %d\n", size, data.length));
        res.append('[');
        for (int i = 0; i < size; i++) {
            res.append(data[i]);
            if (i != size - 1)
                res.append(", ");
        }
        res.append(']');
        return res.toString();
    }
}


说明:我所采用的是for循环复制元素扩容,但这种扩容是有一些问题的
缺陷: 拷贝一部分元素需要计算索引,比较复杂
2.System.arraycopy()
3.Arrays.copyOf扩容

* 观察copyOf方法的源码:

* public static int[] copyOf(int[] original, int newLength) {

* int[] copy = new int[newLength];

* System.arraycopy(original, 0, copy, 0,

* Math.min(original.length, newLength));

* return copy;

* }

4.利用Object类中一个 clone 方法,该方法是真正意义上的复制数组(默认浅拷贝,如果覆写则是深拷贝)

复杂度的震荡

当同时思考addLast和removeLast操作的时候:

假如调用addLast触发resize扩容后调用removeLast显然也会调用resize进行缩容,这个操作如果反复执行就会导致复杂度的震荡,所以代码中removeLast方法中,并没有像addLast中那样直接让data.length/2,而是当数组内的元素等于四分之一容量的时候,才会执行缩容的操作,就可以解决复杂度的震荡

if (size == data.length / 4 && data.length / 2 != 0) {
            resize(data.length / 2);
        }

0 15

链表,做过不少题,包括反转,相交链表等,这次就来试试实现一个LRU缓存淘汰算法吧(最近最少使用算法)

内容整理来自与极客时间

链表的经典使用场景:LRU缓存淘汰算法

先来了解一下缓存

一、 缓存是什么?(空间换时间的思想)

缓存是一种提高数据读取性能的技术,在硬件设计、软件开发中都有着非常广泛的应用,比如常见的 CPU 缓存、数据库缓存、浏览器缓存等等。

二、 为什么需要缓存淘汰策略?

缓存的大小有限,当缓存被用满时,哪些数据应该被清理出去,哪些数据应该被保留?这就需要缓存淘汰策略来决定。

三、常见的缓存策略有哪些?

常见的策略有三种:先进先出策略 FIFO(First In,First Out)、最少使用策略 LFU(Least Frequently Used)、最近最少使用策略 LRU(Least Recently Used)


接下来是链表部分

一、 链表与数组对比

我们先从底层的存储结构上来看一看。为了直观地对比,我画了一张图。

从图中我们看到,数组需要一块连续的内存空间来存储,对内存的要求比较高。如果我们申请一个 100MB 大小的数组当内存中没有连续的、足够大的存储空间时,即便内存的剩余总可用空间大于 100MB,仍然会申请失败

而链表恰恰相反,它并不需要一块连续的内存空间,它通过“指针”将一组零散的内存块串联起来使用,所以如果我们申请的是 100MB 大小的链表,根本不会有问题。

二、 常见的三种链表结构(单链表,双向链表,循环链表)

和单链表相比,循环链表的优点是从链尾到链头比较方便。当要处理的数据具有环型结构特点时,就特别适合采用循环链表。比如著名的约瑟夫问题。尽管用单链表也可以实现,但是用循环链表实现的话,代码就会简洁很多。从我画的图中可以看出来,双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以,如果存储同样多的数据,双向链表要比单链表占用更多的内存空间。虽然两个指针比较浪费存储空间,但可以支持双向遍历,这样也带来了双向链表操作的灵活性。那相比单链表,双向链表适合解决哪种问题呢?从结构上来看,双向链表可以支持 O(1) 时间复杂度的情况下找到前驱结点,正是这样的特点,也使双向链表在某些情况下的插入、删除等操作都要比单链表简单、高效。

链表的插入和删除操作的时间复杂度真的是O(1)吗?有哪些先决条件呢?

我们先来看删除操作。

一、 删除操作(删除某个值,则一样需要遍历;删除某个给定指针指向的结点,双向链表不需要遍历更高效)

在实际的软件开发中,从链表中删除一个数据无外乎这两种情况:

  1. 删除结点中“值等于某个给定值”的结点;(这种情况单链表和双向链表一样O(n))
  2. 删除给定指针指向的结点。(要删除某个结点,需要知道其前结点,双向链表拥有前指针,更高效;即单链表仍需要遍历找到前驱结点O(n),而双向链表只需要O(1))

对于第一种情况,不管是单链表还是双向链表,为了查找到值等于给定值的结点,都需要从头结点开始一个一个依次遍历对比,直到找到值等于给定值的结点,然后再通过我前面讲的指针操作将其删除。尽管单纯的删除操作时间复杂度是 O(1),但遍历查找的时间是主要的耗时点,对应的时间复杂度为 O(n)。根据时间复杂度分析中的加法法则,删除值等于给定值的结点对应的链表操作的总时间复杂度为 O(n)。

对于第二种情况,我们已经找到了要删除的结点,但是删除某个结点 q 需要知道其前驱结点,而单链表并不支持直接获取前驱结点,所以,为了找到前驱结点,我们还是要从头结点开始遍历链表,直到 p->next=q,说明 p 是 q 的前驱结点。

但是对于双向链表来说,这种情况就比较有优势了。因为双向链表中的结点已经保存了前驱结点的指针,不需要像单链表那样遍历。所以,针对第二种情况,单链表删除操作需要 O(n) 的时间复杂度,而双向链表只需要在 O(1) 的时间复杂度内就搞定了!

同理,如果我们希望在链表的某个指定结点前面插入一个结点,双向链表比单链表有很大的优势。双向链表可以在 O(1) 时间复杂度搞定,而单向链表需要 O(n) 的时间复杂度。你可以参照我刚刚讲过的删除操作自己分析一下。

二、 链表如果有序,双向链表的查询也比单链表更高效,思想与二分查找类似

除了插入、删除操作有优势之外,对于一个有序链表,双向链表的按值查询的效率也要比单链表高一些。因为,我们可以记录上次查找的位置 p,每次查询时,根据要查找的值与 p 的大小关系,决定是往前还是往后查找,所以平均只需要查找一半的数据。

现在,你有没有觉得双向链表要比单链表更加高效呢?这就是为什么在实际的软件开发中,双向链表尽管比较费内存,但还是比单链表的应用更加广泛的原因。如果你熟悉 Java 语言,你肯定用过 LinkedHashMap 这个容器。如果你深入研究 LinkedHashMap 的实现原理,就会发现其中就用到了双向链表这种数据结构。

实际上,这里有一个更加重要的知识点需要你掌握,那就是用空间换时间的设计思想。当内存空间充足的时候,如果我们更加追求代码的执行速度,我们就可以选择空间复杂度相对较高、但时间复杂度相对很低的算法或者数据结构。相反,如果内存比较紧缺,比如代码跑在手机或者单片机上,这个时候,就要反过来用时间换空间的设计思路。

还是开篇缓存的例子。缓存实际上就是利用了空间换时间的设计思想。如果我们把数据存储在硬盘上,会比较节省内存,但每次查找数据都要询问一次硬盘,会比较慢。但如果我们通过缓存技术,事先将数据加载在内存中,虽然会比较耗费内存空间,但是每次数据查询的速度就大大提高了。所以我总结一下,对于执行较慢的程序,可以通过消耗更多的内存(空间换时间)来进行优化;而消耗过多内存的程序,可以通过消耗更多的时间(时间换空间)来降低内存的消耗。

 

链表和数组性能对比(内存紧张则使用数组)

大纲:查找效率更高的是数组,插删效率更高的是链表,但是链表天然支持动态扩容,而容器尽管也可以扩容,但需要做数据拷贝(费时),链表占用空间更大,内存紧张使用数组

从JVM角度来说:

数组声明需要申请一块连续的内存空间,如果系统的内存空间不足则会申请失败,但是在垃圾回收阶段,数组可以采用标记后集中回收,减少垃圾回收次数,减少耗时; 链表在内存中不是连续存储,可以动态的增加内存空间,但链表的内存消耗相对于数组是翻倍的(多了一份指向下一个节点的指针),而且对链表频繁的插入,删除操作,会导致频繁的内存申请和释放,容易造成内存碎片,导致频繁的垃圾回收。

数组简单易用,在实现上使用的是连续的内存空间,可以借助 CPU 的缓存机制,预读数组中的数据,所以访问效率更高。

而链表在内存中并不是连续存储,所以对 CPU 缓存不友好,没办法有效预读。

数组的缺点是大小固定,一经声明就要占用整块连续内存空间。如果声明的数组过大,系统可能没有足够的连续内存空间分配给它,导致“内存不足(out of memory)”。如果声明的数组过小,则可能出现不够用的情况。这时只能再申请一个更大的内存空间,把原数组拷贝进去,非常费时。

链表本身没有大小的限制,天然地支持动态扩容,我觉得这也是它与数组最大的区别。你可能会说,我们 Java 中的 ArrayList 容器,也可以支持动态扩容啊?我们上一节课讲过,当我们往支持动态扩容的数组中插入一个数据时,如果数组中没有空闲空间了,就会申请一个更大的空间,将数据拷贝过去,而数据拷贝的操作是非常耗时的。我举一个稍微极端的例子。如果我们用 ArrayList 存储了了 1GB 大小的数据,这个时候已经没有空闲空间了,当我们再插入数据的时候,ArrayList 会申请一个 1.5GB 大小的存储空间,并且把原来那 1GB 的数据拷贝到新申请的空间上。听起来是不是就很耗时?

解答开篇

好了,关于链表的知识我们就讲完了。

我们现在回过头来看下开篇留给你的思考题。如何基于链表实现 LRU 缓存淘汰算法?

我的思路是这样的:(创建一个有序单链表,当有一个新的数据被访问时,从链表头开始遍历链表,如果已存在,则删除再插入到头,如果不存在,判断链表是否满了,没满直接插入头部,满了则先删除链表尾结点,再将新结点插入到头)

我们维护一个有序单链表,越靠近链表尾部的结点是越早之前访问的。

当有一个新的数据被访问时,我们从链表头开始顺序遍历链表。

  1. 如果此数据之前已经被缓存在链表中了,我们遍历得到这个数据对应的结点,并将其从原来的位置删除,然后再插入到链表的头部。
  2.  如果此数据没有在缓存链表中,又可以分为两种情况:
  • 如果此时缓存未满,则将此结点直接插入到链表的头部;
  • 如果此时缓存已满,则链表尾结点删除,将新的数据结点插入链表的头部。

这样我们就用链表实现了一个 LRU 缓存,是不是很简单?现在我们来看下缓存访问的时间复杂度是多少。因为不管缓存有没有满,我们都需要遍历一遍链表,所以这种基于链表的实现思路,缓存访问的时间复杂度为 O(n)。实际上,我们可以继续优化这个实现思路,比如引入散列表(Hash table)来记录每个数据的位置,将缓存访问的时间复杂度降到 O(1)。因为要涉及我们还没有讲到的数据结构,所以这个优化方案,我现在就不详细说了,等讲到散列表的时候,我会再拿出来讲。除了基于链表的实现思路,实际上还可以用数组来实现 LRU 缓存淘汰策略。如何利用数组实现 LRU 缓存淘汰策略呢?我把这个问题留给你思考。

 

补充:“数组简单易用,在实现上使用的是连续的内存空间,可以借助 CPU 的缓存机制,预读数组中的数据,所以访问效率更高。而链表在内存中并不是连续存储,所以对 CPU 缓存不友好,没办法有效预读。”

CPU在从内存读取数据的时候,会先把读取到的数据加载到CPU的缓存中。而CPU每次从内存读取数据并不是只读取那个特定要访问的地址,而是读取一个数据块(这个大小我不太确定。。)并保存到CPU缓存中,然后下次访问内存数据的时候就会先从CPU缓存开始查找,如果找到就不需要再从内存中取。这样就实现了比内存访问速度更快的机制,也就是CPU缓存存在的意义:为了弥补内存访问速度过慢与CPU执行速度快之间的差异而引入。

对于数组来说,存储空间是连续的,所以在加载某个下标的时候可以把以后的几个下标元素也加载到CPU缓存这样执行速度会快于存储空间不连续的链表存储。

0 15

说到数组,我一向自认为熟知其概念,操作,特性,但是最近看到的一个问题却把我难住了,那就是,为什么数组下标从0开始而不是从1开始?

带着这个疑问,结合王争老师的《数据结构与算法》来重新剖析数组这种数据结构

 

如何实现随机访问?

一、为什么数组可以实现随机访问(1.线性表 2.连续空间春初相同类型的数据)

数组(Array)是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据

这个定义里有几个关键词,理解了这几个关键词,我想你就能彻底掌握数组的概念了。

第一是线性表(Linear List)。顾名思义,线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。

其实除了数组,链表、队列、栈等也是线性表结构。而与它相对立的概念是非线性表,比如二叉树、堆、图等。之所以叫非线性,是因为,在非线性表中,数据之间并不是简单的前后关系。

第二个是连续的内存空间和相同类型的数据。

正是因为这两个限制,它才有了一个堪称“杀手锏”的特性:“随机访问”。但有利就有弊,这两个限制也让数组的很多操作变得非常低效,比如要想在数组中删除、插入一个数据,为了保证连续性,就需要做大量的数据搬移工作。

数组的两个限制分别为:

  1. 线性表
  2. 连续的内存空间和相同类型的数据

 

二、数组是如何实现根据下标随机访问数组元素的?(原理  内存偏移公式)

我们拿一个长度为 10 的 int 类型的数组 int[] a = new int[10]来举例。

在我画的这个图中,计算机给数组 a[10],分配了一块连续内存空间 1000~1039,其中,内存块的首地址为 base_address = 1000。我们知道,计算机会给每个内存单元分配一个地址,计算机通过地址来访问内存中的数据。当计算机需要随机访问数组中的某个元素时,它会首先通过下面的寻址公式,计算出该元素存储的内存地址:a[i]_address = base_address + i * data_type_size其中 data_type_size 表示数组中每个元素的大小。我们举的这个例子里,数组中存储的是 int 类型数据,所以 data_type_size 就为 4 个字节。这个公式非常简单,我就不多做解释了。

三、数组的查找时间复杂度为O(1)吗?

我在面试的时候,常常会问数组和链表的区别,很多人都回答说,“链表适合插入、删除,时间复杂度 O(1);数组适合查找,查找时间复杂度为 O(1)”。实际上,这种表述是不准确的。数组是适合查找操作,但是查找的时间复杂度并不为 O(1)。即便是排好序的数组,你用二分查找,时间复杂度也是 O(logn)。所以,正确的表述应该是,数组支持随机访问,根据下标随机访问的时间复杂度为O(1)

 

数组的低效插入和删除(低效均是因为数据偏移)

插入操作

假设数组的长度为 n,现在,如果我们需要将一个数据插入到数组中的第 k 个位置。为了把第 k 个位置腾出来,给新来的数据,我们需要将第 k~n 这部分的元素都顺序地往后挪一位。那插入操作的时间复杂度是多少呢?你可以自己先试着分析一下。如果在数组的末尾插入元素,那就不需要移动数据了,这时的时间复杂度为 O(1)。但如果在数组的开头插入元素,那所有的数据都需要依次往后移动一位,所以最坏时间复杂度是 O(n)。 因为我们在每个位置插入元素的概率是一样的,所以平均情况时间复杂度为 (1+2+…n)/n=O(n)。

插入操作的时间复杂度应该区分数组中的数据是否有序(二者可以采取的策略不同)

如果数组中的数据是有序的,我们在某个位置插入一个新的元素时,就必须按照刚才的方法搬移 k 之后的数据。

但是,如果数组中存储的数据并没有任何规律,数组只是被当作一个存储数据的集合。在这种情况下,如果要将某个数据插入到第 k 个位置,为了避免大规模的数据搬移,我们还有一个简单的办法就是,直接将第 k 位的数据搬移到数组元素的最后,把新的元素直接放入第 k 个位置。为了更好地理解,我们举一个例子。假设数组 a[10]中存储了如下 5 个元素:a,b,c,d,e。我们现在需要将元素 x 插入到第 3 个位置。我们只需要将 c 放入到 a[5],将 a[2]赋值为 x 即可。最后,数组中的元素如下: a,b,x,d,e,c。

在这种特定情况下,即数据无序,插入第K位的元素,时间复杂度可以降低到O(1),此思想在快速排序中也会用到!!!

 

删除操作

删除操作为什么要数据迁移?(避免出现空洞)

删除操作搬移数据是为了避免出现空洞!

跟插入数据类似,如果我们要删除第 k 个位置的数据,为了内存的连续性,也需要搬移数据,不然中间就会出现空洞,内存就不连续了。和插入类似,如果删除数组末尾的数据,则最好情况时间复杂度为 O(1);如果删除开头的数据,则最坏情况时间复杂度为 O(n);平均情况时间复杂度也为 O(n)。

如何提高删除效率?(先标记,再删除,减少数据迁移的次数,与JVM垃圾回收机制相似)

实际上,在某些特殊场景下,我们并不一定非得追求数组中数据的连续性。如果我们将多次删除操作集中在一起执行,删除的效率是不是会提高很多呢?我们继续来看例子。数组 a[10]中存储了 8 个元素:a,b,c,d,e,f,g,h。现在,我们要依次删除 a,b,c 三个元素。

为了避免 d,e,f,g,h 这几个数据会被搬移三次,我们可以先记录下已经删除的数据。每次的删除操作并不是真正地搬移数据,只是记录数据已经被删除。当数组没有更多空间存储数据时,我们再触发执行一次真正的删除操作,这样就大大减少了删除操作导致的数据搬移。

如果你了解 JVM,你会发现,这不就是 JVM 标记清除垃圾回收算法的核心思想吗?没错,数据结构和算法的魅力就在于此,很多时候我们并不是要去死记硬背某个数据结构或者算法,而是要学习它背后的思想和处理技巧,这些东西才是最有价值的。如果你细心留意,不管是在软件开发还是架构设计中,总能找到某些算法和数据结构的影子。

警惕数组的访问越界问题

在Java语言中,当数组出现越界时,会出现异常 在c语言中,数组出现越界时,一样可以访问;ArrayIndexOutOfBoundsException 属于 运行期错误,而不属于编译期错误.

 

容器能否完全替代数组?

针对数组类型,很多语言都提供了容器类,比如 Java 中的 ArrayList、C++ STL 中的 vector。

在项目开发中,什么时候适合用数组,什么时候适合用容器呢?

这里我拿 Java 语言来举例。如果你是 Java 工程师,几乎天天都在用 ArrayList,对它应该非常熟悉。那它与数组相比,到底有哪些优势呢?我个人觉得,ArrayList 最大的优势就是可以将很多数组操作的细节封装起来。比如前面提到的数组插入、删除数据时需要搬移其他数据等。另外,它还有一个优势,就是支持动态扩容

数组本身在定义的时候需要预先指定大小,因为需要分配连续的内存空间。如果我们申请了大小为 10 的数组,当第 11 个数据需要存储到数组中时,我们就需要重新分配一块更大的空间,将原来的数据复制过去,然后再将新的数据插入。

如果使用 ArrayList,我们就完全不需要关心底层的扩容逻辑,ArrayList 已经帮我们实现好了。每次存储空间不够的时候,它都会将空间自动扩容为 1.5 倍大小。(JDK1.8,初始大小为10个)

不过,这里需要注意一点,因为扩容操作涉及内存申请和数据搬移,是比较耗时的。

使用ArrayList如果能事先确定数据大小能省掉很多次的内存申请和数据迁移操作

所以,如果事先能确定需要存储的数据大小,最好在创建 ArrayList 的时候事先指定数据大小。比如我们要从数据库中取出 10000 条数据放入 ArrayList。我们看下面这几行代码,你会发现,相比之下,事先指定数据大小可以省掉很多次内存申请和数据搬移操作。

 

容器和数组对比总结(极致性能则使用数组,否则使用容器)

1.Java ArrayList 无法存储基本类型,比如 int、long,需要封装为 Integer、Long 类,而 Autoboxing、Unboxing 则有一定的性能消耗,所以如果特别关注性能,或者希望使用基本类型,就可以选用数组。自动拆箱,装箱需要读写内存,而基本数据类型只需要使用寄存器,寄存器比内存快一个级别)

2. 如果数据大小事先已知,并且对数据的操作非常简单,用不到 ArrayList 提供的大部分方法,也可以直接使用数组。3. 还有一个是我个人的喜好,当要表示多维数组时,用数组往往会更加直观。比如 Object[][] array;而用容器的话则需要这样定义:ArrayList<arraylist

我总结一下,对于业务开发,直接使用容器就足够了,省时省力。毕竟损耗一丢丢性能,完全不会影响到系统整体的性能。但如果你是做一些非常底层的开发,比如开发网络框架,性能的优化需要做到极致,这个时候数组就会优于容器,成为首选。

 

解答开篇(1.根据内存偏移计算公式,从1开始要多做一次减法 2.历史原因)

现在我们来思考开篇的问题:为什么大多数编程语言中,数组要从 0 开始编号,而不是从 1 开始呢?

从数组存储的内存模型上来看,“下标”最确切的定义应该是“偏移(offset)”。前面也讲到,如果用 a 来表示数组的首地址,a[0]就是偏移为 0 的位置,也就是首地址,a[k]就表示偏移 k 个 type_size 的位置,所以计算 a[k]的内存地址只需要用这个公式:a[k]_address = base_address + k * type_size但是,如果数组从 1 开始计数,那我们计算数组元素 a[k]的内存地址就会变为:a[k]_address = base_address + (k-1)*type_size对比两个公式,我们不难发现,从 1 开始编号,每次随机访问数组元素都多了一次减法运算,对于 CPU 来说,就是多了一次减法指令。

数组作为非常基础的数据结构,通过下标随机访问数组元素又是其非常基础的编程操作,效率的优化就要尽可能做到极致。所以为了减少一次减法操作,数组选择了从 0 开始编号,而不是从 1 开始。不过我认为,上面解释得再多其实都算不上压倒性的证明,说数组起始编号非 0 开始不可。

所以我觉得最主要的原因可能是历史原因。C 语言设计者用 0 开始计数数组下标,之后的 Java、JavaScript 等高级语言都效仿了 C 语言,或者说,为了在一定程度上减少 C 语言程序员学习 Java 的学习成本,因此继续沿用了从 0 开始计数的习惯。实际上,很多语言中数组也并不是从 0 开始计数的,比如 Matlab。甚至还有一些语言支持负数下标,比如 Python。

数组的遍历 485、495、414、628
统计数组中的元素 645、697、448、442、41、274
数组的改变、移动 453、665、283

485:

难度简单131收藏分享切换为英文接收动态反馈给定一个二进制数组, 计算其中最大连续1的个数。

示例 1:

输入: [1,1,0,1,1,1]
输出: 3
解释: 开头的两位和最后的三位都是连续1,所以最大连续1的个数是 3.

class Solution {
  public int findMaxConsecutiveOnes(int[] nums) {
      int maxC=0;
      int C=0;
      for(int i=0;i<nums.length;i++){
          if(nums[i]==1){
              C++;//记录个数;
          }
          else{
              maxC=Math.max(maxC,C);//取到大数;
              C=0;//遇到0则清零;
          }
      }
      return  Math.max(maxC,C);//最后的连续1未在比较;
  }
}
495:

难度中等114收藏分享切换为英文接收动态反馈在《英雄联盟》的世界中,有一个叫 “提莫” 的英雄,他的攻击可以让敌方英雄艾希(编者注:寒冰射手)进入中毒状态。现在,给出提莫对艾希的攻击时间序列和提莫攻击的中毒持续时间,你需要输出艾希的中毒状态总时长。

你可以认为提莫在给定的时间点进行攻击,并立即使艾希处于中毒状态。

示例1:
输入: [1,4], 2
输出: 4
原因: 第 1 秒初,提莫开始对艾希进行攻击并使其立即中毒。中毒状态会维持 2 秒钟,直到第 2 秒末结束。
第 4 秒初,提莫再次攻击艾希,使得艾希获得另外 2 秒中毒时间。
所以最终输出 4 秒。
示例2:
输入: [1,2], 2
输出: 3
原因: 第 1 秒初,提莫开始对艾希进行攻击并使其立即中毒。中毒状态会维持 2 秒钟,直到第 2 秒末结束。
但是第 2 秒初,提莫再次攻击了已经处于中毒状态的艾希。
由于中毒状态不可叠加,提莫在第 2 秒初的这次攻击会在第 3 秒末结束。
所以最终输出 3 。
提示:
你可以假定时间序列数组的总长度不超过 10000。
你可以假定提莫攻击时间序列中的数字和提莫攻击的中毒持续时间都是非负整数,并且不超过 10,000,000。
class Solution {
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        //前元素起始+中毒时长<=后元素,则时长为duration*元素个数;
        //前元素起始+中毒时长>后元素,则时长为<=的个数*duration+大于的时长;
        int i=0,end=0,add=duration;
        if(timeSeries.length==0){
            return 0;
        }
        if(timeSeries.length==1){
            return duration;
        }
        for(i=1;i<timeSeries.length;i++){
            end=timeSeries[i-1]+duration;
            if(end<=timeSeries[i]){
                add+=duration;
            }
            else{
                add+=(timeSeries[i]+duration-end);
            }
        }
        return add;
    }
}
414:

给定一个非空数组,返回此数组中第三大的数。如果不存在,则返回数组中最大的数。要求算法时间复杂度必须是O(n)。

示例 1:
输入: [3, 2, 1]
输出: 1
解释: 第三大的数是 1.
示例 2:
输入: [1, 2]
输出: 2
解释: 第三大的数不存在, 所以返回最大的数 2 .
示例 3:
输入: [2, 2, 3, 1]
输出: 1
解释: 注意,要求返回第三大的数,是指第三大且唯一出现的数。
存在两个值为2的数,它们都排第二。
class Solution {
    private long MIN = Long.MIN_VALUE;    // MIN代表没有在值
    public int thirdMax(int[] nums) {
 if (nums == null || nums.length == 0) throw new RuntimeException(“nums is null or length of 0”);//特殊判断;
int n=nums.length;
int one =nums[0];
long two=MIN;
long three=MIN;
for(int i=1;i<n;i++){
      int now=nums[i];
      if(now==one||now==two||now==three)continue;
      if(now>one){
             three=two;
             two=one;
            one=now;
      }
     if(now>two){
            three=two;
            two=now;
     }
     if(now>threee){
            three=now;
     }
}
if(three==MIN)return one//不存在三个不相同的数;
return (int )three;
}
}
628:

难度简单181收藏分享切换为英文接收动态反馈给定一个整型数组,在数组中找出由三个数组成的最大乘积,并输出这个乘积。

示例 1:
输入: [1,2,3]
输出: 6
示例 2:
输入: [1,2,3,4]
输出: 24
注意:
给定的整型数组长度范围是[3,104],数组中所有的元素范围是[-1000, 1000]。
输入的数组中任意三个数的乘积不会超出32位有符号整数的范围。
//排序;
public class Solution {
    public int maximumProduct(int[] nums) {
         Array.sort(nums);
         return    (nums[0]*nums[1]*nums[length-1],nums[length-3]*nums[length-2]*nums[length-3]);//要么是最小的负数*第二小的负数*最大的正数,要么是最大的正数*第二大的正数*第三大的正数;
}
}

645:

错误的集合难度简单127收藏分享切换为英文接收动态反馈集合 S 包含从1到 n 的整数。不幸的是,因为数据错误,导致集合里面某一个元素复制了成了集合里面的另外一个元素的值,导致集合丢失了一个整数并且有一个元素重复。

给定一个数组 nums 代表了集合 S 发生错误后的结果。你的任务是首先寻找到重复出现的整数,再找到丢失的整数,将它们以数组的形式返回。

示例 1:
输入: nums = [1,2,2,4]
输出: [2,3]
注意:
给定数组的长度范围是 [2, 10000]。
 给定的数组是无序的。
//哈希表;
class Solution {
    public int[] findErrorNums(int[] nums) {
        int[] counter = new int[nums.length+1];
        for (int i: nums) {
            counter[i]++;
        }
        int[] result = new int[2];
        for (int i = 1; i<counter.length; i++) {
            if (counter[i] == 0) {
                result[1] = i;
            } else if (counter[i] == 2) {
                result[0] = i;
            }
        }
        return result;
    }
}
//排序;
public class Solution {
    public int[] findErrorNums(int[] nums) {
        Arrays.sort(nums);
        int dup = -1, missing = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i – 1])
                dup = nums[i];
            else if (nums[i] > nums[i – 1] + 1)
                missing = nums[i – 1] + 1;
        }
        return new int[] {dup, nums[nums.length – 1] != nums.length ? nums.length : missing};
    }
}
//位运算;
697:

数组的度难度简单175收藏分享切换为英文接收动态反馈给定一个非空且只包含非负数的整数数组 nums, 数组的度的定义是指数组里任一元素出现频数的最大值。

你的任务是找到与 nums 拥有相同大小的度的最短连续子数组,返回其长度。

示例 1:
输入: [1, 2, 2, 3, 1]
输出: 2
解释:
输入数组的度是2,因为元素1和2的出现频数最大,均为2.
连续子数组里面拥有相同度的有如下所示:
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
最短连续子数组[2, 2]的长度为2,所以返回2.
示例 2:
输入: [1,2,2,3,1,4,2]
输出: 6
注意:
nums.length 在1到50,000区间范围内。
nums[i] 是一个在0到49,999范围内的整数。
//哈希表的思想,边遍历边记录,次数=度数的可能不止一个,应当注意选取其中最小的
int findShortestSubArray(int* nums, int numsSize){
    int mark[50000]={0},start[50000]={0},end[500000]={0};
    int i;
    int count=0,min;
    for(i=0;i<numsSize;i++)
    {
        mark[nums[i]]++;//记录度
        if(mark[nums[i]]>count)
        count=mark[nums[i]];//记下最大的度
        if(mark[nums[i]]==1)//第一次出现,需要设置起点
        {
            start[nums[i]]=i;
            end[nums[i]]=i;
        }
        else if(mark[nums[i]]>1)//非第一次出现
        end[nums[i]]=i;
    }
    min=50000;//寻找最大
    for(i=0;i<50000;i++)
    {
        if(mark[i]==count)//判断符合要求的
            if(end[i]-start[i]<min)
                min=end[i]-start[i];
    }
        min++;
    return min;
}
448.

找到所有数组中消失的数字难度简单479收藏分享切换为英文接收动态反馈给定一个范围在  1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组,数组中的元素一些出现了两次,另一些只出现一次。

找到所有在 [1, n] 范围之间没有出现在数组中的数字。

您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。

示例:
输入:
[4,3,2,7,8,2,3,1]
输出:
[5,6]
//标记出现了的元素,与未出现的分开,并且利用下标从0到n-1,而值为1到n此条件;
class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        for(int i=0;i<nums.length;i++){
            int newIndex = Math.abs(nums[i]) – 1;
            if(nums[newIndex]>0)
            nums[newIndex]*=-1;//将值-1作为对应的下标;
        }
        List<Integer> result = new LinkedList<Integer>();
        // Iterate over the numbers from 1 to N and add all those
        // that have positive magnitude in the array
        for (int i = 1; i <= nums.length; i++) {  
            if (nums[i – 1] > 0) {
                result.add(i);
            }
        }
        return result;
    }

}

442:

数组中重复的数据难度中等286收藏分享切换为英文接收动态反馈给定一个整数数组 a,其中1 ≤ a[i] ≤ n (n为数组长度), 其中有些元素出现两次而其他元素出现一次。

找到所有出现两次的元素。

你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗?

示例:
输入:
[4,3,2,7,8,2,3,1]
输出:
[2,3]
//使用额外空间则哈希表,不允许的话则使用下标条件;
class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < nums.length; ++i) {
            int index = Math.abs(nums[i])-1;
            if (nums[index] < 0)
                res.add(Math.abs(index+1));
            nums[index] = -nums[index];
        }
        return res;
    }
}
41. 缺失的第一个正数难度困难820收藏分享切换为英文接收动态反馈给你一个未排序的整数数组,请你找出其中没有出现的最小的正整数。
示例 1:
输入: [1,2,0]
输出: 3
示例 2:
输入: [3,4,-1,1]
输出: 2
示例 3:
输入: [7,8,9,11,12]
输出: 1
//不允许使用额外空间,并且时间复杂度要控制在O(n),只能使用下标这个条件,以及元素自我标记;
/*class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            if (nums[i] <= 0) {
                nums[i] = n + 1;
            }
        }
        for (int i = 0; i < n; ++i) {
            int num = Math.abs(nums[i]);
            if (num <= n) {
                nums[num – 1] = -Math.abs(nums[num – 1]);
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return n + 1;
    }
}*/
class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] – 1] != nums[i]) {
                int temp = nums[nums[i] – 1];
                nums[nums[i] – 1] = nums[i];
                nums[i] = temp;
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }
}
 

661. 图片平滑器

难度简单

包含整数的二维矩阵 M 表示一个图片的灰度。你需要设计一个平滑器来让每一个单元的灰度成为平均灰度 (向下舍入) ,平均灰度的计算是周围的8个单元和它本身的值求平均,如果周围的单元格不足八个,则尽可能多的利用它们。

示例 1:

输入:
[[1,1,1],
 [1,0,1],
 [1,1,1]]
输出:
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]]
解释:
对于点 (0,0), (0,2), (2,0), (2,2): 平均(3/4) = 平均(0.75) = 0
对于点 (0,1), (1,0), (1,2), (2,1): 平均(5/6) = 平均(0.83333333) = 0
对于点 (1,1): 平均(8/9) = 平均(0.88888889) = 0

注意:

  1. 给定矩阵中的整数范围为 [0, 255]。
  2. 矩阵的长和宽的范围均为 [1, 150]。
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** imageSmoother(int** M, int MSize, int* MColSize, int* returnSize, int** returnColumnSizes){
    if (MSize == 1 && *MColSize == 1){
        *returnSize = 1;
        ** returnColumnSizes = 1;
        return M;
    }
    int **res = (int**)malloc(sizeof(int*)*MSize);
    *returnSize = MSize;
    for (int i = 0; i < MSize; i++){
        res[i] = (int*)malloc(sizeof(int)*(*MColSize));
        (*returnColumnSizes)[i] = *MColSize;
    }
    for (int i = 0; i < MSize; i++)
        for (int j = 0; j < *MColSize; j++)
            if (MSize == 1)
                res[i][j] = M[i][j];
            else if (i == 0 && MSize>1)
                res[i][j] = M[i][j] + M[i + 1][j];
            else if (i != 0 && i + 1 < MSize)
                res[i][j] = M[i][j] + M[i – 1][j] + M[i + 1][j];
            else if (i != 0 && i + 1 == MSize)
                res[i][j] = M[i][j] + M[i – 1][j];  
    for (int i = 0; i < MSize; i++)
        for (int j = 0; j < *MColSize; j++)
            if (*MColSize == 1)
                M[i][j] = res[i][j];
            else if (j == 0 && *MColSize>1)
                M[i][j] = res[i][j] + res[i][j + 1];
            else if (j != 0 && j + 1 < *MColSize)
                M[i][j] = res[i][j] + res[i][j – 1] + res[i][j + 1];
            else if (j != 0 && j + 1 == *MColSize)
                M[i][j] = res[i][j] + res[i][j – 1];        
    for (int i = 0; i < MSize; i++)
        for (int j = 0; j < *MColSize; j++)
            if ((MSize == 1 || *MColSize == 1) && (i + j == 0 || i + j + 2 == MSize + *MColSize))
                res[i][j] = M[i][j] / 2;
            else if ((MSize == 1 || *MColSize == 1) && (i + j > 0 && i + j + 2 < MSize + *MColSize))
                res[i][j] = M[i][j] / 3;
            else if ((MSize > 1 && *MColSize > 1) && ((i + j == 0) || (i + j + 2 == MSize + *MColSize) || (i == 0 && j == *MColSize – 1) || (i == MSize – 1 && j == 0)))
                res[i][j] = M[i][j] / 4;
            else if ((MSize > 2 && *MColSize > 2) && (i > 0 && i < MSize – 1 && j>0 && j < *MColSize – 1))
                res[i][j] = M[i][j] / 9;
            else
                res[i][j] = M[i][j] / 6;    
    return res;
}

给你一份旅游线路图,该线路图中的旅行线路用数组 paths 表示,其中 paths[i] = [cityAi, cityBi] 表示该线路将会从 cityAi 直接前往 cityBi 。请你找出这次旅行的终点站,即没有任何可以通往其他城市的线路的城市。
题目数据保证线路图会形成一条不存在循环的线路,因此只会有一个旅行终点站。
示例 1:
输入:paths = [[“London”,”New York”],[“New York”,”Lima”],[“Lima”,”Sao Paulo”]]
输出:”Sao Paulo”
解释:从 “London” 出发,最后抵达终点站 “Sao Paulo” 。本次旅行的路线是 “London” -> “New York” -> “Lima” -> “Sao Paulo” 。
解题思路:比较两个字符串使用strcmp函数
char *destCity(char ***paths, int pathsSize, int *pathsColSize)
{
    int i, j;
    int flag;            // 是否终点城市标记
    for (i = 0; i < pathsSize; i++) {
        flag = 0;
        for (j = 0; j < pathsSize; j++) {
            if (strcmp(paths[i][1],paths[j][0])==0) {/*字符串比较要用strcmp函数,而不能使用path[i][1]==paths[j][0];
            因为字符串二维数组是如下定义:
            char c[3][8]={“apple”,”orange”,”banana”}
            等价于char c[3][8]={{“apple”},{“orange”},{“banana”}};
            3表示行,每一行只有一个字符串;
            8表示列,也就是每个字符串的最大长度;
            详情见:  http://c.biancheng.net/view/273.html
            */
                flag = 1; // 标记为1,表示在起点城市中可以找到
            }
        }
        if (flag == 0) {
            return paths[i][1];
        }
    }
    
    // 返回NULL,该句很重要,不然编译有误:control reaches end of non-void function
    return NULL;
}

/输入一个整型数组,数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
示例1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
提示:
1 <= arr.length <= 10^5
-100 <= arr[i] <= 100

解题思路:https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/solution/mian-shi-ti-42-lian-xu-zi-shu-zu-de-zui-da-he-do-2/

动态规划是本题的最优解法,以下按照标准流程解题。
动态规划解析:
状态定义: 设动态规划列表 dpdpdp ,dp[i]dp[i]dp[i] 代表以元素 nums[i]nums[i]nums[i] 为结尾的连续子数组最大和。
为何定义最大和 dp[i]dp[i]dp[i] 中必须包含元素 nums[i]nums[i]nums[i] :保证 dp[i]dp[i]dp[i] 递推到 dp[i+1]dp[i+1]dp[i+1] 的正确性;如果不包含 nums[i]nums[i]nums[i] ,递推时则不满足题目的 连续子数组 要求。
转移方程: 若 dp[i−1]≤0dp[i-1] \leq 0dp[i−1]≤0 ,说明 dp[i−1]dp[i – 1]dp[i−1] 对 dp[i]dp[i]dp[i] 产生负贡献,即 dp[i−1]+nums[i]dp[i-1] + nums[i]dp[i−1]+nums[i] 还不如 nums[i]nums[i]nums[i] 本身大。
当 dp[i−1]>0dp[i – 1] > 0dp[i−1]>0 时:执行 dp[i]=dp[i−1]+nums[i]dp[i] = dp[i-1] + nums[i]dp[i]=dp[i−1]+nums[i] ;
当 dp[i−1]≤0dp[i – 1] \leq 0dp[i−1]≤0 时:执行 dp[i]=nums[i]dp[i] = nums[i]dp[i]=nums[i] ;
初始状态: dp[0]=nums[0]dp[0] = nums[0]dp[0]=nums[0],即以 nums[0]nums[0]nums[0] 结尾的连续子数组最大和为 nums[0]nums[0]nums[0] 。
返回值: 返回 dpdpdp 列表中的最大值,代表全局最大值。
 空间复杂度降低:
由于 dp[i]dp[i]dp[i] 只与 dp[i−1]dp[i-1]dp[i−1] 和 nums[i]nums[i]nums[i] 有关系,因此可以将原数组 numsnumsnums 用作 dpdpdp 列表,即直接在 numsnumsnums 上修改即可。
由于省去 dpdpdp 列表使用的额外空间,因此空间复杂度从 O(N)O(N)O(N) 降至 O(1)O(1)O(1) 。
复杂度分析:
时间复杂度 O(N)O(N)O(N) : 线性遍历数组 numsnumsnums 即可获得结果,使用 O(N)O(N)O(N) 时间。
空间复杂度 O(1)O(1)O(1) : 使用常数大小的额外空间。

动态规划,小试牛刀,感谢楼主。
1.状态,即子问题。
dp[i] 代表以元素 nums[i] 为结尾的连续子数组最大和。

2.转移策略,自带剪枝。
若 dp[i−1]≤0 ,说明 dp[i−1] 对 dp[i] 产生负贡献,即 dp[i−1]+nums[i] 还不如 nums[i] 本身大。

3.状态转移方程,根据前两步抽象而来。

  • 当 dp[i−1]>0 时:执行 dp[i] = dp[i-1] + nums[i];
  • 当 dp[i−1]≤0 时:执行 dp[i] = nums[i] ;

4.设计dp数组,保存子问题的解,避免重复计算

5.实现代码

整个动态规划,最难的就是定义状态。一旦状态定义出来,表明你已经抽象出了子问题,可以肢解原来的大问题了。

贪心算法+分治算法https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/solution/tan-xin-fen-zhi-dong-tai-gui-hua-fa-by-luo-jing-yu/

[et_pb_section admin_label=”section”]
[et_pb_row admin_label=”row”]
[et_pb_column type=”4_4″]
[et_pb_text admin_label=”Text”]

A 和 B 在一个 3 x 3 的网格上玩井字棋。
井字棋游戏的规则如下:
玩家轮流将棋子放在空方格 (” “) 上。
第一个玩家 A 总是用 “X” 作为棋子,而第二个玩家 B 总是用 “O” 作为棋子。
“X” 和 “O” 只能放在空方格中,而不能放在已经被占用的方格上。
只要有 3 个相同的(非空)棋子排成一条直线(行、列、对角线)时,游戏结束。
如果所有方块都放满棋子(不为空),游戏也会结束。
游戏结束后,棋子无法再进行任何移动。
给你一个数组 moves,其中每个元素是大小为 2 的另一个数组(元素分别对应网格的行和列),它按照 A 和 B 的行动顺序(先 A 后 B)记录了两人各自的棋子位置。
如果游戏存在获胜者(A 或 B),就返回该游戏的获胜者;如果游戏以平局结束,则返回 “Draw”;如果仍会有行动(游戏未结束),则返回 “Pending”。
你可以假设 moves 都 有效(遵循井字棋规则),网格最初是空的,A 将先行动。
方法一:模拟
我们可以模拟数组 move 中的每一步落子。我们使用两个集合 A 和 B 存放每位玩家当前已经落子的位置,并用集合 wins 存放棋子排成一条直线的所有情况(排成一行或一列各有 3 种,排成对角线有 2 种,总计 8 种)。当某位玩家落子时,我们枚举 wins 中的每一种情况,并判断该玩家是否将棋子落在了这些位置。如果满足了其中一种情况,则该玩家获胜。
如果直到落子完毕仍然没有玩家获胜,那么根据数组 move 的长度返回平局 Draw 或游戏未结束 Pending。
示例 1:
输入:moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
输出:”A”
解释:”A” 获胜,他总是先走。
“X  ”    “X  ”    “X  ”    “X  ”    “X  ”
”   ” -> ”   ” -> ” X ” -> ” X ” -> ” X ”
”   ”    “O  ”    “O  ”    “OO ”    “OOX”
char * tictactoe(int** moves, int movesSize, int* movesColSize){
    // 将 moves 填入虚拟棋盘, a 为 -1 , b 为 1
    int s[3][3] = {0};
    for (int i = 0; i < movesSize; i++) {
        int x = moves[i][0], y = moves[i][1];
        if (i & 1) s[x][y]++;//按位与判断奇,偶数;第一个i为0,则第一步必将是0,e也就是执行s[x][y]–,即实现了b先走;
        else s[x][y]–;
    }
    // 对角线判断
    int sumD1 = s[0][0] + s[1][1] + s[2][2];
    int sumD2 = s[0][2] + s[1][1] + s[2][0];
    if (sumD1 ==  3 || sumD2 ==  3) return “B”;
    if (sumD1 == -3 || sumD2 == -3) return “A”;
    // 横向、纵向判断
    for (int i = 0; i < 3; i++) {
        int sumR = s[i][0] + s[i][1] + s[i][2];
        int sumC = s[0][i] + s[1][i] + s[2][i];
        if (sumR ==  3 || sumC ==  3) return “B”;
        if (sumR == -3 || sumC == -3) return “A”;
    }
    // 无胜者情况
    return movesSize < 9 ? “Pending” : “Draw”;
}

[/et_pb_text]
[/et_pb_column]
[/et_pb_row]
[/et_pb_section]

平面上有 n 个点,点的位置用整数坐标表示 points[i] = [xi, yi]。请你计算访问所有这些点需要的最小时间(以秒为单位)。
你可以按照下面的规则在平面上移动:
每一秒沿水平或者竖直方向移动一个单位长度,或者跨过对角线(可以看作在一秒内向水平和竖直方向各移动一个单位长度)。
必须按照数组中出现的顺序来访问这些点。
示例 1:
输入:points = [[1,1],[3,4],[-1,0]]
输出:7
解释:一条最佳的访问路径是: [1,1] -> [2,2] -> [3,3] -> [3,4] -> [2,3] -> [1,2] -> [0,1] -> [-1,0]
从 [1,1] 到 [3,4] 需要 3 秒
从 [3,4] 到 [-1,0] 需要 4 秒
一共需要 7 秒
解题思路:坐标轴上两点的最短距离为切比雪夫距离
方法一:切比雪夫距离
对于平面上的两个点 x = (x0, x1) 和 y = (y0, y1),设它们横坐标距离之差为 dx = |x0 – y0|,纵坐标距离之差为 dy = |x1 – y1|,对于以下三种情况,我们可以分别计算出从 x 移动到 y 的最少次数:
dx < dy:沿对角线移动 dx 次,再竖直移动 dy – dx 次,总计 dx + (dy – dx) = dy 次;
dx == dy:沿对角线移动 dx 次;
dx > dy:沿对角线移动 dy 次,再水平移动 dx – dy 次,总计 dy + (dx – dy) = dx 次。
可以发现,对于任意一种情况,从 x 移动到 y 的最少次数为 dx 和 dy 中的较大值 max(dx, dy),这也被称作 x 和 y 之间的 切比雪夫距离。
由于题目要求,需要按照数组中出现的顺序来访问这些点。因此我们遍历整个数组,对于数组中的相邻两个点,计算出它们的切比雪夫距离,所有的距离之和即为答案。
int minTimeToVisitAllPoints(int** points, int pointsSize, int* pointsColSize){
   int sum=0;//总和
   int a,b;//两点x、y距离
   for(int i=0;i<pointsSize-1;i++){
       a=abs(points[i][0]-points[i+1][0]);
       b=abs(points[i][1]-points[i+1][1]);
       sum+=abs(a-b);
       if(a>b) sum+=b;
       else sum+=a;
   }
   *pointsColSize=sum;
   return sum;
}

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如,输入字符串”abcdefg”和数字2,该函数将返回左旋转两位得到的结果”cdefgab”。
示例 1:
输入: s = “abcdefg”, k = 2
输出: “cdefgab”
示例 2:
输入: s = “lrloseumgh”, k = 6
输出: “umghlrlose”
解题思路:数组元素的下标变换;利用传递的n作为作为划分点;将其划分为两部分,前后同时进行存入;在同时满足条件时才跳出;达到一次循环结束,最大的循环次数为俩部分中的长度最大值;
//双指针;
char* reverseLeftWords(char* s, int n){
char *arry;
int sum ,m1,m ,i=0 ,j;
    sum=strlen(s);//strlen求其长度;
    j=sum-1;//下标;
arry=malloc(sizeof(int)*(sum+1));
    arry[sum]=’\0′;//字符串数组最后是’\0′
m=n-1;  //向前的指针;
m1=n;  //向后的指针;
while(m1<sum || 0<=m ){
if(0<=m){
arry[j]=s[m];
j–;
m–;
}
if(m1<sum){
arry[i]=s[m1];
i++;
m1++;
}
}
return arry;
}