关于后端:月度刷题活动同款与位运算结合的简单贪心题

题目形容

这是 LeetCode 上的 397. 整数替换 ，难度为 中等。

Tag :「DFS」、「BFS」、「贪婪」

给定一个正整数 n，你能够做如下操作：

1. 如果 n 是偶数，则用  n / 2 替换 n。
2. 如果 n 是奇数，则能够用 n + 1 或 n - 1 替换 n。

n 变为 $1$ 所需的最小替换次数是多少？

 示例 1：

输出：n = 8

输入：3

解释：8 -> 4 -> 2 -> 1

示例 2：

输出：n = 7

输入：4

解释：7 -> 8 -> 4 -> 2 -> 1
或 7 -> 6 -> 3 -> 2 -> 1

示例 3：

输出：n = 4

输入：2

提醒：

• $1 <= n <= 2^{31} – 1$

DFS

使用 DFS 进行求解。为避免反复解决某些数值，能够应用「哈希表」进行记忆化。

代码：

class Solution {Map<Long, Integer> map = new HashMap<>();
    public int integerReplacement(int n) {return dfs(n * 1L);
    }
    int dfs(long n) {if (n == 1) return 0;
        if (map.containsKey(n)) return map.get(n);
        int ans = n % 2 == 0 ? dfs(n / 2) : Math.min(dfs(n + 1), dfs(n - 1));
        map.put(n, ++ans);
        return ans;
    }
}

• 工夫复杂度：$O(\log{n})$
• 空间复杂度：$O(\log{n})$

BFS

同理，也能够应用 BFS 进行求解。同样应用「哈希表」记录步数，进行避免反复解决。

代码：

class Solution {public int integerReplacement(int n) {if (n == 1) return 0;
        Map<Long, Integer> map = new HashMap<>();
        Deque<Long> d = new ArrayDeque<>();
        d.addLast(n * 1L);
        map.put(n * 1L, 0);
        while (!d.isEmpty()) {long t = d.pollFirst();
            int step = map.get(t);
            long[] ns = t % 2 == 0 ? new long[]{t / 2} : new long[]{t + 1, t - 1};
            for (long x : ns) {if (x == 1) return step + 1;
                if (!map.containsKey(x)) {map.put(x, step + 1);
                    d.addLast(x);
                }
            }
        }
        return -1;
    }
}

• 工夫复杂度：$O(\log{n})$
• 空间复杂度：$O(\log{n})$

贪婪（位运算）

上述两种做法，咱们不可避免地在每个回合枚举了所有咱们能够做的决策：次要体现在对 $x$ 为奇数时的解决，咱们总是解决 $x + 1$ 和 $x – 1$ 两种状况。

咱们能够从二进制的角度进行剖析：给定起始值 $n$，求解将其变为 $(000…0001)_2$ 的最小步数。

• 对于偶数（二进制最低位为 $0$）而言，咱们只能进行一种操作，其作用是将以后值 $x$ 其进行一个单位的右移；

• 对于奇数（二进制最低位为 $1$）而言，咱们可能进行 +1 或 -1 操作，剖析两种操作为 $x$ 产生的影响：

  • 对于 +1 操作而言：最低位必然为 $1$，此时如果次低位为 $0$ 的话，+1 相当于将最低位和次低位替换；如果次低位为 $1$ 的话，+1 操作将将「从最低位开始，间断一段的 $1$」进行打消（置零），并在间断一段的高一位增加一个 $1$；
  • 对于 -1 操作而言：最低位必然为 $1$，其作用是将最低位的 $1$ 进行打消。

因而，对于 $x$ 为奇数所能执行的两种操作，+1 可能打消间断一段的 $1$，只有次低位为 $1$（存在间断段），该当优先应用 +1 操作，但须要留神边界 $x = 3$ 时的状况（此时抉择 -1 操作）。

代码：

class Solution {public int integerReplacement(int _n) {
        long n = _n;
        int ans = 0;
        while (n != 1) {if (n % 2 == 0) {n >>= 1;} else {if (n != 3 && ((n >> 1) & 1) == 1) n++;
                else n--;
            }
            ans++;
        }
        return ans;
    }
}

• 工夫复杂度：$O(\log{n})$
• 空间复杂度：$O(1)$

最初

这是咱们「刷穿 LeetCode」系列文章的第 No.397 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。

在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。

为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。

在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。

更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉

本文由 mdnice 多平台公布