My JAVA Solution with HashMap


  • 0
    J
    
    public class Solution {
         public HashMap<Long, Integer> map = new HashMap<>();
        public int integerReplacement(int n) {
            map.put(1l, 0);
            find(map, n);
            return map.get((long)n);
        }
        
        private int find(HashMap<Long, Integer> map, long n) {
            int num  = Integer.MAX_VALUE, num1 = Integer.MAX_VALUE;
            if (n <= 0) return 0;
            if (n == 1) {
                return 0;
            }
            
            if (map.containsKey(n)) return map.get(n);
            
            if (n % 2 == 0) {
                num = find(map, n/2);
                map.put(n, num + 1);
            } else {
                num = find(map, n + 1);
                num1 = find(map, n - 1);
                num = Math.min(num, num1);
                map.put(n, num + 1);
            }
            
            return num + 1;
        }
        
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.