数据结构一:数据+链表 (Datawhale 系列)

  1. 云栖社区>
  2. 博客>
  3. 正文

数据结构一:数据+链表 (Datawhale 系列)

晓生寒 2019-05-11 14:19:28 浏览538
展开阅读全文

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;
    }

网友评论

登录后评论
0/500
评论
晓生寒
+ 关注