算法训练营-第一周-数组链表

一.时间复杂度&空间复杂度

常见的时间复杂度

常量 O(1)
对数 O(logn)
线性 O(n)
二维 O(n²)
指数 O(2ⁿ)
阶乘 O(n!)

常见的空间复杂度

常量 O(1)
线性 O(n)
二维 O(n²)
递归 O(n) n为递归深度

二.数组

定义

数组是相同变量组成的有序集合

图示

实战题目

283. 移动零

1.两次遍历 2.快慢指针

/*
    将数组中的0移动到最后，保持原来的非零数字的顺序。
        要求不能开辟新数组。
        方法一：
            两次遍历。第一次一边统计0的个数，一遍将非0数放在后面。index记录非0数索引位。
            第二次遍历将后面的数变为0。
            time:  O(n)
            space: O(1)
        方法二：背这个
            快慢指针。ab指针都从0出发，a先走，如果a不为0，就将ab交换。
            time:  O(n)
            space: O(1)
*/


// 方法1，两次遍历。
// class Solution {
//     public void moveZeroes(int[] nums) {
//       int index = 0;
//       for(int num:nums){
//           if(num!=0){
//               nums[index++]=num;
//           }
//       }
//       while(index<nums.length){
//           nums[index++] = 0;
//       }
//     }
// }


// 方法二，快慢指针。
// class Solution {
//     public void moveZeroes(int[] nums) {
//         for (int i = 0, j = 0; i < nums.length; i++) if (nums[i] != 0) nums[j] = nums[i] ^ nums[j] ^ (nums[i] = nums[j++]);
//     }
// }


// 将0移到最左边，一行代码
class Solution {
    public void moveZeroes(int[] a) {
        for (int i = 0, j = 0; i < a.length; i++) if (a[i] != 0) a[j] = a[i] ^ a[j] ^ (a[i] = a[j++]);
    }
}

11. 盛最多水的容器

左右双指针

// 双指针 时间复杂度O(n) 空间复杂度O(1)
class Solution {
    public int maxArea(int[] nums) {
        int maxArea = 0, left = 0, right = nums.length - 1;
        while(left < right) {
            int h = nums[left] < nums[right] ? nums[left++] : nums[right--];               
            maxArea = Math.max(maxArea, h * (right-left + 1)); // 因为上面向中间移动了一次，所以要加一
        }
        return maxArea;
    }
}

15. 三数之和

排序+双指针

// a + b = -c
// 方法一：暴力求解，三重循环 时间复杂度O(n3) 空间复杂度O(1)
// 方法二：两重循环 + hash。判断a+b的负值是否在哈希里面。 时间复杂度O(n2)
// 方法三：排序 + 双指针，排序后夹逼 时间复杂度 O(n2) 空间复杂度 O(logn) 


class Solution {
    public List<List<Integer>> threeSum(int[] a) {
        Arrays.sort(a);
        List<List<Integer>> res = new LinkedList<>();
        for (int i = 0; i < a.length - 2; i++)
            if (i == 0 || (i > 0 && a[i] != a[i - 1])) {
                int x = i + 1, y = a.length - 1;
                while (x < y) {
                    int sum = a[i] + a[x] + a[y];
                    while (x < y && a[x] == a[x + 1]) x++;
                    while (x < y && a[y] == a[y - 1]) y--;
                    if (sum == 0) { res.add(Arrays.asList(a[i], a[x], a[y])); x++; y--; } 
                    else if (sum < 0) x++;
                    else y--;
                }
            }
        return res;
    }
}

26. 删除排序数组中的重复项

快慢指针

/*
    题目：在不创建新数组的条件下，在原数组中删除重复出现的数字。
    PS:数组是引用传递的，传递的是数组的头节点。对数组的修改会对调用者产生影响。
    !只修改前几个数就可以了
    方法一：快慢指针。题目中的数组是排序过了的，不需要单独排序。如果没排序过就Arrays.sort()
        left慢指针，right快指针。
        left左边是处理过的，right右边是未处理过的。
        由right遍历一遍数组。left记录下一个没有重复的数放置的位置。
    时间复杂度：O(n)
    空间复杂度：O(1)    
*/



// 两个关键点，有序，结果只要长度
class Solution {
    public int removeDuplicates(int[] a) {
        int i = 0;
        for (int j = 1; j < a.length; j++) if(a[i] != a[j]) a[++i] = a[j];
        return i + 1;
    }
}

941. 有效的山脉数组

一次遍历，模拟爬山

class Solution {
    public boolean validMountainArray(int[] a) {
        if(a.length < 3) return false;
        int i = 0;
        // 上山
        while(i < a.length - 1 && a[i+1] > a[i]) i++;
        if(i == 0 || i == a.length - 1) return false;
        while( i < a.length - 1 && a[i+1] < a[i]) i++;
        return i == a.length - 1;
    }
}

189. 旋转数组

三次反转

/*
    1.暴力遍历。
        时间复杂度O(n)，空间复杂度O(1)
    2.公式法。 因子 是 a,b,c,根号n,k/c,k/b,k/a。
        只要遍历1-根号n。再从根号n遍历到1。       
        时间复杂度O(logn)，空间复杂度O(1)
*/
// class Solution {
//     public int kthFactor(int n, int k) {
//         int cnt = 0;
//         for (int factor = 1; factor <= n; factor++) {
//             if (n % factor == 0) {
//                 cnt++;
//                 if (cnt == k) return factor;
//             }  
//         }
//         return -1;
//     }
// }
class Solution {
    public int kthFactor(int n, int k) {
        int cnt = 0, i;
        for (i = 1; i * i <= n; i++) { // 1 - 根号n
            if (n % i == 0) {
                cnt++;
                if (cnt == k) return i;
            }
        }
        i--;
        if (i * i == n) i--; // 重复计算情况需要减一个 根号n - 1。求他对应的因子
        while (i > 0) {
            if (n % i == 0) { //
                cnt++;
                if (cnt == k) return n / i;
            }
            i--;
        }
        return -1;
    }
}

三.链表

定义

单向链表包含两个部分，一是保存的数据data，一是指向下一个的指针next

图示

实战题目

160. 相交链表

双指针

public class Solution {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}

21. 合并两个有序链表

递归


class Solution {
    public 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(l1, l2.next);
            return l2;
        }
    }
}

数组VS链表

四.栈

定义

栈是一种线性逻辑结构，栈的元素只能后进先出。最早进入的元素存放的位置叫做栈底，最后进入的元素存放的位置叫栈顶。

图示

栈的实现

数组实现：

链表实现：

实战题目

20. 有效的括号

栈

// 方法一：暴力法。不断地replace匹配到的括号，直到替换为空String
// 死循环，找到能匹配的括号。一轮一轮的找。O(n^2)
// 方法二：用栈。如果是左括号，就压进去，如果是右括号，就匹配。正负抵消掉。把栈顶元素移出。
class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        char[] chars = s.toCharArray();
        for (char c : chars) {
            switch (c) {
                case '(': stack.push(')'); break;
                case '[': stack.push(']'); break;
                case '{': stack.push('}'); break; 
                default : if (stack.isEmpty() || stack.pop() != c) return false;
            }
        }
        return stack.isEmpty();
    }
}

155. 最小栈

栈

class MinStack {
    int min = Integer.MAX_VALUE;
    Stack<Integer> stack = new Stack<Integer>();
    public void push(int x) {
        //当前值更小
        if(x <= min){   
            //将之前的最小值保存
            stack.push(min);
            //更新最小值
            min=x;
        }
        stack.push(x);
    }


    public void pop() {
        //如果弹出的值是最小值，那么将下一个元素更新为最小值
        if(stack.pop() == min) {
            min=stack.pop();
        }
    }


    public int top() {
        return stack.peek();
    }


    public int getMin() {
        return min;
    }
}

84. 柱状图中最大的矩形

栈

/* 
1.暴力
 for i -> 0, n-2
    for j -> i+1, n-1
        (i, j) -> 最小高度，area
        update max=area
 O(n^3)
2.暴力加速 O(n^2)
    for i -> 0, n-1:
        找到左边界，右边界。（保持高度的左右最大化边界
        area = height[i] * (right - left)
        update max=area                                                                      
3.用栈 O(n)
    维护一个栈，从小到大排列的。
    先放-1。放入一个值，第二个值比第一个值小，说明第一个值找到了边界，弹出。      
*/
class Solution {
    public int largestRectangleArea(int[] heights) {
        int max = 0;
        int len = heights.length;
        for (int i = 0; i < len; i++) {
            int left = i, right = i;
            int count = 1;
            while (--left >= 0 && heights[left] >= heights[i]) {
                count++;
            }
            while (++right < len && heights[right] >= heights[i]) {
                count++;
            }
            max = Math.max(max, count * heights[i]);
        }
        return max;
    }
}

五.队列

定义

队列是线性逻辑结构，后进后出。出口叫队头，入口叫队尾。

图示

img

队列的实现

数组实现：

链表实现：

实战题目

239. 滑动窗口最大值

双端队列

/*
    有一个滑动窗口，每次向右启动，取出滑动窗口中的最大值，输出数组
        题目要求线性时间复杂度，只能用双端队列


    1.暴力。for i -> 0, n-3
                for j -> 0, 3
                    求出最大值
        时间复杂度O(n * k)
        空间复杂度O(n − k + 1)
    2.双端队列
        出入队列就可以了。
        新的元素进来，更大，其他的元素就可以出去了。
        时间复杂度O(n)
        空间复杂度O(n)
    3.维护一个最大堆
        会超时，不能使用    
*/


public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0) return nums;
        // 结果数组
        int[] res = new int[nums.length - k + 1];
        // 双端队列，维护一个左大右小，最多k个数的双端队列
        LinkedList<Integer> dq = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            // 迭代器到达目标位置。移动一次，删一个左边元素。最左边的元素
            if (!dq.isEmpty() && dq.getFirst() <= i - k) {
                dq.pollFirst();
            }
            // 如果新元素比右边的大，删除右边的元素
            while (!dq.isEmpty() && nums[i] >= nums[dq.peekLast()]) {
                dq.pollLast();
            }
            // 加入新元素
            dq.add(i);
            // 到达指定位置，将左边最大值放入数组中
            if (i + 1 >= k) {
                res[i +1 - k] = nums[dq.getFirst()];
            }
        }
        return res;
    }
}



/* 用最大堆会超时
public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        // assume nums is not null
        if (nums.length == 0 || k == 0) {
            return new int[0];
        }
        int n = nums.length;
        int[] result = new int[n - k + 1]; // number of windows
        // 创建最大堆
        PriorityQueue<Integer> maxPQ = new PriorityQueue<>((o1, o2) -> (o2 - o1));
        for (int i = 0; i < n; i++) {
            int start = i - k;
            if (start >= 0) {
                maxPQ.remove(nums[start]);
            }
            maxPQ.offer(nums[i]);
            // 当装满后，开始取值
            if (maxPQ.size() == k) {
                result[i - k + 1] = maxPQ.peek();
            }
        }
        return result;
    }
}
*/

[参考资料]

1.快速入门数据结构和算法

2.极客时间-算法训练营

3.极客时间-数据结构与算法之美