一.時(shí)間復(fù)雜度&空間復(fù)雜度
常見的時(shí)間復(fù)雜度
- 常量 O(1)
- 對(duì)數(shù) O(logn)
- 線性 O(n)
- 二維 O(n2)
- 指數(shù) O(2n)
- 階乘 O(n!)
常見的空間復(fù)雜度
- 常量 O(1)
- 線性 O(n)
- 二維 O(n2)
- 遞歸 O(n) n為遞歸深度
二.數(shù)組
定義
數(shù)組是相同變量組成的有序集合
圖示
<img src="https://hexo-1257630696.cos.ap-singapore.myqcloud.com/img/640" alt="img" style="zoom:33%;" />
實(shí)戰(zhàn)題目
283. 移動(dòng)零
1.兩次遍歷 2.快慢指針
/*
將數(shù)組中的0移動(dòng)到最后，保持原來(lái)的非零數(shù)字的順序瓤湘。
要求不能開辟新數(shù)組猫胁。
方法一：
兩次遍歷礁鲁。第一次一邊統(tǒng)計(jì)0的個(gè)數(shù)，一遍將非0數(shù)放在后面芜辕。index記錄非0數(shù)索引位。
第二次遍歷將后面的數(shù)變?yōu)?。
time: O(n)
space: O(1)
方法二：背這個(gè)
快慢指針劣摇。ab指針都從0出發(fā)，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. 盛最多水的容器
左右雙指針
// 雙指針 時(shí)間復(fù)雜度O(n) 空間復(fù)雜度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)); // 因?yàn)樯厦嫦蛑虚g移動(dòng)了一次，所以要加一
}
return maxArea;
}
}
15. 三數(shù)之和
排序+雙指針
// a + b = -c
// 方法一：暴力求解，三重循環(huán) 時(shí)間復(fù)雜度O(n3) 空間復(fù)雜度O(1)
// 方法二：兩重循環(huán) + hash粹舵。判斷a+b的負(fù)值是否在哈希里面钮孵。 時(shí)間復(fù)雜度O(n2)
// 方法三：排序 + 雙指針，排序后夾逼 時(shí)間復(fù)雜度 O(n2) 空間復(fù)雜度 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. 刪除排序數(shù)組中的重復(fù)項(xiàng)
快慢指針
/*
題目：在不創(chuàng)建新數(shù)組的條件下眼滤，在原數(shù)組中刪除重復(fù)出現(xiàn)的數(shù)字巴席。
PS:數(shù)組是引用傳遞的，傳遞的是數(shù)組的頭節(jié)點(diǎn)诅需。對(duì)數(shù)組的修改會(huì)對(duì)調(diào)用者產(chǎn)生影響漾唉。
!只修改前幾個(gè)數(shù)就可以了
方法一：快慢指針。題目中的數(shù)組是排序過(guò)了的堰塌，不需要單獨(dú)排序赵刑。如果沒排序過(guò)就Arrays.sort()
left慢指針，right快指針场刑。
left左邊是處理過(guò)的般此，right右邊是未處理過(guò)的。
由right遍歷一遍數(shù)組牵现。left記錄下一個(gè)沒有重復(fù)的數(shù)放置的位置铐懊。
時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：O(1)
*/
// 兩個(gè)關(guān)鍵點(diǎn)，有序施籍，結(jié)果只要長(zhǎng)度
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. 有效的山脈數(shù)組
一次遍歷居扒，模擬爬山
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. 旋轉(zhuǎn)數(shù)組
三次反轉(zhuǎn)
/*
1.暴力遍歷。
時(shí)間復(fù)雜度O(n)丑慎，空間復(fù)雜度O(1)
2.公式法喜喂。 因子 是 a,b,c,根號(hào)n,k/c,k/b,k/a。
只要遍歷1-根號(hào)n竿裂。再?gòu)母?hào)n遍歷到1玉吁。
時(shí)間復(fù)雜度O(logn)，空間復(fù)雜度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 - 根號(hào)n
if (n % i == 0) {
cnt++;
if (cnt == k) return i;
}
}
i--;
if (i * i == n) i--; // 重復(fù)計(jì)算情況需要減一個(gè) 根號(hào)n - 1腻异。求他對(duì)應(yīng)的因子
while (i > 0) {
if (n % i == 0) { //
cnt++;
if (cnt == k) return n / i;
}
i--;
}
return -1;
}
}
三.鏈表
定義
單向鏈表包含兩個(gè)部分进副，一是保存的數(shù)據(jù)data，一是指向下一個(gè)的指針next
圖示
<img src="https://hexo-1257630696.cos.ap-singapore.myqcloud.com/img/640" alt="img" style="zoom:33%;" />
實(shí)戰(zhàn)題目
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. 合并兩個(gè)有序鏈表
遞歸
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2; // 一個(gè)為空悔常，另外一個(gè)接在最后
if (l2 == null) return l1;
if (l1.val < l2.val) { // 哪個(gè)值小影斑，哪個(gè)作為頭
l1.next = mergeTwoLists(l1.next, l2);
return l1;
}
else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}
數(shù)組VS鏈表
<img src="https://hexo-1257630696.cos.ap-singapore.myqcloud.com/img/640" alt="img" style="zoom: 33%;" />
四.棧
定義
棧是一種線性邏輯結(jié)構(gòu)，棧的元素只能后進(jìn)先出机打。最早進(jìn)入的元素存放的位置叫做棧底矫户，最后進(jìn)入的元素存放的位置叫棧頂。
圖示
<img src="https://hexo-1257630696.cos.ap-singapore.myqcloud.com/img/_CopyPix_4_2.png" alt="img" style="zoom: 50%;" />
棧的實(shí)現(xiàn)
數(shù)組實(shí)現(xiàn)：
<img src="https://hexo-1257630696.cos.ap-singapore.myqcloud.com/img/640" alt="img" style="zoom:33%;" />
鏈表實(shí)現(xiàn)：
<img src="https://hexo-1257630696.cos.ap-singapore.myqcloud.com/img/640" alt="img" style="zoom:33%;" />
實(shí)戰(zhàn)題目
20. 有效的括號(hào)
棧
// 方法一：暴力法残邀。不斷地replace匹配到的括號(hào)皆辽，直到替換為空String
// 死循環(huán)柑蛇，找到能匹配的括號(hào)。一輪一輪的找驱闷。O(n^2)
// 方法二：用棧耻台。如果是左括號(hào)，就壓進(jìn)去空另，如果是右括號(hào)盆耽，就匹配。正負(fù)抵消掉痹换。把棧頂元素移出征字。
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) {
//當(dāng)前值更小
if(x <= min){
//將之前的最小值保存
stack.push(min);
//更新最小值
min=x;
}
stack.push(x);
}
public void pop() {
//如果彈出的值是最小值，那么將下一個(gè)元素更新為最小值
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)
維護(hù)一個(gè)棧冯痢，從小到大排列的。
先放-1框杜。放入一個(gè)值浦楣，第二個(gè)值比第一個(gè)值小，說(shuō)明第一個(gè)值找到了邊界咪辱，彈出振劳。
*/
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;
}
}
五.隊(duì)列
定義
隊(duì)列是線性邏輯結(jié)構(gòu)，后進(jìn)后出油狂。出口叫隊(duì)頭历恐，入口叫隊(duì)尾。
圖示
img
隊(duì)列的實(shí)現(xiàn)
數(shù)組實(shí)現(xiàn)：
<img src="https://hexo-1257630696.cos.ap-singapore.myqcloud.com/img/640" alt="img" style="zoom:33%;" />
鏈表實(shí)現(xiàn)：
<img src="https://hexo-1257630696.cos.ap-singapore.myqcloud.com/img/640" alt="img" style="zoom:33%;" />
實(shí)戰(zhàn)題目
239. 滑動(dòng)窗口最大值
雙端隊(duì)列
/*
有一個(gè)滑動(dòng)窗口专筷，每次向右啟動(dòng)弱贼，取出滑動(dòng)窗口中的最大值，輸出數(shù)組
題目要求線性時(shí)間復(fù)雜度磷蛹，只能用雙端隊(duì)列
1.暴力吮旅。for i -> 0, n-3
for j -> 0, 3
求出最大值
時(shí)間復(fù)雜度O(n * k)
空間復(fù)雜度O(n ? k + 1)
2.雙端隊(duì)列
出入隊(duì)列就可以了。
新的元素進(jìn)來(lái)味咳，更大庇勃，其他的元素就可以出去了。
時(shí)間復(fù)雜度O(n)
空間復(fù)雜度O(n)
3.維護(hù)一個(gè)最大堆
會(huì)超時(shí)槽驶，不能使用
*/
public class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums.length == 0) return nums;
// 結(jié)果數(shù)組
int[] res = new int[nums.length - k + 1];
// 雙端隊(duì)列责嚷，維護(hù)一個(gè)左大右小，最多k個(gè)數(shù)的雙端隊(duì)列
LinkedList<Integer> dq = new LinkedList<>();
for (int i = 0; i < nums.length; i++) {
// 迭代器到達(dá)目標(biāo)位置捺檬。移動(dòng)一次再层，刪一個(gè)左邊元素贸铜。最左邊的元素
if (!dq.isEmpty() && dq.getFirst() <= i - k) {
dq.pollFirst();
}
// 如果新元素比右邊的大，刪除右邊的元素
while (!dq.isEmpty() && nums[i] >= nums[dq.peekLast()]) {
dq.pollLast();
}
// 加入新元素
dq.add(i);
// 到達(dá)指定位置聂受，將左邊最大值放入數(shù)組中
if (i + 1 >= k) {
res[i +1 - k] = nums[dq.getFirst()];
}
}
return res;
}
}
/* 用最大堆會(huì)超時(shí)
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
// 創(chuàng)建最大堆
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]);
// 當(dāng)裝滿后蒿秦，開始取值
if (maxPQ.size() == k) {
result[i - k + 1] = maxPQ.peek();
}
}
return result;
}
}
*/
[參考資料]
1.快速入門數(shù)據(jù)結(jié)構(gòu)和算法
2.極客時(shí)間-算法訓(xùn)練營(yíng)
3.極客時(shí)間-數(shù)據(jù)結(jié)構(gòu)與算法之美
