17.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.
Analysis
就是分解质因数，如果其质因子只包括2，3，5 那么就是丑数，否则就不是 而1是丑数
如果这个数可以直接整除235 然后判读一次是否可以继续整除，如果还可以 再判读， 直到剩下1或者是剩下的不可整除，就结束了
Solution-C/C++
bool isUgly(int num)
{
if(num==0)
return false;
//int temp=0;
while(1)
{
if(num==1)
return true;
if(num%2==0)
{
num=num/2;
continue;
}
if(num%3==0)
{
num=num/3;
continue;
}
if(num%5==0)
{
num=num/5;
continue;
}
else
return false;
}
}
Solution-Python
class Solution(object):
def isUgly(self, num):
"""
:type num: int
:rtype: bool
"""
if num==0:
return False
while(1):
if num==1:
return True
if num%2==0:
num=num/2
continue
if num%3==0:
num=num/3
continue
if num%5==0:
num=num/5
continue
else:
return False
18.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
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
Analysis
先要分解n 得到每位数字，然后再按照这个来做 但题目没说这个数字有多大啊 如果非常大 那就很蛋疼了啊
也有办法 每次分解一个数字 然后平方相加 再去分解 再平方相加 成为一个循环。
然后这个题有一个无限循环的机制，这个需要在程序中预判出。
如果要无限循环，应该不是所有值都能无限的，看看是否能找到有限个循环值
首先这个值应该是个两位数，并且两个的平方和等于其自身 或者等于一个会无限的两位数 （本来想用一个计数器来设置循环次数，发现9999999都无法算出来17 我擦勒）
最后解决办法基本上就是每计算一次所有值，然后记录一次，如果这个值为1就为真，不为1 去记录区寻找是否有相同的
没有相同的就记录一下， 如果查找到了相同的数字 ，那么就是假的
Solution-C/C++
bool isHappy(int n)
{
//先分解n
int digit=n,sum=0,digit2=0,digit3=0,count=0,i=0;
int sumlist[30]={0};
while(1)
{
digit=n%10;
n=n/10;
sum=digit*digit+sum;
if(n==0)
{
//这个数计算完毕，开始计算下一个数，存储sum
n=sum;
if(sum==1)
return true;
sum=0;
//检索是否有重复的结果
for(i=0;i<count+1;i++)
if(n==sumlist[i])
return false;
//当前结果加入检索
sumlist[count++]=n;
}
}
return false;
}
Solution-Python
python的代码相对简单了一些，因为有set的存在 直接判断是否存在就很容易
class Solution(object):
def isHappy(self, n):
"""
:type n: int
:rtype: bool
"""
sum=0
s=set()
while 1:
digit=n%10
n=n/10
sum=sum+digit*digit
if n==0:
if sum==1:
return True
n=sum
sum=0
if(n in s ):
return False
else:
s.add(n)
19.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, and is empty operations 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).
Analysis
使用栈来实现队列，所以用C++来写，而不用c，发现leetcode上c和c++要求还不一样，多了好几个函数
队列是先进先出，栈是先进后出，那要如何做到这个呢
首先得想到如果只用一个栈，那么要peek的时候就需要把剩下元素全都临时弹出去 然后拿到最底部的那个才能返回
如果在这个时候还需要添加或者删除队尾元素 就很麻烦，所以需要一个栈来存储剩下的元素。让两个栈来回切换存储就可以了。
Solution-C/C++
class Queue
{
public:
stack<int> in;
stack<int> out;
// Push element x to the back of queue.
void move(void)
{
while(!in.empty())
{
out.push(in.top());
in.pop();
}
}
void push(int x)
{
in.push(x);
}
// Removes the element from in front of queue.
void pop(void)
{
if(out.empty())
move();//把in中内容移动到out中
out.pop();//得到第一个元素
}
// Get the front element.
int peek(void)
{
if(out.empty())
move();//把in中内容移动到out中
return out.top();//得到第一个元素
}
// Return whether the queue is empty.
bool empty(void)
{
if(in.empty()&&out.empty())
return true;
else
return false;
}
};
2017年2月21日 13:53:10 第二次重写,要求也有些不同了
思路更加明确:
- 首先两个栈,分管输入与输出.
- push时,全部加入输入栈
- peek时,由于要拿到最底的数据,如果out中有内容,那么栈顶就是队首,如果out是空的,那么把in栈内容全部压入out中,栈顶就是队首
- pop时,由于要先返回队首,所以先调用peek保存栈首内容,然后再像上面一样处理两个栈,处理完了以后再pop栈就行了.
class MyQueue
{
private:
stack<int> in;
stack<int> out;
public:
/** Initialize your data structure here. */
MyQueue()
{
}
/** Push element x to the back of queue. */
void push(int x)
{
in.push(x);
}
/** Removes the element from in front of queue and returns that element. */
int pop()
{
int temp=peek();
if(!out.empty())
{
out.pop();
}
else
{
while(!in.empty())
{
out.push(in.top());
in.pop();
}
out.pop();
}
return temp;
}
/** Get the front element. */
int peek()
{
if(!out.empty())
{
return out.top();
}
else
{
while(!in.empty())
{
out.push(in.top());
in.pop();
}
return out.top();
}
}
/** Returns whether the queue is empty. */
bool empty()
{
if(in.empty()&&out.empty())
return true;
else
return false;
}
};
Solution-Python
class Queue(object):
datain=[] #我假装认为这里的list其实是一个栈好了
dataout=[]
def __init__(self):
"""
initialize your data structure here.
"""
self.datain=[] #我假装认为这里的list其实是一个栈好了
self.dataout=[]
def move(self):
"""
:type : nothing
:rtype: nothing
"""
while(self.datain!=[]):
self.dataout.append(self.datain.pop())
def push(self, x):
"""
:type x: int
:rtype: nothing
"""
self.datain.append(x)
def pop(self):
"""
:rtype: nothing
"""
if(self.dataout==[]):
self.move()
self.dataout.remove(self.dataout[-1])
def peek(self):
"""
:rtype: int
"""
if(self.dataout==[]):
self.move()
return self.dataout[-1]
def empty(self):
"""
:rtype: bool
"""
if self.datain==[] and self.dataout==[] :
return True
else:
return False
20.Merge Two Sorted Lists
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
Analysis
合并两个有序链表，没啥难得，就是不知道这个链表是什么顺序排列的 一般应该是由到大吧
然后分别插入就ok了
Solution-C/C++
迭代
说白了首先把各种空指针传入的情况给排除掉
然后开始先确定头指针是谁
然后用pre记录上一节点，l1是在l1链表上的滑动指针，l2是在l2链表上的头指针，通过比较l1与l2的大小，插入值
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2)
{
struct ListNode* temp=NULL;
struct ListNode* head=l1;
struct ListNode* pre=NULL;
if(!l1&&!l2)
return l1;
if(!l1&&l2)
return l2;
if(l1&&!l2)
return l1;
//先解决头部问题，头部肯定是最小的值
if(l2->val<l1->val||l2->val==l1->val)
{
if(l2->next)
{
temp=l2->next;
l2->next=l1;
head=l2;
pre=head;
l2=temp;
}
else
{
l2->next=l1;
l1=l2;
return l1;
}
}
else
pre=l1;
while(1)
{
if(l2->val<l1->val||l2->val==l1->val)
{
if(l2->next)
{
temp=l2->next;
l2->next=l1;
pre->next=l2;
pre=l2;
l2=temp;
}
else
{
l2->next=l1;
pre->next=l2;
l1=l2;
break;
}
}
else
{
if(l1->next)
{
pre=l1;
l1=l1->next;
}
else
{
l1->next=l2;
break;
}
}
}
return head;
}
2017年2月21日 15:54:17 更简洁的写法.
思路清晰:
- 首先创建一个pre头指针,保存好融合后的头指针,利用cur来指向当前尾指针
- 然后依次滑动两个链表,取小值,链入当前指针尾部,被取得链表头指针移动,当前尾指针移动
- 结束时由于有一个链表提前到尾部,结束循环,那么把剩下的另一个链表整个链接进来
class Solution
{
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
{
ListNode prehead(INT_MIN);
ListNode *tail =&prehead;
while (l1 && l2)
{
if (l1->val < l2->val)
{
tail->next = l1;
l1 = l1->next;
}
else
{
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
tail->next = l1 ? l1 : l2;
return prehead.next;
}
};
递归
这个题目无意间看到一个递归的解法，写的非常简单，比上面的代码少多了
想一想递归怎么解呢
结束条件肯定是l1或者是l2为空的时候开始返回，而返回之后需要将当前的尾部和上一个值进行连接
连接的时候 首先得让小的值来当作头节点，然后移动具有头部节点的列表的当前指针，和另一个列表 进行下一次比较返回一个较小的值
继续把较小的值作为头部，再去寻找下一个较小的值，直到某一方为空，当为空时返回对方的值，然后将返回值连接到当前较小的值中去
从而达成了递归
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2)
{
if (l1 == NULL) return l2;
if (l2 == NULL) return l1;
struct ListNode *ret = NULL;
if (l1->val < l2->val)
{
ret = l1;
ret->next = mergeTwoLists(l1->next, l2);
}
else
{
ret = l2;
ret->next = mergeTwoLists(l1, l2->next);
}
return ret;
}
Solution-Python
迭代
把之前c迭代部分稍微改了改，去掉了一些冗余判断
class Solution(object):
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
#排除空节点情况
if(not l1):
return l2
if(not l2):
return l1
#确定头和上一节点
if (l2.val<l1.val or l2.val==l1.val):
if l2.next:#如果l2的下一个节点还存在，顺移l2，修改头和上一节点
temp=l2.next
l2.next=l1
head=l2
pre=l2
l2=temp
else:#如果l2的下一节点不存在了，l2直接接到l1的前面就可以了 返回l2
l2.next=l1
return l2
else:
head=l1
pre=l1
while True:
if (l2.val<l1.val or l2.val==l1.val):
if l2.next:#如果l2的下一个节点还存在，顺移l2，修改上一节点
temp=l2.next
l2.next=l1
pre.next=l2
pre=l2
l2=temp
else:#如果l2的下一节点不存在了，l2直接接到l1的前面就可以了 返回l2
l2.next=l1
pre.next=l2
return head
else:
if l1.next:
pre=l1
l1=l1.next
else:
l1.next=l2
break;
return head
2017年2月23日 19:00:37
class Solution(object):
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
head=ListNode(1)
cur=head
while l1 and l2:
if l1.val<l2.val:
cur.next=l1;
l1=l1.next
else:
cur.next=l2;
l2=l2.next
cur=cur.next
cur.next=l1 or l2
return head.next
递归
class Solution(object):
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
if l1==None:
return l2
if l2==None:
return l1
if l1.val<l2.val:
ret=l1
ret.next=self.mergeTwoLists(l1.next, l2)
else:
ret=l2
ret.next=self.mergeTwoLists(l1, l2.next)
return ret
发现还能优化一下上面的代码
class Solution(object):
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
if not l1 or not l2:
return l1 or l2
if l1.val < l2.val:
l1.next = self.mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = self.mergeTwoLists(l1, l2.next)
return l2
这样递归思路就是:找到两个链表的尾部,然后开始链接,最后返回的自然就是链表头了.
Quote
http://blog.csdn.net/business122/article/details/7541486
http://blog.csdn.net/sunao2002002/article/details/46793425