【216-week 01】第一周学习总结

[lyp305]

Week01总结：

• 数组

  随机访问的时间复杂度为 O(1)
  如果在数组的末尾插入元素，复杂度为 O(1)
  如果在开头 ，复杂度为 O(n)
  删除同插入

• 旋转数组

//挂起本次目标位元素
//降前一轮挂起元素 放入目标位
//目标位 = (起始位+ 移动位数) 同 长度 取模

`public class Solution {
    public void rotate(int[] nums, int k) {
        k = k % nums.length;  //考虑移动位数大于长度 so 取模 
        int count = 0; //转换次数不能超过数组长度
        for (int start = 0; count < nums.length; start++) { // 0位开始移动
            int current = start; // 起始位：0
            int prev = nums[start]; //初始化前一轮被复制(挂起)元素 ： 第0个
            do {
                    int next = (current + k) % nums.length;  // +k位坐标( 前一轮被复制元素的目标位置)  
                    int temp = nums[next];   //复制(挂起) 目标位置元素 
                          
                    nums[next] = prev;   //前一轮被复制元素 填入
                    prev = temp;    // 目标位置原有元素作为下一轮被移动(填入)元素
                    current = next;  //下一轮起始位
                    count++;
            } while (start != current);
        }
    }
}`

梳理逻辑的草图@_@

• 栈：

后进先出，简称LIFO结构
peek() 取得栈顶
pop() 取得栈顶并从栈中移除栈顶
push(E item) 入栈

• 接雨水

  `public int trap(int[] height) {

    int res = 0;
    Stack<Integer> stack = new Stack<Integer>();
    int index = 0;
    while (index < height.length) {
        while (stack.size() > 0 && height[index] > height[stack.peek()]) {
            //数组当前index下值>数组中栈顶元素对应值----》  确定一组边界
            int top = stack.pop();            //保存并弹出栈顶元素                                 
            if (stack.empty()) {
                break;
            }
            int h = Math.min(height[index], height[stack.peek()]) - height[top];
            //长度差=min(数组中index下值,数组中当前栈顶下值)-数组中当旧栈顶(top)下值
            //旧栈顶对应的一组边界的面积已经在旧栈顶入栈时计算，所以去和原栈顶的长度差？？
            int d = index - stack.peek() - 1; // 宽度=数组坐标差
  
            res = res + h * d;
        }
        stack.push(index++);
    }
    return res;
  

  }`

草图@_@

PriorityQueue 优先队列 有优先顺序的queue

• 优先队列的元素会根据构造时提供的Comparator进行排序
• 不能加入null和不能排序比较的Object
• 非线程安全 需要线程安全需使用PriorityBlockingQueue

poll() 取得并移除队列头部元素
peek() 取得但不移除队列头部元素
add() ,offer()
语义相同，都是向优先队列中插入元素 ,并按自然顺序或比较器Comparator的顺序排序
offer 插入失败时返回false
add插入失败时返回异常
插入或移除元素时 会对队列进行扩容 或减小size 并调用siftUp,siftDown重新调整排序