转载

每周学算法/读英文/知识点心得分享 9.6

 每周一个 Algorithm,Review 一篇英文文章,总结一个工作中的技术 Tip,以及 Share 一个传递价值观的东西!

Algorithm: 学习算法

题目:Combination Sum (数字组合)

描述:

给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明:

  • 所有数字(包括 target)都是正整数。
  • 解集不能包含重复的组合。 

解题过程:

一般要求列出所有组合的题目,都可以用回溯法来解决。

回溯的核心思想是:

1.通过深度优先的方式求解。

2.每探索一个节点时,判断是否包含可行解。

3.当目前不符合要求时,回退到上一步继续探索。

解法:

 1 import java.util.ArrayList;
 2 import java.util.Arrays;
 3 import java.util.List;
 4 import java.util.stream.IntStream;
 5 
 6 /**
 7  * description : https://leetcode.com/problems/combination-sum/
 8  * contains unique/duplicates solutions
 9  * 题目描述 : https://leetcode-cn.com/problems/combination-sum/
10  * 包含 唯一/重复 两种解题思路
11  */
12 public class CombinationSum {
13 
14     public List<List<Integer>> combine(int[] candidates, int target) {
15         Integer[] objects =
16                 IntStream.of(candidates).boxed().toArray(Integer[]::new);
17         Arrays.sort(objects);
18         List<List<Integer>> result = new ArrayList<>();
19         if (target > 0) {
20             backtrace(result, new ArrayList<>(), target, objects, 0);
21         }
22         return result;
23     }
24 
25     private void backtrace(List<List<Integer>> result,
26                            List<Integer> arr, int remain,
27                            Integer[] candidates, int index) {
28         if (remain < 0) {
29             return;
30         } else if (remain == 0) {
31             result.add(new ArrayList<>(arr));
32         } else {
33             for (int i = index; i < candidates.length; i++) {
34                 arr.add(candidates[i]);
35                 backtrace(result, arr, remain - candidates[i],
36                         candidates, i);
37                 arr.remove(arr.size() - 1);
38             }
39         }
40     }
41 
42     public List<List<Integer>> combineUnique(int[] candidates,
43                                              int target) {
44         Integer[] objects =
45                 IntStream.of(candidates).boxed().toArray(Integer[]::new);
46         List<List<Integer>> result = new ArrayList<>();
47         Arrays.sort(objects);
48         if (target > 0) {
49             backtraceUnqiue(result, new ArrayList<>(), target,
50                     objects, 0);
51         }
52         return result;
53     }
54 
55     private void backtraceUnqiue(List<List<Integer>> result,
56                                  List<Integer> arr, int remain,
57                                  Integer[] candidates, int index) {
58         if (remain < 0) {
59             return;
60         } else if (remain == 0) {
61             if (!result.contains(arr)) {
62                 result.add(new ArrayList<>(arr));
63             }
64         } else {
65             for (int i = index; i < candidates.length; i++) {
66                 arr.add(candidates[i]);
67                 backtraceUnqiue(result, arr, remain - candidates[i],
68                         candidates, i + 1);
69                 arr.remove(arr.size() - 1);
70             }
71         }
72     }
73 
74 
75 }
Combination Sum

 

 

 

Review: 学习英文

 

Tips: 知识点

举个例子,某一面包房要把早晨制作的面包分发到全市的所有合作店铺里,店铺需要的面包数量各异,位置分散,并且一辆车运不完,要用多辆车给所有店铺配送。面包房要找出一个办法,用最少的车,行驶最短路程,送完所有面包。

这个就是运筹学中的车辆路径规划问题(VRP), 求解这个问题有很多方法,我介绍一种思路比较清晰,实现比较简单的方法 C-W 节约算法。

算法的核心思想是通过计算节点间的 节约距离, 根据节约距离来选择路径,从而节省最多的路程。

可以通过这个例子来理解: 节约里程法

具体实现参看我另一篇博文:基于C-W节约算法的车辆路径规划问题的Java实现

Share: 价值观

  人生苦难重重,如果你不解决问题,你就会成为问题。解决部分问题需要部分的自律,解决全部问题需要全部的自律。自律包括四部分:推迟满足感, 承担责任,忠于事实,平衡。

转载于:https://www.cnblogs.com/andrew-chen/p/11478698.html

正文到此结束
本文目录