算法训练营-第一周-数组链表
2020-08-23 本文已影响0人
我是阿喵酱
一.时间复杂度&空间复杂度
常见的时间复杂度
- 常量 O(1)
- 对数 O(logn)
- 线性 O(n)
- 二维 O(n2)
- 指数 O(2n)
- 阶乘 O(n!)
常见的空间复杂度
- 常量 O(1)
- 线性 O(n)
- 二维 O(n2)
- 递归 O(n) n为递归深度
二.数组
定义
数组是相同变量组成的有序集合
图示
<img src="https://hexo-1257630696.cos.ap-singapore.myqcloud.com/img/640" alt="img" style="zoom:33%;" />
实战题目
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
图示
<img src="https://hexo-1257630696.cos.ap-singapore.myqcloud.com/img/640" alt="img" style="zoom:33%;" />
实战题目
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链表
<img src="https://hexo-1257630696.cos.ap-singapore.myqcloud.com/img/640" alt="img" style="zoom: 33%;" />
四.栈
定义
栈是一种线性逻辑结构，栈的元素只能后进先出。最早进入的元素存放的位置叫做栈底，最后进入的元素存放的位置叫栈顶。
图示
<img src="https://hexo-1257630696.cos.ap-singapore.myqcloud.com/img/_CopyPix_4_2.png" alt="img" style="zoom: 50%;" />
栈的实现
数组实现：
<img src="https://hexo-1257630696.cos.ap-singapore.myqcloud.com/img/640" alt="img" style="zoom:33%;" />
链表实现：
<img src="https://hexo-1257630696.cos.ap-singapore.myqcloud.com/img/640" alt="img" style="zoom:33%;" />
实战题目
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
队列的实现
数组实现：
<img src="https://hexo-1257630696.cos.ap-singapore.myqcloud.com/img/640" alt="img" style="zoom:33%;" />
链表实现：
<img src="https://hexo-1257630696.cos.ap-singapore.myqcloud.com/img/640" alt="img" style="zoom:33%;" />
实战题目
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;
}
}
*/
[参考资料]
2.极客时间-算法训练营
3.极客时间-数据结构与算法之美
