发表于

题目描述

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。

如果没有任何一种硬币组合能组成总金额，返回 -1。

解析

我们采用自下而上的方式进行思考。仍定义 F(i)，F(i) 为组成金额 i 所需最少的硬币数量，假设在计算 F(i)之前，我们已经计算出 F(0)-F(i-1)的答案。 再算上枚举的这枚硬币数量 1 的贡献，由于要硬币数量最少，所以 F(i) 为前面能转移过来的状态的最小值加上枚举的硬币数量 1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
  public int coinChange(int[] coins, int amount) {
    int max = amount + 1;
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, max);
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
      for (int j = 0; j < coins.length; j++) {
        if (coins[j] <= i) {
          dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
        }
      }
    }
    return dp[amount] > amount ? -1 : dp[amount];
  }
}

转载自：

  1. 零钱兑换

发表于 | 更新于

题目描述

给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

解析

首先我们给一个通用的解法：

1
2
3
4
5
6
7
8
9
10
11
var removeDuplicates = function(nums) {
    if(nums.length == 0)return 0;
    var i =0;
    for(var j =0; j< nums.length;j++){
        if(nums[j] != nums[i])
        {
            nums[++i] = nums[j];
        }
    }
        return i + 1;
};

转载自：

  1. 删除排序数组中的重复项

发表于

时间复杂度

  1. 时间复杂度的表示方式用符号来表示就是大O。

T(n)=O(f(n))
其中，T(n)就是算法的时间复杂度；
f(n)表示执行与算法优劣和问题规模有关的执行数；
O()表示一种运算符号，和加减乘除类似。作用就是去除其他项，包括与最高项相乘的常数，只保留最高项，比如f(n)=2n^2+1,O(f(n))=O(n^2)

  1. 常见的时间复杂度量级进行大O的理解：

常数阶O(1)
无论代码执行了多少行，其他区域不会影响到操作，这个代码的时间复杂度都是O(1)
void swapTwoInts(int &a, int &b){
int temp = a;
a = b;
b = temp;
}

线性阶O(n)
一个普通for循环里面的代码会执行 n 遍，因此它消耗的时间是随着 n 的变化而变化的，因此可以用O(n)来表示它的时间复杂度

平方阶O(n²)
存在双重循环的时候，即把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²) 了

对数阶O(logn)
比如一个函数，总是把参数除以2，既：n/2，折半查找的核心步骤就是这个。那么最终函数运行时间，应该是：log n，也就是O(log n)
线性对数阶O(nlogn)
将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n * O(logn)，也就是了O(nlogn)。

参考资料：

  1. 如何清晰的理解算法中的时间复杂度？
  2. 快速排序算法C++实现[评注版]
  3. 快速排序算法的时间复杂度分析[详解Master method]

发表于 | 更新于

记得多年前面试的时候就在手写斐波那契数列上栽过，今天就趁这机会在这总结下。这题虽是老生常谈了，

但相信我这里分享的一定会给自己和你们一个温故而知新的机会。

题目描述

斐波那契数列是一位意大利的数学家，他闲着没事去研究兔子繁殖的过程，研究着就发现，可以写成这么一个序列：1，1，2，3，5，8，13，21… 也就是每个数等于它前两个数之和。那么给你第 n 个数，问 F(n) 是多少。

解析

首先我们给一个通用的解法：

1
2
3
4
5
6
7
8
9
10
class Solution {
  public int fib(int N) {
      if (N == 0) {
          return 0;
      } else if (N == 1) {
          return 1;
      }
      return fib(N-1) + fib(N-2);
  }
}

这个算法的复杂度太高了，有些函数会重复执行的。

优化算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int fib(int N) {
        int a = 0;
        int b = 1;
        if(N == 0) {
            return a;
        }
        if(N == 1) {
            return b;
        }
        for(int i = 2; i <= N; i++) {
            int tmp = a + b;
            a = b;
            b = tmp;
        }
        return b;
    }
}

参考资料：

  1. 这才是面试官想听的：详解「递归」正确的打开方式

发表于

题目： 如何判断一个数是否是2的n次方，要求时间复杂度为O(1).

常规数学解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function isPowerOfTwo(n){
    if(n > 0){
      while(n > 1){
       if(n%2 == 0){
        n = n / 2;
       }else{
        return false;
       }
    }
    return true;
    }else{
    return false;
    }
}

如果面试官看见你写出这样的代码，可能印象就会大打折扣，因为时间复杂度不是O(1),虽然解法没问题，那么我们要往编程方面换个思路。

思路： 考察的是位运算，尤其是对二进制的理解；当一个数为2的n 次方时，整个二进制数，只有他本位是1 其他位为0，如果我们给这个数减一，那么本位变为0 其他位全部变成1；我们可以通过&运算， 如果为0即为2的n次方; 本题暂不讨论n为分数（既浮点数）的情况。

例子： 我们通过8来进行举例 他是2的3次方。

0 0 0 0 1 0 0 0 //数字8
0 0 0 0 0 1 1 1 //数字7
0 0 0 0 0 0 0 0 //&运算的结果

代码实现：

1
2
3
4
public static  boolean isPowerOfTwo(int n){

   return n > 0 && (n & n - 1) == 0;
}

参考资料：

  1. 随笔-如何判断一个数是否是2的n次方O(1)算法
  2. js 判断一个数字是不是2的n次方幂的实例
0%