刷题记录

Problem: Count the number of prime numbers less than a non-negative number,  n . Example: Input: 10 Output: 4 Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7. 7/2/2018 update A shorter solution: class Solution { public int countPrimes ( int n) { boolean [] notPrime = new boolean [n]; int count = 0 ; for ( int i = 2 ; i < n; i ++ ) { if ( ! notPrime[i]) { count ++ ; for ( int j = 2 ; i * j < n; j ++ ) { notPrime[i * j] = true; } } } return count; } } ----------------------------- ----------------------------- ----------------------------- ----------------------------- ------------------------ Analysis: The  Sieve of Eratosthenes  is one of the most efficient ways to find all prime numbers up to  n . But don't let that name scare you, I promise that the concept...

Problem: Write an algorithm to determine if a number is "happy". A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers. Example:  Input: 19 Output: true Explanation: 1 2 + 9 2 = 82 8 2 + 2 2 = 68 6 2 + 8 2 = 100 1 2 + 0 2 + 0 2 = 1 Analysis: Use hash set to cache the sum, if sum exists in set, then the algorithm falls into cycle. So its not happy number. Solution: class Solution { public boolean isHappy ( int n) { Set< Integer > set = new HashSet<> (); int sum = 0 ; while (set . add(sum)) { sum = 0 ; while (n > 0 ) { sum += (n % 10 ) * (n % 10 ); ...

Problem: Reverse bits of a given 32 bits unsigned integer. Example: Input: 43261596 Output: 964176192 Explanation: 43261596 represented in binary as 00000010100101000001111010011100 ,   return 964176192 represented in binary as 00111001011110000010100101000000 . Analysis: skip Solution: public class Solution { // you need treat n as an unsigned value public int reverseBits ( int n) { int res = 0 ; for ( int i = 0 ; i < 32 ; i ++ ) { if ((n & 1 ) == 1 ) { res = (res << 1 ) + 1 ; } else { res = res << 1 ; } n = n >> 1 ; } return res; } }

Problem: Given a list of non negative integers, arrange them such that they form the largest number. Example 1: Input: [10,2] Output: " 210" Example 2: Input: [3,30,34,5,9] Output: " 9534330" Analysis: Sort the array first. To determine which number comes first see below. s1 = "30", s2 = "34" s1 + s2 = "3034" s2 + s1 = "3430" s2 is ahead of s1, so the comparator in lambda expression is (s1, s2) -> (s2 + s1).compareTo(s1 + s2). Solution: class Solution { public String largestNumber ( int [] nums) { if (nums == null || nums . length == 0 ) return "" ; String [] strs = new String [nums . length]; for ( int i = 0 ; i < nums . length; i ++ ) { strs[i] = String . valueOf(nums[i]); } Arrays . sort(strs, ((a,b) - > (b + a) . compareTo(a + b))); if (strs[ 0 ] . charAt( 0 ) == '0' ) return ...

Problem: The demons had captured the princess ( P ) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight ( K ) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess. The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately. Some of the rooms are guarded by demons, so the knight loses health ( negative  integers) upon entering these rooms; other rooms are either empty ( 0's ) or contain magic orbs that increase the knight's health ( positive  integers). In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step. Write a function to determine the knight's minimum initial health so that he is able to rescue the princess. For example, given the dungeon below, the initial h...

Problem: Given a column title as appear in an Excel sheet, return its corresponding column number. For example: A -> 1 B -> 2 C -> 3 ... Z -> 26 AA -> 27 AB -> 28 ... Example 1: Input: "A" Output: 1 Example 2: Input: "AB" Output: 28 Example 3: Input: "ZY" Output: 701 Analysis: Skip Solution: class Solution { public int titleToNumber ( String s) { int res = 0 , temp = 1 ; for ( int i = s . length() - 1 ; i >= 0 ; i -- ) { res += (s . charAt(i) - 'A' + 1 ) * temp; temp *= 26 ; } return res; } }

Problem: Given a positive integer, return its corresponding column title as appear in an Excel sheet. For example: 1 -> A 2 -> B 3 -> C ... 26 -> Z 27 -> AA 28 -> AB ... Example 1: Input: 1 Output: "A" Example 2: Input: 28 Output: "AB" Example 3: Input: 701 Output: "ZY" Analysis : To get "Z", we need to use 'A' + number. The number should be 25. So we have 'A' + (26 - 1) % 26. Solution : class Solution { public String convertToTitle ( int n) { StringBuilder sb = new StringBuilder (); while (n > 0 ) { sb . append(( char )( 'A' + ( -- n % 26 ))); n = n / 26 ; } sb . reverse(); return sb . toString(); } }