DoorDash 面试经验分享：城市景点路线优化 | 面试代面, OA代做, 面试辅导

DoorDash 面试经验分享：城市景点路线优化 | 面试代面, OA代做, 面试辅导

在这次DoorDash的面试中，考官要求实现一个算法来优化城市中的景点路线，目的是在限定的时间内获取尽可能高的景点美丽值。这个问题涉及图论的基础算法，考察了考生对图的遍历、深度优先搜索（DFS）和动态规划（DP）等知识的掌握。通过这个问题，考官能够评估考生在解决复杂路径问题和优化策略方面的能力。

如果你希望在这样的面试中脱颖而出，我们的代面服务可以为你提供全面的准备，帮助你掌握各种算法和编程技巧，以便在面试中展示出最佳表现。

想要了解更多或获取我们的服务，欢迎添加微信 leetcode-king。

---

题目：优化城市景点路线

Problem Description:

You have just arrived in a new city and would like to see its sights. Each sight is located in a square and you have assigned each a beauty value. Each road to a square takes an amount of time to travel, and you have limited time for sightseeing. Determine the maximum value of beauty that you can visit during your time in the city. Start and finish at your hotel, the location of sight zero.

Parameters:

• int n: an integer, the number of sights in the city
• int m: an integer, the number of connecting roads
• int max_t: an integer, the amount of time for sightseeing
• int beauty[n]: integer array, the beauty values you have assigned to each sight
• int u[m]: integer array, the starting sight location for each bidirectional road
• int v[m]: integer array, the ending sight location for each bidirectional road
• int t[m]: integer array, the travel time for each bidirectional road

Returns:

• int: an integer, the maximum sum of beauty values of squares you will visit.

Constraints:

• 1 ≤ n ≤ 1000
• 1 ≤ m ≤ 2000
• 10 ≤ max_t ≤ 100
• 0 ≤ u[i], v[i] ≤ n - 1
• u[i] ≠ v[i]
• 1 ≤ t[i] ≤ 100
• 0 ≤ beauty[i] ≤ 10^8

Example:

n = 4
m = 3
max_t = 50
beauty = [5, 10, 15, 20]
u = [0, 1, 0]
v = [1, 2, 3]
t = [10, 10, 10]

Output: 43

Solution:

import java.util.*;

public class CityAttractions {

    static class Edge {
        int destination;
        int travelTime;

        Edge(int destination, int travelTime) {
            this.destination = destination;
            this.travelTime = travelTime;
        }
    }

    public int findBestPath(int n, int m, int max_t, int[] beauty, int[] u, int[] v, int[] t) {
        Map<Integer, List<Edge>> graph = new HashMap<>();
        for (int i = 0; i < n; i++) {
            graph.put(i, new ArrayList<>());
        }

        for (int i = 0; i < m; i++) {
            graph.get(u[i]).add(new Edge(v[i], t[i]));
            graph.get(v[i]).add(new Edge(u[i], t[i]));
        }

        boolean[] visited = new boolean[n];
        return findBestPathHelper(graph, beauty, max_t, 0, visited);
    }

    private int findBestPathHelper(Map<Integer, List<Edge>> graph, int[] beauty, int curTime, int curNode, boolean[] visited) {
        visited[curNode] = true;
        int maxGain = 0;

        for (Edge edge : graph.get(curNode)) {
            if (!visited[edge.destination] && curTime >= edge.travelTime) {
                maxGain = Math.max(maxGain, findBestPathHelper(graph, beauty, curTime - edge.travelTime, edge.destination, visited));
            }
        }

        visited[curNode] = false;
        return maxGain + beauty[curNode];
    }

    public static void main(String[] args) {
        CityAttractions ca = new CityAttractions();
        int n = 4;
        int m = 3;
        int max_t = 50;
        int[] beauty = {5, 10, 15, 20};
        int[] u = {0, 1, 0};
        int[] v = {1, 2, 3};
        int[] t = {10, 10, 10};

        System.out.println(ca.findBestPath(n, m, max_t, beauty, u, v, t)); // Output: 43
    }
}