一、前言
之前一直想學習資料結構與算法，因為一直聽說這個很重要嘛，還有力扣這個網站那也是神交已久啊~~
但是又不敢接觸，因為恐懼嘛，害怕學不會，害怕被吊打~~~~~
後來遇到了一個大佬，算法大佬，超強的！
————
英雄哪裡出來我跟他聊了我的情況，他就推薦我開始刷力扣，刷簡單的，通過率高的，先培養習慣，興趣，信心。然後我就開始了！
小結計劃
這是我第一篇小結
以後每周一會做一篇周結
每月月結，同時删除周結
二、相關知識
1. 時間複雜度O()
算法的目的就是為了提高程式的效率，而在優化了程式後，表現最突出的就是程式的運作時間。
那麼測試我們的程式是否跑的更快了，難道掐秒計算嗎?
舉個例子：
程式優化完後，運作一結束。诶诶，快停，記錄時間！！看看快了沒!
而這個時間，為實際時間，也可以說是絕對時間，但是這個時間能被很多因素影響
而這個因素就有很多了，硬體，軟體，系統等…
是以進引入了相對時間的計時方法，也就是時間複雜度，來判斷我們的程式是否得到了優化
規定，一段程式的時間由時間複雜度來表示。
而時間複雜度又分為三種，最優情況，最劣情況，平均情況。而這個情況是由問題來決定的
比如：我們将某個正在軍訓的班級拉出來一排，一排五個人，讓他們從左到右依次報數(從1開始)
用這個數來代表他們本來的名字，作為代号
而我們需要找一個叫做張三的人
不過我們不能大聲問誰是張三，隻能根據代号挨個去問
如果張三的代号為1，那麼我們隻需要尋找一次就可以
如果為3那麼我們需要尋找3次
如果為5或者張三不在這一排，我們就必須查找5次才能得到結果
而這個第一種情況就是最優情況，為O(1)，第三種情況為最劣情況，也就是O(n)
通常使用最劣情況來表示一個程式的最終情況，也就是O()
一個簡單的指派語句，判斷語句的時間複雜度為O(1)，而不管你這個語句有多長，隻要他是切實能寫出來的次數，都是O(1)
循環語句根據循環的次數的變化而分為O(1)，O(N)，上面說過O(1)那麼O(n)就是循環的次數随着題目或者問題的改變而改變的，就屬于O(n)
而判斷整個程式時間複雜度的方法為，以時間複雜度最高的為主：也就是說，就算你指派了1000000個變量，而循環結果是随時間變化的，那麼你的程式的時間複雜度為：O(n)
因為随着循環次數的增加，也就是n->無窮大，你的變量數目，也會相對于n來說越來越小。
是以可以忽略不計，為O(1)*O(n)==O(n)
常見的時間複雜度：O(1)，O(logn)，O(n)，O(nlogn)，O(n*2)，O(2**n)O(n!)
按照從小到大的順序排列
2. 空間複雜度O()
空間複雜度也具有相同的概念，隻是有些地方變得不太一樣了
如果說時間還能掐秒計算時間，那麼占用空間就沒那麼好計算了，難不成，你去看看代碼多少航，行多的占用記憶體就大嗎？這也不是，有的代碼很少，但是需要占用的記憶體多，有的代碼看着很多，但是占用記憶體很小
空間複雜度是想對占用空間，比如說，你的程式建立100個變量接收了100個數字，字元串，在空間複雜度裡面屬于O(1)，而你建立一個數組，哈希表，棧等就是O(n)
三、刷題小結
自從開始刷力扣，也有些許日子了，從一開始的每日一題，到每日兩題，再到學習學到無聊的時候就去刷題，也算是經曆了一番蛻變。
從一開始的什麼都不懂，做題全靠暴力破解，但現在掌握了幾個方法。
也了解了一些關于資料結構與算法的小知識
學習新知識固然重要，但是也需要總結之前的知識，畢竟溫故而知新嘛
1. 二分法
二分查找法是一種算法
他經常用在：
給定一個升序的數組/清單和一個目标值，盡可能快的查找其中的目标值
若存在，傳回目标值得索引
若不存在，傳回-1
這樣的場景
相比于直接周遊整個數組，使用二分法無疑會讓我們的程式效率更高！
因為是升序的，是以我們可以以數組中間的元素為中線，将數組分為左右兩個數組
python代碼展示：
target = 7 # 給一個目标值
start = 0 # 用于計算中間值，和後面陸續的将數組劃分為兩個數組
end = len(li)-1 # 用于計算中間值，記錄清單最後值的索引
li = [1, 2, 3, 4, 5, 6 ,7, 8, 9, 10]
while start<end:
# 記錄一個循環
mid = (start+n)//2 # 值為4
"""
一個升序數組/清單
以中間mid（//是保持中間值為整數）為界限
看似分成兩個數組
li_left = [1， 2， 3 ，4， 5]
li_right = [6, 7, 8, 9, 10]
"""
if target>li[mid]:
# 如果目标值比中間值大，就說名目标值（7）在右邊的清單
start = mid+1 # 讓start變成右邊清單的第一個元素的索引
# 抛棄左邊的清單不要，隻看右邊的清單li_right = [6, 7, 8, 9, 10]
else:
# 如果目标值小于等于中間值，就說明目标值在左邊的清單
end = mid # 讓n變成左邊清單的最大值的索引
# 抛棄右邊的清單不要，隻看左邊的清單
print("mid的值就是目标值的索引：", mid)
# 運作結果為6 Java代碼：
public class Test{
public static void main(String[] args){
int[] aa = new int[]{1, 2, 3, 4, 5, 6 ,7, 8, 9, 10};
int target = 7; // 給一個目标值，查找目标值是否在數組中
int start = 0; // 用于計算中間值，和後面陸續的将數組劃分為兩個數組
int mid = 0; // 設定中間值周遊
int end = aa.length; // 用于計算中間值，記錄清單最後值的索引
while(start<end){ // 設定循環條件，當頭指針小于尾指針時終止循環
mid = (start+end)/2;
/*
一個升序數組/清單
以中間mid（//是保持中間值為整數）為界限
看似分成兩個數組
左邊是： [1， 2， 3 ，4， 5]
右邊是： [6, 7, 8, 9, 10]
*/
if (target>aa[mid]) start = mid+1; // 如果目标值比中間值大，就說名目标值（7）在右邊的清單,讓start變成右邊清單的第一個元素的索引
else end = mid; // 如果目标值小于等于中間值，就說明目标值在左邊的清單，讓end程式設計左邊清單的尾部
}
System.out.println("mid的值就是目标值在數組中的索引："+mid);
}
}
// 運作結果為6 随着循環的進行，清單會越來越小，最後隻剩目标值，然後最小值的索引就是我們需要的值
二分法時間複雜度分析：O(logn) 每次循環使數組長度減半，是以又被稱為折半查找法
直接周遊整個數組（暴力解法）時間複雜度分析：O(n)
2. 雙指針法
在我們的二分法中就是用了雙指針的方法，起始時一個指針指向數組的頭部，一個指針指向數組的尾部，使用這種方法會讓我們對數組的操作更加流暢一些。
雙指針法常常是用在：
查找某些元素時
力扣的第一道題就是一個經典的雙指針優化程式的題目
給你一個目标值和一個有序數組
找出數組中和為目标值的元素
傳回她們的下标
元素不能與自己相加
正常的做法是進行嵌套循環，挨個查找，這樣的時間複雜度為：O(n*2)
而如果使用雙指針的方法，結合二分法就能使時間複雜度降低到：O(logn)
周遊的方法就相當于一個人在找東西，雙指針的方法就好像是兩個人在找東西
打個例子：
我有一塊種着10棵樹的地
有人告訴我，你有一棵樹需要澆水了
如果隻有我自己（正常周遊）
并且我不需要跑到樹前面觀察才能判斷我的樹是否需要澆水
我隻能一棵一棵的找，然後判斷
而如果我有一個助手（雙指針）
我就可以縮短排查的時間
java：
public class Shuzu {
public static void main(String[] args) {
int target = 7;
int[] arr = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
System.out.println(ArrD(7,arr)+"\n"+ArrS(target,arr));
}
static int ArrD(int target, int[] arr) {
// 單指針
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) return i;
}
return -1;
}
static int ArrS(int target, int[] arr){
// 雙指針
int end = arr.length-1;
int start = 0;
while (start<end){
if (arr[start]==target) return start;
if (arr[end]==target) return end;
start++;
end--;
}
return -1;
}
}
py：
def ArrD(target, arr):
# 單指針
for i in range(len(arr)):
if arr[i]target: return i
return -1;
def ArrS(target, arr):
# 雙指針
start = 0
end = len(arr)-1
while start<end:
if arr[start]==target: return start
if arr[end]==target: return end
start+=1
end-=1
return end
target = 7
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
print(ArrD(target, arr), "\n", ArrS(target, arr)) 3. 遞歸
遞歸與其說是一種算法，不如說是一種思想。
它更類似于我們高中數學學過的數列的遞推推導式：A(n) = A(n-1)+5 首項為1
讓你通過這個式子計算第n項的值的話
你高中會使用它推導出一個通項公式，再将n代入求解
但是再計算機眼裡就不用這麼麻煩
你隻需要每次調用這個公式，然後計算出值就好
在程式設計語言裡就是 ：定義一個函數，調用自身，傳回結果就是遞歸
就相當于計算機幫你從1開始執行了很多遍的A(n) = A(n-1)+5
無限套娃？不不不，他還是有個限度的，沒法無限，哈哈哈
比如需要求A(5)，那麼就是：
A(5) = A(4)+5
A(4) = A(3)+5
A(3) = A(2)+5
A(2) = A(1)+5
A(1) = 3
A(5) = 3+5+5+5+5=23
代碼實作：
java代碼：
public class Digui {
public static void main(String[] args) {
int sum = Shu(5);
System.out.println(sum);
}
static int Shu(int n){
if (n<=1) return 3;
else return Shu(n-1)+5;
}
} py代碼：
def Shu(n:int)->int:
if n<=1: return 3
else: return Shu(n-1)+5
print(Shu(5)) 最後的計算結果是23
4. 數組
什麼是數組？數組就是存儲多個相同資料的集合，他們的記憶體位址是相鄰的，是以可以通過數組取值。
這麼說，是不是有點不好了解，那麼這樣呢？
我有一顆白菜，手拿着就能回家，那如果是十幾顆呢？
我就可以用麻袋！麻袋！裝進去，帶回家！是的你要存的資料就是白菜，而這個數組就是你要用的麻袋~~~~~
麻袋中的白菜怎麼拿出來我需要用的呢？
下标，數組中的下标是以0開始的，什麼是下标，就是你從0開始查，查到某個你要的資料，查到幾，下标就是幾，就相當于，我在裝白菜的時候，說“這是第0個白菜，這是第1個白菜…”，而他們也能聽懂（别管他們能不能聽懂，我說能就能，哈哈~~），等我需要哪一顆白菜的時候，喊一聲，他就自己跳出來了
當然我們的數組一般存儲的資料比較多，而計算機又不和人一樣能夠直接看到數組的全部元素，他隻記得裡面第一顆白菜的樣子，是以我們在查找某個元素，但是又不知道他在哪裡的時候，隻能通過周遊的手段來擷取了
周遊每一棵白菜，将他與我們需要找的白菜對比沒如果是就不找了，如果不是就繼續找。
具體的代碼形式我就不多說了，這個都是知道的。
5. 字元串
字元串是我們在程式設計語言裡面見到的第一個資料結構 hello world
當然，字元串不僅是我們滴各一人士的資料結構，也是我們在生活中用到最多的，比如我們網上聊天，就是字元串，看的小說，是字元串…
而有的字元擦混存儲在檔案中供計算機讀取，然後輸出到螢幕上給我們看。
字元串可以看成是一個字元型數組，但是又不盡相同
字元串可以周遊，查詢，拼接，但是不能修改
有的時候拼接用得好也能很大程度上降低我們解決問題的難度
我們可以通過運算符号對字元串進行
| 運算符 | 作用 | 執行個體 |
| + | 拼接字元串 | “a”+“a”=>“aa” |
| = | 指派字元串 | “a”=“b”=>“b” |
| == | 判斷字元串是否相等 | “a”==“b”=>false |
| [] | 通過下标擷取字元串中的字元 | “asd”[0]=>“a” |
說起字元串，能說的也可以很多，也可以很少
說多了有AI的NLP自然語言處理，K近鄰算法，正規表達式…
這裡就不多說了，先學會基本操作
6. 連結清單
連結清單是一種抽象的資料結構，他實際上是一個連結清單對象，頭結點就是這個連結清單對象，而連結清單的沒一個節點都是一個對象。
連結清單是一個不定長的線性表資料結構，連結清單沒有内置方法來擷取其長度，隻能通過周遊來獲得裡面的内容。
連結清單實作：
class ListNode{
public int val; // 存儲的值
public ListNode next; // 指向下一節點
public ListNode(int val){ // 構造函數/方法
this.val = val;
next = null;
}
} class ListNode:
def __init__(self,val): # 構造函數
self.val = val # 存儲的值
next = None # 指向下一節點 是的，連結清單就是這樣實作的。我們一般隻能拿到頭結點，然後通過判斷下一節點是否為空位限制條件來終止循環。
執行個體：
給你個連結清單[1, 2, 3, 4, 5]
求連結清單的長度
package com.example.demo;
public class ListNodeStudy {
public static void main(String[] args) {
ListNode h1 = new ListNode(1); // 1
ListNode h2 = new ListNode(2); // 2
ListNode h3 = new ListNode(3); // 3
ListNode h4 = new ListNode(4); // 4
ListNode h5 = new ListNode(5); // 5
h1.next = h2; // 下一節點
h2.next = h3; // 下一節點
h3.next = h4; // 下一節點
h4.next = h5; // 下一節點
// 題目的連結清單是這樣是實作的，不過不會讓你去實作，而是給你h1讓你來找長度
System.out.println(len(h1));
}
static int len(ListNode head){
int len = 0; // 為連結清單長度定義變量
while (head!=null){ // 周遊連結清單擷取長度
len++;
head = head.next;
}
return len;
}
}
class ListNode{
public int val; // 存儲的值
public ListNode next; // 指向下一節點
public ListNode(int val){ // 構造函數/方法
this.val = val;
next = null;
}
}
class ListNode:
def __init__(self, val): # 構造函數
self.val = val # 存儲的值
self.next = None # 指向下一節點
h1 = ListNode(1)
h2 = ListNode(2)
h3 = ListNode(3)
h4 = ListNode(4)
h5 = ListNode(5)
h1.next = h2
h2.next = h3
h3.next = h4
h4.next = h5
def ListNodeLen(head: ListNode) -> int:
len = 0
while head != None:
len += 1
head = head.next
return len
print(ListNodeLen(h1)) 三、結語
也許我學的慢，但是我始終都在進步！那我總有一天會成功。