Ascendlogo

Posted on Edited on In

342.Power of Four

Given an integer n, return true if it is a power of four. Otherwise, return false.

An integer n is a power of four, if there exists an integer x such that n == 4x.

Example 1:

1
2
Input: n = 16
Output: true

Example 2:

1
2
Input: n = 5
Output: false

Example 3:

1
2
Input: n = 1
Output: true

时间复杂度：O(logn)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
class Solution {
public:
    bool isPowerOfFour(int n) {
        while(n && n % 4 == 0) {
            n /= 4;
        }
        return n == 1;
    }
};

二进制中1的位置：

时间复杂度：O(1)

空间复杂度：O(1)

1
2
3
4
5
6
class Solution {
public:
    bool isPowerOfFour(int n) {
        return n > 0 && (n & (n - 1)) == 0 && (n & 0xaaaaaaaa) == 0;
    }
};

取模性质：

时间复杂度：O(1)

空间复杂度：O(1)

1
2
3
4
5
6
class Solution {
public:
    bool isPowerOfFour(int n) {
        return n > 0 && (n & (n - 1)) == 0 && n % 3 == 1;
    }
};

Posted on Edited on In

338.Counting Bits

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1‘s in the binary representation of i.

Example 1:

1
2
3
4
5
6
Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10

Example 2:

1
2
3
4
5
6
7
8
9
Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

Brian Kernighan 算法：

时间复杂度：O(nlogn)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int countOnes(int x) {
        int ones = 0;
        while (x > 0) {
            x &= (x - 1);
            ones++;
        }
        return ones;
    }

    vector<int> countBits(int n) {
        vector<int> bits(n + 1);
        for (int i = 0; i <= n; i++) {
            bits[i] = countOnes(i);
        }
        return bits;
    }
};

动态规划：

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> bits(n + 1);
        int highBit = 0;
        for (int i = 1; i <= n; i++) {
            if ((i & (i - 1)) == 0) {
                highBit = i;
            }
            bits[i] = bits[i - highBit] + 1;
        }
        return bits;
    }
};
1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> bits(n + 1);
        for (int i = 1; i <= n; i++) {
            bits[i] = bits[i >> 1] + (i & 1);
        }
        return bits;
    }
};
1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> bits(n + 1);
        for (int i = 1; i <= n; i++) {
            bits[i] = bits[i & (i - 1)] + 1;
        }
        return bits;
    }
};

Posted on Edited on In

326.Power of Three

Given an integer n, return true if it is a power of three. Otherwise, return false.

An integer n is a power of three, if there exists an integer x such that n == 3x.

Example 1:

1
2
3
Input: n = 27
Output: true
Explanation: 27 = 33

Example 2:

1
2
3
Input: n = 0
Output: false
Explanation: There is no x where 3x = 0.

Example 3:

1
2
3
Input: n = -1
Output: false
Explanation: There is no x where 3x = (-1).

时间复杂度：O(logn)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
class Solution {
public:
    bool isPowerOfThree(int n) {
        while (n && n % 3 == 0) {
            n /= 3;
        }
        return n == 1;
    }
};

最大约数法：

时间复杂度：O(1)

空间复杂度：O(1)

1
2
3
4
5
6
class Solution {
public:
    bool isPowerOfThree(int n) {
        return n > 0 && 1162261467 % n == 0;
    }
};

Posted on Edited on In

303.Range Sum Query - Immutable

Given an integer array nums, handle multiple queries of the following type:

  1. Calculate the sum of the elements of nums between indices left and right inclusive where left <= right.

Implement the NumArray class:

  • NumArray(int[] nums) Initializes the object with the integer array nums.
  • int sumRange(int left, int right) Returns the sum of the elements of nums between indices left and right inclusive (i.e. nums[left] + nums[left + 1] + ... + nums[right]).

Example 1:

1
2
3
4
5
6
7
8
9
10
11
Input
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
Output
[null, 1, -1, -3]

Explanation
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return (-2) + 0 + 3 = 1
numArray.sumRange(2, 5); // return 3 + (-5) + 2 + (-1) = -1
numArray.sumRange(0, 5); // return (-2) + 0 + 3 + (-5) + 2 + (-1) = -3

时间复杂度：O(n2)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class NumArray {
public:
    vector<int> arr;
    NumArray(vector<int>& nums) {
        arr = nums;
    }

    int sumRange(int left, int right) {
        int sum = 0;
        while(left<=right) {
            sum += arr[left];
            left++;
        }
        return sum;
    }
};

前缀和：

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class NumArray {
public:
    vector<int> sums;

    NumArray(vector<int>& nums) {
        int n = nums.size();
        sums.resize(n + 1);
        for (int i = 0; i < n; i++) {
            sums[i + 1] = sums[i] + nums[i];
        }
    }

    int sumRange(int i, int j) {
        return sums[j + 1] - sums[i];
    }
};

Posted on Edited on In

292.Nim Game

You are playing the following Nim Game with your friend:

  • Initially, there is a heap of stones on the table.
  • You and your friend will alternate taking turns, and you go first.
  • On each turn, the person whose turn it is will remove 1 to 3 stones from the heap.
  • The one who removes the last stone is the winner.

Given n, the number of stones in the heap, return true if you can win the game assuming both you and your friend play optimally, otherwise return false.

Example 1:

1
2
3
4
5
6
7
Input: n = 4
Output: false
Explanation: These are the possible outcomes:
1. You remove 1 stone. Your friend removes 3 stones, including the last stone. Your friend wins.
2. You remove 2 stones. Your friend removes 2 stones, including the last stone. Your friend wins.
3. You remove 3 stones. Your friend removes the last stone. Your friend wins.
In all outcomes, your friend wins.

Example 2:

1
2
Input: n = 1
Output: true

Example 3:

1
2
Input: n = 2
Output: true

时间复杂度：O(1)
空间复杂度：O(1)

1
2
3
4
5
6
class Solution {
public:
    bool canWinNim(int n) {
    	return n % 4 != 0;
    }
};

Posted on Edited on In

290.Word Pattern

Given a pattern and a string s, find if s follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in s.

Example 1:

1
2
Input: pattern = "abba", s = "dog cat cat dog"
Output: true

Example 2:

1
2
Input: pattern = "abba", s = "dog cat cat fish"
Output: false

Example 3:

1
2
Input: pattern = "aaaa", s = "dog cat cat dog"
Output: false

哈希表：

时间复杂度：O(n+m)，n为pattern长度，m为s长度

空间复杂度：O(n+m)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool wordPattern(string pattern, string s) {
        int s_size = s.size();
        unordered_map<char, string>pattern_s;
        unordered_map<string, char>s_pattern;
        int i = 0;
        for (char ch : pattern) {
            string str;
            for (; i < s_size;i++) {
                if (s[i] == ' ')break;
                str += s[i];
            }
            i++;
            if(pattern_s.count(ch)&&pattern_s[ch]!=str||
               (s_pattern.count(str))&&s_pattern[str]!=ch)return false;
            pattern_s[ch] = str;
            s_pattern[str] = ch;
        }
        return i == s_size+1;
    }
};

Posted on Edited on In

283.Move Zeroes

Given an integer array nums, move all 0‘s to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

Example 1:

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

Example 2:

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

双指针：

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size(), left = 0, right = 0;
        while (right < n) {
            if (nums[right]) {
                swap(nums[left], nums[right]);
                left++;
            }
            right++;
        }
    }
};

Posted on Edited on In

278.First Bad Version

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Example 1:

1
2
3
4
5
6
7
Input: n = 5, bad = 4
Output: 4
Explanation:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.

Example 2:

1
2
Input: n = 1, bad = 1
Output: 1

二分法：

时间复杂度：O(logn)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int left = 1, right = n;
        while (left < right) { 
            int mid = left + (right - left) / 2; 
            if (isBadVersion(mid)) {
                right = mid; 
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
};

Posted on Edited on In

268.Missing Number

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Example 1:

1
2
3
Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

Example 2:

1
2
3
Input: nums = [0,1]
Output: 2
Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.

Example 3:

1
2
3
Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.

排序法：

时间复杂度：O(nlogn)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int missingNumber(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] - 1)return nums[i] + 1;
        }
        if (nums[0] != 0)return 0;
        else return nums_size;
    }
};

哈希表：

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        unordered_set<int> hash;
        int nums_size = nums.size();
        for (int i = 0; i < nums_size; i++) {
            hash.insert(nums[i]);
        }
        int missing = -1;
        for (int i = 0; i <= nums_size; i++) {
            if (!hash.count(i)) {
                missing = i;
                break;
            }
        }
        return missing;
    }
};

数学：

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int total = n * (n + 1) / 2;
        int arrSum = 0;
        for (int i = 0; i < n; i++) {
            arrSum += nums[i];
        }
        return total - arrSum;
    }
};

位运算：

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int res = 0;
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            res ^= nums[i];
        }
        for (int i = 0; i <= n; i++) {
            res ^= i;
        }
        return res;
    }
};

Posted on Edited on In

263.Ugly Number

An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.

Given an integer n, return true if n is an ugly number.

Example 1:

1
2
3
Input: n = 6
Output: true
Explanation: 6 = 2 × 3

Example 2:

1
2
3
Input: n = 1
Output: true
Explanation: 1 has no prime factors, therefore all of its prime factors are limited to 2, 3, and 5.

Example 3:

1
2
3
Input: n = 14
Output: false
Explanation: 14 is not ugly since it includes the prime factor 7.

个人解答：

时间复杂度：O(logn)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool isUgly(int n) {
        if(n <= 0)return false;
        while(n != 1) {
            if(n%2 == 0)n /= 2;
            else if(n%3 == 0)n /= 3;
            else if(n%5 == 0)n /= 5;
            else return false;
        }
        return true;
    }
};

优化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool isUgly(int n) {
        if (n <= 0) {
            return false;
        }
        vector<int> factors = {2, 3, 5};
        for (int factor : factors) {
            while (n % factor == 0) {
                n /= factor;
            }
        }
        return n == 1;
    }
};