[LintCode/LeetCode] Integer Replacement

fyber 發(fā)布于2019-08-16 12:44 / 2914人閱讀

Problem

Given a positive integer n and you can do operations as follow:

1.If n is even, replace n with n/2.
2.If n is odd, you can replace n with either n + 1 or n - 1.

What is the minimum number of replacements needed for n to become 1?

Example

Example 1:

Input:
8

Output:
3

Explanation:

8 -> 4 -> 2 -> 1

Example 2:

Input:
7

Output:
4

Explanation:

7 -> 8 -> 4 -> 2 -> 1

7 -> 6 -> 3 -> 2 -> 1

Solution

public class Solution {
    /**
     * @param n: a positive integer 
     * @return: the minimum number of replacements
     */
    public int integerReplacement(int n) {
        // Write your code here
        if (n == 1) return 0;
        if (n == Integer.MAX_VALUE) return 32;
        int count = 0;
        while (n > 1) {
            if (n % 2 == 0) {
                n /= 2;
                count++;
            } else {
                if ((n+1) % 4 == 0 && n != 3) {
                    n++;
                    count++;
                } else {
                    n--;
                    count++;
                }
            }
        }
        return count;
    }
}

GPU云服務(wù)器云服務(wù)器 Replacement integer integer類型 reverse-integer

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/71614.html

相關(guān)文章

[LintCode/LeetCode] Edit Distance

摘要：構(gòu)造數(shù)組，是的，是的，是將位的轉(zhuǎn)換成位的需要的步數(shù)。初始化和為到它們各自的距離，然后兩次循環(huán)和即可。 Problem Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 s...

snowell 2019-08-14 15:29 評(píng)論0 收藏0
[LintCode/LeetCode] Decode Ways [String to Integer

摘要：用將子字符串轉(zhuǎn)化為，參見和的區(qū)別然后用動(dòng)規(guī)方法表示字符串的前位到包含方法的個(gè)數(shù)。最后返回對(duì)應(yīng)字符串末位的動(dòng)規(guī)結(jié)果。 Problem A message containing letters from A-Z is being encoded to numbers using the following mapping: A -> 1 B -> 2 ... Z -> 26 Given ...

andong777 2019-08-14 15:44 評(píng)論0 收藏0
[LintCode/LeetCode] Find Median From / Data Stream

摘要：建立兩個(gè)堆，一個(gè)堆就是本身，也就是一個(gè)最小堆另一個(gè)要寫一個(gè)，使之成為一個(gè)最大堆。我們把遍歷過的數(shù)組元素對(duì)半分到兩個(gè)堆里，更大的數(shù)放在最小堆，較小的數(shù)放在最大堆。同時(shí)，確保最大堆的比最小堆大，才能從最大堆的頂端返回。 Problem Numbers keep coming, return the median of numbers at every time a new number a...

zxhaaa 2019-08-14 14:35 評(píng)論0 收藏0
[LintCode/LeetCode] Flatten Nested List Iterator

摘要：首先，根據(jù)迭代器需要不斷返回下一個(gè)元素，確定用堆棧來做。堆棧初始化數(shù)據(jù)結(jié)構(gòu)，要先從后向前向堆棧壓入中的元素。在調(diào)用之前，先要用判斷下一個(gè)是還是，并進(jìn)行的操作對(duì)要展開并順序壓入對(duì)直接返回。 Problem Given a nested list of integers, implement an iterator to flatten it. Each element is either...

spacewander 2019-08-14 15:45 評(píng)論0 收藏0
[LintCode/LeetCode] Min Stack/Max Stack

Problem Implement a stack with min() function, which will return the smallest number in the stack. It should support push, pop and min operation all in O(1) cost. Example push(1)pop() // return 1pus...

GHOST_349178 2019-08-14 15:14 評(píng)論0 收藏0