Skip to content

Latest commit

 

History

History
173 lines (124 loc) · 5.53 KB

20220513.md

File metadata and controls

173 lines (124 loc) · 5.53 KB

Algorithm

322. Coin Change

Description

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Example 1:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

Example 3:

Input: coins = [1], amount = 0
Output: 0

Constraints:

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 231 - 1
  • 0 <= amount <= 104

Solution

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

Discuss

Java 中将实参传递给方法（或函数）的方式是 值传递 ：

如果参数是基本类型的话，很简单，传递的就是基本类型的字面量值的拷贝，会创建副本。 如果参数是引用类型，传递的就是实参所引用的对象在堆中地址值的拷贝，同样也会创建副本。

Review

Tip

Share

关于面试

  1. 如何准备基础知识

  • 提纲挈领画脑图: 可以根据目标岗位的招聘要求整理知识点 (1) 列出关键的知识点名称 例如: 计算机网络知识点 (2) 根据简历上的项目往知识点方向靠拢 例如: 在项目过程中遇到网络500的错误码，我是怎么排查的

  • 结合自身项目经验和公开的知识点，总结常见的问题，对解决方案触类旁通 (1) 关注大厂的技术输出，比如JVM性能优化方案、Java锁优化、监控服务原理等 (2) 回答项目问题时，从本质原理出发，然后构造思路和框架，寻找解决方案 例如: 如何优化计算机性能，我们从IO和计算两个角度，分别做存储优化和计算复杂度优化，这里可以参考Kafka的高可用原理知识点

  • 擅长的方向要有充分的准备 (1) 对比较熟悉的领域要有深刻的了解，面试会由浅到深挖掘，不会的地方可以从自身如何解决问题的角度分析，还是不会做到知之为知之，不知为不知 例如: 计算机网络中MTU含义，在网络传输中的应用场景，进而涉及到TCP如何保证传输的顺序性，UDP能不能保证顺序性，为什么UDP发送视频帧还是能够顺序播放等等

  • 准确描述算法原理并分析 对于动态规划、双指针能够分析他们是解决哪一类问题，算法复杂度以及优化空间 对于常见的机器学习算法，能够熟练进行公式推到和应用场景介绍，以及延伸到你看过的论文或者你正在做的课题

  • 技术选型优劣分析 对于你在项目里面用到的底层数据库，为什么要用？解决什么问题？消息中间件用的推模式还是拉模式？如何保证顺序性？有没有替代方案？高可用场景下如何做到限流熔断？算法如果应用在工程领域如何做好灰度验证？引流策略如何制定？DB中的数据一致性可以通过哪些手段去保障等等

  1. 如何准备项目介绍
  • 提纲挈领抓重点

STAR原则:

Situation: 项目背景 Target: 目标如何拆解 Action: 你采取了哪些行动解决了哪些问题 Result: 最后的效果(能够量化)以及总结反思

  • 对项目架构和业务逻辑有充分了解

  • 言简意赅介绍项目整体框架和关键设计

框架 设计模式 技术选型 中间件 核心领域模型

  • 业务/技术解决方案选型、决策逻辑

为什么要用 解决什么问题 如何优化

  • 涉及到的组件充分掌握 Hbase底层原理 与MySQL的区别

  • 疑难杂症问题排查 内存泄漏 Full GC 慢SQL优化 定时任务排查 并发问题排查 幂等设计

  1. 如何准备算法

(1) 按照类别横向准备，按照所投公司的Top问题纵向练习 (2) 常见的数据结构及其操作要会 (3) 适度刷题，LeetCode中等及以下或者剑指Offer (4) 触类旁通，排序、二叉树、DFS、BFS、动态规划、链表双指针很多问题都是有一些模板解决方案，学会一个即可 (5) 面试的过程中:

  • 多跟面试官沟通、不明确题意多问，不要上来就写
  • 分析是哪一类问题，想如何去解决
  • 代码要能够讲明白，并且经得住条件
  • 注意边界条件和特殊case
  • 思路清晰，可以通过注释划分子问题，然后逐一解决
  • 注意编码风格和规范，如变量命名、注释、格式化等
  1. 哪些知识点会重点考察

  • 计算机网络、操作系统、数据库、数据结构和算法、编译原理、组成原理

  • 熟悉C++/C/Java/Python/Go其中一种即可，了解其特性和原理

  • 参考教材可以选一些比较经典的

如果有实习经历

  • 可以准备下中间件Dubbo、MQ、Redis的原理和使用场景
  • 服务治理方案、领域建模能力、微服务划分
  • 结合自己项目，重点关注你的理解和思考