Code – 第254页 – 柳婼の blog

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;

}

};

LeetCode 217. Contains Duplicate

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        set<int> m;
        for(int i = 0; i < nums.size(); i++) {
            m.insert(nums[i]);
        }
        return nums.size() != m.size();
    }
};

class Solution {

public:

bool containsDuplicate(vector<int>& nums) {

set<int> m;

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

m.insert(nums[i]);

}

return nums.size() != m.size();

}

};

LeetCode 169. Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int temp = 0, maxvalue = 0, ans = nums[0];
        for(int i = 1; i < nums.size(); i++) {
            if(nums[i - 1] == nums[i]) {
                temp++;
                if(temp > maxvalue) {
                    maxvalue = temp;
                    ans = nums[i];
                }
            } else {
                temp = 0;
            }
        }
        return ans;
    }
};

class Solution {

public:

int majorityElement(vector<int>& nums) {

sort(nums.begin(), nums.end());

int temp = 0, maxvalue = 0, ans = nums[0];

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

if(nums[i - 1] == nums[i]) {

temp++;

if(temp > maxvalue) {

maxvalue = temp;

ans = nums[i];

}

} else {

temp = 0;

}

return ans;

}

};

LeetCode 171. Excel Sheet Column Number

Related to question Excel Sheet Column Title

Given a column title as appear in an Excel sheet, return its corresponding column number.

For example:

A -> 1
B -> 2
C -> 3
…
Z -> 26
AA -> 27
AB -> 28

class Solution {
public:
    int titleToNumber(string s) {
        int ans = 0;
        for(int i = 0; i < s.length(); i++) {
              ans = ans*26 + s[i] - 'A' + 1;
        }
        return ans;
    }
};

class Solution {

public:

int titleToNumber(string s) {

int ans = 0;

for(int i = 0; i < s.length(); i++) {

ans = ans*26 + s[i] - 'A' + 1;

}

return ans;

}

};