本文主要是介绍leetcode题解日练--2016.6.18，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
编程新手，尽量保证每天至少3道leetcode题，仅此记录学习的一些题目答案与思路，尽量用多种思路来分析解决问题，不足之处还望指出。
今日题目：1、判断3的幂次；2、判断2的幂次；3、丑数；4、去除有序链表中的重复元素;5、快乐数
326. Power of Three | Difficulty: Easy
Given an integer, write a function to determine if it is a power of three.
Follow up:
Could you do it without using any loop / recursion?
题意：给定一个整数，判断是不是3的次方，能否不用任何的循环与递归实现？
思路：
1、对输入的n进行判断，等于0返回false，如果不为0，每次对n%3进行判断，等于0说明能除尽，n=n/3，否则直接返回false，一直循环到n==1结束循环
代码：
class Solution {
public:bool isPowerOfThree(int n) {if (n==0)return false;while(n!=0){if(n==1)return true;if(n%3!=0)return false;n/=3;}return true;}
};结果：116ms Your runtime beats 99.59% of cppsubmissions.
2、首先用一段python代码求出最大的int型的3的次方数是1162261467
max_3 = 0
for i in range(32):if (3**i<2**32):max_3 = 3**i
print max_3然后再判断输入的数是否能被1162261467整除即可。
代码：
class Solution {
public:bool isPowerOfThree(int n) {return n>0&&(1162261467 % n == 0);}
};结果：132ms，Your runtime beats 78.27% of cppsubmissions.
231. Power of Two | Difficulty: Easy
Given an integer, write a function to determine if it is a power of two.
描述：给定一个整数，判断是不是2的次方。
思路：
1、当然可以和上题判断3的次方一样的做法，但是这里不妨利用下2的次方的规律，2的幂次的规律是展开成二进制只有一个1.例如2：10；4:100;8:1000等等，那么知道了这个规律很快就能写出代码了。
代码：
class Solution {
public:bool isPowerOfTwo(int n) {return ((n&n-1)==0&&n>0);}
};8ms Your runtime beats 12.81% of cppsubmissions.
class Solution {
public:bool isPowerOfTwo(int n) {if (n==0)return false;while(n!=0){if(n==1)return true;if(n%2!=0)return false;n/=2;}return true;}
};8ms Your runtime beats 12.81% of cppsubmissions.
263. Ugly Number | Difficulty: Easy
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.
题意：丑数是指的素因子只包含2,3,5的正数，1是一个特殊的丑数，因为其不包含2、3、5。
思路：
1、每次去判断是否能被2、3、5之间的一个数整除，如果可以就更新num，如果不行就直接返回false；
代码：
class Solution {
public:bool isUgly(int num) {while(num>0){if(num==1)return true;else if (num%2==0)num/=2;else if(num%3==0)num/=3;else if(num%5==0)num/=5;elsereturn false;}return false;}
};结果：8ms Your runtime beats 8.34% of cppsubmissions.
83. Remove Duplicates from Sorted List | Difficulty: Easy
Given a sorted linked list, delete all duplicates such that each element appear only once.
For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.
题意：给定一个排好序的链表，删除所有连续出现的重复值保证每个值只出现一次。
思路：
从头开始遍历链表，如果当前节点的值和下一个节点相等，那么直接将当前节点指向下一个节点的下一个节点，如果不相等，就将当前节点切换为下一个节点，直到最后一个NULL节点结束循环返回head。
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* deleteDuplicates(ListNode* head) {if(head==NULL) return head;ListNode* pNode = head;while(pNode){if(pNode->next&&pNode->next->val==pNode->val)pNode->next = pNode->next->next;elsepNode = pNode->next;}return head;}
};结果：16ms Your runtime beats 12.68% of cppsubmissions.
202. Happy Number | Difficulty: Easy
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.
题意：将数字各位的平方相加，然后得到的相加之后再循环上一步操作，如果最后能等于1就是Happy Number，也存在不会停下的的可能。
思路：
1、首先，观察两个例子，一个是题目给的19->82->68->100->1->1->1……
另外一个不是Happy Number的数字 9->81->65->61->37->58->89->145->42->20->4->16->37->58，注意到这里58又进入到了循环，因此可以考虑设置两个指针，一快一慢，然后如果不是丑数，相遇的时候一定不是1，相反如果是丑数那么相遇一定是1。
class Solution {
public:int digitSquareSum(int n) {int sum = 0, tmp;while (n) {tmp = n % 10;sum += tmp * tmp;n /= 10;}return sum;}bool isHappy(int n) {int slow, fast;slow = fast = n;do {slow = digitSquareSum(slow);fast = digitSquareSum(fast);fast = digitSquareSum(fast);} while(slow != fast);if (slow == 1) return 1;else return 0;}};结果：4ms Your runtime beats 41.98% of cppsubmissions.
2、
1 : 1
2 : 4 -> … -> 4
3 : 9 -> … -> 4
4 : 4 -> … -> 4
5 : 25 -> … -> 4
6 : 4 -> … -> 4
7 : 49 -> … -> 1
8 : 4 -> … -> 4
9 : 25 -> … -> 4
利用1-9中只有1和7是Happy Number这一条件，写出如下代码
class Solution {
public:bool isHappy(int n) {while(n>9){int next = 0;while(n){next+=(n%10)*(n%10); n/=10;}n = next;}return n==1||n==7;
}
};结果：0ms Your runtime beats 98.88% of cppsubmissions
3、用一个集合来存出现过的情况
class Solution {
public:bool isHappy(int n) {set<int> s;while (n != 1) {int t = 0;while (n) {t += (n % 10) * (n % 10);n /= 10;}n = t;if (s.count(n)) break;else s.insert(n);}return n == 1;}
};结果： 4ms Your runtime beats 41.98% of cppsubmissions.
参考资料
1、https://leetcode.com/discuss/33055/my-solution-in-c-o-1-space-and-no-magic-math-property-involved
2、http://www.cnblogs.com/grandyang/p/4447233.html
这篇关于leetcode题解日练--2016.6.18的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
