算法题二-贪心算法类型

题目来自leetcode

强度：简单

给你一个非负整数 num ，请你返回将它变成 0 所需要的步数。 如果当前数字是偶数，你需要把它除以 2 ；否则，减去 1 。

1
2
3
4
5
6
7
8
9
10
11
示例 1：

输入：num = 14
输出：6
解释：
步骤 1) 14 是偶数，除以 2 得到 7 。
步骤 2） 7 是奇数，减 1 得到 6 。
步骤 3） 6 是偶数，除以 2 得到 3 。
步骤 4） 3 是奇数，减 1 得到 2 。
步骤 5） 2 是偶数，除以 2 得到 1 。
步骤 6） 1 是奇数，减 1 得到 0 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
示例 2：

输入：num = 8
输出：4
解释：
步骤 1） 8 是偶数，除以 2 得到 4 。
步骤 2） 4 是偶数，除以 2 得到 2 。
步骤 3） 2 是偶数，除以 2 得到 1 。
步骤 4） 1 是奇数，减 1 得到 0 。

​```
示例 3：

输入：num = 123
输出：12
​```


1
2
3
提示：

0 <= num <= 10^6

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-steps-to-reduce-a-number-to-zero
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这个没啥好讲的思路

就轮询->再判断奇数偶数

image-20200226021807639

说里说一下判断奇数偶数的 (num&1)==1

a&b即a与b

a的二进制操作位与b的二进制操作数等于1 否则等于0

这里 11和13的二进制是1011和1101

1
2
3
4
5
6
1011  1101
1=1 1
0！=1 0
1=！0 0
1=1 1
结果为1001 十进制为9

再来一个带入这个实际情况的例子

14&1和7&1

1110&1 111&1

1
2
3
4
5
6
7
1110 1
0！=1 0
后面三位就是000 得到结果为1000 十进制为8
111 1
1=1 1
二进制1的十进制也是1 结果为1

多数情况下 判断骑数偶数时 使用这种方法比使用运算符更省内存。

第二题 玩筹码 难度：简单

数轴上放置了一些筹码，每个筹码的位置存在数组 chips 当中。

你可以对 任何筹码 执行下面两种操作之一（不限操作次数，0 次也可以）：

将第 i 个筹码向左或者右移动 2 个单位，代价为 0。
将第 i 个筹码向左或者右移动 1 个单位，代价为 1。
最开始的时候，同一位置上也可能放着两个或者更多的筹码。

返回将所有筹码移动到同一位置（任意位置）上所需要的最小代价。

1
2
3
4
5
示例 1：

输入：chips = [1,2,3]
输出：1
解释：第二个筹码移动到位置三的代价是 1，第一个筹码移动到位置三的代价是 0，总代价为 1。
1
2
3
4
5
示例 2：

输入：chips = [2,2,2,3,3]
输出：2
解释：第四和第五个筹码移动到位置二的代价都是 1，所以最小总代价为 2。
1
2
3
4
提示：

1 <= chips.length <= 100
1 <= chips[i] <= 10^9

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/play-with-chips
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这一题说实话 读这个题目就很难，其他都还好;

思路：

根据

1
将第 i 个筹码向左或者右移动 2 个单位，代价为 0。

可以得到一个结论 奇数移到奇数 偶数移到偶数代价都为0

代价增加的主要原因是奇数-偶数 或者偶数-奇数的位移

代入示例二

这句话真是他妈的精华 示例二意思是位置2有3个筹码

位置3有二个筹码

把位置2的两个筹码位移到位置2 明显最优

得到结论 求得是奇数偶数较小的一方的总和

代码很简单 主要是理解 这他妈不是算法题 是理解题

1
2
3
4
5
6
7
8
9
10
11
12
13
public static int minCostToMoveChips(int[] chips) {

      int odd = 0, even = 0;
      for (int i = 0; i < chips.length; i++) {


          if ((chips[i]&1)==1)
              odd++;
          else
              even++;
      }
      return Math.min(even, odd);
  }