今天做到一道题是这样的：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.
可能是因为本人的英语水平不过关，一开始都Get不到这道题想要表达什么，最后想了挺久的才想到，原来这就是一个小学生的题目，这个丑数字原来就是不是纯（2,3,5）的倍数的数字就是了。害我想那么久。
好了知道思路之后就简单了，下面贴一下我的代码：
public boolean isUgly(int num) {
if(num == 0) return false;
while(num % 5 == 0) num /= 5;
while(num % 3 == 0) num /= 3;
while(num % 2 == 0) num /= 2;
if(num == 1) return true;
return false;
}
好了，这题真的是没什么难的，重在理解好吧。
但是在这里我要提一下，上面while中的顺序是有一点道理的，这样排下来要是给的num大的话，可以减少循环的次数。
一道简单的合并有序链表的题目：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.
先给一下我自己的代码：
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode newl,temp;
if(l2 == null) return l1;
if(l1 == null) return l2;
if(l1.val <= l2.val){
temp = l1;
l1 = l1.next;
}
else{
temp = l2;
l2 = l2.next;
}
newl = temp;
while(l1 != null || l2 != null){
if(l1 == null){
temp.next = l2;
break;
}
if(l2 == null){
temp.next = l1;
break;
}
if(l1.val <= l2.val){
temp.next = l1;
l1 = l1.next;
}
else{
temp.next = l2;
l2 = l2.next;
}
temp = temp.next;
}
return newl;
}
我上面的做法是一般人都会想到的，其实我上面的代码还可以再省去一个链表指针的。（这里需要提醒大家的是，不要忘记提前判空喔，少了这个这个可是会报错的。）
然而以下是很简洁的代码，这是一个递归的方法：
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
ListNode head = l1.val < l2.val ? l1 : l2;
ListNode nonHead = l1.val < l2.val ? l2 : l1;
head.next = mergeTwoLists(head.next, nonHead);
return head;
}
这是另外一道合并有序数组的题目：Merge Sorted Array
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.
我一开始想到的一下的办法：
public void merge(int[] nums1, int m, int[] nums2, int n) {
int t;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(nums1[i] > nums2[j]){
t = nums1[i];
nums1[i] = nums2[j];
nums2[j] = t;
}
}
}
Arrays.sort(nums2);
for(int i = m, j = 0; i < m + n; i++,j++){
nums1[i] = nums2[j];
}
}
我的方法是从前面开始遍历，这样的方法在这道题中会显得比较差，首先事件复杂度就大了。
所以下面给出一个从后面开始比较的方法，这样的方法比较比上面的，在时间复杂度上就优化的好多。
public void merge(int[] nums1, int m, int[] nums2, int n) {
int l = m+n-1;
m--;
n--;
while (m >= 0 && n >= 0) {
if (nums1[m] > nums2[n]) {
nums1[l] = nums1[m];
l--;
m--;
} else {
nums1[l] = nums2[n];
l--;
n--;
}
}
for (int i = 0; i <= n; i++) {
nums1[i] = nums2[i];
}
}
一段让我很佩服的递归代码：
题目：Swap Nodes in Pairs
内容：Given a linked list, swap every two adjacent nodes and return its head.
For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.
要求：Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.（意思就是不要直接修改链表中的值）。
public ListNode swapPairs(ListNode head) {
if ((head == null)||(head.next == null))
return head;
ListNode n = head.next;
head.next = swapPairs(head.next.next);
n.next = head;
return n;
}
我当时要看懂这个递归花了好多时间，按照递归的定义一步一步拆出来才能理解，真心让我佩服的一段代码。
回文数的一个很好算法：
原题目：Palindrome Number
Determine whether an integer is a palindrome. Do this without extra space.
下面是个好方法：
public boolean isPalindrome(int x) {
if(x != 0 && x % 10 == 0) return false;
int finhalf = 0;
while(x >finhalf){
finhalf = finhalf * 10 + x % 10;
x /= 10;
}
return x == finhalf || x == finhalf / 10;
}
本来按照正常的思路我们应该会把一个一个将对称的数字进行比较，可是这个算法的思维比较“发散”直接将这个数分成两半，另这两半直接比较。这确实能省时间和不用额外的空间开销。
LeetCode中里面还有好多很有意思的递归，以后有看到会继续在这里分享。
本篇博文已经太长了，下一篇请看：LeetCode上做题之体会（二）
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
