liuchuo – 第256页 – 我不管，反正我最萌～

LeetCode 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
Credits:
Special thanks to @mithmatt and @ts for adding this problem and creating all test cases.

//即使输入的数为9*10^10，也会在第一次 while 降到3位数，第二次 while 降到2位数，不超过10次肯定能知道是否满足题目条件
//所以加了一个 cnt 计数器 在超过10次就跳出循环说明不满足题意

class Solution {
public:
    bool isHappy(int n) {
        int cnt = 0;
        while(n != 1) {
            cnt++;
            int temp = 0;
            while(n) {
                temp = temp + (n % 10) * (n % 10);
                n = n / 10;
            }
            n = temp;
            if(cnt == 10) {
                return false;
            }
        }
        return true;
    }
};

//即使输入的数为9*10^10，也会在第一次 while 降到3位数，第二次 while 降到2位数，不超过10次肯定能知道是否满足题目条件

//所以加了一个 cnt 计数器在超过10次就跳出循环说明不满足题意

class Solution {

public:

bool isHappy(int n) {

int cnt = 0;

while(n != 1) {

cnt++;

int temp = 0;

while(n) {

temp = temp + (n % 10) * (n % 10);

n = n / 10;

}

n = temp;

if(cnt == 10) {

return false;

}

return true;

}

};

LeetCode 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.

class Solution {
public:
    bool isUgly(int num) {
        if(num <= 0) {
            return false;
        }
        int flag = 0;
        while(num != 1) {
            flag = 0;
            if(num % 2 == 0) {
                num = num / 2;
                flag = 1;
            }
            if(num % 3 == 0) {
                 num = num / 3;
                 flag = 1;
            }
            if(num % 5 == 0) {
                num = num / 5;
                flag = 1;
            }
            if(flag == 0) {
                return false;
            }
        }
        return true;
    }
};

class Solution {

public:

bool isUgly(int num) {

if(num <= 0) {

return false;

}

int flag = 0;

while(num != 1) {

flag = 0;

if(num % 2 == 0) {

num = num / 2;

flag = 1;

}

if(num % 3 == 0) {

num = num / 3;

flag = 1;

}

if(num % 5 == 0) {

num = num / 5;

flag = 1;

}

if(flag == 0) {

return false;

}

return true;

}

};

LeetCode 70. Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

class Solution {
public:
    int climbStairs(int n) {
        int *a = new int [n + 1];
        a[0] = 1;
        a[1] = 1;
        for(int i = 2; i <= n; i++) {
            a[i] = a[i - 1] + a[i - 2];
        }
        return a[n];
    }
};


//一开始我写了个Fibonacci递归，在n = 44 时候超时了
class Solution {
public:
    int climbStairs(int n) {
        if(n == 1 || n == 2)
            return n;
        return climbStairs(n - 1) + climbStairs(n - 2);
    }
};


//最最一开始我用的最原始的递归， 在 n=38的时候超时了
class Solution {
public:
    int ans = 0;
    int climbStairs(int n) {
        if(n == 0) {
            ans++;
            return ans;
        }
        if(n >= 1) {
            climbStairs(n - 1);
        }
        if(n >= 2) {
            climbStairs(n - 2);
        }
    }
};

class Solution {

public:

int climbStairs(int n) {

int *a = new int [n + 1];

a[0] = 1;

a[1] = 1;

for(int i = 2; i <= n; i++) {

a[i] = a[i - 1] + a[i - 2];

}

return a[n];

}

};

//一开始我写了个Fibonacci递归，在n = 44 时候超时了

class Solution {

public:

int climbStairs(int n) {

if(n == 1 || n == 2)

return n;

return climbStairs(n - 1) + climbStairs(n - 2);

}

};

//最最一开始我用的最原始的递归，在 n=38的时候超时了

class Solution {

public:

int ans = 0;

int climbStairs(int n) {

if(n == 0) {

ans++;

return ans;

}

if(n >= 1) {

climbStairs(n - 1);

}

if(n >= 2) {

climbStairs(n - 2);

}

};

LeetCode 83. Remove Duplicates from Sorted List

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.

/**
 * 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 || head->next == NULL) {
            return head;
        }
        ListNode *p = head;
        while(p != NULL &&  p->next != NULL) {
            while (p->next != NULL && p->next->val == p->val) {
                    p->next = p->next->next;
            }
            p = p->next;
        }
        return 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 || head->next == NULL) {

return head;

}

ListNode *p = head;

while(p != NULL && p->next != NULL) {

while (p->next != NULL && p->next->val == p->val) {

p->next = p->next->next;

}

p = p->next;

}

return head;

}

};

LeetCode 191. Number of 1 Bits

Write a function that takes an unsigned integer and returns the number of ’1′ bits it has (also known as the Hamming weight).

For example, the 32-bit integer ’11′ has binary representation 00000000000000000000000000001011, so the function should return 3.

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int ans = 0;
        while(n != 0) {
            ans = ans + n % 2;
            n = n / 2;
        }
        return ans;
    }
};

class Solution {

public:

int hammingWeight(uint32_t n) {

int ans = 0;

while(n != 0) {

ans = ans + n % 2;

n = n / 2;

}

return ans;

}

};

LeetCode 206. Reverse Linked List

Reverse a singly linked list.

题目大意：反转一个单链表～

分析：设立三个指针：cur——当前结点；pre——当前结点的前一个结点；temp——临时结点（标记cur的next）。首先保存cur的next到temp，然后将cur的next指向pre，将pre移动到当前cur，然后将cur指向temp，直到cur==NULL，返回pre即反转了该链表～

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == NULL) return head;
        ListNode *cur = head, *pre = NULL, *temp = NULL;
        while (cur != NULL) {
            temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};

class Solution {

public:

ListNode* reverseList(ListNode* head) {

if (head == NULL) return head;

ListNode *cur = head, *pre = NULL, *temp = NULL;

while (cur != NULL) {

temp = cur->next;

cur->next = pre;

pre = cur;

cur = temp;

}

return pre;

}

};