讨论/《高频算法实战》 - 实现动态数组/
《高频算法实战》 - 实现动态数组
共 20 个回复
class LCArray {
    private int[] data;
    private int size;

    public LCArray() {
        data = new int[10];
        size = 0;
    }

    public void push_back(int n) {
        if (size == data.length) {
            resize(2 * data.length);
        }
        data[size++] = n;
    }

    private void resize(int capacity) {
        int[] newData = new int[capacity];
        System.arraycopy(data, 0, newData, 0, data.length);
        data = newData;
    }

    public void pop_back() {
        if (size > 0) {
            size--;
        }
    }

    public int size() {
        return size;
    }

    public int index(int idx) {
        if (idx < 0 || idx >= size) {
            throw new ArrayIndexOutOfBoundsException("数组索引越界异常");
        }
        return data[idx];
    }
}
8

没有标准答案吗

3

题目保证所给操作均合法。

故省去了对于非法输入的检查。

class LCArray {
private:
    int *arr;
    int sz, cap;

public:
    LCArray() {
        sz = 0;
        cap = 10;
        arr = new int[cap];
    }

    ~LCArray() {
        delete[] arr;
    }

    void push_back(int n) {
        if (sz >= cap) {
            cap <<= 1;
            int *newArr = new int[cap];
            memcpy(newArr, arr, sz * sizeof(int));
            delete[] arr;
            arr = newArr;
        }
        arr[sz] = n;
        sz += 1;
    }

    void pop_back() {
        sz -= 1;
    }

    int size() {
        return sz;
    }

    int index(int idx) {
        return arr[idx];
    }
};
3
class LCArray {
    int array[] = null;
    int cap;
    int curIndex = -1;
    public LCArray() {
        this.cap = 10;
        array = new int[cap];
    }
    public void push_back(int n) {
        if (size() == cap) {
            cap *= 2;
            array = Arrays.copyOf(array, cap);
        }
        array[++curIndex] = n;
    }

    public void pop_back() {
        curIndex--;
    }

    public int size() {
        return curIndex + 1;
    }

    public int index(int idx) {
        if(idx<0||idx>=size()){return -1;}
        return array[idx];
    }
}
3

python动态数组

class LCArray:

    def __init__(self):
        self.static_list = [-1]*10
        self.lsize = 0
        self.space = 10

    def push_back(self, n: int) -> None:
        if self.lsize == self.space: self.resize()
        self.static_list[self.lsize] = n
        self.lsize += 1

    def pop_back(self) -> None:
        if self.lsize > 0: self.lsize -= 1

    def size(self) -> int:
        return self.lsize

    def resize(self) -> None:
        self.space *= 2
        tmp_list = [-1] * self.space
        for i in range(self.lsize):
            tmp_list[i] = self.static_list[i]
        self.static_list = tmp_list

    def index(self, idx: int) -> int:
        if idx in range(0,self.lsize): return self.static_list[idx] 
        return -1
1

C语言, 16ms; 7.7 MB

#define NMAX 1000
typedef struct {
    int validSize;
    int stack[NMAX];
} LCArray;

LCArray* lCArrayCreate() {
    LCArray *array = (LCArray *)malloc(sizeof(LCArray));
    array->validSize = 0;
    return array;
}

void lCArrayPush_back(LCArray* obj, int n) {
    obj->stack[obj->validSize] = n;
    (obj->validSize)++;
}

void lCArrayPop_back(LCArray* obj) {
    (obj->validSize)--;
}

int lCArraySize(LCArray* obj) {
    return obj->validSize;
}

int lCArrayIndex(LCArray* obj, int idx) {
    return obj->stack[idx];
}

void lCArrayFree(LCArray* obj) {
    free(obj);
}

/**
 * Your LCArray struct will be instantiated and called as such:
 * LCArray* obj = lCArrayCreate();
 * lCArrayPush_back(obj, n);
 
 * lCArrayPop_back(obj);
 
 * int param_3 = lCArraySize(obj);
 
 * int param_4 = lCArrayIndex(obj, idx);
 
 * lCArrayFree(obj);
*/

C++动态数组

class LCArray {
private:
    int addlength;//添加数据,数组长度不都时,默认添加长度
    int length;//用户看得到的数组长度
    int* val;//动态数组
    int vallength;//实际已经申请的数组长度
public:
    LCArray() {
        val = new int[50];
        length = 0;
        addlength = 10;
        vallength = 50;
    }
    
    void push_back(int n) {
        if(length>=vallength)
        {
            int *arrayNew=new int[vallength+addlength];
            memcpy(arrayNew,val,vallength * sizeof(int));
            delete(val);
            val = arrayNew;
            vallength += addlength;
        }   
        val[length++]=n;
    }
    
    void pop_back() {
        if(length>0)
            length--;
    }
    int size() {
        return length;
    } 
    int index(int idx) {
        return val[idx];
    }
};

image.png

class LCArray {
    int m_index;
    int m_size;
    int* m_data;

public:
    LCArray() : m_index(0), m_size(10) {
        m_data = new int[m_size];
    } 
    
    ~LCArray() {
        delete[] m_data;
    }
    
    void push_back(int n) {
        if(m_index>=m_size){
            int* newData = new int[m_size*2];
            memcpy(newData, m_data, m_size*sizeof(int));
            delete[] m_data;
            m_data = newData;
            m_size *= 2;
        }
        m_data[m_index] = n;
        m_index++;
    }
    
    void pop_back() {
        m_index--;
    }
    
    int size() {
        return m_index;
    }
    
    int index(int idx) {
        if(idx<0 || idx>m_index)
            return -1;
        
        return m_data[idx];
    }
};

没看懂这个输入什么意思,输入两个数组,写出四个操作,输出一个数组?

class LCArray {
private:
    int *arr;
    int sz,length;

public:
    LCArray() {
      length=10;
      arr=new int[length];
      sz=0;
    }
    
    void push_back(int n) {
      if(sz>=length){
          int *arrayNew=new int[length*2];
          memcpy(arrayNew,arr,sz * sizeof(int));
          arr=arrayNew;
      }
      arr[sz]=n;
      sz++;
    }
    
    void pop_back() {
      sz--;
    }
    
    int size() {
      return sz;
    }
    
    int index(int idx) {
      return arr[idx];
    }
};

/**
 * Your LCArray object will be instantiated and called as such:
 * LCArray* obj = new LCArray();
 * obj->push_back(n);
 * obj->pop_back();
 * int param_3 = obj->size();
 * int param_4 = obj->index(idx);
 */

12ms,10.6MB