2304. 网格中的最小路径代价 : 从「图论最短路」过渡到「O(1) 空间的原地模拟」

题目描述

这是 LeetCode 上的 「2304. 网格中的最小路径代价」 ,难度为 「中等」

Tag : 「最短路」、「图」、「模拟」、「序列 DP」、「动态规划」

给你一个下标从 0 开始的整数矩阵 grid,矩阵大小为 m x n,由从 0 的不同整数组成。

你可以在此矩阵中,从一个单元格移动到下一行的任何其他单元格。

如果你位于单元格 ,且满足 ,你可以移动到 , , ..., 中的任何一个单元格。注意: 在最后一行中的单元格不能触发移动。

每次可能的移动都需要付出对应的代价,代价用一个下标从 0 开始的二维数组 moveCost 表示,该数组大小为 ,其中 moveCost[i][j] 是从值为 i 的单元格移动到下一行第 j 列单元格的代价。从 grid 最后一行的单元格移动的代价可以忽略。

grid 一条路径的代价是:所有路径经过的单元格的值之和加上所有移动的代价之和 。从第一行任意单元格出发,返回到达最后一行任意单元格的最小路径代价。

示例 1: alt

输入:grid = [[5,3],[4,0],[2,1]], moveCost = [[9,8],[1,5],[10,12],[18,6],[2,4],[14,3]]

输出:17

解释:最小代价的路径是 5 -> 0 -> 1 。
- 路径途经单元格值之和 5 + 0 + 1 = 6 。
- 从 5 移动到 0 的代价为 3 。
- 从 0 移动到 1 的代价为 8 。
路径总代价为 6 + 3 + 8 = 17 。

示例 2:

输入:grid = [[5,1,2],[4,0,3]], moveCost = [[12,10,15],[20,23,8],[21,7,1],[8,1,13],[9,10,25],[5,3,2]]

输出:6

解释:
最小代价的路径是 2 -> 3 。 
- 路径途经单元格值之和 2 + 3 = 5 。 
- 从 2 移动到 3 的代价为 1 。 
路径总代价为 5 + 1 = 6 。

提示:

  • grid 由从 0m * n - 1 的不同整数组成

建新图 + 建虚拟点 + 堆优化 Dijkstra

注意:可以直接使用解法二的方法,但先认真看完本做法,再去看解法二,会有相当丝滑的体验。

每次移动,「实际路径权值 = 经过边的权值 + 目的地的权值」

利用原图,构建新图:「每个单元格视为一个点,除最后一行外,每个点对下一行的所有点连一条有向边,边权 = 原图中该边的权值 + 原图中该目的地的权值」

分析新图中的点边数量:

  • 点:共 个点,数量为
  • 边:不算最后一行,共 个点,这些点与下一行的每个点均有一条有向边,合计 条边,数量为

原问题转换为:求点 的最短路,其中点 所在位置为第 行,点 所在位置为第 行。

这似乎是一个「多源汇最短路」问题?但求解多源汇最短路的 Floyd 算法是 的,会超时。

实际上,我们也并不真的关心图中任意点之间的最短路,仅仅关心第一行到最后一行的最短路。

因此,「我们可通过建立“虚拟源点”和“虚拟汇点”的方式,来将“多源汇最短路”问题转换为“单源最短路”问题。」

具体的,我们创建一个“虚拟源点”,该点向所有第一行的点连权值为 的有向边;同时创建一个“虚拟汇点”,最后一行的所有点向该点连权值为 的有向边。

问题进一步转化为:求“虚拟源点”到“虚拟汇点”的最短路。

至此,我们通过 「建新图 -> 创建虚拟源汇点(转换为单源最短路)-> 套用单源最短路算法」 解决本题。

将新图中点的数量记为 ,边数记为 ,朴素 Dijkstra 复杂度为 ,堆优化的 Dijkstra 的复杂度为 ,当 (相对稀疏)时,优先使用堆优化 Dijkstra

Java 代码:

class Solution {
    int N = 50 * 50 + 2, M = 50 * 50 * 50, idx = 0, n;
    int[] he = new int[N], e = new int[M], ne = new int[M], w = new int[M];
    void add(int a, int b, int c) {
        e[idx] = b;
        ne[idx] = he[a];
        w[idx] = c;
        he[a] = idx++;
    }
    public int minPathCost(int[][] grid, int[][] moveCost) {
        int N = grid.length, M = grid[0].length;
        int S = N * M, T = S + 1;
        n = N * M + 2;
        Arrays.fill(he, -1);
        //「虚拟源点」向「第一行」进行连边
        for (int i = 0; i < M; i++) add(S, grid[0][i], grid[0][i]);
        // 转换原图
        for (int i = 0; i < N - 1; i++) {
            for (int j = 0; j < M; j++) {
                int a = grid[i][j];
                for (int k = 0; k < M; k++) {
                    int b = grid[i + 1][k];
                    add(a, b, moveCost[a][k] + b);
                }
            }
        }
        //「最后一行」向「虚拟汇点」进行连边
        for (int i = 0; i < M; i++) add(grid[N - 1][i], T, 0);
        // 最短路
        int[] dist = dijkstra(S);
        return dist[T];
    }
    int[] dijkstra(int x) {
        // 起始先将所有的点标记为「未更新」和「距离为正无穷」
        int[] dist = new int[n];
        Arrays.fill(dist, 0x3f3f3f3f);
        boolean[] vis = new boolean[n];
        dist[x] = 0;
        // 使用「优先队列」存储所有可用于更新的点
        // 以 (点编号, 到起点的距离) 进行存储,优先弹出「最短距离」较小的点
        PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->a[1]-b[1]);
        q.add(new int[]{x, 0});
        while (!q.isEmpty()) {
            // 每次从「优先队列」中弹出
            int[] poll = q.poll();
            int u = poll[0], step = poll[1];
            // 如果弹出的点被标记「已更新」,则跳过
            if (vis[u]) continue;
            // 标记该点「已更新」,并使用该点更新其他点的「最短距离」
            vis[u] = true;
            for (int i = he[u]; i != -1; i = ne[i]) {
                int j = e[i];
                if (dist[j] <= dist[u] + w[i]) continue;
                dist[j] = dist[u] + w[i];
                q.add(new int[]{j, dist[j]});
            }
        }
        return dist;
    }
}

C++ 代码:

class Solution {
public:
    static const int N = 50 * 50 + 2, M = 50 * 50 * 50;
    int he[N], e[M], ne[M], w[M], idx, n, INF = 0x3f3f3f3f;
    void add(int a, int b, int c) {
        e[idx] = b;
        ne[idx] = he[a];
        w[idx] = c;
        he[a] = idx++;
    }
    int minPathCost(vector<vector<int>>& grid, vector<vector<int>>& moveCost) {
        int N = grid.size(), M = grid[0].size();
        int S = N * M, T = S + 1;
        n = N * M + 2;
        fill(he, he + n, -1);
        //「虚拟源点」向「第一行」进行连边
        for (int i = 0; i < M; i++) add(S, grid[0][i], grid[0][i]);
        // 转换原图
        for (int i = 0; i < N - 1; i++) {
            for (int j = 0; j < M; j++) {
                int a = grid[i][j];
                for (int k = 0; k < M; k++) {
                    int b = grid[i + 1][k];
                    add(a, b, moveCost[a][k] + b);
                }
            }
        }
        //「最后一行」向「虚拟汇点」进行连边
        for (int i = 0; i < M; i++) add(grid[N - 1][i], T, 0);
        // 最短路
        vector<int> dist = dijkstra(S);
        return dist[T];
    }
    vector<intdijkstra(int x) {
        vector<intdist(n, 0x3f3f3f3f);
        vector<boolvis(n, false);
        dist[x] = 0;
        // 使用「优先队列」存储所有可用于更新的点
        // 以 (到起点的距离, 点编号) 进行存储,优先弹出「最短距离」较小的点
        priority_queue<pair<intint>, vector<pair<intint>>, greater<pair<intint>>> q;
        q.push({0, x});
        while (!q.empty()) {
            // 每次从「优先队列」中弹出
            auto [step, u] = q.top();
            q.pop();
            // 如果弹出的点被标记「已更新」,则跳过
            if (vis[u]) continue;
            // 标记该点「已更新」,并使用该点更新其他点的「最短距离」
            vis[u] = true;
            for (int i = he[u]; i != -1; i = ne[i]) {
                int j = e[i];
                if (dist[j] <= dist[u] + w[i]) continue;
                dist[j] = dist[u] + w[i];
                q.push({dist[j], j});
            }
        }
        return dist;
    }
};

Python 代码:

import heapq

class Solution:
    def minPathCost(self, grid, moveCost):
        N, M = len(grid), len(grid[0])
        S, T = N * M, N * M + 1
        n = N * M + 2
        he = [-1] * n
        e, ne, w = [-1] * (50 * 50 * 50), [-1] * (50 * 50 * 50), [-1] * (50 * 50 * 50)
        idx = 0

        def add(a, b, c):
            nonlocal idx
            e[idx] = b
            ne[idx] = he[a]
            w[idx] = c
            he[a] = idx
            idx += 1

        def dijkstra(x):
            dist = [float('inf')] * n
            vis = [False] * n
            dist[x] = 0
            # 使用「优先队列」存储所有可用于更新的点
            # 以 (到起点的距离, 点编号) 进行存储,优先弹出「最短距离」较小的点
            q = [(0, x)]
            heapq.heapify(q)
            while q:
                # 每次从「优先队列」中弹出
                step, u = heapq.heappop(q)
                # 如果弹出的点被标记「已更新」,则跳过
                if vis[u]: continue
                # 标记该点「已更新」,并使用该点更新其他点的「最短距离」
                vis[u] = True
                i = he[u]
                while i != -1:
                    j, c = e[i], w[i]
                    i = ne[i]
                    if dist[j] <= dist[u] + c: continue
                    dist[j] = dist[u] + c
                    heapq.heappush(q, (dist[j], j))
            return dist

        #「虚拟源点」向「第一行」进行连边
        for i in range(M):
            add(S, grid[0][i], grid[0][i])
        # 转换原图
        for i in range(N - 1):
            for j in range(M):
                a = grid[i][j]
                for k in range(M):
                    b = grid[i + 1][k]
                    add(a, b, moveCost[a][k] + b)
        #「最后一行」向「虚拟汇点」进行连边
        for i in range(M):
            add(grid[N - 1][i], T, 0)
        # 最短路
        dist = dijkstra(S)
        return dist[T]
  • 时间复杂度: ,其中 为新图中的点数 为新图中的边数
  • 空间复杂度:

堆优化 Dijkstra

什么?你说你实在不想建新图,也不想搞什么虚拟点,就想用你心爱的 BFS 来做?!

我懂你意思,但那不叫 BFS

只是将「建新图」和「建虚拟点」的过程省掉,仍需要使用优先队列(堆)来每次取出当前“路径代价最小”的点来进行扩充,执行过程仍为堆优化 Dijkstra 的核心操作。

尤其所谓“省掉” 建新图 和 建虚拟点,真就字面上的“省掉”,并非不存在,因为两种做法思路是完全一致的。可简单列举「本解法」与「解法一」的对应关系:

  • 起始往队列放入首行元素,对应了解法一的“建立虚拟源点”过程;
  • 从队列中取元素出来扩充时,若当前元素所在行是最后一行时,用当前路径代价来更新答案,对应了解法一的“建立虚拟汇点”过程;
  • 扩充时直接遍历列(即下一行的所有点),对应的解法一的“用原图边建新图”的过程。

Java 代码:

class Solution {
    public int minPathCost(int[][] grid, int[][] moveCost) {
        int m = grid.length, n = grid[0].length, INF = 0x3f3f3f3f, ans = INF;
        int[][] dist = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) dist[i][j] = INF;
        }
        PriorityQueue<int[]> d = new PriorityQueue<>((a,b)->a[2]-b[2]);
        for (int i = 0; i < n; i++) {
            d.add(new int[]{0, i, grid[0][i]});
            dist[0][i] = grid[0][i];
        }
        while (!d.isEmpty()) {
            int[] info = d.poll();
            int x = info[0], y = info[1], cur = info[2];
            if (x == m - 1) {
                ans = Math.min(ans, cur);
                continue;
            }
            for (int i = 0; i < n; i++) {
                int step = moveCost[grid[x][y]][i], ne = grid[x + 1][i];
                int tot = cur + step + ne;
                if (tot >= ans || dist[x + 1][i] <= tot) continue;
                dist[x + 1][i] = tot;
                d.add(new int[]{x + 1, i, tot});
            }
        }
        return ans;
    }
}

C++ 代码:

class Solution {
public:
    int minPathCost(vector<vector<int>>& grid, vector<vector<int>>& moveCost) {
        int m = grid.size(), n = grid[0].size(), INF = 0x3f3f3f3f, ans = INF;
        vector<vector<int>> dist(m, vector<int>(n, INF));
        priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq;
        for (int i = 0; i < n; i++) {
            pq.push({0, i, grid[0][i]});
            dist[0][i] = grid[0][i];
        }
        while (!pq.empty()) {
            vector<int> info = pq.top();
            pq.pop();
            int x = info[0], y = info[1], cur = info[2];
            if (x == m - 1) {
                ans = min(ans, cur);
                continue;
            }
            for (int i = 0; i < n; i++) {
                int step = moveCost[grid[x][y]][i], ne = grid[x + 1][i];
                int tot = cur + step + ne;
                if (tot >= ans || dist[x + 1][i] <= tot) continue;
                dist[x + 1][i] = tot;
                pq.push({x + 1, i, tot});
            }
        }
        return ans;
    }
};

Python 代码:

class Solution:
    def minPathCost(self, grid, moveCost):
        m, n, INF = len(grid), len(grid[0]), float('inf')
        ans = INF
        dist = [[INF] * n for _ in range(m)]
        for i in range(n):
            dist[0][i] = grid[0][i]
        pq = [(0, i, grid[0][i]) for i in range(n)]
        while pq:
            x, y, cur = heapq.heappop(pq)
            if x == m - 1:
                ans = min(ans, cur)
                continue
            for i in range(n):
                step, ne = moveCost[grid[x][y]][i], grid[x + 1][i]
                tot = cur + step + ne
                if tot >= ans or dist[x + 1][i] <= tot: continue
                dist[x + 1][i] = tot
                heapq.heappush(pq, (x + 1, i, tot))
        return ans
  • 时间复杂度: ,其中 为新图中的点数 为新图中的边数
  • 空间复杂度:

原地模拟

什么?你说你连图论的方法都不想用,想就着题意做一遍?

可以。甚至当你调整更新方向,还能利用已有的 grid,实现原地模拟。

具体的,我们将“从上往下走”调整为“从下往上走”,这样可以确保当我们使用底下一行 来更新当前行 时,所用到的 不会被覆盖。

Java 代码:

class Solution {
    public int minPathCost(int[][] grid, int[][] moveCost) {
        int m = grid.length, n = grid[0].length, INF = 0x3f3f3f3f, ans = INF;
        for (int i = m - 2; i >= 0; i--) {
            for (int j = 0; j < n; j++) {
                int cur = INF;
                for (int k = 0; k < n; k++) cur = Math.min(cur, grid[i + 1][k] + moveCost[grid[i][j]][k]);
                grid[i][j] += cur;
            }
        }
        for (int i = 0; i < n; i++) ans = Math.min(ans, grid[0][i]);
        return ans;
    }
}

C++ 代码:

class Solution {
public:
    int minPathCost(vector<vector<int>>& grid, vector<vector<int>>& moveCost) {
        int m = grid.size(), n = grid[0].size(), INF = INT_MAX, ans = INF;
        for (int i = m - 2; i >= 0; i--) {
            for (int j = 0; j < n; j++) {
                int cur = INF;
                for (int k = 0; k < n; k++) cur = min(cur, grid[i + 1][k] + moveCost[grid[i][j]][k]);
                grid[i][j] += cur;
            }
        }
        for (int i = 0; i < n; i++) ans = min(ans, grid[0][i]);
        return ans;
    }
};

Python 代码:

class Solution:
    def minPathCost(self, grid, moveCost):
        m, n = len(grid), len(grid[0])
        for i in range(m - 2-1-1):
            for j in range(n):
                grid[i][j] += min([grid[i + 1][k] + moveCost[grid[i][j]][k] for k in range(n)])
        return min([grid[0][i] for i in range(n)])

TypeScript 代码:

function minPathCost(grid: number[][], moveCost: number[][]): number {
    let m = grid.length, n = grid[0].length, INF = 0x3f3f3f3f, ans = INF;
    for (let i = m - 2; i >= 0; i--) {
        for (let j = 0; j < n; j++) {
            let cur = INF;
            for (let k = 0; k < n; k++) cur = Math.min(cur, grid[i + 1][k] + moveCost[grid[i][j]][k]);
            grid[i][j] += cur;
        }
    }
    for (let i = 0; i < n; i++) ans = Math.min(ans, grid[0][i]);
    return ans;
};
  • 时间复杂度: ,其中 分别代表给定 grid 的长宽
  • 空间复杂度:

最后

这是我们「刷穿 LeetCode」系列文章的第 No.2304 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/204046.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

设计模式之十二:复合模式

模式通常被一起使用&#xff0c;并被组合在同一个解决方案中。 复合模式在一个解决方案中结合两个或多个模式&#xff0c;以解决一般或重复发生的问题。 首先重新构建鸭子模拟器&#xff1a; package headfirst.designpatterns.combining.ducks;public interface Quackable …

Scala如何写一个通用的游戏数据爬虫程序

以前想要获取一些网站数据的时候&#xff0c;都是通过人工手动复制粘贴&#xff0c;这样的效率及其低下。数据少无所谓&#xff0c;如果需要采集大量数据&#xff0c;手动就显得乏力了。半夜睡不着&#xff0c;爬起来写一段有关游戏商品数据的爬虫通用模板&#xff0c;希望能帮…

Servlet实现一个简单的表白墙网站

文章目录 前言效果展示事前准备HTML、CSS、JavaScript分别负责哪些HTML和CSS构架出页面的基本结构和样式JavaScript 实现行为和交互实现服务器端的业务代码整理pom.xmlweb.xmlmessageWall.htmlMessageServlet.java 前言 前面我们学习了 Java 中知名的 HTTP 服务器 tomcat 的安…

linux下的工具---yum

一、什么是yum yum是Linux下的软件包管理器 二、什么是软件包管理器 1、在Linux下安装软件, 一个通常的办法是下载到程序的源代码, 并进行编译, 得到可执行程序. 2、但是这样太麻烦了, 于是有些人把一些常用的软件提前编译好, 做成软件包(可以理解成windows上的安装程序)放在…

【密码学引论】Hash密码

第六章 Hash密码 md4、md5、sha系列、SM3 定义&#xff1a;将任意长度的消息映射成固定长度消息的函数功能&#xff1a;确保数据的真实性和完整性&#xff0c;主要用于认证和数字签名Hash函数的安全性&#xff1a;单向性、抗若碰撞性、抗强碰撞性生日攻击&#xff1a;对于生日…

保护您的IP地址:预防IP地址盗用的关键措施

随着互联网的发展&#xff0c;IP地址作为标识互联网设备的重要元素&#xff0c;成为网络通信的基石。然而&#xff0c;IP地址盗用威胁正不断增加&#xff0c;可能导致敏感信息泄露、未经授权的访问和网络攻击。本文将介绍一些有效的方法&#xff0c;以帮助组织和个人预防IP地址…

初学vue3与ts:路由跳转带参数

index-router <!-- 路由跳转 --> <template><div><div class"title-sub flex"><div>1、用router-link跳转带参数id1&#xff1a;</div><router-link to"./link?id1"><button>点我跳转</button>&…

scipy 笔记:scipy.spatial.distance

1 pdist 计算n维空间中观测点之间的成对距离。 scipy.spatial.distance.pdist(X, metriceuclidean, *, outNone, **kwargs) 1.1 主要参数 X一个m行n列的数组&#xff0c;表示n维空间中的m个原始观测点metric使用的距离度量out输出数组。如果非空&#xff0c;压缩的距离矩阵…

Mindomo Desktop for Mac免费思维导图软件,助您高效整理思维

思维导图是一种强大的工具&#xff0c;可以帮助我们整理思维、提高记忆力、激发创造力。而Mindomo Desktop for Mac作为一款免费的思维导图软件&#xff0c;能够帮助我们更高效地进行思维整理和项目管理。在本文中&#xff0c;我们将介绍Mindomo Desktop for Mac的功能和优势&a…

C++ day41 动态规划 整数拆分 不同的二叉搜索树

题目1&#xff1a;343 整数拆分 题目链接&#xff1a;整数拆分 对题目的理解 将正整数n&#xff0c;拆分成k个正整数的和&#xff08;k>2&#xff09;使得这些整数的乘积最大化&#xff0c;返回最大乘积 动规五部曲 1&#xff09;dp数组的含义以及其下标i的含义 dp[i]…

Linux shell编程学习笔记31:alias 和 unalias 操作 命令别名

目录 0 前言1 定义别名2 查看别名 2.1 查看所有别名2.2 查看某个别名 2.2.1 alias 别名2.2.2 alias | grep 别名字符串2.2.3 使用 CtrlAltE 组合键3 unalias&#xff1a;删除别名4 如何执行命令本身而非别名 4.1 方法1&#xff1a;使用 CtrlAltE 组合键 && unalias4…

主机的具体权限规划:ACL的使用

目的&#xff1a;针对某一用户或某一组来设置特定权限需求&#xff0c;针对上&#xff0c;接着设置 ACL可以针对单一用户&#xff0c;文件&#xff0c;或者目录来进行rwx的权限设置&#xff0c;对于需要特殊权限的设置非常有帮助。 第一&#xff0c;查看文件系统是否支持&…

YOLOv5算法进阶改进(5)— 主干网络中引入SCConv | 即插即用的空间和通道维度重构卷积

前言:Hello大家好,我是小哥谈。SCConv是一种用于减少特征冗余的卷积神经网络模块。相对于其他流行的SOTA方法,SCConv可以以更低的计算成本获得更高的准确率。它通过在空间和通道维度上进行重构,从而减少了特征图中的冗余信息。这种模块的设计可以提高卷积神经网络的性能。�…

【开源】基于JAVA的森林火灾预警系统

项目编号&#xff1a; S 019 &#xff0c;文末获取源码。 \color{red}{项目编号&#xff1a;S019&#xff0c;文末获取源码。} 项目编号&#xff1a;S019&#xff0c;文末获取源码。 目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 数据中心模块2.2 系统基础模块2.3 烟…

前五年—中国十大科技进展新闻(2012年—2017年)

前五年—中国十大科技进展新闻&#xff08;2012-2017&#xff09; 2017年中国十大科技进展新闻1. 我国科学家利用化学物质合成完整活性染色体2. 国产水下滑翔机下潜6329米刷新世界纪录3. 世界首台超越早期经典计算机的光量子计算机诞生4. 国产大型客机C919首飞5. 我国首次海域天…

02【SpringBoot静态处理、错误处理】

目录 一、SpringBoot的WEB开发 1.1 静态资源的处理 1.1.1 静态资源目录 1&#xff09;SpringBoot静态资源处理 2&#xff09;关于静态资源处理的配置 3&#xff09;欢迎页面的处理 4&#xff09;修改SpringBoot资源访问路径 1.1.2 WebJars资源 1.2 注册Servlet三大组件…

java学习part17final

110-面向对象(高级)-关键字final的使用及真题_哔哩哔哩_bilibili 1.概念 tips&#xff1a;java里有const关键字&#xff0c;但是用于保留字&#xff0c;不会使用&#xff0c;目前没有意义。 final变量没有默认赋值&#xff0c;只能在以下三个地方赋值&#xff0c;且只能赋值一…

03、K-means聚类实现步骤与基于K-means聚类的图像压缩(1)

03、K-means聚类实现步骤与基于K-means聚类的图像压缩&#xff08;1&#xff09; 03、K-means聚类实现步骤与基于K-means聚类的图像压缩&#xff08;1&#xff09; 03、K-means聚类实现步骤与基于K-means聚类的图像压缩&#xff08;2&#xff09; 开始学习机器学习啦&#xf…

【数据库】基于排序算法的去重,集合与包的并,差,交,连接操作实现原理,执行代价以及优化

基于两趟排序的其它操作 ​专栏内容&#xff1a; 手写数据库toadb 本专栏主要介绍如何从零开发&#xff0c;开发的步骤&#xff0c;以及开发过程中的涉及的原理&#xff0c;遇到的问题等&#xff0c;让大家能跟上并且可以一起开发&#xff0c;让每个需要的人成为参与者。 本专栏…

【Android】Android Framework系列--Launcher3各启动场景源码分析

Android Framework系列–Launcher3各启动场景源码分析 Launcher3启动场景 Launcher3是Android系统提供的默认桌面应用(Launcher)&#xff0c;它的源码路径在“packages/apps/Launcher3/”。 Launcher3的启动场景主要包括&#xff1a; 开机后启动&#xff1a;开机时&#xff…