2021-01-31 近期記錄

Leetcode

概覽
題目

題目
具體題目(部分)

1584. 連接所有點(diǎn)的最小費(fèi)用

題目描述:


1584

代碼:

class Solution(object):
    def minCostConnectPoints(self, points):
        Edges = []
        mydict = {} # 用來(lái)存儲(chǔ)哪些點(diǎn)已經(jīng)在圖中了
        m = len(points)
        for i in range(m-1):
            for j in range(i+1, m):
                pot1 = points[i]
                pot2 = points[j]
                absdis = abs(pot1[0] - pot2[0]) + abs(pot1[1] - pot2[1])
                Edges.append([absdis, i ,j])
        def takeFirst(elem):
            return elem[0]
        Edges.sort(key=takeFirst)
        edges = 0
        flag = 0
        alldistance = 0
        while edges < m-1:
            find = 0
            val = []
            for item in Edges:
                if flag == 0:
                    alldistance += item[0]
                    mydict[item[1]] = 1
                    mydict[item[2]] = 1
                    flag = 1
                    edges += 1
                    find = 1
                    val = item
                    break
                else:
                    i = item[1]
                    j = item[2]
                    if mydict.get(i,'no') == 'no':
                        haveI = False
                    else:
                        haveI = True
                    if mydict.get(j,'no') == 'no':
                        haveJ = False
                    else:
                        haveJ = True
                    if haveI == True and haveJ == True:
                        continue
                    if haveI == False and haveJ == False:
                        continue
                    mydict[i] = 1
                    mydict[j] = 1
                    alldistance += item[0]
                    val = item
                    edges += 1
                    break
            Edges.remove(val)
        return alldistance

思路:構(gòu)造一個(gè)無(wú)向圖G,輸入的每個(gè)點(diǎn)都是G的結(jié)點(diǎn)闸与,各個(gè)點(diǎn)之間的曼哈頓距離就是邊的度扇丛,原問題被轉(zhuǎn)化成一個(gè)求最小生成樹的問題赘被,可以用prim算法解決攘滩。
提交結(jié)果:


output

215. 數(shù)組中的第K個(gè)最大元素
題目描述:

image.png

代碼:

class Solution(object):
    def findKthLargest(self, nums, k):
        while k>1:
            maxN = max(nums)
            nums.remove(maxN)
            k = k - 1
        return max(nums)

思路:每次找到最大的刪除掉祠挫,執(zhí)行k-1次汉嗽, 然后返回?cái)?shù)組中的最大值插掂。

提交結(jié)果:


image.png

275. H 指數(shù) II
題目描述:

image.png

代碼:

class Solution(object):
    def hIndex(self, citations):
        m = len(citations) - 1
        if m == -1:
            return 0
        if citations == [0]:
            return 0
        if m == 0 and citations[0] != 0:
            return 1
        if max(citations) == 0:
            return 0
        flag = 0
        while m >= 0:
            if citations[m] > flag:
                flag += 1
                m -= 1
            else:
                return flag
        return flag

思路:因?yàn)檩斎胍呀?jīng)是升序排序的了,讓H指數(shù)用變量flag來(lái)代替鸠项,初始值為0干跛。從數(shù)組的末端往前遍歷,每執(zhí)行一次flag增加1祟绊,當(dāng)flag不再滿足小于當(dāng)前所遍歷到的數(shù)組值的時(shí)候楼入,就說明它被引用flag次的論文不多于flag篇。(本題要注意一些邊界條件)

提交結(jié)果:


image.png

279 完全平方數(shù)

題目描述:


image.png

代碼:

class Solution(object):
    def numSquares(self, n):
        if n==1:
            return 1
        dishu = 1
        ans = [i for i in range(n+1)]
        for i in range(1,n+1):
            j = 1
            while i - j*j >= 0:
                ans[i] = min(ans[i], ans[i-j*j]+1)
                j+=1

        return ans[-1]

思路:
動(dòng)態(tài)規(guī)劃牧抽,重點(diǎn)是要找準(zhǔn)狀態(tài)轉(zhuǎn)移方程:ans[i] = min(ans[i], ans[i-j*j]+1)

提交結(jié)果:


image.png

150 逆波蘭表達(dá)式求值

題目描述:


image.png

代碼:

class Solution(object):
    def evalRPN(self, tokens):
        """
        :type tokens: List[str]
        :rtype: int
        """
        stackOfNum = []
        for item in tokens:
            # print(stackOfNum)
            if item == '+' or item =='-' or item=='*' or item == '/':
                num1 = int(stackOfNum[-2])
                num2 = int(stackOfNum[-1])
                if item == '+':
                    newNum = num1 + num2
                elif item == '-':
                    newNum = num1-num2
                elif item == '*':
                    newNum = num2 * num1
                else:
                    # newNum =int( num1 / num2 )
                    if (num1 <= 0 and num2 >= 0) or (num1>=0 and num2<=0):
                        newNum = -(abs(num1) // abs(num2))
                    else:
                        newNum = num1 // num2
                del stackOfNum[-1]
                del stackOfNum[-1]
                stackOfNum.append(str(newNum))
            else:
                stackOfNum.append(item)
        # print(stackOfNum)
        return int(stackOfNum[-1])
                

思路:
用一個(gè)stack來(lái)輔助操作浅辙,當(dāng)輸入是數(shù)字則入棧,當(dāng)輸入是運(yùn)算符號(hào)阎姥,則讓棧尾的兩個(gè)元素參與運(yùn)算,然后把這兩個(gè)元素出棧鸽捻,讓運(yùn)算結(jié)果入棧呼巴,完成所有運(yùn)算后,最終結(jié)果就保存在棧頂御蒲。(要注意的是除法操作時(shí)衣赶,對(duì)于除數(shù)和被除數(shù)異號(hào)的情況單獨(dú)討論)

提交結(jié)果:


image.png

299 猜數(shù)字游戲

題目描述:


image.png

代碼:

class Solution(object):
    def getHint(self, secret, guess):
        """
        :type secret: str
        :type guess: str
        :rtype: str
        """
        def findBulls(secret, guess):
            flag = 0
            str1 = ''
            str2 = ''
            for i in range(len(secret)):
                if secret[i] == guess[i]:
                    flag += 1
                else:
                    str1 += secret[i]
                    str2 +=  guess[i]
            return flag , str1 ,str2

        bulls , sec, gue = findBulls(secret, guess)
        mydice = {}
        cows = 0
        for item in sec:
            if mydice.get(item,'no') == 'no':
                mydice[item] = 1
            else :
                mydice[item] += 1
        for i in gue:
            if mydice.get(i, 'no') != 'no':
                if mydice[i] >= 1:
                    cows += 1
                    mydice[i] -= 1
        return ''+str(bulls) + 'A' + str(cows) + 'B'

思路:
將題目分解為兩部分,1厚满、找公牛府瞄,2、找奶牛碘箍。
1遵馆、構(gòu)造找公牛的函數(shù),按位逐次比較即可找出公牛數(shù)量丰榴。同時(shí)货邓,該函數(shù)還返回秘密數(shù)字和猜測(cè)值的不同部分。便于找奶牛四濒。
2换况、分別遍歷密文和guess职辨,利用字典來(lái)找奶牛數(shù)量。

提交結(jié)果:


提交結(jié)果

17 電話號(hào)碼的字母組合
題目描述:

image.png

代碼:

class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if digits == '':
            return []
        mydict = {
            '2':['a','b','c'],
            '3':['d','e','f'],
            '4':['g','h','i'],
            '5':['j','k','l'],
            '6':['m','n','o'],
            '7':['p','q','r','s'],
            '8':['t','u','v'],
            '9':['w','x','y','z']
        }
        # ans = []
        ans = mydict[digits[0]]
        for i in range(1, len(digits)):
            newans = []
            nowC = mydict[digits[i]]
            nowS = ''
            for item in nowC:
                for items in ans:
                    nowS = items + item
                    newans.append(nowS)
            ans = newans
        return ans
            

思路:
1戈二、用字典存儲(chǔ)電話號(hào)碼對(duì)應(yīng)的字母
2舒裤、暴力迭代
3、注意每完成一次外層循環(huán)更新一下ans

提交結(jié)果:


image.png

1631 最小體力消耗路徑

題目描述:


image.png

代碼:

/**
 * @param {number[][]} heights
 * @return {number}
 */
var minimumEffortPath = function(heights) {
    const m = heights.length;
    const n = heights[0].length;
    const edges = [];
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            const id = i * n + j;
            if (i > 0) {
                edges.push([id - n, id, Math.abs(heights[i][j] - heights[i - 1][j])]);
            }
            if (j > 0) {
                edges.push([id - 1, id, Math.abs(heights[i][j] - heights[i][j - 1])]);
            }
        }
    }
    // 按照l(shuí)ist的第三項(xiàng)做排序(升序)
    // 原本的每個(gè)空格heights[i][j] 是被作為了圖G中的一個(gè)結(jié)點(diǎn)觉吭,結(jié)點(diǎn)編號(hào)為0 - (m*n -1)
    edges.sort((a, b) => a[2] - b[2]);
    console.log(edges)
    // new 一個(gè)并查集
    const uf = new UnionFind(m * n);
    let ans = 0;
    // 按照權(quán)重從小到大挨個(gè)往并查集里面并入腾供。
    // 等到第0和結(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn)聯(lián)通,此時(shí)的權(quán)重就是最小 體力消耗值
    for (const edge of edges) {
        const x = edge[0], y = edge[1], v = edge[2];
        uf.unite(x, y);
        if (uf.connected(0, m * n - 1)) {
            ans = v;
            break;
        }
    }
    return ans;
};

// JS版本的 并查集模板
class UnionFind {
    // 構(gòu)造函數(shù)
    constructor (n) {
        this.parent = new Array(n).fill(0).map((element, index) => index);
        this.size = new Array(n).fill(1);
        // 當(dāng)前連通分量數(shù)目
        this.setCount = n;
    }
    // 找parent
    findset (x) {
        if (this.parent[x] === x) {
            return x;
        }
        this.parent[x] = this.findset(this.parent[x]);
        return this.parent[x];
    }
    // 將兩個(gè)子集聯(lián)合起來(lái)亏栈, (聯(lián)通起來(lái))
    unite (a, b) {
        // 找這兩個(gè)子集parent台腥, 如果parent相同,則本身就是聯(lián)通的绒北,返回false
        let x = this.findset(a), y = this.findset(b);
        if (x === y) {
            return false;
        }
        // 讓小的為y黎侈, 大的為x, 保證是小的并入大的
        if (this.size[x] < this.size[y]) {
            [x, y] = [y, x];
        }
        // 把y并入x 
        this.parent[y] = x;
        this.size[x] += this.size[y];
        // 聯(lián)通分量的數(shù)量減一
        this.setCount -= 1;
        return true;
    }
    // 如果 a和b 在同一個(gè)聯(lián)通分量中闷游,返回true峻汉,否則返回false
    connected (a, b) {
        const x = this.findset(a), y = this.findset(b);
        return x === y;
    }
}

思路:
將每個(gè)格子作為一個(gè)結(jié)點(diǎn),格子之間的差值為邊的權(quán)重脐往,把邊按權(quán)重從小到大排序休吠。
構(gòu)建并查集
按照權(quán)重從小到大,將邊加入业簿,每次檢查圖的聯(lián)通性瘤礁,讓圖剛好能聯(lián)通的最后一條邊的權(quán)重就是最小的體力消耗、

提交結(jié)果:


image.png

4 尋找兩個(gè)正序數(shù)組的中位數(shù)

題目描述:


image.png

代碼:

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        def getmid(nums1, nums2):
            if nums1 == [] or nums2 ==[]:
                if nums1 == [] and nums2 != []:
                    nums = nums2
                if nums2 == [] and nums1 != []:
                    nums = nums1
                n = len(nums)
                if n % 2 == 0: # 偶數(shù)個(gè)
                    a = nums[n//2]
                    b = nums[n//2 - 1]
                    c = float((a + b)) / 2
                else:
                    # 奇數(shù)個(gè)數(shù)
                    c = nums[n//2]
                return c
            else:
                ptr1 = 0
                ptr2 = 0
                m = len(nums1)
                n = len(nums2)
                end = (m + n ) / 2
                flag = 0
                tick = 0
                ans = []
                if (m+n) % 2 == 0: #偶數(shù)個(gè)
                    # end = (m + n ) / 2
                    flag = 1
                else:
                    pass
                while tick <= end:
                    if ptr1 == m or ptr2 == n:
                        if ptr1 == m:
                            ans.append(nums2[ptr2])
                            ptr2 += 1
                        if ptr2 == n and ptr1 != m:
                            ans.append(nums1[ptr1])
                            ptr1 += 1
                    else:
                        if nums2[ptr2] <= nums1[ptr1]:
                            ans.append(nums2[ptr2])
                            ptr2 +=1
                        else:
                            ans.append(nums1[ptr1])
                            ptr1 +=1
                    tick += 1
                print(ans)
                if flag == 1:
                    return float((ans[-2] + ans[-1])) / 2
                else:
                    return ans[-1]
        num =  getmid(nums1, nums2)
        
        return num

思路:
分兩種情況:輸入的兩個(gè)數(shù)組中有一個(gè)數(shù)組為空梅尤;兩個(gè)數(shù)組都不為空
第一種情況:去不為空的那個(gè)數(shù)組里找中位數(shù)即可柜思,需要分開討論數(shù)組長(zhǎng)度為奇數(shù)和偶數(shù)的情況。
第二種情況:兩個(gè)都不為空巷燥,用雙指針的思想去維護(hù)一個(gè)新的數(shù)組赡盘,為了減少計(jì)算量, 可以提前計(jì)算出要求中位數(shù)需要計(jì)算的步長(zhǎng)缰揪,設(shè)為end陨享,每一步的標(biāo)志設(shè)為tick,同樣钝腺,要注意對(duì)長(zhǎng)度為奇數(shù)和長(zhǎng)度為偶數(shù)情況的討論抛姑。

提交結(jié)果:


image.png

2 兩數(shù)相加

題目描述:


image.png

代碼:

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
    let head = null, tail = null;
    let jinwei = 0
    while (l1||l2){
        let n1 = l1 ? l1.val : 0
        let n2 = l2 ? l2.val : 0
        let sum = n1 + n2 + jinwei
        if (sum >= 10) jinwei = 1
        else jinwei = 0
        if (! head){
            head = tail = new ListNode(sum % 10)
        }else{
            tail.next = new ListNode(sum % 10)
            tail = tail.next
        }

        if (l1){
            l1 = l1.next
        }
        if (l2){
            l2 = l2.next
        }
    }

    // 如果尾巴上還有一個(gè)進(jìn)位的
    if (jinwei > 0){
        tail.next = new ListNode(jinwei)
    }
    return head
};

思路:
思路很簡(jiǎn)單,對(duì)應(yīng)位的值相加即可艳狐,注意要維護(hù)一個(gè)進(jìn)位符途戒。主要是學(xué)習(xí)javascript的鏈表操作。

提交結(jié)果:


image.png

778 水位上升的泳池中游泳

題目描述:


image.png

代碼:

/**
 * @param {number[][]} grid
 * @return {number}
 */

var swimInWater = function(grid) {
    heights = grid
    const m = heights.length;
    const n = heights[0].length;
    const edges = [];
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            // edges.push([i, j, heights[i][j]])
            const id = i * n + j;
            if (i > 0) {
                edges.push([id - n, id, Math.max(heights[i][j] , heights[i - 1][j])]);
            }
            if (j > 0) {
                edges.push([id - 1, id, Math.max(heights[i][j] , heights[i][j - 1])]);
            }
        }
    }
    // 按照l(shuí)ist的第三項(xiàng)做排序(升序)
    // 原本的每個(gè)空格heights[i][j] 是被作為了圖G中的一個(gè)結(jié)點(diǎn)僵驰,結(jié)點(diǎn)編號(hào)為0 - (m*n -1)
    edges.sort((a, b) => a[2] - b[2]);
    // console.log(edges)
    // new 一個(gè)并查集
    const uf = new UnionFind(m * n);
    let ans = 0;
    // 按照權(quán)重從小到大挨個(gè)往并查集里面并入喷斋。
    // 等到第0和結(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn)聯(lián)通唁毒,此時(shí)的權(quán)重就是最小 體力消耗值
    for (const edge of edges) {
        const x = edge[0], y = edge[1], v = edge[2];
        uf.unite(x, y);
        if (uf.connected(0, m * n - 1)) {
            ans = v;
            break;
        }
    }
    return ans;
};

// JS版本的 并查集模板
class UnionFind {
    // 構(gòu)造函數(shù)
    constructor (n) {
        this.parent = new Array(n).fill(0).map((element, index) => index);
        this.size = new Array(n).fill(1);
        // 當(dāng)前連通分量數(shù)目
        this.setCount = n;
    }
    // 找parent
    findset (x) {
        if (this.parent[x] === x) {
            return x;
        }
        this.parent[x] = this.findset(this.parent[x]);
        return this.parent[x];
    }
    // 將兩個(gè)子集聯(lián)合起來(lái), (聯(lián)通起來(lái))
    unite (a, b) {
        // 找這兩個(gè)子集parent星爪, 如果parent相同浆西,則本身就是聯(lián)通的,返回false
        let x = this.findset(a), y = this.findset(b);
        if (x === y) {
            return false;
        }
        // 讓小的為y顽腾, 大的為x近零, 保證是小的并入大的
        if (this.size[x] < this.size[y]) {
            [x, y] = [y, x];
        }
        // 把y并入x 
        this.parent[y] = x;
        this.size[x] += this.size[y];
        // 聯(lián)通分量的數(shù)量減一
        this.setCount -= 1;
        return true;
    }
    // 如果 a和b 在同一個(gè)聯(lián)通分量中,返回true抄肖,否則返回false
    connected (a, b) {
        const x = this.findset(a), y = this.findset(b);
        return x === y;
    }
}

思路:和前面那道并查集的題思路一模一樣久信,代碼中只需要把邊的權(quán)重計(jì)算時(shí)算差值改成算max值就可以了。

提交結(jié)果:


image.png

19 刪除鏈表的倒數(shù)第 N 個(gè)結(jié)點(diǎn)
題目描述:

描述

代碼:

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
    nums = 0
    q = head
    while(q){
        q = q.next
        nums += 1
    }
    // console.log(nums)

    flag = 0
    end = nums - n -1 
    if (n == nums) return head.next
    tail = head
    while(tail){
        if (flag == end) tail.next = tail.next.next
        else tail = tail.next
        flag += 1
    }
    return head
};

思路:
先遍歷漓摩,求出鏈表總長(zhǎng)度裙士,然后計(jì)算出倒數(shù)第n位對(duì)應(yīng)的是正數(shù)第幾位,再次遍歷去刪掉那一位即可管毙。

提交結(jié)果:

image.png

701 二叉搜索樹中的插入操作
題目描述:

image.png

代碼:

var insertIntoBST = function(root, val) {
    let N = new TreeNode(val, null, null)
    if (root == null) {
        return N
    }
    let nowN = root
    let a = true
    while (a){
        if (nowN){
            if (nowN.val < val){
                if (nowN.right != null){
                    nowN = nowN.right
                }else{
                    nowN.right = N
                    a = false
                }
            }else{
                if (nowN.left != null){
                    nowN = nowN.left
                }else{
                    nowN.left = N
                    a= false
                }
            }
        }
    }
    return root
};

思路:
根據(jù)二叉搜索樹的性質(zhì)(比該節(jié)點(diǎn)小的值應(yīng)該在其左子樹中腿椎,比該節(jié)點(diǎn)大的值在右子樹中),迭代搜索找到該結(jié)點(diǎn)應(yīng)該插入的位置夭咬。
提交結(jié)果:


image.png

725 分隔鏈表

題目描述:


image.png

代碼:

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} root
 * @param {number} k
 * @return {ListNode[]}
 */
var splitListToParts = function(root, k) {
  // 先要直到鏈表有多長(zhǎng)
    let q = root
    flag = 0
    while(q){
      flag += 1
      q = q.next
    }
    // console.log(flag)
    let num1 = Math.floor(flag / k) 
    let num2 = flag % k
    let ans = []
    for (let i=0;i<k;i++){
        if (num2 > 0) ans.push(num1 + 1)
        else ans.push(num1)
        num2 -= 1
    }
    let out = []
    // console.log(ans)
    let tail = root
    for(var i=0;i<ans.length;i++){
        let p = tail
        num = ans[i]-1
        while(num > 0){
            p = p.next
            num -= 1
        }
        if (p==null) ppp = null
        else
        {
            ppp = p.next 
            p.next = null
        }
        
        out.push(tail)
        console.log(out)
        tail = ppp
    }
    return out
    // return 0
};

思路:先要求出鏈表有多長(zhǎng)啃炸,然后用一個(gè)ans數(shù)組來(lái)存儲(chǔ)分離信息。len(ans)代表了分成幾段卓舵,ans[i]代表第 i 段有多少個(gè)元素南用。然后遍歷ans數(shù)組來(lái)實(shí)施分段。
提交結(jié)果:


看到代碼有打印掏湾,于是把它們注釋了再交了一遍

328 奇偶鏈表
題目描述:

image.png

代碼:

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var oddEvenList = function(head) {
    flag = 0
    if (! head) return head 
    k = new ListNode(head.val, null)
    k_tail = k
    tail = head.next
    while(tail){
        if (flag == 0){
            tail = tail.next
            flag = 1
        }else{
            q = new ListNode(tail.val, null)
            k_tail.next = q
            tail = tail.next
            k_tail = k_tail.next
            flag = 0
        }
    }
    ans = 0
    while(head){
        if (ans == 0){
            head = head.next
            ans = 1
        }else{
            q = new ListNode(head.val, null)
            k_tail.next = q
            head = head.next
            k_tail = k_tail.next
            ans = 0
        }
    }
    return k
};

思路:先遍歷取出奇數(shù)結(jié)點(diǎn)训枢,再遍歷取出偶數(shù)結(jié)點(diǎn)(還沒有滿足題中讓嘗試的要求)

提交結(jié)果:


image.png

94 二叉樹的中序遍歷(后序遍歷類似)

題目描述:
image.png

代碼:

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
    if (! root) return []
    ans = []
    function midB(root){
        if (root){
            midB(root.left)
            ans.push(root.val)
            midB(root.right)
        }
        return 
    }
    midB (root)
    return ans
};

思路:
遞歸,左中右的順序讀取值忘巧、
提交結(jié)果:


image.png

論文閱讀

Dual Attention Network for Scene Segmentation

DA-net

出自 : cvpr 2019

任務(wù)背景:

為實(shí)現(xiàn)更好的場(chǎng)景分割。因?yàn)閷?duì)象的比例睦刃、遮擋砚嘴、光照變化等因素會(huì)造成場(chǎng)景分割的困難。

現(xiàn)狀:

現(xiàn)在常用全卷積神經(jīng)網(wǎng)絡(luò)來(lái)處理語(yǔ)義分割任務(wù)涩拙。為提升分割準(zhǔn)確性际长,常見的思路有:
1、多尺度方法(有助于捕捉不同比例的對(duì)象兴泥,但它不能在全局視圖中利用對(duì)象或素材之間的關(guān)系)
2工育、編-解碼形狀網(wǎng)絡(luò)
3、利用循環(huán)神經(jīng)網(wǎng)絡(luò)做語(yǔ)義分割(嚴(yán)重依賴長(zhǎng)期記憶的學(xué)習(xí)結(jié)果)

本文創(chuàng)新點(diǎn):

提出了一種雙注意力網(wǎng)絡(luò)(DA-net)搓彻,包括位置注意力模塊(Position Attention Module)和通道注意力模塊(Channel Attention Module)如绸。
位置注意力模塊:引入了自我注意機(jī)制來(lái)捕捉特征地圖任意兩個(gè)位置之間的空間相關(guān)性嘱朽。
通道注意力模塊:使用自我注意機(jī)制來(lái)捕獲任意兩個(gè)頻道映射之間的頻道依賴關(guān)系

貢獻(xiàn):

1、提出引入雙注意力機(jī)制的DA-net
2怔接、提出了位置注意模塊來(lái)學(xué)習(xí)特征的空間相關(guān)性搪泳,并設(shè)計(jì)了通道注意模塊來(lái)建模通道相關(guān)性。它通過對(duì)局部特征的豐富上下文依賴性建模扼脐,顯著改善了分割結(jié)果岸军。
3、在Cityscapes瓦侮、PASCAL Context 和 COCO Stuff 數(shù)據(jù)集上取得了最好的效果艰赞。

網(wǎng)絡(luò)結(jié)構(gòu):

概覽:

網(wǎng)絡(luò)結(jié)構(gòu)

可見,DA-net主要由三部分組成:
1肚吏、主干網(wǎng)絡(luò) 2方妖、空間注意力模塊(PAM) 3、通道注意力模塊(CAM)
其中须喂,PAM模塊詳細(xì)結(jié)構(gòu)如下圖所示:
PAM

過程描述:
start
give input --> A(C * H * W)
use 1 * 1 conv get B, C ,D
B (C * H * W) reshape --> to B(C * N) while N = H * W
C (C * H * W) reshape --> to C(C * N) while N = H * W
D (C * H * W) reshape --> to D(C * N) while N = H * W
Bt (N * C) = transpose(B)
S (N * N) = softmax( Bt * C )
St (N * N) = transpose(S)
D = D * St
D (C * N) reshape --> to D(C * H * W)
E = A + a * D (a 是加權(quán)值吁断,a是可訓(xùn)練參數(shù),初始值為0)
output E
end

CAM模塊結(jié)構(gòu)如下:

CAM

CAM模塊的實(shí)現(xiàn)和PAM的類似坞生,不過要注意它沒有1 * 1卷積

作者實(shí)驗(yàn):

作者分別用實(shí)驗(yàn)討論了PAM模塊和CAM模塊的作用


PAM

PAM模塊有助于增強(qiáng)細(xì)節(jié)的區(qū)分度


CAM

CAM模塊有助于提升語(yǔ)義的一致性仔役,增加分類的正確性
特定點(diǎn)的空間注意子圖以及通道注意子圖

可以發(fā)現(xiàn):空間注意子圖總能關(guān)注到與該點(diǎn)同類的物體的位置;而不同的通道則關(guān)注了不同的重點(diǎn)是己。
PAM模塊和CAM模塊的作用從評(píng)價(jià)指標(biāo)上也可以得到反映:


image.png

在各數(shù)據(jù)集上的最終結(jié)果:


CityScapes

VOC 2012

PASCAL Context

COCO stuff

我的實(shí)驗(yàn)

對(duì)OCTA-500數(shù)據(jù)集又兵,做了以下嘗試:
1、只使用oct模態(tài)卒废,將三維輸入數(shù)據(jù)的height維度當(dāng)做channel沛厨,利用u-net網(wǎng)絡(luò)跑了一下看效果。得到的輸出只能分割出FAZ(視網(wǎng)膜中央凹無(wú)血管區(qū))摔认,無(wú)法分割出RV(視網(wǎng)膜血管)逆皮,且分割出來(lái)的FAZ指標(biāo)也不好。猜測(cè)的原因可能有:1)二維卷積對(duì)于空間信息的利用不夠?qū)е路植怀鲅堋?2)數(shù)據(jù)集作者在做3分類時(shí)参袱,采用的是兩次二分類电谣,而非直接做的多分類,可能原作者也遇到了直接多分類比較困難的問題抹蚀。 3)可能數(shù)據(jù)處理階段有代碼寫錯(cuò)了剿牺,不過因?yàn)檩斎胧侨S的tensor,通過打印中間過程來(lái)排查不好觀察环壤。
2晒来、結(jié)合oct模態(tài)和octa模態(tài),讓兩種數(shù)據(jù)以兩個(gè)channel的形式輸入郑现,用作者論文中的IPN網(wǎng)絡(luò)做實(shí)驗(yàn)湃崩,因?yàn)?D卷積資源消耗大荧降,會(huì)導(dǎo)致爆顯存,原作者將長(zhǎng)和寬從400 * 400裁剪為了100 * 100竹习。裁剪方式用了兩種:1)誊抛、將每個(gè)400 * 400的圖裁成16張100 * 100的圖,分別存儲(chǔ)裁剪后的子圖整陌,原數(shù)據(jù)集擴(kuò)充16倍拗窃。2)、為每張圖生成隨機(jī)值泌辫,依據(jù)隨機(jī)值做裁剪随夸,每張大圖只生成一張裁剪后的小圖,通過增加epoch輪數(shù)來(lái)增加迭代次數(shù)震放。 還沒有跑出效果來(lái)宾毒,還在找問題。

后續(xù)安排

1殿遂、繼續(xù)看論文诈铛,大致方向是3D分割方面的,比如3D-U-net和V-net這類型的
2墨礁、裝tensorflow環(huán)境把作者的代碼跑起來(lái)先看看效果再考慮用pytorch復(fù)現(xiàn)和修改網(wǎng)絡(luò)結(jié)構(gòu)
3幢竹、leetcode作題目,最近打算多做一些數(shù)據(jù)結(jié)構(gòu)相關(guān)的題目

(遠(yuǎn)程連接做實(shí)驗(yàn)有些不穩(wěn)定恩静,本來(lái)打算截些實(shí)驗(yàn)過程的圖焕毫,又突然連不上了)

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市驶乾,隨后出現(xiàn)的幾起案子邑飒,更是在濱河造成了極大的恐慌,老刑警劉巖级乐,帶你破解...
    沈念sama閱讀 223,002評(píng)論 6 519
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件疙咸,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡风科,警方通過查閱死者的電腦和手機(jī)撒轮,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,357評(píng)論 3 400
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)丐重,“玉大人,你說我怎么就攤上這事杆查“绲耄” “怎么了?”我有些...
    開封第一講書人閱讀 169,787評(píng)論 0 365
  • 文/不壞的土叔 我叫張陵亲桦,是天一觀的道長(zhǎng)崖蜜。 經(jīng)常有香客問我浊仆,道長(zhǎng),這世上最難降的妖魔是什么豫领? 我笑而不...
    開封第一講書人閱讀 60,237評(píng)論 1 300
  • 正文 為了忘掉前任抡柿,我火速辦了婚禮,結(jié)果婚禮上等恐,老公的妹妹穿的比我還像新娘洲劣。我一直安慰自己,他們只是感情好课蔬,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,237評(píng)論 6 398
  • 文/花漫 我一把揭開白布囱稽。 她就那樣靜靜地躺著,像睡著了一般二跋。 火紅的嫁衣襯著肌膚如雪战惊。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,821評(píng)論 1 314
  • 那天扎即,我揣著相機(jī)與錄音吞获,去河邊找鬼。 笑死谚鄙,一個(gè)胖子當(dāng)著我的面吹牛各拷,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播襟锐,決...
    沈念sama閱讀 41,236評(píng)論 3 424
  • 文/蒼蘭香墨 我猛地睜開眼撤逢,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼!你這毒婦竟也來(lái)了粮坞?” 一聲冷哼從身側(cè)響起蚊荣,我...
    開封第一講書人閱讀 40,196評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎莫杈,沒想到半個(gè)月后互例,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,716評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡筝闹,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,794評(píng)論 3 343
  • 正文 我和宋清朗相戀三年媳叨,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片关顷。...
    茶點(diǎn)故事閱讀 40,928評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡糊秆,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出议双,到底是詐尸還是另有隱情痘番,我是刑警寧澤,帶...
    沈念sama閱讀 36,583評(píng)論 5 351
  • 正文 年R本政府宣布,位于F島的核電站汞舱,受9級(jí)特大地震影響伍纫,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜昂芜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,264評(píng)論 3 336
  • 文/蒙蒙 一莹规、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧泌神,春花似錦良漱、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,755評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)。三九已至幼苛,卻和暖如春窒篱,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背舶沿。 一陣腳步聲響...
    開封第一講書人閱讀 33,869評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工墙杯, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人括荡。 一個(gè)月前我還...
    沈念sama閱讀 49,378評(píng)論 3 379
  • 正文 我出身青樓高镐,卻偏偏與公主長(zhǎng)得像,于是被迫代替她去往敵國(guó)和親畸冲。 傳聞我的和親對(duì)象是個(gè)殘疾皇子嫉髓,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,937評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容