【263】Ugly Number
Write a program to check whether a given number is an ugly number.
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7.
Note that 1 is typically treated as an ugly number.
思路：prime factors：素数，就是这个数只能被1和自身整除。所以检验这个数分别循环除以2、3、5的，如果最后只剩下1，则这个数就是由素数组成。
public class Solution { public boolean isUgly(int num) { if(num==0)return false; //way 1: for(int i =2; i<6;i++){ while(num%i==0){ num/=i; } } /*way 2: while(num%2==0){ num/=2; } while(num%3==0){ num/=3; } while(num%5==0){ num/=5; }*/ return num==1; } }
【202】Happy Number
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: 19 is a happy number
- 12 + 92 = 82
- 82 + 22 = 68
- 62 + 82 = 100
- 12 + 02 + 02 = 1
思路：循环取出一个数各个位，然后平方和，问题的关键在于这个循环什么时候结束，题干中说的很清楚，当平方和是1或者存在环路（平方和经过循环计算又是计算过的平方和）陷入死循环的时候，不再迭代。
有两种方法，一种是通过类似快慢指针的方式检测环路，这种要快很多，另一种是通过Java的set结构，每计算一个数，则添加进set，如果循环出添加过的数字，则set添加失败，所以存在环路
public class Solution { public boolean isHappy(int n) { //way 2 to use two pointers:fast and slow pointers t detect of there is a loop int slow ,fast ; slow = fast = n; do{ slow = computeSum(slow); fast = computeSum(fast); fast = computeSum(fast); }while(slow!=fast); if(slow==1)return true; else return false; /*way1:use the hashset to detect if there is a loop HashSet<Integer> sumSet = new HashSet<Integer>(); while(sumSet.add(n)){ int sum = 0; while(n>0){ int m = n%10; sum+=m*m; n/=10; } if(sum==1)return true; else n = sum;; } return false;*/ } int computeSum(int n){ int sum = 0; while(n>0){ int temp = n%10; sum+= temp*temp; n/=10; } return sum; } }
【232】 Implement Queue using Stacks
Implement the following operations of a queue using stacks.
- push(x) -- Push element x to the back of queue.
- pop() -- Removes the element from in front of queue.
- peek() -- Get the front element.
- empty() -- Return whether the queue is empty.
Notes:
- You must use only standard operations of a stack -- which means only
push to top,peek/pop from top,size, andis emptyoperations are valid. - Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
- You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).
思路： 使用栈来模拟队列的基本操作，肯定是需要两个栈，一个用来push，一个用来pop，pop的时候，要把push栈里的元素一个一个弹出来push进pop栈里
class MyQueue { private Stack<Integer> stackForPush = new Stack<Integer>(); private Stack<Integer> stackForPop = new Stack<Integer>(); // Push element x to the back of queue. public void push(int x) { stackForPush.push(new Integer(x)); } // Removes the element from in front of queue. public void pop() { peek();//the subprocess is the same to peek,so call peek() for short. stackForPop.pop(); } // Get the front element. public int peek() { if(stackForPop.isEmpty()){ while(!stackForPush.isEmpty()){ stackForPop.push(stackForPush.pop()); } //return stackForPop.peek(); } return stackForPop.peek(); } // Return whether the queue is empty. public boolean empty() { return stackForPop.isEmpty()&&stackForPush.isEmpty(); } }
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if(l1==null)return l2; if(l2==null)return l1; ListNode newHead = null; if(l1.val<l2.val){ newHead = l1; newHead.next = mergeTwoLists(l1.next,l2); }else{ newHead = l2; newHead.next = mergeTwoLists(l2.next,l1); } return newHead; } }
public class Solution { public boolean isPowerOfTwo(int n) { return (n>0&&(n&(n-1))==0); } }