Here are my solutions to the LeetCode problems, linking to my Github repository:

EASY

• Leetcode 1 Two Sum
• Leetcode 9 Palindrome Number
• Leetcode 13 roman2integer
• Leetcode 14 longestcommonprefix
• Leetcode 20 valid parentheses
• Leetcode 21 merge2sortedlist

• Leetcode 73 矩阵置零

  给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
  进阶：
  一个直观的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
  一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
  你能想出一个仅使用常量空间的解决方案吗？
  示例 1：
  输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
  输出：[[1,0,1],[0,0,0],[1,0,1]]
  示例 2：
  输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
  输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

  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 28 29

  代码： class Solution { public: void setZeroes(vector<vector<int>>& matrix) { int m = matrix.size(); int n = matrix[0].size(); int flag_col0 = false; for (int i = 0; i < m; i++) { if (!matrix[i][0]) { flag_col0 = true; } for (int j = 1; j < n; j++) { if (!matrix[i][j]) { matrix[i][0] = matrix[0][j] = 0; } } } for (int i = m - 1; i >= 0; i--) { for (int j = 1; j < n; j++) { if (!matrix[i][0] || !matrix[0][j]) { matrix[i][j] = 0; } } if (flag_col0) { matrix[i][0] = 0; } } } };

• Leetcode 150 逆波兰表达式求值

  逆波兰表达式：
  逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。
  平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) ( 3 + 4 ) 。
  该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) ) 。
  逆波兰表达式主要有以下两个优点：
  去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + 也可以依据次序计算出正确结果。
  适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中
  根据 逆波兰表示法，求表达式的值。
  有效的算符包括 +、-、、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
  说明：
  整数除法只保留整数部分。
  给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
  示例 1：
  输入：tokens = [“2”,”1”,”+”,”3”,”“]
  输出：9
  解释：该算式转化为常见的中缀算术表达式为：((2 + 1) 3) = 9
  示例 2：
  输入：tokens = [“4”,”13”,”5”,”/“,”+”]
  输出：6
  解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

  class Solution: def evalRPN(self, tokens: List[str]) -> int: if len(tokens) == 1: return int(tokens[0]) stack = [] for token in tokens: if token not in '+-*/': stack.append(token) else: if len(stack) != 0: num1 = stack.pop() num2 = stack.pop() num3 = int(eval(str(num2) + token + str(num1))) stack.append(num3) return stack[0]

• Leetcode 191 位1的个数

  编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。
  提示：
  请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
  在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的 示例 3 中，输入表示有符号整数 -3。
  示例 1：
  输入：00000000000000000000000000001011
  输出：3
  解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 ‘1’。
  示例 2：
  输入：00000000000000000000000010000000
  输出：1
  解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 ‘1’。
  示例 3：
  输入：11111111111111111111111111111101
  输出：31
  解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 ‘1’。
  提示：
  输入必须是长度为 32 的 二进制串 。

  1 2 3 4 5 6 7 8 9 10 11 12 13 14

  代码： class Solution { public: int hammingWeight(uint32_t n) { int res = 0; while (n > 0) { if (n & 1 == 1) { ++res; } n /= 2; } return res; } };

• Leetcode 461 Hamming Distance

• Leetcode 709 To Lower Case
• Leetcode 771 Jewels and Stones
• Leetcode 804 Unique Morse Code Words
• Circle
• Leetcode 832 Flipping an Image

MEDIUM

• Leetcode 12 int2roman
• Leetcode 21 merge2sortedlist
• Leetcode 22 generateParentheses
• Leetcode 29 DivideTwoIntegers
• Leetcode 33 SearchInRotatedSortedArray
• Leetcode 34 FindFirstAndLastPositionInSortedArray
• Leetcode 36 SearchInRotatedSortedArray

• Leetcode 341 扁平化嵌套列表迭代器

  问题描述：
  给你一个嵌套的整型列表。请你设计一个迭代器，使其能够遍历这个整型列表中的所有整数。
  列表中的每一项或者为一个整数，或者是另一个列表。其中列表的元素也可能是整数或是其他列表。
  示例 1:
  输入: [[1,1],2,[1,1]]
  输出: [1,1,2,1,1]
  解释: 通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,1,2,1,1]。
  示例 2:
  输入: [1,[4,[6]]]
  输出: [1,4,6]
  解释: 通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,4,6]。

  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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57

  代码： /** * // This is the interface that allows for creating nested lists. * // You should not implement it, or speculate about its implementation * class NestedInteger { * public: * // Return true if this NestedInteger holds a single integer, rather than a nested list. * bool isInteger() const; * * // Return the single integer that this NestedInteger holds, if it holds a single integer * // The result is undefined if this NestedInteger holds a nested list * int getInteger() const; * * // Return the nested list that this NestedInteger holds, if it holds a nested list * // The result is undefined if this NestedInteger holds a single integer * const vector<NestedInteger> &getList() const; * }; */ class NestedIterator { public: NestedIterator(vector<NestedInteger> &nestedList) { Hello(nestedList); } void Hello(vector<NestedInteger> &nestedList) { for (int i = 0; i < nestedList.size(); i++) { if (nestedList[i].isInteger()) { nestedList_.push_back(nestedList[i].getInteger()); continue; } else { Hello(nestedList[i].getList()); } } } int next() { return nestedList_[count++]; } bool hasNext() { if (count < nestedList_.size()) { return true; } else { return false; } } private: vector<int> nestedList_; int count = 0; }; /** * Your NestedIterator object will be instantiated and called as such: * NestedIterator i(nestedList); * while (i.hasNext()) cout << i.next(); */

• Leetcode 516 LongestPalindSubstring

• 1. 回旋镖的数量

     给定平面上 n 对 互不相同 的点 points ，其中 points[i] = [xi, yi] 。回旋镖 是由点 (i, j, k) 表示的元组 ，其中 i 和 j 之间的距离和 i 和 k 之间的距离相等（需要考虑元组的顺序）。
     返回平面上所有回旋镖的数量。
     示例 1：
     输入：points = [[0,0],[1,0],[2,0]]
     输出：2
     解释：两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]
     示例 2：
     输入：points = [[1,1],[2,2],[3,3]]
     输出：2
     示例 3：
     输入：points = [[1,1]]
     输出：0

     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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87

     class Solution1 { public: int numberOfBoomerangs(vector<vector<int>>& points) { int ans = 0; for (auto& p : points) { unordered_map<int, int> cnt; for (auto& q : points) { int dis = (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1]); ++cnt[dis]; } for (auto& [_, m] : cnt) { ans += m * (m - 1); } } return ans; } }; class Solution { public: int CalculateDistance(vector<int> pointX, vector<int> pointY) { return (pointX[0] - pointY[0]) * (pointX[0] - pointY[0]) + (pointX[1] - pointY[1]) * (pointX[1] - pointY[1]); } int CountHuixuanbiao(vector<tuple<int, int, int>>& distanceTuple) { auto totalCount = 0; auto lastCount = 1; auto currentCount = 0; int lastDistance; for (auto i = distanceTuple.begin(); i != distanceTuple.end(); ++i) { auto x = get<0>(*i); auto y = get<1>(*i); auto z = get<2>(*i); if (currentCount++ == 0) { lastDistance = z; continue; } if (z == lastDistance) { // equal lastCount++; if (i == distanceTuple.end() - 1) { totalCount += lastCount * (lastCount - 1); } continue; } else { // not equal lastDistance = z; if (lastCount == 1) { continue; } else { totalCount += lastCount * (lastCount - 1); lastCount = 1; lastDistance = z; } } } return totalCount; } int numberOfBoomerangs(vector<vector<int>>& points) { if (points.empty()) { return 0; } else if (points[0].empty()) { return 0; } int pointSize = points.size(); auto totalCount = 0; for (auto i = 0; i < pointSize; i++) { vector<tuple<int, int, int>> distanceTuple; for (auto j = 0; j < pointSize; j++) { if (i != j) { distanceTuple.emplace_back(i, j, CalculateDistance(points[i], points[j])); } } //printf("\n"); sort(distanceTuple.begin(), distanceTuple.end(), [](const tuple<int, int, int>& a, const tuple<int, int, int>& b) -> bool {return get<2>(a) < get<2>(b); }); totalCount += CountHuixuanbiao(distanceTuple); //for (auto [x, y, z] : distanceTuple) { // cout << x << " " << y << " " << z << " " << totalCount << endl; //} } return totalCount; } };

HARD

• Leetcode 23 mergeKsortedlists