动态规划
给你一个由 无重复 正整数组成的集合 nums ，请你找出并返回其中最大的整除子集 answer ，子集中每一元素对 (answer[i], answer[j]) 都应当满足：
-
answer[i] % answer[j] == 0 ，或
-
answer[j] % answer[i] == 0
如果存在多个有效解子集，返回其中任何一个均可。
示例 1：
输入：nums = [1,2,3]
输出：[1,2]
解释：[1,3] 也会被视为正确答案。
示例 2：
输入：nums = [1,2,4,8]
输出：[1,2,4,8]
我的解答
思路一
先找出有倍数关系的结果，然后找出能除尽有倍数关系的每一个元素，如果结果是每一个元素的倍数，那么把这个结果添加到结果中，这样这个列表会越来越长，看是否能得到最终的结果
func largestDivisibleSubset(nums []int) []int {
var answer []int
ins := false
OuterLoop:
for i:=0;i<len(nums);i++{
for j:=i+1;j<len(nums);j++{
if nums[i] % nums[j] == 0 || nums[j] % nums[i] == 0{
answer = append(answer, nums[i], nums[j])
ins = true
break OuterLoop;
}
}
}
if ins{
for _,num := range nums{
ok := true
for _,ans := range answer{
if num % ans != 0{
ok = false
break
}
}
if ok{
in := false
for _,obj := range answer{
if num == obj{
in = true
}
}
if !in{
answer = append(answer,num)
}
}
}
}
if len(answer) == 0 && len(nums) >= 0{
answer = []int{nums[0]}
}
return answer
}
结果：21 / 48 个通过测试用例
输入
[3,4,16,8]
输出
[4,16]
预期结果
[4,8,16]
思路二
既然要求最大长度的整除子集，那么就先将它排序，排序后计算首位的倍数，假订首位一定是因数。
func largestDivisibleSubset(nums []int) []int {
for i := 1;i<len(nums);i++{
tmpv := nums[i]
j := i-1
for ;j >= 0 && nums[j] > tmpv;j--{
nums[j+1] = nums[j]
}
nums[j+1] = tmpv
}
if len(nums) <= 1{
return nums
}
answer := []int{nums[0]}
for _,num := range nums[1:len(nums)]{
ok := true
for _,ans := range answer{
if num % ans != 0{
ok = false
break
}
}
if ok{
answer = append(answer, num)
}
}
return answer
}
结果：34 / 48 个通过测试用例
输入
[3,4,16,8]
输出
[3]
预期结果
[4,8,16]
思路三
既然最小的数不一定是因子，那么就枚举每一个对象，假订每一个数都可能是最小因子，然后选出最优
func largestDivisibleSubset(nums []int) []int {
for i := 1;i<len(nums);i++{
tmpv := nums[i]
j := i-1
for ;j >= 0 && nums[j] > tmpv;j--{
nums[j+1] = nums[j]
}
nums[j+1] = tmpv
}
if len(nums) <= 1{
return nums
}
var res []int
for i:=0;i<len(nums);i++{
answer := []int{nums[i]}
for j:=i+1;j<len(nums);j++{
ok := true
for _,ans := range answer{
if nums[j] % ans != 0{
ok = false
break
}
}
if ok{
answer = append(answer, nums[j])
}
}
if len(answer) > len(res){
res = answer
}
}
return res
}
结果：39 / 48 个通过测试用例
输入
[5,9,18,54,108,540,90,180,360,720]
输出
[5,90,180,360,720]
预期结果
[9,18,90,180,360,720] //枚举到9时，命中了[9,18,54,108,540],和结果一样长
思路四
既然有可能是跳过某个对象的，那么排序就没有用呀，不如直接枚举每个对象为可能是最小公因数，然后找出最长的，当相等时，不加入到最优的列表
func largestDivisibleSubset(nums []int) []int {
if len(nums) <= 1{
return nums
}
var arr []int
for i:=0;i<len(nums);i++{
obj := []int{nums[i]}
fmt.Println("---",obj)
for j:=0;j<len(nums);j++{
ok := true
for _,ans := range obj {
if ans % nums[j] != 0 && nums[j] % ans != 0{
ok = false
break
}
}
if ok && nums[j] != obj[0]{
obj = append(obj, nums[j])
}
}
if len(obj)>len(arr){
arr = obj
}
}
for i := 1;i<len(arr);i++{
tmpv := arr[i]
fmt.Println(arr[i])
j := i-1
for ;j >= 0 && arr[j] > tmpv;j--{
arr[j+1] = arr[j]
}
arr[j+1] = tmpv
}
return arr
}
结果：43 / 48 个通过测试用例
输入
[5,9,18,54,108,540,90,180,360,720]
输出
[9,18,54,108,540]
预期结果
[9,18,90,180,360,720]
思路五
看没有通过的测试用例，如果从最大开始找，那么是可以将最长记录找出来的
func sortArr(nums []int)[]int{
for i := 1;i<len(nums);i++{
tmpv := nums[i]
j := i-1
for ;j >= 0 && nums[j] > tmpv;j--{
nums[j+1] = nums[j]
}
nums[j+1] = tmpv
}
return nums
}
func largestDivisibleSubset(nums []int) []int {
if len(nums) <= 1{
return nums
}
nums = sortArr(nums)
var arr []int
for i:=len(nums)-1;i>-1;i--{
ins := nums[i]
answer := []int{ins}
for j:=i-1;j > -1;j--{
if ins % nums[j] == 0{
answer = append(answer, nums[j])
ins = nums[j]
}
}
fmt.Println(sortArr(answer))
if len(arr) < len(answer){
arr = answer
}
}
return sortArr(arr)
}
结果：45 / 48 个通过测试用例
输入
[4,8,10,240]
输出
[10,240]
预期结果
[4,8,240]
总结
总结一下，到这里，以上所有的思路，都不会得到最终结果，因枚举到某个对象时，他可能的因数可能会跳过比当前数小的值，最长的可能是比之次小的因数，所以美剧一种的前提下是有可能由多种情况的，但是这个情况用暴力的方式很难解决，以[4,8,10,240]为例，会有以下枚举树，代码实现不确定的树形，不好实现，所有这种思路感觉也不可取
动态规划（dynamic programming）
Simplifying a complicated problem by breaking it down into simpler sub-problems
动态规划常常适用于分治和最优子结构性质的问题
动态规划与递归
动态规划和递归或者分治没有根本上的区别（关键看有无最优的子结构）
共性：找到重复子问题
差异性：动态规划是最优子结构，中途可以淘汰次优解
动态规划是自底向上，递归是自顶向下
啥叫「自顶向下」？
注意我们刚才画的递归树（或者说图），是从上向下延伸，都是从一个规模较大的原问题比如说 f(20)，向下逐渐分解规模，直到 f(1) 和 f(2) 触底，然后逐层返回答案，这就叫「自顶向下」
func fibo(n int)int{
if n<=1{
return n
}
return fibo(n-1)+fibo(n-2)
}
啥叫「自底向上」？
反过来，我们直接从最底下，最简单，问题规模最小的 f(1) 和 f(2) 开始往上推，直到推到我们想要的答案 f(20)，这就是动态规划的思路，这也是为什么动态规划一般都脱离了递归，而是由循环迭代完成计算。
func fibo(n int) int {
dp := make([]int, n+1)
dp[0] = 0
dp[1] = 1
for i := 2; i <= n; i++ {
dp[i] = dp[i-1] + dp[i-2]
}
return dp[n]
}
Count the paths
黄色框是障碍物，只能向右或者向下走，有多少种走法？
递归
dp递推
dp递推结果
最终解答
func largestDivisibleSubset(nums []int) (res []int) {
sort.Ints(nums)
// 第 1 步：动态规划找出最大子集的个数、最大子集中的最大整数
n := len(nums)
dp := make([]int, n)
for i := range dp {
dp[i] = 1
}
maxSize, maxVal := 1, 1
for i := 1; i < n; i++ {
for j, v := range nums[:i] {
if nums[i]%v == 0 && dp[j]+1 > dp[i] {
dp[i] = dp[j] + 1
}
}
if dp[i] > maxSize {
maxSize, maxVal = dp[i], nums[i]
}
}
if maxSize == 1 {
return []int{nums[0]}
}
// 第 2 步：倒推获得最大子集
for i := n - 1; i >= 0 && maxSize > 0; i-- {
if dp[i] == maxSize && maxVal%nums[i] == 0 {
res = append(res, nums[i])
maxVal = nums[i]
maxSize--
}
}
return
}
serviceBroker
初始化
每种资源封装为一个client
class DeploymentClient(Service):
SERVICE_ID = "f599ff6b-23ad-4dc4-a671-daocloud-deployment"
PLAN_ID = "deployment-plan-default"
api_rollback_address = "{}/v1/namespaces/{}/deployments/{}/rollback"
api_get_version_address = "{}/v1/namespaces/{}/deployments/{}/replicasets"
api_list_address = "{}/v1/namespaces/{}/deployments"
api_get_address = "{}/v1/namespaces/{}/deployments/{}"
api_delete_address = "{}/v1/namespaces/{}/deployments/{}"
api_create_address = "{}/v1/namespaces/{}/deployments"
api_update_address = "/v1/namespaces/{}/deployments/{}/scale"
def __init__(self, base_url, username=None, password=None):
super(DeploymentClient, self).__init__(base_url, username, password)
注册serviceBroker
serviceBroker = ServiceBroker()
serviceBroker.register(
RouteClient(
config.APP_BROKER_BACKEND_ADDRESS, config.APP_BROKER_BACKEND_USERNAME, config.APP_BROKER_BACKEND_PASSWORD
)
)
class ServiceBroker:
def __init__(self):
self._services = []
self._services_mapper = {}
def register(self, server: Service):
self._services.append(server)
self._services_mapper[server.SERVICE_ID] = server
def get_server(self, server_id):
return self._services_mapper[server_id]
def get_catalog(self):
return {"services": [server.get_service() for server in self._services]}
将注册的service入库
def init_platform_services():
...
catalog = adapter_service_catalog("platform_service_zone_mock")
if not catalog and not catalog.get("services"):
raise NotFoundException(gettext("Get services from platform_service_catalog"))
services = catalog.get("services")
LOG.info("Platform service has {} services in total.".format(len(services)))
for new_service in services:
new_plans = new_service.get("plans")
new_service_name = new_service.get("name")
old_service = (
session.query(ServiceModel)
.filter(ServiceModel.service_id == new_service.get("id"), ServiceModel.broker_id == "")
.first()
)
if old_service:
LOG.info("Service {} has already been added".format(new_service.get("name")))
else:
service_conflict = session.query(ServiceModel).filter(ServiceModel.name == new_service_name).first()
if service_conflict:
raise BadRequestException(gettext("Service {} has already been added".format(new_service_name)))
service_orm = ServiceModel(
name=new_service_name,
available=True,
plan_updateable=new_service.get("plan_updateable", False),
bindable=new_service.get("plan_updateable", False),
instances_retrievable=new_service.get("instances_retrievable", False),
instances_deletable=new_service.get("instances_deletable", True),
broker_id="",
service_id=new_service.get("id"),
)
session.add(service_orm)
LOG.info("update space of Service {}".format(new_service_name))
LOG.info("update plan of Service {} ".format(new_service_name))
update_service_plan(service_orm, new_plans)
LOG.info("Service {} has been added.".format(new_service_name))
init_platform_superservice_by_service(
service_orm, available="platform", superserivce_name=new_service.get("name")
)
载入superservice配置
def load_superservice_config():
superserivce_config_path = config.get_static_file_full_path("config/superservice_init_config.yml")
if not os.path.exists(superserivce_config_path):
return {}
with open(superserivce_config_path, encoding="utf-8") as f:
content = yaml.safe_load(f)
LOG.info("get {} SuperService from {}".format(len(content["superservices"]), superserivce_config_path))
return content["superservices"]
创建超服务,并更新service_type
superservice = Superservice(
name=supper_service.get("name", ""),
description=supper_service.get("description"),
short_description=supper_service.get("short_description", ""),
logo_url=logo_url,
pictures=pictures,
available=available,
)
if supper_service.get("service_type", ""):
service.service_type = supper_service.get("service_type")
session.add(service)
session.add(superservice)
session.flush()
查询deploy list
endpoint注入
space_management.add_url_rule(
rule="/v1/spaces/<space_id>/deployments",
endpoint="list_deployments:Deployment",
view_func=ViewFuncWrapper(
list_instances_view,
description=u"获取deployment列表",
header=BasicAuthHeader,
query=ZoneQuery,
responses={
"200": {"schema": ListSchema, "description": u"获取deployment列表成功"},
"404": {"schema": NotFound, "description": u"找不到对应的实例"},
},
tags=["deployment"],
),
methods=["GET"],
)
def list_instances_view(space_id):
endpoint = request.endpoint
zone_id = request.args.get("zone", "")
query_data = request.args
service = get_service_by_endpoint(endpoint)
space = get_space_by_id(space_id)
zone = get_zone_by_id(zone_id)
instances_data, status_code = open_list_instance(space, service, zone, query_data=query_data)
get_approving_instances(space_id, zone_id, service.id, status_code=status_code, instances_data=instances_data)
return instances_data, status_code
根据endpoint获取到service
def get_service_by_endpoint(endpoint):
service_type = endpoint.split(":")[-1]
with sqlalchemy_session() as session:
service = session.query(Service).filter(Service.service_type == service_type).first()
if not service:
raise NotFoundException(gettext("service type {} does not exists").format(service_type))
if not Service.available:
raise BadRequestException(gettext("error_service_unavailable"))
return service
broker上有封装了一层AdapterClient
def open_list_instance(space, service, zone, query_data=None):
user = g.user
# TODO FIX ME
LOCAL_REQUEST.headers = dict(username=user.username)
platform_query_params = {"space": space, "service": service, "zone": zone, "query": query_data}
try:
result, status_code = AdapterClient(
zone_id=platform_query_params.get("zone").id, service_id=platform_query_params.get("service").id
)._list_instance(platform_query_params)
except Exception as e:
LOG.info("List service type :%s fail: %s ", service.service_type, e)
raise e
return result, status_code
根据service_id获取对应的client
def _list_instance(self, json_data):
service_type = json_data.get("service").service_type
service_id = json_data.get("service").service_id
json_data["namespace"] = json_data.get("space").short_name
LOG.info("serviceBroker list service: %s start", service_type)
result, status_code = serviceBroker.get_server(service_id).list(json_data)
LOG.info("serviceBroker list service: %s result: %s", service_type, status_code)
if status_code in [200, 201]:
return result, status_code
else:
return self.get_error_respose(result)
最终执行client所实现的方法
def list(self, platform_parameters):
namespace = platform_parameters.get("namespace")
query_params = platform_parameters.get("query")
response = WrappedRequests.get(
self.api_list_address.format(self.base_url, namespace),
params=query_params,
auth=(self.username, self.password),
)
if response.status_code == 200:
return response.json(), 200
else:
LOG.error("list deployment error: %s %s", response.status_code, response.text)
raise InternalServerError(gettext("Deployment list error"), get_error_message(response))