（一）drf基礎

全稱：django-rest framework

接口：什麼是接口、restful接口規範（協議）

CBV（基於FBV的基礎上形成）、CBV生命周期源碼—-基於restful規範下的CBV接口

請求生命周期：請求組件、解析組件、響應組件

序列化組件（序列化、反序列化簡單來說就是對象轉為字符串、字符串轉為對象，目的是為傳輸數據（傳給別的語言或者存儲））

三大認證（重中之重）：認證（用戶是否合法）、權限（管理員、普通用戶）、頻率（次數過多限制）

其他組件（過濾、篩選、排序、分頁、路由）

1.接口

概念：聯繫兩個物質的媒介，完成信息的交互。在web程序中，聯繫前台頁面與後台數據庫的媒介。

web接口組成：

url：長得像返回數據的url鏈接。如api.baidu.map/search

（www.baidu.com不叫接口，叫url鏈接，訪問只能拿到主頁。api.baidu.map/search是接口，返回的是json數據）

請求參數：前台按照指定的key提供數據給後台。（必須是給定的，這樣後台才能以此提取數據再到數據庫查詢返回）

響應數據：後台與數據庫交互后，將數據反饋給前台。

因此，接口就是帶着請求參數訪問能夠得到響應數據的url鏈接。

接口 = url + 請求參數 + 響應數據

2.restful接口規範

接口規範：不同後台語言，使用同樣的接口返回同樣的數據。

如何寫接口：要寫url和響應數據。如果將請求參數也加上，就是在寫接口文檔。

兩大部分：

（1）url

1）用api關鍵字標識接口url。方式1：api.baidu.com；方式2:www.baudu.com/api

2）接口數據安全性決定優先選用https協議。

3）如果一個接口有多版本存在，需要在url中標識體現。如下的v1和v2

api.baidu.com/v1/….  api.baidu.com/v2/….

4）操作中的數據稱為資源，在url中資源一般採用複數形式，一個接口可以概括對該資源的多種操作方式。（一個url對應一個類，類裏面可以有多個請求方法）

可以對操作隱藏，並且復用性更強（寫動作了，只能適用這一個動作，不寫其他動作都可以用）如api.baidu.com/books    api.baidu.com/books/(pk)

5）請求方式有多種，用一個url處理如何讓保證不混亂——通過不同的請求方式標識不同操作資源的方式

/books      get     獲取所有

/books post   增加一個（多個）

/books/(pk) delete 刪除一個

/books/(pk)  put 整體更新一個  #改一個用戶

/books/(pk)  patch 局部更新一個 #改一個用戶的密碼

6）資源往往涉及數據的各種操作方式：篩選、排序、限制

api.baidu.com/books/?search=寶馬&ordering=-price&limit=3

（2）響應數據

1）http請求的響應會有響應狀態碼，接口用來返回操作的資源數據，也有自己操作數據結果的資源狀態碼（status 0代表操作資源成功，1代表操作失敗，2代表操作成功，但沒匹配結果）

注：資源狀態碼和http狀態碼不一樣，為前後台的約定

2）資源狀態碼的文字提示。

status ok “賬號有誤或者密碼有誤”

3）資源本身

results

注:刪除資源成功不做任何數據返回（只返回空字符串，連狀態碼、狀態信息都不返回）

4）不能直接返回的資源（子資源、圖片、視頻等資源），返回該資源的url鏈接。

https://api.baidu.com/v1/books?limit=3
get|post|delete|put|patch   
{
　　“status” : 0,
　　“msg” : “ok”,
　　“results”: [
{
　　“title”: “三國”,
　　“price”: 78,
　　“img”: “https://.....”   
　　　　}
　　]
}

3.django流程

（1）項目準備：

from django.http import JsonResponse
from django.views import View

class Book(View):

    def get(self, request, *args, **kwargs):
        return JsonResponse('get ok', safe=False)

    def post(self, request, *args, **kwargs):
        return JsonResponse('get ok', safe=False)   #safe默認為true，要返回字典。不是字典否則拋異常。

from django.conf.urls import url
from . import views    #注意在應用中導入視圖都是.   從當前應用中導入

urlpatterns = [
    url(r'^books/', views.Book.as_view()),
]

from django.db import models

class Book(models.Model):

    title = models.CharField(max_length=64)
    price = models.DecimalField(max_digits=5, decimal_places=2) #整數、小數位

    class Meta:    #嵌套類（給上級類添加功能或指定標準）
        
       db_table = 'book'    #自定義數據庫表名
        verbose_name = "book"   #給模型起個可讀的名字，默認是複數
        verbose_name_plural = verbose_name   #取消上面的複數

    def __str__(self):      #显示的內容
        return '<<%s>>' % self.title    

from django.contrib import admin
port models

admin.site.register(models.Book)

 （2）CBV的請求生命周期

請求如何到CBV下的get和post

a.請求過來，項目文件中路由分發給應用api的路由

b.應用分發路由走as_view函數。

views.Book.as_view()  保存一系列數據（request、args、**kwargs等）給Book對象，然後都給dispatch進行路由分發。

dispatch乾的事：判斷請求方式是否支持，然後返回（通過getattr）支持的這些請求方法（get、post等，在視圖中自定義get、post的返回值）的結果。

c.通過dispatch就執行了CBV下請求方式的結果，返回結果

4.django原生的接口、序列化

  六大基礎接口：獲取一個、獲取所有、增加一個、刪除一個、整體更新一個、局部更新一個

 十大接口：6大基礎、群增、群刪、整體群改、局部群改

JsonResponse返回時，中文會變成unicode，要加json_dumps_params={‘ensure_ascii’:False}選項。但在linux環境下的火狐瀏覽器，加了是亂碼。

filter返回queryset對象，對象里是個列表（表名：對象信息（有自定義str就是自定義的信息））。first取里第一個對象（相當於print(第一個對象)）values展示對應的對象里的值

<QuerySet [<Book: <<三國演義>>>]>                   #直接.filter

<<三國演義>>                                    #.first()

<QuerySet [{‘title’: ‘三國演義‘, ‘price’: Decimal(‘56.00’)}]>  #.values(‘title’,’price’)

{‘title’: ‘三國演義‘, ‘price’: Decimal(‘56.00’)}             #.values.first()  是個字典

 上面序列化的工作很麻煩。drf就是為了方便序列化的。

postman可以完成不同方式的請求：get、post、put等

postman發送數據包有三種方式：form-data、urlencoded、json. 原生django對urlencoded數據提交兼容。

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※教你寫出一流的銷售文案?

※廣告預算用在刀口上，台北網頁設計公司幫您達到更多曝光效益

※回頭車貨運收費標準

※別再煩惱如何寫文案,掌握八大原則!

※超省錢租車方案

※產品缺大量曝光嗎?你需要的是一流包裝設計!

概述篇

LCA (Least Common Ancestors) ，即最近公共祖先，是指這樣的一個問題：在一棵有根樹中，找出某兩個節點 u 和 v 最近的公共祖先。

LCA 可分為在線算法與離線算法

• 在線算法：指程序可以以序列化的方式一個一個處理輸入，也就是說在一開始並不需要知道所有的輸入。
• 離線算法：指一開始就需要知道問題的所有輸入數據，而在解決一個問題后立即輸出結果。

算法篇

對於該問題，很容易想到的做法是從 u、v 分別回溯到根節點，然後這兩條路徑中的第一個交點即為 u、v 的最近公共祖先，在一棵平衡二叉樹中，該算法的時間複雜度可以達到 O(logn)O(log⁡n) ，但是對於某些退化為鏈狀的樹來說，算法的時間複雜度最壞為 O(n)O(n) ，顯然無法滿足更高頻率的查詢。

本節將介紹幾種比較高效的算法來解決這一問題，常見的算法有三種：在線 DFS + ST 算法、倍增算法、離線 Tarjan 算法。

接下來我們來一一解釋這三種 /* 看似高深，其實也不簡單 */ 的算法。

在線 DFS + ST 算法

首先看到 ST 你會想到什麼呢？（腦補許久都沒有想到它會是哪個單詞的縮寫）

看過前文 『數據結構』RMQ 問題 的話你便可以明白 ST算法 的思路啦~

So ，關於 LCA 的這種在線算法也是可以建立在 RMQ 問題的基礎上咯~

我們設 LCA(T,u,v) 為在有根樹 T 中節點 u、v 的最近公共祖先， RMQ(A,i,j) 為線性序列 A 中區間 [i,j] 上的最小（大）值。

如下圖這棵有根樹：

我們令節點編號滿足父節點編號小於子節點編號（編號條件）

可以看出 LCA(T,4,5) = 2, LCA(T,2,8) = 1, LCA(T,3,9) = 3 。

設線性序列 A 為有根樹 T 的中序遍歷，即 A = [4,2,5,1,8,6,9,3,7] 。

由中序遍歷的性質我們可以知道，任意兩點 u、v 的最近公共祖先總在以該兩點所在位置為端點的區間內，且編號最小。

舉個栗子：

假設 u = 8, v = 7 ，則該兩點所確定的一段區間為 [8,6,9,3,7] ，而區間最小值為 3 ，也就是說，節點 3 為 u、v 的最近公共祖先。

解決區間最值問題我們可以採用 RMQ 問題中的 ST 算法 。

但是在有些問題中給出的節點並不一定滿足我們所說的父節點編號小於子節點編號，因此我們可以利用節點間的關係建圖，然後採用前序遍歷來為每一個節點重新編號以生成線性序列 A ，於是問題又被轉化為了區間最值的查詢，和之前一樣的做法咯~

時間複雜度： n×O(logn)n×O(log⁡n) 預處理 + O(1)O(1) 查詢

想了解 RMQ 問題 的解法可以戳上面的鏈接哦~

以上部分介紹了 LCA 如何轉化為 RMQ 問題，而在實際中這兩種方案之間可以相互轉化

類比之前的做法，我們如何將一個線性序列轉化為滿足編號條件的有根樹呢？

1. 設序列中的最小值為 AkAk ，建立優先級為 AkAk 的根節點 TkTk
2. 將 A[1…k−1]A[1…k−1] 遞歸建樹作為 TkTk 的左子樹
3. 將 A[k+1…n]A[k+1…n] 遞歸建樹作為 TkTk 的右子樹

讀者可以試着利用此方法將之前的線性序列 A = [4,2,5,1,8,6,9,3,7] 構造出有根樹 T ，結果一定滿足之前所說的編號條件，但卻不一定唯一。

離線 Tarjan 算法

Tarjan 算法是一種常見的用於解決 LCA 問題的離線算法，它結合了深度優先搜索與並查集，整個算法為線性處理時間。

首先來介紹一下 Tarjan 算法的基本思路：

1. 任選一個節點為根節點，從根節點開始
2. 遍歷該點 u 的所有子節點 v ，並標記 v 已經被訪問過
3. 若 v 還有子節點，返回 2 ，否則下一步
4. 合併 v 到 u 所在集合
5. 尋找與當前點 u 有詢問關係的點 e
6. 若 e 已經被訪問過，則可以確定 u、e 的最近公共祖先為 e 被合併到的父親節點

偽代碼：

Tarjan(u)               // merge 和 find 為並查集合併函數和查找函數
{
    for each(u,v)       // 遍歷 u 的所有子節點 v
    {
        Tarjan(v);      // 繼續往下遍歷
        merge(u,v);     // 合併 v 到 u 這一集合
        標記 v 已被訪問過;
    }
    for each(u,e)       // 遍歷所有與 u 有查詢關係的 e
    {
        if (e 被訪問過)
            u, e 的最近公共祖先為 find(e);
    }
}
C++

感覺講到這裏已經沒有其它內容了，但是一定會有好多人沒有理解怎麼辦呢？

我們假設在如下樹中模擬 Tarjan 過程（節點數量少一點可以畫更少的圖o(￣▽￣)o）

存在查詢： LCA(T,3,4)、LCA(T,4,6)、LCA(T,2,1) 。

注意：每個節點的顏色代表它當前屬於哪一個集合，橙色線條為搜索路徑，黑色線條為合併路徑。

當前所在位置為 u = 1 ，未遍歷孩子集合 v = {2,5} ，向下遍歷。

當前所在位置為 u = 2 ，未遍歷孩子集合 v = {3,4} ，向下遍歷。

當前所在位置為 u = 3 ，未遍歷孩子集合 v = {} ，遞歸到達最底層，遍歷所有相關查詢發現存在 LCA(T,3,4) ，但是節點 4 此時標記未訪問，因此什麼也不做，該層遞歸結束。

遞歸返回，當前所在位置 u = 2 ，合併節點 3 到 u 所在集合，標記 vis[3] = true ，此時未遍歷孩子集合 v = {4} ，向下遍歷。

當前所在位置 u = 4 ，未遍歷孩子集合 v = {} ，遍歷所有相關查詢發現存在 LCA(T,3,4) ，且 vis[3] = true ，此時得到該查詢的解為節點 3 所在集合的首領，即 LCA(T,3,4) = 2 ；又發現存在相關查詢 LCA(T,4,6) ，但是節點 6 此時標記未訪問，因此什麼也不做。該層遞歸結束。

遞歸返回，當前所在位置 u = 2 ，合併節點 4 到 u 所在集合，標記 vis[4] = true ，未遍歷孩子集合 v = {} ，遍歷相關查詢發現存在 LCA(T,2,1) ，但是節點 1 此時標記未訪問，因此什麼也不做，該層遞歸結束。

遞歸返回，當前所在位置 u = 1 ，合併節點 2 到 u 所在集合，標記 vis[2] = true ，未遍歷孩子集合 v = {5} ，繼續向下遍歷。

當前所在位置 u = 5 ，未遍歷孩子集合 v = {6} ，繼續向下遍歷。

當前所在位置 u = 6 ，未遍歷孩子集合 v = {} ，遍歷相關查詢發現存在 LCA(T,4,6) ，且 vis[4] = true ，因此得到該查詢的解為節點 4 所在集合的首領，即 LCA(T,4,6) = 1 ，該層遞歸結束。

遞歸返回，當前所在位置 u = 5 ，合併節點 6 到 u 所在集合，並標記 vis[6] = true ，未遍歷孩子集合 v = {} ，無相關查詢因此該層遞歸結束。

遞歸返回，當前所在位置 u = 1 ，合併節點 5 到 u 所在集合，並標記 vis[5] = true ，未遍歷孩子集合 v = {} ，遍歷相關查詢發現存在 LCA(T,2,1) ，此時該查詢的解便是節點 2 所在集合的首領，即 LCA(T,2,1) = 1 ，遞歸結束。

至此整個 Tarjan 算法便結束啦~

PS：不要在意最終根節點的顏色和其他節點顏色有一點點小小差距，可能是在染色的時候沒仔細看，總之就這樣咯~

PPS：所謂的首領就是、就是首領啦~

倍增算法

哇！還有一個倍增算法以後繼續補充吧！

總結篇

對於不同的 LCA 問題我們可以選擇不同的算法。

假若一棵樹存在動態更新，此時離線算法就顯得有點力不從心了，但是在其他情況下，離線算法往往效率更高（雖然不能保證得到解的順序與輸入一致，不過我們有 sort 呀）

總之，喜歡哪種風格的 code 是我們自己的意願咯~

另外， LCA 和 RMQ 問題是兩個非常基礎的問題，很多複雜問題都可以轉化為這兩類問題來解決。（當然這兩類問題之間也可以相互轉化啦~）

參考資料

OI wiki https://oi-wiki.org/graph/lca/

https://blog.csdn.net/my_sunshine26/article/details/72717112

https://wizardforcel.gitbooks.io/the-art-of-programming-by-july/content/03.03.html

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※超省錢租車方案

※別再煩惱如何寫文案,掌握八大原則!

※回頭車貨運收費標準

※教你寫出一流的銷售文案?

※FB行銷專家,教你從零開始的技巧