鸭梨公共文档

主题

LeetCode 答题笔记 ​

1. 两数之和 ​

[简单] 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。

暴力法解决时间复杂度为 O(n2)O(n^2) ，哈希表解法时间复杂度为 O(n)O(n) 。

python
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        s = {}
        for i, x in enumerate(nums):
            if target - x in s:
                return [s[target - x], i]
            s[x] = i
        return []
cpp
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hashset;
        int i;
        for(i = 0; i< nums.size(); i++){
            if(hashset.count(target - nums[i])){
                return {hashset[target - nums[i]], i};
            }
            hashset[nums[i]] = i;
        }
        return {-1, -1};
    }
};

5. 最长回文子串 ​

[中等] 中心扩展法，分奇数和偶数讨论。

python
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        res_len = 1
        curr = 0
        for i in range(n):
            j = 1
            temp = 1
            while i - j >= 0 and i + j < n:
                if s[i-j] == s[i+j]:
                    temp += 2
                    j += 1
                else:
                    break
            if temp > res_len:
                curr = i-j+1
                res_len = temp
            if i + 1 < n and s[i] == s[i+1]:
                j = 1
                temp = 2
                while i - j >= 0 and i + j + 1 < n:
                    if s[i-j] == s[i+j+1]:
                        temp += 2
                        j += 1
                    else:
                        break
                if temp > res_len:
                    curr = i-j+1
                    res_len = temp
        return s[curr:curr+res_len]
cpp

6. Z 字形变换 ​

[中等] 逐个检查每个字符的所在位置，然后合并。

python
class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1:
            return s
        res = [''] * numRows
        for i, val in enumerate(s):
            mod = i % (2 * numRows - 2)
            if mod < numRows:
                res[mod] += val
            else:
                res[2 * numRows - 2 - mod] += val
        return ''.join(res)
cpp
class Solution {
   public:
    string convert(string s, int numRows) {
        if (numRows == 1)
            return s;
        vector<string> res(numRows);
        for (int i = 0; i < s.size(); i++) {
            int mod = i % (2 * numRows - 2);
            if (mod < numRows)
                res[mod] += s.at(i);
            else
                res[2 * numRows - 2 - mod] += s.at(i);
        }
        string out;
        for (string s : res) {
            out += s;
        }
        return out;
    }
};

8. 字符串转换整数 (atoi) ​

[中等] 模拟 atoi() 函数，逐个字分析，然后转换。

python
MAXVAL = 2 ** 31 -1
MINVAL = -2 ** 31

class Solution:
    def myAtoi(self, s: str) -> int:
        out = []
        for ch in s:
            if ch == ' ' and len(out) == 0:
                continue
            elif ch in '+-' and len(out) == 0:
                out.append(ch)
            elif ch.isdigit():
                out.append(ch)
            else:
                break
        if len(out) == 0:
            return 0
        if len(out) == 1 and out[0] in '+-':
            return 0
        num = int(''.join(out))
        if num > MAXVAL:
            return MAXVAL
        if num < MINVAL:
            return MINVAL
        return num
cpp

10. 正则表达式匹配 ​

[困难] 模拟正则表达式匹配 . 和 *。

这里回答了一直以来的误解，正则语言就是正则表达式是错误的。通常编程语言里的正则表达式是 NFA 引擎支持的语言，而非确定有穷自动机并不都是正则语言（使用泵原理证明），而正则语言是 3 型语言，通常的正则表达式是 2 型语言，一个简单的例子 a*c*a，不能转换为 DFA，但是正则语言总存在 NFA NN 和 DFA DD 等价，并等价于一个正则表达式。

最开始想到的算法，只能解决狭义的正则表达式

python
from collections import deque

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        if len(p) == 0:
            return len(s) == 0
        queue = deque()
        length = len(p)
        lp = list(p)
        for i in range(1, length - 1):
            if lp[i] == '*' and lp[i-1] == lp[i+1]:
                lp[i], lp[i+1] = lp[i+1], lp[i]
        p = ''.join(lp)
        temp = ''
        i = 0
        while i < length:
            if i + 1 < length and p[i + 1] == '*':
                temp += p[i:i+2]
                i += 2
            else:
                if temp:
                    queue.append(temp + p[i])
                    temp = ''
                else:
                    queue.append(p[i])
                i += 1
        if temp:
            queue.append(temp)
        for ch in s:
            print(ch, queue)
            if len(queue) == 0:
                return False
            if '*' in queue[0]:
                if ch in queue[0]:
                    index = queue[0].index(ch)
                    queue[0] = queue[0][index:]
                    if len(queue[0]) <= 1:
                        queue.popleft()
                elif queue[0][0] == '.':
                    pass
                else:
                    queue.popleft()
            elif queue[0] == '.':
                queue.popleft()
            elif queue[0] == ch:
                queue.popleft()
            else:
                return False
        print(queue)
        if len(queue) == 0:
            return True
        if len(queue) > 1:
            return False
        if '.*' in queue[0] and len(queue[0]) > 2:
            return False
        if '*' in queue[0]:
            if len(queue[0]) > 2:
                return False
            return True
        return False

这个算法效率很高，时空复杂度都是线性。经过测试，300 多个测试可以满足 200 多个，也就是说大多数正则表达式都是确定性的，这也指示我们平时写正则表达式养成好习惯，减少引擎回溯搜索。

正确解法是动态规划算法。使用 dp 背包解决：

python
cpp

11. 盛最多水的容器 ​

[中等] 贪心策略的双指针问题，每次收敛最小端。

python
class Solution:
    def maxArea(self, height: List[int]) -> int:
        maxVol = 0
        i = 0
        j = len(height) - 1
        while j > i:
            maxVol = max(maxVol, (j - i) * min(height[j], height[i]))
            if height[j] < height[i]:
                j -= 1
            else:
                i += 1
        return maxVol
cpp
class Solution {
   public:
    int maxArea(vector<int>& height) {
        int maxVol = 0;
        int i = 0, j = height.size() - 1;
        while (j > i) {
            maxVol = max(maxVol, (j - i) * min(height.at(j), height.at(i)));
            if (height.at(j) < height.at(i))
                --j;
            else
                ++i;
        }
        return maxVol;
    }
};

12. 整数转罗马数字 ​

[中等] 按照规则判断每一位的值即可，还可以列举每一种情况进行判断。官方解答中使用了硬编码。

python
class Solution:
    def intToRoman(self, num: int) -> str:
        f4, num = divmod(num, 1000)
        f3, num = divmod(num, 100)
        f2, num = divmod(num, 10)
        f1 = num
        res = 'M' * f4
        if f3 == 9:
            res += 'CM'
        elif f3 == 4:
            res += 'CD'
        elif f3 >= 5:
            f3 -= 5
            res += 'D' + 'C' * f3
        else:
            res += 'C' * f3
        if f2 == 9:
            res += 'XC'
        elif f2 == 4:
            res += 'XL'
        elif f2 >= 5:
            f2 -= 5
            res += 'L' + 'X' * f2
        else:
            res += 'X' * f2
        if f1 == 9:
            res += 'IX'
        elif f1 == 4:
            res += 'IV'
        elif f1 >= 5:
            f1 -= 5
            res += 'V' + 'I' * f1
        else:
            res += 'I' * f1
        return res
cpp
const string thousands[] = {"", "M", "MM", "MMM"};
const string hundreds[] = {
    "", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
const string tens[] = {
    "", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
const string ones[] = {
    "", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};

class Solution {
   public:
    string intToRoman(int num) {
        return thousands[num / 1000] + 
        hundreds[num % 1000 / 100] + 
        tens[num % 100 / 10] + ones[num % 10];
    }
};

15. 三数之和 ​

[中等] 排序加上双指针时间 O(n2)O(n^2) ，不考虑空间。

python
class Solution:
    def threeSum(self, nums: List[int]):
        nums.sort()
        res = []
        length = len(nums) - 1
        for i, val in enumerate(nums):
            if i >= length:
                return res
            if i > 0 and val == nums[i-1]:
                continue
            fast = length
            slow = i + 1
            while fast > slow:
                temp = nums[fast] + nums[slow]
                if temp > -val:
                    fast -= 1
                if temp < -val:
                    slow += 1
                if temp == -val:
                    newelem = [val, nums[slow], nums[fast]]
                    if res:
                        if res[-1] != newelem:
                            res.append(newelem)
                    else:
                        res.append(newelem)
                    fast -= 1
                    slow += 1
        return res
cpp
class Solution {
   public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        int length = nums.size() - 1;
        int fast, slow, temp;
        for (int i = 0; i < nums.size(); ++i) {
            if (i >= length)
                return res;
            if (i > 0 && nums.at(i) == nums.at(i - 1))
                continue;
            fast = length;
            slow = i + 1;
            while (fast > slow) {
                temp = nums.at(fast) + nums.at(slow);
                if (temp > -nums.at(i))
                    --fast;
                else if (temp < -nums.at(i))
                    ++slow;
                else {
                    vector<int> newelem = {nums.at(i), nums.at(slow), nums.at(fast)};
                    if (res.size() > 0) {
                        if (res.at(res.size() - 1) != newelem) {
                            res.push_back(newelem);
                        }
                    } else {
                        res.push_back(newelem);
                    }
                    --fast;
                    ++slow;
                }
                
            }
        }
        return res;
    }
};

16. 最接近的三数之和 ​

[中等] 排序加双指针，时间复杂度 O(n2)O(n^2) ，空间复杂度 O(1)O(1) （如果计算排序则为 O(log⁡n)O(\log n) ）。

python
class Solution:
    def threeSumClosest(self, nums: List[int],
                        target: int) -> int:
        res = sum(nums[:3])
        nums.sort()
        n = len(nums)
        for i in range(n):
            slow = 0
            fast = n - 1
            while fast > slow:
                temp = nums[i] + nums[fast] + nums[slow]
                if fast != slow and fast != i and slow != i:
                    if abs(target - res) > abs(target - temp):
                        res = temp
                if target > temp:
                    slow += 1
                elif target < temp:
                    fast -= 1
                else:
                    slow += 1
                    fast -= 1
        return res
cpp

17. 电话号码的字母组合 ​

[中等] 笛卡尔乘积，Python 可以使用 itertools 相关的迭代器。

product 方法

python
from itertools import product

NUM_DICT = {
    '2': 'abc',
    '3': 'def',
    '4': 'ghi',
    '5': 'jkl',
    '6': 'mno',
    '7': 'pqrs',
    '8': 'tuv',
    '9': 'wxyz'
}

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        return list(map(
            lambda x: ''.join(x),
            product(*map(lambda x :NUM_DICT[x], digits))
        ))

回溯算法

python
NUM_DICT = [
    '',
    '',
    'abc',
    'def',
    'ghi',
    'jkl',
    'mno',
    'pqrs',
    'tuv',
    'wxyz'
]

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        res = list[str]()
        s_list = list[str]()

        def backtracking(digits: str, index: int) -> None:
            if index == len(digits):
                res.append(''.join(s_list))
                return
            dig = ord(digits[index]) - ord('0')
            for ch in NUM_DICT[dig]:
                s_list.append(ch)
                backtracking(digits, index + 1)
                s_list.pop()

        if len(digits) == 0:
            return res
        backtracking(digits, 0)
        return res
cpp
class Solution {
    string tmp;
    vector<string> res;
    vector<string> board{
        "", "", "abc", "def", "ghi",
        "jkl", "mno", "pqrs", "tuv", "wxyz"};

   public:
    void dfs(int pos, string digits) {
        if (pos == digits.size()){
            res.push_back(tmp);
            return;
        }
        char num = digits.at(pos) - '0';
        for(int i = 0; i < board.at(num).size(); ++i){
            tmp.push_back(board.at(num).at(i));
            dfs(pos + 1, digits);
            tmp.pop_back();
        }
    }
    vector<string> letterCombinations(string digits) {
        if (digits.size() == 0)
            return res;
        dfs(0, digits);
        return res;
    }
};

18. 四数之和 ​

[中等] 排序加双指针，时间复杂度 O(n3)O(n^3) ，空间复杂度 O(log⁡n)O(\log n) （排序复杂度，不包含答案）。

python
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        res = set[tuple[int]]()
        nums.sort()
        n = len(nums)
        for i in range(n-2):
            for j in range(i+1, n-1):
                slow = j+1
                fast = n-1
                while fast > slow:
                    temp = nums[i] + nums[j] + nums[fast] + nums[slow]
                    if temp < target:
                        slow += 1
                    elif temp > target:
                        fast -= 1
                    else:
                        res.add((nums[i], nums[j], nums[fast], nums[slow]))
                        slow += 1
                        fast -= 1
        return list(map(list, res))
cpp

19. 删除链表的倒数第 N 个结点 ​

[中等] 快慢指针即可。维护两个指针，使快指针比慢指针领先 nn 个节点。

python
class Solution:
    def removeNthFromEnd(self, head: ListNode,
                         n: int) -> ListNode:
        root_node = ListNode(0, head)
        fast = root_node
        slow = root_node
        for _ in range(n):
            fast = fast.next
        while fast and fast.next:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return root_node.next
cpp

22. 括号生成 ​

[中等] 回溯算法。

python
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = list[str]()
        path = list[str]()

        def backtracking(left: int, right: int) -> None:
            nonlocal n
            if left == n and right == n:
                res.append(''.join(path))
                return

            if left < n:
                path.append('(')
                backtracking(left + 1, right)
                path.pop()
            if right < left:
                path.append(')')
                backtracking(left, right + 1)
                path.pop()

        backtracking(0, 0)
        return res
cpp

25. K 个一组翻转链表 ​

[困难] 快慢指针翻转，两个指针内的链表翻转，然后复原，翻转下一组的链表。

python
class Solution:
    def reverse_list(self, node: ListNode) -> ListNode:
        if node is None or node.next is None:
            return node
        prev = None
        curr = node
        nextnode = node.next
        while curr.next is not None:
            curr.next = prev
            prev = curr
            curr = nextnode
            nextnode = nextnode.next
        curr.next = prev
        return curr

    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        if k == 1:
            return head
        root = ListNode()
        root.next = head
        slow = root
        fast = root
        while fast and fast.next:
            for _ in range(k):
                fast = fast.next
                if not fast:
                    return root.next
            next_linklist = fast.next
            fast.next = None
            tail = slow.next
            self.reverse_list(slow.next)
            slow.next = fast
            tail.next = next_linklist
            slow = tail
            fast = tail
        return root.next
cpp

30. 串联所有单词的子串 ​

[困难] 滑动窗口的简单应用，滚动哈希表即可。

python
from collections import Counter

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        word_length = len(words[0])
        n = len(words)
        res = []
        len_s = len(s)
        for i in range(word_length):
            j = i
            curr_zero = 0
            ct = Counter(words)
            while j + word_length <= len_s:
                temp = s[j:j+word_length]
                if temp in ct:
                    ct[temp] -= 1
                    if ct[temp] == 0:
                        curr_zero += 1
                    elif ct[temp] == -1:
                        curr_zero -= 1
                if j - word_length * (n) >= 0:
                    t2 = s[j-word_length*(n):j-word_length*(n-1)]
                    if t2 in ct:
                        ct[t2] += 1
                        if ct[t2] == 0:
                            curr_zero += 1
                        if ct[t2] == 1:
                            curr_zero -= 1
                if temp in ct and curr_zero == len(ct):
                    res.append(j - word_length * (n-1))
                j += word_length
        return res
cpp

36. 有效的数独 ​

[中等] 按照定义比较即可，有一些地方可以被优化。

python
class Solution:
    def isValid(self, l: List[str]) -> bool:
        valid = [0] * 9
        for x in l:
            if x != '.':
                valid[int(x)-1] += 1
        return all(x < 2 for x in valid)

    def isValidSudoku(self, board: List[List[str]]) -> bool:
        for i in range(9):
            if not self.isValid(board[i]):
                return False
            if not self.isValid(x[i] for x in board):
                return False
            x, y = divmod(i, 3)
            x *= 3
            y *= 3
            if not self.isValid(board[y][x:x+3] +
                                board[y+1][x:x+3] +
                                board[y+2][x:x+3]):
                return False
        return True
cpp

37. 解数独 ​

[困难] 回溯搜索。

python
class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        def is_vaild(r: int, c: int, val: str) -> bool:
            for i in range(9):
                if board[i][c] == val or\
                    board[r][i] == val:
                    return False
            start_row = (r // 3) * 3
            start_col = (c // 3) * 3
            for i in range(start_row, start_row + 3):
                for j in range(start_col, start_col + 3):
                    if board[i][j] == val:
                        return False
            return True

        def backtracking() -> bool:
            for i in range(9):
                for j in range(9):
                    if board[i][j] != '.':
                        continue
                    for k in range(1, 10):
                        if is_vaild(i, j, str(k)):
                            board[i][j] = str(k)
                            if backtracking():
                                return True
                            board[i][j] = '.'
                    return False
            return True

        backtracking()
cpp

38. 外观数列 ​

[中等] 递归解答即可，实际是简单题。

python
class Solution:
    def countAndSay(self, n: int) -> str:
        if n == 1:
            return '1'
        if n == 2:
            return '11'
        last = self.countAndSay(n - 1)
        temp_char = last[0]
        temp_nums = 0
        res = ''
        for ch in last:
            if ch == temp_char:
                temp_nums += 1
            else:
                res += str(temp_nums) + temp_char
                temp_char = ch
                temp_nums = 1
        res += str(temp_nums) + temp_char
        return res
cpp
class Solution {
   public:
    string countAndSay(int n) {
        if (n == 1)
            return "1";
        if (n == 2)
            return "11";
        string last = countAndSay(n - 1);
        char temp_char = last[0];
        int temp_nums = 0;
        string res;
        for (const char ch : last) {
            if (ch == temp_char) {
                ++temp_nums;
            } else {
                res += to_string(temp_nums);
                res += temp_char;
                temp_char = ch;
                temp_nums = 1;
            }
        }
        res += to_string(temp_nums);
        res += temp_char;
        return res;
    }
};

39. 组合总和 ​

[中等] 回溯算法，需要剪枝搜索优化。

python
class Solution:
    def combinationSum(self, candidates: List[int],
                       target: int) -> List[List[int]]:
        res = list[list[int]]()
        path = list[int]()

        def backtracking(target: int, sum: int, start: int
            ) -> None:
            if sum > target:
                return
            if sum == target:
                res.append(path.copy())
                return
            for i in range(start, len(candidates)):
                path.append(candidates[i])
                backtracking(target, sum + candidates[i], i)
                path.pop()

        backtracking(target, 0, 0)
        return res
cpp

40. 组合总和 II ​

[中等] 本来理解 candidates 集合每一个元素都不重复，直到看到测试用例发现 candidates 可以重复，candidates 非重复情况也给出了算法如下。本题使用回溯算法，需要剪枝优化。

非重复的情况（不是本题情况）

python
class Solution:
    def combination(self, candidates: List[int],
                    target: int) -> List[List[int]]:
        res = set[tuple[int]]()
        path = set[int]()

        def backtracking(target: int) -> None:
            if target < 0:
                return
            if target == 0:
                res.add(tuple(sorted(path)))
                return
            for elem in set(candidates) - path:
                path.add(elem)
                backtracking(target - elem)
                path.remove(elem)

        backtracking(target)
        return list(map(list, res))

剪枝搜索

python
class Solution:
    def combinationSum2(self, candidates: List[int],
                        target: int) -> List[List[int]]:
        res = list[list[int]]()
        path = list[int]()
        n = len(candidates)
        candidates.sort()

        def backtracking(sums: int, index: int) -> None:
            if sums > target:
                return None
            if sums == target:
                res.append(path.copy())
                return None

            for i in range(index, n):
                if sums + candidates[i] > target:
                    break
                if i > index and candidates[i] == candidates[i-1]:
                    continue
                path.append(candidates[i])
                backtracking(sums + candidates[i], i + 1)
                path.pop()

        backtracking(0, 0)
        return res
cpp

43. 字符串相乘 ​

[中等] 模拟乘法。

python
class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        zero = ord('0')
        res = 0
        for i, c1 in enumerate(reversed(num1)):
            next_val = 0
            for j, c2 in enumerate(reversed(num2)):
                times = (ord(c1) - zero) * (ord(c2) - zero)
                res += 10 ** (i+j) * times
        return str(res)
cpp

45. 跳跃游戏 II ​

[中等] 贪心算法即可。

python
class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        maxPos, end, step = 0, 0, 0
        for i in range(n - 1):
            if maxPos >= i:
                maxPos = max(maxPos, i + nums[i])
                if i == end:
                    end = maxPos
                    step += 1
        return step
cpp

46. 全排列 ​

[中等] 全排列，Python 可以用标准库 itortools。

python
import itertools

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        return list(map(list, itertools.permutations(nums)))

回溯搜索

python
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = list[list[int]]()
        path = list[int]()
        n = len(nums)
        used = [False] * n

        def backtracking():
            if len(path) == n:
                res.append(path.copy())
                return
            for i, val in enumerate(nums):
                if used[i]:
                    continue
                used[i] = True
                path.append(val)
                backtracking()
                path.pop()
                used[i] = False

        backtracking()
        return res
cpp

47. 全排列 II ​

[中等] 使用集合存放即可，回溯剪枝算法。

python
from itertools import permutations

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        res = set(permutations(nums))
        return list(map(list, res))

回溯剪枝搜索

python
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        nums.sort()
        res = list[list[int]]()
        path = list[int]()
        used = [False] * n

        def backtracking() -> None:
            if len(path) == n:
                res.append(path.copy())
                return
            for i in range(n):
                if used[i] or (i > 0 and nums[i] == nums[i-1] and used[i-1] is False):
                    continue
                used[i] = True
                path.append(nums[i])
                backtracking()
                path.pop()
                used[i] = False

        backtracking()
        return res
cpp

48. 旋转图像 ​

[中等] 一个巧妙的方法是翻转两次即为旋转。或者使用临时变量储存中间值，然后分四块旋转矩阵，这两种方法空间复杂度均为 O(1)O(1) ，时间复杂度为 O(n2)O(n^2) 。

python
class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)
        for i in range(n):
            for j in range(n - i):
                matrix[i][j], matrix[n-j-1][n-i-1] =\
                    matrix[n-j-1][n-i-1], matrix[i][j]
        for i in range(n // 2):
            for j in range(n):
                matrix[i][j], matrix[n-i-1][j] =\
                    matrix[n-i-1][j], matrix[i][j]
cpp

50. Pow(x, n) ​

[中等] 实现 pow(x, n) ，即计算 x 的 n 次幂函数（即 xnx^n ）

思路，可以使用递归考虑，每一次幂运算都可以判断是否是偶数，这个是尾递归，考虑优化就是分治思想了。

python
class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n == 0:
            return 1
        if n == 1:
            return x
        reverse = False
        if n < 0:
            reverse = True
            n = -n
        result = 1
        while n >= 1:
            if n % 2:
                result *= x
            x *= x
            n //= 2
        if reverse:
            return 1 / result
        return result
cpp
class Solution {
   public:
    double myPow(double x, int n) {
        if (n == 0)
            return 1;
        if (n == 1)
            return x;
        long temp = n;
        if (n < 0) {
            temp = -(long)n;
        }
        double result = 1;
        while (temp >= 1) {
            if (temp % 2) {
                result *= x;
            }
            x *= x;
            temp /= 2;
        }
        if (n < 0) {
            return 1 / result;
        }
        return result;
    }
};