LeetCode OJ – 第49页

LeetCode 27. Remove Element

Given an array and a value, remove all instances of that value in place and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

The order of elements can be changed. It does not matter what you leave beyond the new length.

Example:
Given input array nums = [3,2,2,3], val = 3

Your function should return length = 2, with the first two elements of nums being 2.

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int len = 0;
        for(int i = 0; i < nums.size(); i++) {
            if(nums[i] != val) {
                nums[len++] = nums[i];
            }
        }
        return len;
    }
};

class Solution {

public:

int removeElement(vector<int>& nums, int val) {

int len = 0;

for(int i = 0; i < nums.size(); i++) {

if(nums[i] != val) {

nums[len++] = nums[i];

}

return len;

}

};

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;

}

};