第5章 第3节 复杂度

2021/01/04 09:59
阅读数 78

● 一行里有很多IP地址,互相之间用 || 隔开,共有一万行。要求:取双竖线分隔的倒数第二列所有的IP地址并且去重并输出每个IP地址的出现次数。

参考回答:

考虑时间效率,用trie树统计每个IP出现的次数,时间复杂度是O(n*le)(le表示IP的平均长度)。

● 手写代码:硬币找零问题(要求时间复杂度最佳)

参考回答:

给定一组硬币数,找出一组最少的硬币数,来找换零钱N。

如何减小时间复杂度:不用全局变量来保存计算过的值,也不用递归的方法来实现,用一个一维数组,再用循环来实现。

public int coinChange(int[] coins, int amount) {if (coins == null || coins.length == 0 || amount <= 0)return 0;int[] minNumber = new int[amount + 1];for (int i = 1; i <= amount; i++) {minNumber[i] = amount + 1;for (int j = 0; j < coins.length; j++) {if (coins[j] <= i && minNumber[i - coins[j]] != amount + 1)minNumber[i] = Integer.min(minNumber[i], 1 + minNumber[i - coins[j]]);}}if (minNumber[amount] == amount + 1)return -1;elsereturn minNumber[amount];}


时间复杂度为O(c*n),c是coin的数量,n是amount的值。

图片


展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部