Ascendlogo

Posted on Edited on In

217.Contains Duplicate

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

Example 1:

1
2
Input: nums = [1,2,3,1]
Output: true

Example 2:

1
2
Input: nums = [1,2,3,4]
Output: false

Example 3:

1
2
Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true

排序法：

时间复杂度：O(nlogn)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        int nums_size = nums.size();
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums_size - 1; i++) {
            if (nums[i] == nums[i + 1])return true;
        }
        return false;
    }
};

哈希表：

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> hash;
        for (int num : nums) {
            if (hash.count(num))return true;
            else hash.insert(num);
        }
        return false;
    }
};

Posted on Edited on In

206.Reverse Linked List

Given the head of a singly linked list, reverse the list, and return the reversed list.

Example 1:

img

1
2
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2:

img

1
2
Input: head = [1,2]
Output: [2,1]

Example 3:

1
2
Input: head = []
Output: []

个人解答：

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
	ListNode* reverseList(ListNode* head) {
        if(head == nullptr)return head;
        vector<int> vec;
        int i = 1;
        while (head != nullptr) {
            vec.resize(i);
            vec.push_back(head->val);
            head = head->next;
            i++;
        }
        ListNode* ans_head, * node, * end;
        i--;
        ans_head = new ListNode;
        ans_head->val = vec[i];
        end = ans_head;
        while(--i) {
            node = new ListNode;
            node->val = vec[i];
            end->next = node;
            end = node;
        }
        end->next = NULL;
        return ans_head;
    }
};

迭代法：

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

递归法：

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }
        ListNode* newHead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newHead;
    }
};

Posted on Edited on In

205.Isomorphic Strings

Given two strings s and t, determine if they are isomorphic.

Two strings s and t are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character, but a character may map to itself.

Example 1:

1
2
Input: s = "egg", t = "add"
Output: true

Example 2:

1
2
Input: s = "foo", t = "bar"
Output: false

Example 3:

1
2
Input: s = "paper", t = "title"
Output: true

哈希表：

时间复杂度：O(n)

空间复杂度：O(m)，m为字符串字符集数目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
	bool isIsomorphic(string s, string t) {
		unordered_map<char, char>s_t;
		unordered_map<char, char>t_s; 
		int len = s.length();
		for (int i = 0; i < len; i++) {
			char x = s[i];
			char y = t[i];
			if ((s_t.count(x) && s_t[x] != y) 
                || (t_s.count(y) && t_s[y] != x))return false;
			s_t[x] = y;
			t_s[y] = x;
		}
		return true;
	}
};

Posted on Edited on In

203.Remove Linked List Elements

Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.

Example 1:

img

1
2
Input: head = [1,2,6,3,4,5,6], val = 6
Output: [1,2,3,4,5]

Example 2:

1
2
Input: head = [], val = 1
Output: []

Example 3:

1
2
Input: head = [7,7,7,7], val = 7
Output: []

迭代法：

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        while (head != NULL && head->val == val)head = head->next;
        ListNode* t = head;
        ListNode* in = head;
        while (t != NULL)
        {
            if (t->val == val) {
                in->next = t->next;
                t = t->next;
                continue;
            }
            in = t;
            t = t->next;
        }
        return head;
    }
};

优化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummyHead = new ListNode(0, head);
        ListNode* temp = dummyHead;
        while (temp->next != NULL) {
            if (temp->next->val == val) {
                temp->next = temp->next->next;
            } else {
                temp = temp->next;
            }
        }
        return dummyHead->next;
    }
};

递归法：

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        if (head == nullptr) {
            return head;
        }
        head->next = removeElements(head->next, val);
        return head->val == val ? head->next : head;
    }
};

Posted on Edited on In

202.Happy Number

Write an algorithm to determine if a number n 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.
  • 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.

Return true if n is a happy number, and false if not.

Example 1:

1
2
3
4
5
6
7
Input: n = 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

Example 2:

1
2
Input: n = 2
Output: false

哈希表：

时间复杂度：O(logn)

空间复杂度：O(logn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool isHappy(int n) {
        unordered_set<int> hash;
        int sum = 0;
        while (1) {
            while (n != 0) {
                sum += (n % 10) * (n % 10);
                n /= 10;
            }
            if (sum == 1)return true;
            if (hash.count(sum))return false;
            else {
                hash.insert(sum);
                n = sum;
                sum = 0;
            }
        }
    }
};

快慢指针：

时间复杂度：O(logn)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public:
    int get_next(int value) {
        int sum = 0;
        while (value) {
            sum += (value % 10) * (value % 10);
            value /= 10;
        }
        return sum;
    }
    bool isHappy(int n) {
        int slow = n;
        int fast = get_next(n);
        while (fast != 1 && fast != slow) {
            slow = get_next(slow);
            fast = get_next(get_next(fast));
        }
        return fast == 1;
    }
};

Posted on Edited on In

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.

Note:

  • Note that in some languages, such as Java, there is no unsigned integer type. In this case, the input will be given as a signed integer type. It should not affect your implementation, as the integer’s internal binary representation is the same, whether it is signed or unsigned.
  • In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 3, the input represents the signed integer. -3.

Example 1:

1
2
3
Input: n = 00000000000000000000000000001011
Output: 3
Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits.

Example 2:

1
2
3
Input: n = 00000000000000000000000010000000
Output: 1
Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit.

Example 3:

1
2
3
Input: n = 11111111111111111111111111111101
Output: 31
Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one '1' bits.

位操作：

时间复杂度：O(logn)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int sum = 0;
        while (n!=0) {
            if ((n & 1) == 1)sum += 1;
            n >>= 1;
        }
        return sum;
    }
};

优化：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int ret = 0;
        while (n) {
            n &= n - 1;
            ret++;
        }
        return ret;
    }
};

Posted on Edited on In

190.Reverse Bits

Reverse bits of a given 32 bits unsigned integer.

Note:

  • Note that in some languages, such as Java, there is no unsigned integer type. In this case, both input and output will be given as a signed integer type. They should not affect your implementation, as the integer’s internal binary representation is the same, whether it is signed or unsigned.
  • In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 2 above, the input represents the signed integer -3 and the output represents the signed integer -1073741825.

Example 1:

1
2
3
Input: n = 00000010100101000001111010011100
Output:    964176192 (00111001011110000010100101000000)
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

Example 2:

1
2
3
Input: n = 11111111111111111111111111111101
Output:   3221225471 (10111111111111111111111111111111)
Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.

位操作：

时间复杂度：O(logn)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t r ans = 0;
        for (int i = 0; i < 32 && n > 0; ++i) {
            ans |= (n & 1) << (31 - i);
            n >>= 1;
        }
        return ans;
    }
};

分治：

时间复杂度：O(1)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
private:
    const uint32_t M1 = 0x55555555; // 01010101010101010101010101010101
    const uint32_t M2 = 0x33333333; // 00110011001100110011001100110011
    const uint32_t M4 = 0x0f0f0f0f; // 00001111000011110000111100001111
    const uint32_t M8 = 0x00ff00ff; // 00000000111111110000000011111111

public:
    uint32_t reverseBits(uint32_t n) {
        n = n >> 1 & M1 | (n & M1) << 1;
        n = n >> 2 & M2 | (n & M2) << 2;
        n = n >> 4 & M4 | (n & M4) << 4;
        n = n >> 8 & M8 | (n & M8) << 8;
        return n >> 16 | n << 16;
    }
};

Posted on Edited on In

171.Excel Sheet Column Number

Given a string columnTitle that represents the column title as appears in an Excel sheet, return its corresponding column number.

For example:

1
2
3
4
5
6
7
8
A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28 
...

Example 1:

1
2
Input: columnTitle = "A"
Output: 1

Example 2:

1
2
Input: columnTitle = "AB"
Output: 28

Example 3:

1
2
Input: columnTitle = "ZY"
Output: 701

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
	int titleToNumber(string columnTitle) {
		long n = pow(26, (columnTitle.size() - 1));
		int ans = 0;
		for (char c : columnTitle) {
			ans += (c - 'A' + 1) * n;
			n /= 26;
		}
		return ans;
	}
};

Posted on Edited on In

169.Majority Element

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Example 1:

1
2
Input: nums = [3,2,3]
Output: 3

Example 2:

1
2
Input: nums = [2,2,1,1,1,2,2]
Output: 2

排序法：

时间复杂度：O(nlogn)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int nums_size = nums.size();
        sort(nums.begin(), nums.end());
        int times = 1;
        for (int i = 1; i < nums_size; ++i) {
            if (nums[i] == nums[i - 1]) {
                times++;
                if (times > nums_size / 2)return nums[i];
            }
            else times = 1;
        }
        return nums[0];
    }
};

优化：

1
2
3
4
5
6
7
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        return nums[nums.size() / 2];
    }
};

哈希表：

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> counts;
        int majority = 0, cnt = 0;
        for (int num: nums) {
            ++counts[num];
            if (counts[num] > cnt) {
                majority = num;
                cnt = counts[num];
            }
        }
        return majority;
    }
};

随机法：

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int nums_size = nums.size();
        while (true) {
            int candidate = nums[rand() % nums_size];
            int count = 0;
            for (int num : nums)
                if (num == candidate)
                    ++count;
            if (count > nums_size / 2)
                return candidate;
        }
        return -1;
    }
};

分治：

时间复杂度：O(nlogn)

空间复杂度：O(logn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    int count_in_range(vector<int>& nums, int target, int lo, int hi) {
        int count = 0;
        for (int i = lo; i <= hi; ++i)
            if (nums[i] == target)
                ++count;
        return count;
    }
    int majority_element_rec(vector<int>& nums, int lo, int hi) {
        if (lo == hi)
            return nums[lo];
        int mid = (lo + hi) / 2;
        int left_majority = majority_element_rec(nums, lo, mid);
        int right_majority = majority_element_rec(nums, mid + 1, hi);
        if (count_in_range(nums, left_majority, lo, hi) > (hi - lo + 1) / 2)
            return left_majority;
        if (count_in_range(nums, right_majority, lo, hi) > (hi - lo + 1) / 2)
            return right_majority;
        return -1;
    }
public:
    int majorityElement(vector<int>& nums) {
        return majority_element_rec(nums, 0, nums.size() - 1);
    }
};

Boyer-Moore 投票算法：

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate = -1;
        int count = 0;
        for (int num : nums) {
            if (num == candidate)
                ++count;
            else if (--count < 0) {
                candidate = num;
                count = 1;
            }
        }
        return candidate;
    }
};

Posted on Edited on In

168.Excel Sheet Column Title

Given an integer columnNumber, return its corresponding column title as it appears in an Excel sheet.

For example:

1
2
3
4
5
6
7
8
A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28 
...

Example 1:

1
2
Input: columnNumber = 1
Output: "A"

Example 2:

1
2
Input: columnNumber = 28
Output: "AB"

Example 3:

1
2
Input: columnNumber = 701
Output: "ZY"

时间复杂度：O(log26columnNumber)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    string convertToTitle(int columnNumber) {
        string ans_s = "";
        while (columnNumber != 0) {
            ans_s += (columnNumber - 1) % 26 + 'A';
            columnNumber = (columnNumber - (columnNumber - 1) % 26 - 1) / 26;
        }
        reverse(ans_s.begin(), ans_s.end());
        return ans_s;
    }
};

代码优化：

时间复杂度：O(log26columnNumber)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    string convertToTitle(int columnNumber) {
        string ans;
        while (columnNumber > 0) {
            --columnNumber;
            ans += columnNumber % 26 + 'A';
            columnNumber /= 26;
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};