数据结构一：数据+链表（Datawhale 系列）-低调大师

数据结构一：数据+链表（Datawhale 系列）

2019-05-10 663

Task1.1 数组

1.1.1实现一个支持动态扩容的数组

    public class EnsureCapacityArray {

    private static final Object[] EMPTY_ELEMENTDATA = {};

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    
    transient Object[] elementData; 
    //传入固定值的情况
    public EnsureCapacityArray(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
    //没有传入数组大小的情况
    public EnsureCapacityArray() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    /**
     * 扩容
     * @param minCapacity
     */
    public void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    //数组容量最大的情况
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }
}

1.1.2 实现一个大小固定的有序数组，支持动态增删改操作

这里理解，大小固定的有序数组，那也就是说数组大小和内部的元素个数完全相同。那么增的时候，需要扩容，删的时候，需要减容。然后数组有序，也就是说，改的时候需要重新排序。

public class FixedArray{
    
    private static final int DEFAULT_SIZE = 10;
    private static final Object[] EMPTY_ELEMENTDATA = {};
    private static final Object[] DEFAULT_ELEMENTDATA = new Object[DEFAULT_SIZE];
    
    transient Object[] elementData;
    
    private int size;
    
    public FixedArray(){
        this.elementData=DEFAULT_ELEMENTDATA;
    }
    
    public FixedArray(int initialCapacity){
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
    //保证增和删时数组长度和元素长度一致
    private void ensureCapacityInternal(int minCapacity ){
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    public void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    //数组容量最大的情况
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }
    //去掉删除之后，重新排序的，空的数组
    public void trimToSize() {
        if (size < elementData.length) {
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size);
        }
    }
    //判断数组长度
    public int size(){
        return size;
    }
    //判断数组是否为空
    public boolean isEmpty() {
        return size == 0;
    }
    
    //排序
    @SuppressWarnings("unchecked")
    private <E> void sort() {
        Arrays.sort((E[]) elementData, 0, size);
    }
    
    //添加
    public <E> boolean add(E e) {
        ensureCapacityInternal(size + 1);  
        elementData[size++] = e;
        sort();
        return true;
    }
    //删除
    public <E> boolean remove(int index) {
        if (index >= size)
                throw new IndexOutOfBoundsException();
        
        System.arraycopy(elementData, index+1, elementData, index,
                size-1);
        size--;
        trimToSize();
        return true;
    }
    //改
    public <E> boolean set(int index,Object e) {  
        elementData[index] = e;
        sort();
        return true;
    }
    //查
    public Object get(int index) {     
        return elementData[index];
    }
}

1.1.3 合并两个有序的数组

public static int[] mergeArrays(int[]a ,int[]b){
        int alen=a.length;
        int blen=b.length;
        int aindex=0;
        int bindex=0;
        int [] re=new int[alen+blen];
        for(int i=0;i<alen+blen;i++){
            if(aindex<alen && bindex<blen){
                re[i]=a[aindex] > b[bindex] ? b[bindex++] :a[aindex++];
                continue;
            }
            if(aindex==alen && bindex<blen )
                re[i]=b[bindex++];
            if(bindex==blen &&aindex<alen)
                re[i]=a[aindex++];
        }
        return re;
    }

1.1.4学习哈希表思想，并完成leetcode上的两数之和(1)及Happy Number(202)！

哈希表

//两数之和
public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[] { map.get(complement), i };
        }
        map.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
}

//Happy Number(202)
class Solution {
    public boolean isHappy(int n) {
        if(n==1) return true;
        while(n!=1 && n!=4){
            int a=0;
            int ans=0;
            while(n>0){
                a=n%10;
                ans+=a*a;
                n /=10;
            }
            n=ans;
        }
        if(n==1) return true;
        else return false;
    }
}

1.1.5 练习

//Three Sum
public List<List<Integer>> threeSum(int[] num) {
    Arrays.sort(num);
    List<List<Integer>> res = new LinkedList<>(); 
    for (int i = 0; i < num.length-2; i++) {
        if (i == 0 || (i > 0 && num[i] != num[i-1])) {
            int lo = i+1, hi = num.length-1, sum = 0 - num[i];
            while (lo < hi) {
                if (num[lo] + num[hi] == sum) {
                    res.add(Arrays.asList(num[i], num[lo], num[hi]));
                    while (lo < hi && num[lo] == num[lo+1]) lo++;
                    while (lo < hi && num[hi] == num[hi-1]) hi--;
                    lo++; hi--;
                } else if (num[lo] + num[hi] < sum) lo++;
                else hi--;
           }
        }
    }
    return res;
}

//Majority Element
public int majorityElement(int[] nums) {
        int res=0;
        int cnt=0;
        for(int num:nums){
            if(cnt==0){
                res=num;
                ++cnt;
            }
            else if(num == res) ++cnt;
            else --cnt;
        }
        return res;
    }

//Missing Positive
 public int firstMissingPositive(int[] nums) {
       if(nums == null&&nums.length==0)
            return 1;
        int i;
        for(i=0;i<nums.length;i++){
           if(nums[i] != i+1){
               while(0<nums[i]&& nums[i] <= nums.length && nums[nums[i]-1] != nums[i]){
                   int temp = nums[i];
                    nums[i] = nums[nums[i]-1];
                    nums[temp-1] = temp;
               }
           }
       }
        for(i=0;i<nums.length;i++) {
            if(nums[i]!=i+1) {
                return i+1;
            }
        }
        return i+1;
    }

TASK1.2 链表

1.2.1 实现单链表、循环链表、双向链表，支持增删操作

//单链表
class singleNode{
    public int data;
    public singleNode next;
    
    public singleNode head =null;
    
    public singleNode(int data){
        this.data=data;
    }
    
    public void addNode(singleNode node){
        singleNode newNode = new singleNode(data);
        if(head == null){
            head = newNode;
            return;
        }
        singleNode temp = head;
        while(temp.next != null){
            temp = temp.next;
        }
        temp.next = newNode;
    }
    
    public boolean removeNode(int index){
        if(index<1 || index>length()){
            return false;
        }
        if(index == 1){//删除头结点
            head = head.next;
            return true;
        }
        singleNode preNode = head;
        singleNode curNode = preNode.next;
        int i = 1;
        while(curNode != null){
            if(i==index){//寻找到待删除结点
                preNode.next = curNode.next;//待删除结点的前结点指向待删除结点的后结点
                return true;
            }
            //当先结点和前结点同时向后移
            preNode = preNode.next;
            curNode = curNode.next;
            i++;
        }
        return true;
    }
     public int length(){
            int length = 0;
            singleNode curNode = head;
            while(curNode != null){
                length++;
                curNode = curNode.next;
            }
            return length;
     }
}

//双向链表
//单向循环链表类
public class CycleLinkList implements List {

    Node head; //头指针
    Node current;//当前结点对象
    int size;//结点个数
    
    //初始化一个空链表
    public CycleLinkList()
    {
        //初始化头结点，让头指针指向头结点。并且让当前结点对象等于头结点。
        this.head = current = new Node(null);
        this.size =0;//单向链表，初始长度为零。
        this.head.next = this.head;
    }
    
    //定位函数，实现当前操作对象的前一个结点，也就是让当前结点对象定位到要操作结点的前一个结点。
    //比如我们要在a2这个节点之前进行插入操作，那就先要把当前节点对象定位到a1这个节点，然后修改a1节点的指针域
    public void index(int index) throws Exception
    {
        if(index <-1 || index > size -1)
        {
          throw new Exception("参数错误！");    
        }
        //说明在头结点之后操作。
        if(index==-1)    //因为第一个数据元素结点的下标是0，那么头结点的下标自然就是-1了。
            return;
        current = head.next;
        int j=0;//循环变量
        while(current != head&&j<index)
        {
            current = current.next;
            j++;
        }
        
    }    
    
    @Override
    public void delete(int index) throws Exception {
        // TODO Auto-generated method stub
        //判断链表是否为空
        if(isEmpty())
        {
            throw new Exception("链表为空，无法删除！");
        }
        if(index <0 ||index >size)
        {
            throw new Exception("参数错误！");
        }
        index(index-1);//定位到要操作结点的前一个结点对象。
        current.setNext(current.next.next);
        size--;
    }

    @Override
    public Object get(int index) throws Exception {
        // TODO Auto-generated method stub
        if(index <-1 || index >size-1)
        {
            throw new Exception("参数非法！");
        }
        index(index);
        
        return current.getElement();
    }

    @Override
    public void insert(int index, Object obj) throws Exception {
        // TODO Auto-generated method stub
        if(index <0 ||index >size)
        {
            throw new Exception("参数错误！");
        }
        index(index-1);//定位到要操作结点的前一个结点对象。
        current.setNext(new Node(obj,current.next));
        size++;
    }

    @Override
    public boolean isEmpty() {
        // TODO Auto-generated method stub
        return size==0;
    }
    @Override
    public int size() {
        // TODO Auto-generated method stub
        return this.size;
    }
}

//双向循环链表
//单向链表类
public class DoubleCycleLinkList implements List {

    Node head; //头指针
    Node current;//当前结点对象
    int size;//结点个数

    //初始化一个空链表
    public DoubleCycleLinkList() {
        //初始化头结点，让头指针指向头结点。并且让当前结点对象等于头结点。
        this.head = current = new Node(null);
        this.size = 0;//单向链表，初始长度为零。
        this.head.next = head;
        this.head.prior = head;
    }

    //定位函数，实现当前操作对象的前一个结点，也就是让当前结点对象定位到要操作结点的前一个结点。
    public void index(int index) throws Exception {
        if (index < -1 || index > size - 1) {
            throw new Exception("参数错误！");
        }
        //说明在头结点之后操作。
        if (index == -1)
            return;
        current = head.next;
        int j = 0;//循环变量
        while (current != head && j < index) {
            current = current.next;
            j++;
        }

    }

    @Override
    public void delete(int index) throws Exception {
        // TODO Auto-generated method stub
        //判断链表是否为空
        if (isEmpty()) {
            throw new Exception("链表为空，无法删除！");
        }
        if (index < 0 || index > size) {
            throw new Exception("参数错误！");
        }
        index(index - 1);//定位到要操作结点的前一个结点对象。
        current.setNext(current.next.next);
        current.next.setPrior(current);
        size--;
    }

    @Override
    public Object get(int index) throws Exception {
        // TODO Auto-generated method stub
        if (index < -1 || index > size - 1) {
            throw new Exception("参数非法！");
        }
        index(index);

        return current.getElement();
    }

    @Override
    public void insert(int index, Object obj) throws Exception {
        // TODO Auto-generated method stub
        if (index < 0 || index > size) {
            throw new Exception("参数错误！");
        }
        index(index - 1);//定位到要操作结点的前一个结点对象。
        current.setNext(new Node(obj, current.next));
        current.next.setPrior(current);
        current.next.next.setPrior(current.next);

        size++;
    }

    @Override
    public boolean isEmpty() {
        // TODO Auto-generated method stub
        return size == 0;
    }

    @Override
    public int size() {
        // TODO Auto-generated method stub
        return this.size;
    }
}

1.2.2 实现单链表反转

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode p = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return p;
}

1.2.3 实现两个有序的链表合并为一个有序链表

 ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1 == NULL) return l2;  
        if(l2 == NULL) return l1;  
        if(l1->val < l2->val) {  
            l1->next = mergeTwoLists(l1->next, l2);  
            return l1;  
        } else {  
            l2->next = mergeTwoLists(l2->next, l1);  
            return l2;  
        }  
    }

1.2.4 实现求链表的中间结点

public ListNode middleNode(ListNode head) {
        ListNode fast=head;
        ListNode low=head;
        while(fast != null && fast.next != null){
            low = low.next;
            fast= fast.next.next;
        }
        return low;
    }

1.2.5 练习

//Linked List Cycle I（环形链表）
public boolean hasCycle(ListNode head) {
        ListNode f=head;
        ListNode s=head;
        if(head == null || head.next == null) return false;
        while(f!=null && f.next!=null){
            f=f.next.next;
            s=s.next;
            if(f == s) return true;
        }
        return false;
    }
//Merge k Sorted Lists（合并 k 个排序链表）
 public ListNode mergeKLists(ListNode[] lists){
        if(lists.length == 0)
            return null;
        if(lists.length == 1)
            return lists[0];
        if(lists.length == 2){
           return mergeTwoLists(lists[0],lists[1]);
        }

        int mid = lists.length/2;
        ListNode[] l1 = new ListNode[mid];
        for(int i = 0; i < mid; i++){
            l1[i] = lists[i];
        }

        ListNode[] l2 = new ListNode[lists.length-mid];
        for(int i = mid,j=0; i < lists.length; i++,j++){
            l2[j] = lists[i];
        }

        return mergeTwoLists(mergeKLists(l1),mergeKLists(l2));

    }
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;

        ListNode head = null;
        if (l1.val <= l2.val){
            head = l1;
            head.next = mergeTwoLists(l1.next, l2);
        } else {
            head = l2;
            head.next = mergeTwoLists(l1, l2.next);
        }
        return head;
    }

微信关注我们

原文链接：https://yq.aliyun.com/articles/702095

转载内容版权归作者及来源网站所有！

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

网站被提示该网站内容被禁止访问

很多建站公司都在使用Kindeditor开源的图片上传系统，该上传系统是可视化的，采用的开发语言支持asp、aspx、php、jsp,几乎支持了所有的网站可以使用他们的上传系统，对浏览器的兼容以及手机端也是比较不错的，用户使用以及编辑上传方面得到了很多用户的喜欢。前端时间我们SINE安全对其进行全面的网站漏洞检测的时候发现，Kindeditor存在严重的上传漏洞，很多公司网站，以及事业单位的网站都被上传违规内容，包括一些赌博的内容，从我们的安全监测平台发现，2019年3月份，4月份，5月份，利用Kindeditor漏洞进行网站攻击的情况，日益严重，有些网站还被阿里云拦截，并提示该网站内容被禁止访问，关于该网站漏洞的详情，我们来看下。很多被攻击的网站的后台使用的是Kindeditor编辑器并使用upliad_json组件来进行上传图片以及文档等文件，目前存在漏洞的版本是Kindeditor 4.1.5以下，漏洞发生的代码文件是在upload_json.php代码里，该代码并没有对用户上传的文件格式，以及大小进行安全检测，导致用户可以伪造恶意文件进行上传，尤其html文件可以直接上传到...

2019-05-11

576

1 面试题 redis都有哪些数据类型？分别在哪些场景下使用比较合适？ 2 考点分析除非是感觉看你简历，就是工作3年以内的比较初级的一个同学，可能对技术没有很深入的研究过，我才会问这类问题，在宝贵的面试时间里，我实在是不想多问其实问这个问题,主要就俩原因看看你到底有没有全面的了解redis有哪些功能，一般怎么来用，啥场景用什么，就怕你别就会最简单的kv操作看看你在实际项目里都怎么玩儿过redis 要是你回答的不好，没说出几种数据类型，也没说什么场景，你完了，面试官对你印象肯定不好，觉得你平时就是做个简单的set和get。 3 详解 3.1 string 这是最基本的类型了，没啥可说的，就是普通的set和get，做简单的kv缓存 3.2 hash 这个是类似map的一种结构，这个一般就是可以将结构化的数据，比如一个对象（前提是这个对象没嵌套其他的对

2019-05-11

611

资源下载

更多资源

优质分享App

近一个月的开发和优化，本站点的第一个app全新上线。该app采用极致压缩，本体才4.36MB。系统里面做了大量数据访问、缓存优化。方便用户在手机上查看文章。后续会推出HarmonyOS的适配版本。

Mario

马里奥是站在游戏界顶峰的超人气多面角色。马里奥靠吃蘑菇成长，特征是大鼻子、头戴帽子、身穿背带裤，还留着胡子。与他的双胞胎兄弟路易基一起，长年担任任天堂的招牌角色。

腾讯云软件源

为解决软件依赖安装时官方源访问速度慢的问题，腾讯云为一些软件搭建了缓存服务。您可以通过使用腾讯云软件源站来提升依赖包的安装速度。为了方便用户自由搭建服务架构，目前腾讯云软件源站支持公网访问和内网访问。

Rocky Linux

Rocky Linux（中文名：洛基）是由Gregory Kurtzer于2020年12月发起的企业级Linux发行版，作为CentOS稳定版停止维护后与RHEL（Red Hat Enterprise Linux）完全兼容的开源替代方案，由社区拥有并管理，支持x86_64、aarch64等架构。其通过重新编译RHEL源代码提供长期稳定性，采用模块化包装和SELinux安全架构，默认包含GNOME桌面环境及XFS文件系统，支持十年生命周期更新。