代码拉取完成，页面将自动刷新
leetcode 找出数组中重复的数字。 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
int cnt[100000];
int findRepeatNumber(vector<int>& nums) {
for (int i = 0; i < nums.size(); ++i) {
cnt[nums[i]]++;
if (cnt[nums[i]] > 1) return nums[i];
}
return -1;
}
int findRepeatNumber(vector<int>& nums) {
sort(nums.begin(), nums.end());
for (int i = 1; i < nums.size(); ++i) {
if (nums[i] == nums[i -1 ]) return nums[i];
}
return -1;
}
leetcode在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。 请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
target比他还要小，说明target一定不在此行。他又是本列的最大值，如果target比他还要大，那target一定不在这一列。通过这样可以筛选掉一行或者一列。 bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
int row = matrix.size() - 1;
int col = 0;
while (row >= 0 && col < matrix[0].size()) {
if (matrix[row][col] == target) return true;
else if (matrix[row][col] > target) row--;
else col++;
}
return false;
}
bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
if (matrix.empty()) return false;
int row = matrix.size();
for (int i = 0; i < row; ++i) {
if (find(matrix, i, target)) return true;
}
return false;
}
bool find(vector<vector<int>>& matrix, int row, int target) {
if (matrix[row].empty()) return false;
int left = 0, right = matrix[0].size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (matrix[row][mid] < target) left = mid + 1;
else if (matrix[row][mid] > target) right = mid;
else if (matrix[row][mid] == target) return true;
}
return matrix[row][left] == target;
}
leetcode请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
输入：s = "We are happy."
输出："We%20are%20happy."
限制： 0 <= s 的长度 <= 10000
1. erase(pos,n); 删除从pos开始的n个字符，比如erase(0,1)就是删除第一个字符
2. erase(position);删除position处的一个字符(position是个string类型的迭代器)
3. erase(first,last);删除从first到last之间的字符（first和last都是迭代器）
string replaceSpace(string s) {
for (int i = 0; s[i] != '\0'; ++i) {
if (s[i] == ' ') {
s.erase(i, 1);
s.insert(i, string("%20"));
}
}
return s;
}
？a ：b运算符中a和b必须属于同一类型，“%20”是const char*类型，而ch属于char类型，只能用以下形式来写。 string replaceSpace(string s) {
string ans = "";
for (char ch : s)
ans = (ch == ' ') ? ans + "%20" : ans + ch ;
return ans;
}
string replaceSpace(string s) {
int len = s.size();
string res;
for (int i = 0; i < len; ++i) {
if (s[i] == ' ') {
res += "%20";
} else {
res += s[i];
}
}
return res;
}
string replaceSpace(string s) {
int len = s.size();
int cnt = 0;
for (int i = 0; i < len; ++i) {
if (s[i] == ' ') cnt++;
}
s += string(cnt * 2, ' ');
int p1 = s.size() - 1;
int p2 = len - 1;
while (p2 >= 0) {
if (s[p2] == ' ') {
s[p1--] = '0';
s[p1--] = '2';
s[p1--] = '%';
} else {
s[p1--] = s[p2];
}
p2--;
}
return s;
}
leetcode输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
vector<int> reversePrint(ListNode* head) {
ListNode* pre = NULL;
ListNode* cur = head;
while (cur != NULL) {
ListNode * tmp = cur->next;
cur->next = pre;
pre = cur;
cur = tmp;
}
vector<int> res;
while (pre != NULL) {
res.push_back(pre->val);
pre = pre->next;
}
return res;
}
vector<int> reversePrint(ListNode* head) {
stack<int> sck;
while (head) {
sck.push(head->val);
head = head->next;
}
vector<int> res;
while (!sck.empty()) {
res.push_back(sck.top());
sck.pop();
}
return res;
}
leetcode输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
root结点并给root->left和root->right赋值。left > right,left=right是最后一个结点或者说叶子节点。pre_root根结点再先序列中的索引，in_left中序列中左子树左边界 in_right 中序列中右子树右边界。idHash。 unordered_map<int, int> idHash;
vector<int> pre;
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
pre = preorder;
for (int i = 0; i < inorder.size(); ++i) {
idHash[inorder[i]] = i;
}
return buildTree(0, 0, inorder.size() - 1);
}
TreeNode* buildTree(int pre_root, int in_left, int in_right) {
if (in_left > in_right) return NULL;
TreeNode* root = new TreeNode(pre[pre_root]);
int in_root = idHash[pre[pre_root]];
root->left = buildTree(pre_root + 1, in_left, in_root - 1);
// 左节点个数是：in_root - in_left + 1 经常容易写错
root->right = buildTree(pre_root + in_root - in_left + 1, in_root + 1, in_right);
return root;
}
leetcode 用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
stack<int> sck1;
stack<int> sck2;
CQueue() { }
void appendTail(int value) {
sck1.push(value);
}
int deleteHead() {
if (sck2.empty() && sck1.empty()) return -1;
if (sck2.empty()) {
while (!sck1.empty()) {
sck2.push(sck1.top());
sck1.pop();
}
}
int front = sck2.top();
sck2.pop();
return front;
}
leetcode 写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下,斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
dp[i] = dp[i -1] + dp[i -2]
int fib(int n) {
int dp[n + 1];
for (int i = 0; i <= n; ++i) {
if (i == 0) dp[0] = 0;
else if (i == 1) dp[1] = 1;
else dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
}
return dp[n];
}
int fib(int n) {
int first = 0, second = 1;
int ans = n == 0 ? 0 : 1;
for (int i = 2; i <= n; ++i) {
ans = (first + second) % 1000000007;
first = second;
second = ans;
}
return ans;
}
leetcode 一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
int numWays(int n) {
int dp[n + 1];
for (int i = 0; i <= n; ++i) {
if (i == 0) dp[0] = 1;
else if (i == 1) dp[1] = 1;
else if (i == 2) dp[2] = 2;
else dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
}
return dp[n];
}
int numWays(int n) {
if (n == 0 || n == 1) return 1;
if (n == 2) return 2;
int first = 1;
int second = 2;
int res = 0;
for (int i = 2; i < n; ++i) {
res = (first + second) % 1000000007;
first = second;
second = res;
}
return res;
}
leetcode 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。
right--
int minArray(vector<int>& nums) {
int left = 0;
int right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) left = mid + 1;
else if (nums[mid] < nums[right]) right = mid;
else if (nums[mid] == nums[right]) right--;
}
return nums[left];
}
int minArray(vector<int>& numbers) {
for (int i = 0; i + 1 < numbers.size(); ++i) {
if (numbers[i] > numbers[i + 1])
return numbers[i + 1];
}
return numbers[0];
}
leetcode 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。 [["a","b","c","e"], ["s","f","c","s"], ["a","d","e","e"]] 但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。
public:
bool exist(vector<vector<char>>& board, string word) {
for (int i = 0; i < board.size(); i++) {
for (int j = 0; j < board[0].size(); j++) {
if (dfs(board, word, i, j, 0))
return true;
}
}
return false;
}
private:
bool dfs(vector<vector<char>>& b, string& w, int i, int j, int k) {
if (i >= b.size() || i < 0 || j >= b[0].size() || j < 0 || b[i][j] != w[k])
return false;
if (k == w.length() - 1)
return true;
char temp = b[i][j];
b[i][j] = '/';
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
for (int q = 0; q < 4; q ++ ) {
int m = i + dx[q], n = j + dy[q];
if (dfs(b, w, m, n, k + 1)) return true;
}
b[i][j] = temp;
return false;
}
int off[4][2] = {{1,0}, {-1,0}, {0, 1}, {0, -1}};
vector<vector<bool>> isVis;
string word;
vector<vector<char>> board;
int row;
int col;
bool exist(vector<vector<char>>& board, string word) {
row = board.size();
col = board[0].size();
this->isVis.resize(row, vector<bool>(col, false));
this->board = board;
this->word = word;
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
if (board[i][j] == word[0]) {
int depth = 0;
if(dfs(i, j, depth)) return true;
}
}
}
return false;
}
bool dfs(int x, int y, int depth) {
if (isVis[x][y]) return false;
isVis[x][y] = true;
cout << board[x][y];
if (depth == word.size() - 1) return true;
for (int i = 0; i < 4; ++i) {
int m = x + off[i][0];
int n = y + off[i][1];
if (m < row && m >= 0 && n < col && n >= 0 && board[m][n] == word[depth + 1])
if (dfs(m, n, depth + 1)) return true;
}
isVis[x][y] = false;
return false;
}
leetcode 地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
int cnt = 0;
int m, n, k;
int off[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
bool** isVis;
int movingCount(int m, int n, int k) {
this->m = m;
this->n = n;
this->k = k;
isVis = new bool*[m];
for (int i = 0; i < m; ++i) {
isVis[i] = new bool[n];
memset(isVis[i], 0, n * sizeof(bool));
}
dfs(0, 0, isVis);
return cnt;
}
void dfs(int i, int j, bool** isVis) {
if (isVis[i][j]) return;
isVis[i][j] = true;
cnt++;
for (int z = 0; z < 4; ++z) {
int x = i + off[z][0];
int y = j + off[z][1];
if (x >= 0 && y >= 0 && x < m && y < n &&
(x / 10 + x % 10 + y / 10 + y % 10 <= k))
dfs(x, y, isVis);
}
return;
}
leetcode 给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]k[1]...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
int cuttingRope(int n) {
int res = 0;
for (int m = 2; m <=n; ++m) {
int avg = n / m;
int sum = n % m ? pow(avg, m - n % m) * pow(avg + 1, n % m) : pow(avg, m);
res = max(res, sum);
}
return res;
}
leetcode 给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m - 1] 。请问 k[0]k[1]...*k[m - 1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
2 <= n <= 1000
(xy)⊙p=[(x⊙p)(y⊙p)]⊙p
int cuttingRope(int n) {
if (n == 2 || n == 3) return n -1;
long res = 1;
while (n > 4) {
res = res * 3 % 1000000007;
n -= 3;
}
return res * n % 1000000007;
}
int cuttingRope(int n) {
if (n == 2 || n == 3) return n - 1;
int a = n / 3;
int b = n % 3;
if (b == 2) return quickPow(3, a) * 2 % 1000000007;
else return quickPow(3, a - 1) * (b + 3) % 1000000007;
}
long quickPow(int x, int n) {
long res = 1;
long t = x;
while (n) {
if (n & 1)
res = res * t % 1000000007;
t = t * t % 1000000007;
n /= 2;
}
return res;
}
请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。
(num & 1) 判断num二进制形式的最后一位是否是1，num >>= 1让num二进制数右移一位，就可以实现逐位判断。 int hammingWeight(uint32_t n) {
int cnt = 0;
while (n) {
if (n & 1) cnt++;
n >>= 1;
}
return cnt;
}
int hammingWeight(uint32_t n) {
uint32_t mask = 1;
int i = 32;
int cnt = 0;
while (i--) {
if (n & mask) cnt++;
mask <<= 1;
}
return cnt;
}
int hammingWeight(uint32_t n) {
int cnt = 0;
while (n) {
n &= n - 1;
cnt++;
}
return cnt;
}
leetcode 实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。
x^9 指数为9，二进制是:1001, 那么9 = 2^3 + 2^0, 所以x^9 = x^8 * x^1 ) double myPow(double x, int n) {
if (n == 0) return 1;
bool isPositive = true;
long t = n;
if (t < 0) t = -t, isPositive = false;
double res = 1;
while (t) {
if (t & 1) res *= x;
x *= x;
t >>= 1;
}
return isPositive ? res : (1 / res);
}
t >>= 1,t不能是负数（因为负数用的是补码），因此之前现做绝对化处理,但是力扣的用例中使用了n = -2147483648这个数，int的取值范围是-2147483648到2147483647，但-2147483648取绝对值2147483648超出int范围，所以需要long去接他。 double myPow(double x, int n) {
double res = 1;
int t = n;
while (n) {
if (n & 1) res *= x;
x *= x;
n /= 2;
}
return t > 0 ? res : 1 / res;
}
n在递归中发送变化，因此结束条件只考虑n的情况。 double myPow(double x, int n) {
if (n == 0) return 1;
if (n == 1) return x;
if (n == -1) return 1 / x;
double half = myPow(x, n / 2);
double mod = myPow(x, n % 2);
return half * half * mod;
}
leetcode 输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。
输入: n = 1
输出: [1,2,3,4,5,6,7,8,9]
vector<int> printNumbers(int n) {
int cnt = 0;
vector<int> res;
while (n--) {
cnt = cnt * 10 + 9;
}
for (int i = 1; i <= cnt; ++i) {
res.push_back(i);
}
return res;
}
vector<int> printNumbers(int n) {
int limit = pow(10, n) - 1;
vector<int> res;
for (int i = 1; i <= limit; ++i) {
res.push_back(i);
}
return res;
}
leetcode给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。 返回删除后的链表的头节点。
ListNode* deleteNode(ListNode* head, int val) {
ListNode* dummy = new ListNode(-1);
dummy->next = head;
ListNode* cur = head;
ListNode* pre = dummy;
while (cur->val != val) {
cur = cur->next;
pre = pre->next;
}
pre->next = cur->next;
return dummy->next;
}
leetcode 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
vector<int> exchange(vector<int>& nums) {
if (nums.size() == 0) return {};
int left = 0;
int right = nums.size() - 1;
int temp = nums[right];
while (left < right) {
while ((nums[left] & 1) == 1 && left < right) left++;
nums[right] = nums[left];
while ((nums[right] & 1) == 0 && left < right) right--;
nums[left] = nums[right];
}
nums[left] = temp;
return nums;
}
vector<int> exchange(vector<int>& nums) {
if (nums.empty()) return {};
int left = 0 ,right = nums.size() - 1;
while (left < right) {
while (left < right && (nums[right] & 1) == 0) right--;
while (left < right && (nums[left] & 1) == 1) left++;
swap(nums[left++], nums[right--]);
}
return nums;
}
leetcode输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。
null时，慢指针正好指向倒数第k个结点。dummy，方便删第一个结点。 ListNode* getKthFromEnd(ListNode* head, int k) {
ListNode* dummy = new ListNode(-1);
dummy->next = head;
ListNode* fast = dummy;
ListNode* slow = dummy;
while (k--) {
fast = fast->next;
}
while (fast) {
fast = fast->next;
slow = slow->next;
}
return slow;
}
leetcode定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
ListNode* reverseList(ListNode* head) {
ListNode* pre = NULL;
ListNode* cur = head;
while (cur) {
ListNode* tmp = cur->next;
cur->next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
ListNode* reverseList(ListNode* head) {
if (!head) return NULL;
stack<ListNode*> sck;
ListNode* cur = head;
while (cur) {
sck.push(cur);
cur = cur->next;
}
ListNode* pre = sck.top();
ListNode* curr = sck.top();
sck.pop();
while (!sck.empty()) {
curr->next = sck.top();
sck.pop();
curr = curr->next;
}
curr->next = NULL;
return pre;
}
leetcode 输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
p1,指向l2的p2，遍历合并后链表的cur指针,新链表的头指针pre。 ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* p1 = l1;
ListNode* p2 = l2;
ListNode* pre = new ListNode(-1);
ListNode* cur = pre;
while (p1 != NULL && p2 != NULL) {
if (p1->val <= p2->val){
cur->next = p1;
p1 = p1->next;
} else {
cur->next = p2;
p2 = p2->next;
}
cur = cur->next;
}
cur->next = p1 == NULL ? p2 : p1;
return pre->next;
}
||或. ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* p1 = l1, p2 = l2;
ListNode* dummy = new ListNode(-1);
ListNode* cur = dummy;
while (p1 || p2) {
if (p1 == NULL) {
cur->next = p2;
break;
}
if (p2 == NULL) {
cur->next = p1;
break;
}
if (p1->val <= p2->val) {
cur->next = p1;
p1 = p1->next;
} else {
cur->next = p2;
p2 = p2->next;
}
cur = cur->next;
}
return dummy->next;
}
null表示其中一条遍历结束，直接返回另一条链表。 ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1 == NULL) return l2;
if (l2 == NULL) return l1;
if (l1->val <= l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
} else {
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
leetcode输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构) B是A的子结构， 即 A中有出现和B相同的结构和节点值。
例如:
给定的树 A:
3
/ \
4 5
/ \
1 2
给定的树 B：
4
/
1
返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。
null说明还没发现子树，因此返回false，再根据题意空树B == null不属于任何子树(A == NULL && B == NULL)即两个树同时遍历结束 ，说明A和B完全相等，
如果A先结束，说明A属于B，返回false，B先结束说吧B属于A，B是A的子树，返回true
bool isSubStructure(TreeNode* A, TreeNode* B) {
if (A == NULL || B == NULL) return false; // 空树不算任何子树
if (isEqual(A, B)) return true;
return isSubStructure(A->left, B) || isSubStructure(A->right, B);
}
bool isEqual(TreeNode* A, TreeNode* B) {
if (A == NULL && B == NULL) return true; // 都刚好遍历完
if (B == NULL) return true; // B遍历到尾部，A下面还有
if (A == NULL) return false; // B还没有遍历完， A下面就没了
if (A->val != B->val) return false;
return isEqual(A->left, B->left) && isEqual(A->right, B->right);
}
leetcode 请完成一个函数，输入一个二叉树，该函数输出它的镜像。
root->left = 和root->right = 左右子树重新赋值的操作。 TreeNode* mirrorTree(TreeNode* root) {
if (root == NULL) return NULL;
TreeNode* tmp = mirrorTree(root->left);
root->left = mirrorTree(root->right);
root->right = tmp;
return root;
}
swap()代替。 TreeNode* mirrorTree(TreeNode* root) {
if (!root) return NULL;
stack<TreeNode*> sck;
sck.push(root);
TreeNode* cur = NULL;
while (!sck.empty()) {
cur = sck.top();
sck.pop();
// swap(cur->left, cur->right)
TreeNode* tmp = cur->left;
cur->left = cur->right;
cur->right = tmp;
if (cur->right) sck.push(cur->right);
if (cur->left) sck.push(cur->left);
}
return root;
}
leetcode 请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3
null时的处理，都是null也属于对称。 bool isSymmetric(TreeNode* root) {
if(!root) return true;
return isSymmetric(root->left, root->right);
}
bool isSymmetric(TreeNode* left, TreeNode* right) {
if (left == NULL && right == NULL) return true;
if (left == NULL || right == NULL || left->val != right->val) return false;
return isSymmetric(left->left, right->right) && isSymmetric(left->right, right->left) ;
}
leetcode 输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
vector<int> spiralOrder(vector<vector<int>>& matrix) {
if (matrix.empty()) return {};
vector<int> res;
int top = 0, bottom = matrix.size() - 1;
int left = 0, right = matrix[0].size() - 1;
while (left < right && top < bottom) {
for (int i = left; i < right; ++i) res.push_back(matrix[top][i]);
for (int i = top; i < bottom; ++i) res.push_back(matrix[i][right]);
for (int i = right; i > left; --i) res.push_back(matrix[bottom][i]);
for (int i = bottom; i > top; --i) res.push_back(matrix[i][left]);
left++, right--;
top++, bottom--;
}
if (left == right){ // 还剩一列 或者一个
for (int i = top; i <= bottom; ++i) res.push_back(matrix[i][left]);
} else if (top == bottom) { // 还剩一行
for (int i = left; i <= right; ++i) res.push_back(matrix[top][i]);
}
return res;
}
leetcode 定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
stack<int> dataSck;
stack<int> minSck;
MinStack() {}
void push(int x) {
dataSck.push(x);
if (minSck.empty()) {
minSck.push(x);
} else {
if (x <= minSck.top())
minSck.push(x);
}
}
void pop() {
if (dataSck.empty()) return;
if (dataSck.top() == minSck.top()) {
dataSck.pop();
minSck.pop();
} else {
dataSck.pop();
}
}
int top() {
return dataSck.top();
}
int min() {
return minSck.top();
}
leetcode 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
stack<int> sck;
int j = 0;
for (auto num : pushed) {
sck.push(num);
while (!sck.empty() && sck.top() == popped[j]) {
sck.pop();
j++;
}
}
return sck.empty();
}
leetcode从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
vector<int> levelOrder(TreeNode* root) {
if (root == NULL) return {};
queue<TreeNode*> que;
que.push(root);
TreeNode* cur = NULL;
vector<int> res;
while (!que.empty()) {
cur = que.front();
que.pop();
res.push_back(cur->val);
if (cur->left) que.push(cur->left);
if (cur->right) que.push(cur->right);
}
return res;
}
vector<int> levelOrder(TreeNode* root) {
if (root == NULL) return {};
vector<int> res;
list<TreeNode*> List;
List.push_back(root);
TreeNode* cur = NULL;
while (!List.empty()) {
cur = List.front();
List.pop_front();
res.push_back(cur->val);
if (cur->left) List.push_back(cur->left);
if (cur->right) List.push_back(cur->right);
}
return res;
}
leetcode 从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
3
/ \
9 20
/ \
15 7
输出：
[
[3],
[9,20],
[15,7]
]
vector<vector<int>> levelOrder(TreeNode* root) {
if (root == NULL) return {};
vector<vector<int>> res;
queue<TreeNode*> que;
que.push(root);
TreeNode* cur = NULL;
while (!que.empty()) {
vector<int> level;
int len = que.size();
while (len--) {
cur = que.front();
que.pop();
level.push_back(cur->val);
if (cur->left) que.push(cur->left);
if (cur->right) que.push(cur->right);
}
res.push_back(level);
}
return res;
}
vector<vector<int>> res;
vector<vector<int>> levelOrder(TreeNode* root) {
dfs(root, 0);
return res;
}
void dfs(TreeNode* root, int depth) {
if (!root) return;
if(depth == res.size()) res.emplace_back(vector<int>()); // 新建一行
res[depth].emplace_back(root->val);
dfs(root->left, depth + 1);
dfs(root->right, depth + 1);
}
leetcode 请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
3
/ \
9 20
/ \
15 7
输出：
[
[3],
[20,9],
[15,7]
]
vector<vector<int>> levelOrder(TreeNode* root) {
if (root == NULL) return {};
vector<vector<int>> res;
queue<TreeNode*> que;
que.push(root);
TreeNode* cur = NULL;
int layer = 0;
while (!que.empty()) {
vector<int> level;
int len = que.size();
while (len--) {
cur = que.front();
que.pop();
level.push_back(cur->val);
if (cur->left) que.push(cur->left);
if (cur->right) que.push(cur->right);
}
if (layer % 2 != 0)
reverse(level.begin(), level.end());
res.push_back(level);
layer++;
}
return res;
}
vector<list<int>> res;
vector<vector<int>> ans;
vector<vector<int>> levelOrder(TreeNode* root) {
dfs(root, 0);
ans.resize(res.size());
for (int i = 0; i < res.size(); ++i)
for (auto it : res[i]) ans[i].emplace_back(it);
return ans;
}
void dfs(TreeNode* root, int depth) {
if (!root) return;
if (depth == res.size()) res.emplace_back(list<int>());
if (depth & 1) res[depth].emplace_front(root->val);
else res[depth].emplace_back(root->val);
dfs(root->left, depth + 1);
dfs(root->right, depth + 1);
}
leetcode 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同
5
/ \
2 6
/ \
1 3
输入: [1,6,3,2,5]
输出: false
输入: [1,3,2,6,5]
输出: true
left和right,因为要框出左子树和右子树。right所指一定是这个树得根结点root
bool verifyPostorder(vector<int>& postorder) {
int left = 0, right = postorder.size() - 1;
return dfs(postorder, left, right);
}
bool dfs(vector<int>& postorder, int left, int right) {
if (left >= right) return true;
int root = postorder[right];
int mid = left;
while (postorder[mid] < root) mid++;
// mid左为left，< root; mid右为right > root
for (int i = mid; i < right; ++i) {
if (postorder[i] < root) return false;
}
return dfs(postorder, left , mid - 1) && dfs(postorder, mid, right - 1);
}
leetcode 输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
返回:
[
[5,4,11,2],
[5,8,4,5]
]
vector<vector<int>> res;
vector<vector<int>> pathSum(TreeNode* root, int sum) {
vector<int> path;
dfs(root, sum, path);
return res;
}
void dfs (TreeNode* root, int sum, vector<int>& path) {
if (root == NULL) return;
path.push_back(root->val);
sum -= root->val;
if (root->left == NULL && root->right == NULL && sum == 0) res.push_back(path);
dfs(root->left, sum, path);
dfs(root->right, sum, path);
path.pop_back();
return;
}
leetcode 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
Node* copyRandomList(Node* head) {
unordered_map<Node*, int> idx;
unordered_map<int, Node*> addr;
Node* cur = head;
Node* dummy = new Node(-1);
Node* pre = dummy;
int i = 0;
while (cur) {
idx[cur] = i;
Node* node = new Node(cur->val);
addr[i] = node;
pre->next = node;
pre = pre->next;
cur = cur->next;
i++;
}
pre->next = NULL;
cur = head;
Node* curr = dummy->next;
while (cur) {
if (cur->random)
curr->random = addr[idx[cur->random]];
else
curr->random = NULL;
cur = cur->next;
curr = curr->next;
}
return dummy->next;
}
leetcode 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
pre
Node* pre = NULL; //上一个结点
Node* treeToDoublyList(Node* root) {
if (!root) return NULL;
Node* head = new Node(-1);
pre = head;
inorder(root);
pre->right = head->right;
head->right->left = pre;
return head->right;
}
void inorder(Node* root) {
if (!root) return;
inorder(root->left);
pre->right = root;
root->left = pre;
pre = root;
inorder(root->right);
}
leetcode 请实现两个函数，分别用来序列化和反序列化二叉树。
你可以将以下二叉树：
1
/ \
2 3
/ \
4 5
序列化为 "[1,2,3,null,null,4,5]"
str.erase(str.end() - 1);
str.substr(0, str.size() - 1);
str.pop_back();
reverse()反转字符串。效率很低。 string serialize(TreeNode* root) {
if (!root) return "";
queue<TreeNode*> que;
que.push(root);
TreeNode* cur = NULL;
string res;
while (!que.empty()) {
cur = que.front();
que.pop();
if (cur) {
res += toString(cur->val);
res += ',';
que.push(cur->left);
que.push(cur->right);
} else {
res += "null,";
}
}
//res.erase(res.end() - 1); // 迭代器/三种用法
//res.substr(0, res.size() - 1); // 子串
res.pop_back();
//cout << "[" + res + "]"<<endl;
return "[" + res + "]";
}
string toString(int val) {
string res = "";
if (val < 0) { // val < 10
res += '-';
res += abs(val) + '0';
} else { // val >= 0
while (val) {
res += val % 10 + '0';
val /= 10;
}
reverse(res.begin(), res.end());
}
return res;
}
TreeNode* deserialize(string data) {
if (data.size() == 0) return NULL;
vector<int> data_int;
int left = 1;
int right = 1;
while (left < data.size()) {
while (data[right] != ',' && data[right] != ']') right++;
int val = toInt(data, left, right - 1);
data_int.push_back(val);
left = right + 1;
right++;
}
TreeNode* root = new TreeNode(data_int[0]);
queue<TreeNode*> que;
que.push(root);
double start = 0; // 子结点起始坐标
double end = 0;
double n = 1; // 层数
TreeNode* cur = NULL;
while (!que.empty()) {
double cnt = pow(2, n++);
start = cnt - 1;
end = start + cnt - 1;
while (start <= end) {
if (start >= data_int.size()) break;
cur = que.front();
que.pop();
TreeNode* leftNode = NULL;
TreeNode* rightNode = NULL;
if (data_int[start] != INT_MIN)
leftNode = new TreeNode(data_int[start]);
if (data_int[start + 1] != INT_MIN)
rightNode = new TreeNode(data_int[start + 1]);
if (leftNode) que.push(leftNode);
if (rightNode) que.push(rightNode);
cur->right = rightNode;
cur->left = leftNode;
start += 2;
}
}
return root;
}
int toInt(string str, int left, int right) {
if (str[left] == 'n') return INT_MIN;
int res = 0;
bool isNeg = false;
if (str[left] == '-') left++, isNeg = true;
while (left <= right) {
res = res * 10 + str[left] - '0';
left++;
}
return isNeg ? -res : res;
}
leetcode输入一个字符串，打印出该字符串中字符的所有排列。 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]
vector<string> permutation(string s) {
vector<string> res;
string path;
vector<bool> isVis(s.size(), false);
dfs(s, path, isVis, res);
//unordered_set<string> set(res.begin(), res.end()); //使用集合去重。
//res.assign(set.begin(), set.end());
sort(res.begin(), res.end()); // 排序去重
auto end = unique(res.begin(),res.end()); // 返回最后一位
res.erase(end, res.end()); // 剪掉
return res;
}
void dfs (string s, string& path, vector<bool>& isVis, vector<string>& res) {
if (path.size() == s.size()) {
res.push_back(path);
return;
}
// 在所有得选择列表中继续选择
for (int i = 0; i < s.size(); ++i) {
if (isVis[i]) continue;
isVis[i] = true;
path += s[i];
dfs(s, path, isVis, res);
isVis[i] = false;
path.pop_back();
}
}
vector<bool> isVis;
string s;
vector<string> res;
vector<string> permutation(string s) {
this->s = s;
isVis.resize(s.size(), false);
string path;
for (int i = 0; i < s.size(); ++i) {
dfs(i, path);
}
unordered_set set(res.begin(), res.end());
res.assign(set.begin(), set.end());
return res;
}
void dfs(int root, string& path) {
if (isVis[root]) return;
isVis[root] = true;
path += s[root];
if (path.size() == s.size()) {
isVis[root] = false;
res.push_back(path);
return;
}
for (int i = 0; i < s.size(); ++i) {
dfs(i, path);
}
isVis[root] = false;
path.pop_back();
}
leetcode数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
int majorityElement(vector<int>& nums) {
int len = nums.size();
unordered_map<int, int> cnt;
for (auto& num : nums) {
cnt[num]++;
if (cnt[num] > len / 2) return num;
}
return -1;
}
int majorityElement(vector<int>& nums) {
sort(nums.begin(), nums.end());
return nums[nums.size() / 2];
}
last值记录上衣结点的数值，用于比较，vato票数一旦为0就重新更新last值。，由于 int majorityElement(vector<int>& nums) {
int last = 0, vote = 0; // 记录投票数
for (int i = 0; i < nums.size(); ++i) {
if (vote == 0) { // 正负票正好抵消，
last = nums[i];
vote++;
} else { // 当前票与上一票进行比较，相同就++，不同就抵消了
last == nums[i] ? vote++ : vote--;
}
}
return last; // 最后就剩多数票了
}
leetcode输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
vector<int> getLeastNumbers(vector<int>& arr, int k) {
if (k == 0 || arr.size() == 0) return {};
priority_queue<int, vector<int>, less<int>> que;
vector<int> res;
for (auto& num : arr) {
if (que.size() == k) {
if (num <= que.top())
que.pop();
else
continue;
}
que.push(num);
}
while (k--) {
res.push_back(que.top());
que.pop();
}
return res;
}
vector<int> getLeastNumbers(vector<int>& arr, int k) {
int cnt[10001];
memset(cnt, 0, sizeof(int) * 10001);
for (auto num : arr) {
cnt[num]++;
}
vector<int> res;
for (int i = 0; i < 10001; ++i) {
while (cnt[i]-- && res.size() < k)
res.push_back(i);
if (res.size() == k) break;
}
return res;
}
{leetcode](https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/)输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。 要求时间复杂度为O(n)。
int maxSubArray(vector<int>& nums) {
int len = nums.size();
vector<int> dp(len);
int maxSum = nums[0];
for (int i = 0; i < len; ++i) {
if (i == 0) dp[0] = nums[0];
else dp[i] = max(dp[i - 1] + nums[i], nums[i]);
maxSum = max(maxSum, dp[i]);
}
return maxSum;
}
cur += max(pre, 0);来代替if else操作。 int maxSubArray(vector<int>& nums) {
int maxSum = nums[0];
int pre = nums[0];
int cur = 0;
for (int i = 1; i < nums.size(); i++) {
cur = nums[i];
cur += max(pre, 0);
pre = cur;
maxSum = max(maxSum, cur);
}
return maxSum;
}
int maxSubArray(vector<int>& nums) {
int n = nums.size();
int cur = 0;
int pre = nums[0];
int MAX = nums[0];
for (int i = 1; i < n; ++i) {
cur = nums[i];
cur = max(cur + pre, cur);
MAX = max(MAX, cur);
pre = cur;
}
return MAX;
}
int maxSubArray(vector<int>& nums) {
int left = 0, right = 0;
int len = nums.size();
int sum = 0;
int MAX = INT_MIN;
while (right < len) {
while (right < len && sum >= 0) {
sum += nums[right];
MAX = max(sum, MAX);
right++;
}
sum -= nums[left];
left++;
}
return MAX;
}
leetcode 输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。 例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。
int countDigitOne(int n) {
int res = 0;
for (int i = 1; i <= n; ++i)
res += count(i);
return res;
}
int count(int num) {
int cnt = 0;
while (num) {
cnt += (num % 10 == 1);
num /= 10;
}
return cnt;
}
digit有关0~99,十位会出现10次1，而0~99出现的次数又是23次,因此1出现的总次数为：23 * 10 = 230，公式:high * dight
10，11，12，13，14 5 个，即 23 * 10 + 4 + 1 公式:high * digit + low + 1
10,12,13,14,15,16,17,18,19即23 * 10 + 10 公式：high + digit + dight
int countDigitOne(int n) {
int high = n / 10, cur = n % 10, low = 0;
long digit = 1;
int cnt = 0;
while (high || cur) { // 只有同时为0时才结束
if (cur == 0) cnt += high * digit;
else if (cur == 1) cnt += high * digit + low + 1;
else cnt += (high + 1) * digit;
low += cur * digit;
cur = high % 10;
high /= 10;
digit *= 10;
}
return cnt;
}
leetcode数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。 请写一个函数，求任意第n位对应的数字。
int findNthDigit(int n) {
long digit = 1, start = 1, cnt = 9;
while (n > cnt) {
n -= cnt;
digit += 1;
start *= 10;
cnt = digit * start * 9;
}
int num = start + (n - 1) / digit; // 括号不能省 n-1 是因为从0开始不是从1开始，减去0
return to_string(num)[(n - 1) % digit] - '0';
}
leetcode输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
[](type parm, type parm){return ;} 使用lamada表达式建立得匿名函数，作为sort函数得比较cmp函数 string minNumber(vector<int>& nums) {
vector<string> res;
for (auto it : nums) res.push_back(to_string(it));
sort(res.begin(), res.end(), [](string str1, string str2){return str1 + str2 < str2 + str1;});
string ans;
for (auto it : res) ans += it;
return ans;
}
join()：用一个字符去拼接一个字符列表append()：列表得追加functools.cmp_to_key：将老式得cmp函数转换为关键词函数，（python3取消了cmp函数使用关键字函数）class Solution:
def minNumber(self, nums: List[int]) -> str:
def sort_rule(x, y):
a, b = x + y, y + x
if a > b: return 1
elif a < b: return -1
else: return 0
strs = []
for num in nums:
strs.append(str(num))
strs.sort(key = functools.cmp_to_key(sort_rule))
return ''.join(strs)
leetcode给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
// 判断与前一个数组能否形成一个字母
bool helper(int num1, int num2) {
if (num1 == 0)return false;
return num1 * 10 + num2 >= 0 && num1 * 10 + num2 <= 25;
}
// 将一个数，按位填入数组中
vector<int> toVector(int num) {
vector<int> res;
if (num == 0) return {0};
while (num) {
res.push_back(num % 10);
num /= 10;
}
reverse(res.begin(), res.end());
return res;
}
int translateNum(int num) {
if (num < 10) return 1;
vector<int> nums = toVector(num);
vector<int> dp(nums.size());
dp[0] = 1;
dp[1] = helper(nums[0], nums[1]) ? 2 : 1;
for (int i = 2; i < nums.size(); ++i)
dp[i] = helper(nums[i - 1], nums[i]) ? dp[i - 1] + dp[i - 2] : dp[i - 1];
return dp.back();
}
bool help(string num, int i) {
if (num[i - 1] == '1' || (num[i - 1] == '2' && num[i] < '6')) return true;
return false;
}
int translateNum(int num) {
if (num < 10) return 1;
string n = to_string(num);
vector<int> dp(n.size());
dp[0] = 1;
dp[1] = help(n, 1) ? 2 : 1;
for (int i = 2; i < n.size(); ++i) {
dp[i] = help(n, i) ? dp[i - 1] + dp[i - 2] : dp[i - 1];
}
return dp.back();
}
leetcode在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
dp[i[j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
int maxValue(vector<vector<int>>& grid) {
int row = grid.size();
int col = grid[0].size();
vector<vector<int>> dp(row, vector<int>(col, 0));
dp[0][0] = grid[0][0];
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
if (i == 0 && j == 0) continue;
if (i == 0) dp[0][j] = dp[0][j - 1] + grid[0][j];
else if (j == 0) dp[i][0] = dp[i - 1][0] + grid[i][0];
else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[row-1][col-1];
}
leetcode请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
int lengthOfLongestSubstring(string s) {
int left = 0, right = 0;
int n = s.size();
map<char, int> cnt;
int res = 0;
while (right < n) {
while (cnt[s[right]] == 0 && right < n) {
cnt[s[right]]++;
res = max(res, right - left + 1);
right++;
}
cnt[s[left]]--;
left++;
}
return res;
}
emplace(), erase(), find()
int lengthOfLongestSubstring(string s) {
int left = 0, right = 0;
int longest = 0;
int n = s.size();
unordered_set<char> ch;
while (right < n) {
while (ch.find(s[right]) == ch.end() && right < n ) {
longest = max(longest, right - left + 1);
ch.emplace(s[right]);
right++;
}
ch.erase(s[left]); // 此处容易写成right 必须在left++前
left++;
}
return longest;
}
leetcode我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
丑数序列 * 2 丑数序列 * 3 丑数序列 * 5合并去重后得到的。 int nthUglyNumber(int n) {
vector<int> ugly(n, 0);
int p1 = 0, p2 = 0, p3 = 0;
ugly[0] = 1;
for (int i = 1; i < n; ++i) {
int minVal = min(ugly[p1] * 2, min(ugly[p2] * 3, ugly[p3] * 5));
if (minVal == ugly[p1] * 2) p1++;
if (minVal == ugly[p2] * 3) p2++;
if (minVal == ugly[p3] * 5) p3++;
ugly[i] = minVal;
}
return ugly.back();
}
leetcode 在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
char firstUniqChar(string s) {
unordered_map<char,int> cnt;
for (char ch : s)
cnt[ch]++;
for (auto ch : s)
if (cnt[ch] == 1) return ch;
return ' ';
}
leetcode输入两个链表，找出它们的第一个公共节点。
太浪漫了 两个结点不断的去对方的轨迹中寻找对方的身影，只要二人有交集，就终会相遇❤
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode* p1 = headA;
ListNode* p2 = headB;
while (p1 != p2) {
p1 = p1 == NULL ? headB : p1->next;
p2 = p2 == NULL ? headA : p2->next;
}
return p1 == NULL ? NULL: p1;
}
leetcode统计一个数字在排序数组中出现的次数。
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) right = mid;
else if (nums[mid] < target) left = mid + 1;
else right = mid;
}
int cnt = 0;
while (left < nums.size() && nums[left++] == target)
cnt++;
return cnt;
}
leetcode一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
int missingNumber(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] != mid) right = mid;
else left = mid + 1;
}
return left == nums.size() - 1 && nums[left] == left ? left + 1 : left;
}
leetcode给定一棵二叉搜索树，请找出其中第k大的节点。
输入: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
2
输出: 4
int res = 0;
int cnt = 0;
int kthLargest(TreeNode* root, int k) {
dfs(root, k);
return res;
}
void dfs(TreeNode* root, int& k) {
if (!root) return;
dfs(root->right, k);
if (--k == 0) {
res = root->val;
return ;
}
dfs(root->left, k);
}
vector<int> res;
int kthLargest(TreeNode* root, int k) {
dfs(root);
return res[res.size() - k];
}
void dfs(TreeNode* root) {
if (!root) return;
dfs(root->left);
res.push_back(root->val);
dfs(root->right);
}
leetcode输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
unordered_map<TreeNode*, int> height;
int maxDepth(TreeNode* root) {
if (!root) {
height[root] = 0;
return 0;
}
int left = maxDepth(root->left);
int right = maxDepth(root->right);
height[root] = max(height[root->left], height[root->right]) + 1;
return height[root];
}
unordered_map<TreeNode*, int> height;
int maxDepth(TreeNode* root) {
if (height.find(root) != height.end()) {
return height[root];
}
if (!root) {
height[root] = 0;
return 0;
}
int left = maxDepth(root->left);
int right = maxDepth(root->right);
height[root] = max(left, right)+ 1;
return height[root];
}
leetcode输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
unordered_map<TreeNode*, int> height;
bool isBalanced(TreeNode* root) {
if (!root) {
height[root] = 0;
return true;
}
if (!isBalanced(root->left) || !isBalanced(root->right)) return false;
if (abs(height[root->left] - height[root->right]) > 1) return false;
height[root] = max(height[root->left], height[root->right]) + 1;
return true;
}
leetcode一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
int mask = A & (-A) 可以得A二进制最右边位的1，用这个数mask来做为掩码。 vector<int> singleNumbers(vector<int>& nums) {
int sum = 0;
for (auto num: nums)
sum ^= num;
int res1 = 0, res2 = 0;
int mask = sum & (-sum);
for (auto num : nums) {
if (mask & num)
res1 ^= num;
else
res2 ^= num;
}
return {res1, res2};
}
leetcode 在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
cnt[32]
int singleNumber(vector<int>& nums) {
int cnt[32];
memset(cnt, 0, sizeof(int) * 32);
for (auto num : nums) {
unsigned int mask = 1; // 每个数都要重新复位一下, 不用无符号会报错
for (int i = 31; i >= 0; --i) {
if (num & mask) cnt[i]++;
mask <<= 1;
}
}
int res = 0;
for (int i = 0; i < 32; ++i) {
res <<= 1; // 必须先左移，否则结果最后会多移一位，变成2倍的值
res += cnt[i] % 3;
}
return res;
}
int singleNumber(vector<int>& nums) {
int once = 0, twice = 0;
for (auto num : nums) {
once = once ^ num & ~twice;
twice = twice ^ num & ~once;
}
return once;
}
leetcode 输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
vector<int> twoSum(vector<int>& nums, int target) {
for (auto num : nums) {
int res = qsort(nums, target - num);
if (res > 0) return {num , res};
}
return {};
}
int qsort(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return target;
else if (nums[mid] > target) right = mid;
else left = mid + 1;
}
return -1;
}
vector<int> twoSum(vector<int>& nums, int target) {
int left = 0, right =nums.size() - 1;
while (left < right) {
if (nums[left] + nums[right] > target) right--;
else if (nums[left] + nums[right] == target) return {nums[left],nums[right]};
else left++;
}
return {};
}
leetcode
输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
target,如果等于target就存入结果中，如果大于就移动左指针。 vector<vector<int>> findContinuousSequence(int target) {
int left = 1, right = 1;
vector<vector<int>> res;
while (right < target) {
while ((left + right) * (right - left + 1) / 2 < target) {
right++;
}
if ((left + right) * (right - left + 1) / 2 == target) {
vector<int> ret;
for (int i = left; i <= right; ++i) {
ret.push_back(i);
}
res.push_back(ret);
}
left++;
}
return res;
}
leetcode输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. "，则输出"student. a am I"。
输入: "the sky is blue"
输出: "blue is sky the"
string reverseWords(string s) {
stack<string> sck;
for (int i = 0; i < s.size(); ++i) {
string str;
while (i < s.size() && !isblank(s[i])) {
str += s[i];
++i;
}
if (!str.empty()) sck.push(str); // 防止空串入栈
}
string res = "";
while (!sck.empty()) {
res = res + sck.top() + ' ';
sck.pop();
}
if(!res.empty()) res.pop_back(); // 防止弹出空字符串
return res;
}
string reverseWords(string s) {
if (s.empty()) return "";
vector<string> res;
int i = 0;
while (i < s.size()) {
string word;
while (i < s.size() && s[i] != ' ')
word += s[i++];
if (!word.empty()) res.push_back(word);
i++;
}
if (res.empty()) return "";
reverse(res.begin(), res.end());
string ans;
for (auto it : res) ans += it + ' ';
ans.pop_back();
return ans;
}
leetcode字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。
输入: s = "abcdefg", k = 2
输出: "cdefgab"
len取模，形成从头循环。 string reverseLeftWords(string s, int n) {
int len = s.size();
string res = "";
for (int i = 0; i < len; ++i) {
res += s[(n + i) % len];
}
return res;
}
string reverseLeftWords(string s, int n) {
string res;
int len = s.size();
while (res.size() != s.size()) {
res += s[n % len];
n++;
}
return res;
}
substr(int begin, int end) 注意end指最后一位字母的后一位索引。 string reverseLeftWords(string s, int n) {
return s.substr(n, s.size()) + s.substr(0, n);
}
leetcode 给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
1 - k < left < n - k + 1 和 0 < right < n 两个指针同时运动。 vector<int> maxSlidingWindow(vector<int>& nums, int k) {
if (nums.size() == 0 || k == 0) return {};
deque<int> que;
vector<int> res;
for (int left = 1 - k, right = 0; right < nums.size(); ++left, ++right) {
// 删除得元素等于队首元素时，弹出队首 因为left - 1为弹出的元素，所以left指针不能 = 0.
if (left > 0 && que.front() == nums[left - 1]) que.pop_front();
// 保持队列单调递减
while (!que.empty() && nums[right] > que.back()) que.pop_back();
que.push_back(nums[right]);
if (left >= 0) res.push_back(que.front()); // left = 0以后才形成窗口，才有最大值出现。
}
return res;
}
leetcode 请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。 若队列为空，pop_front 和 max_value 需要返回 -1
class MaxQueue {
public:
queue<int> data;
deque<int> maxque;
MaxQueue() {}
int max_value() {
if(!maxque.empty()) return maxque.front();
return -1;
}
void push_back(int value) {
while (!maxque.empty() && value > maxque.back()) maxque.pop_back();
data.push(value);
maxque.push_back(value);
}
int pop_front() {
if (data.empty()) return -1;
int res = data.front();
if (res == maxque.front()) maxque.pop_front();
data.pop();
return res;
}
};
leetcode 把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。 你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。
输入: 2
输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]
dp[n][j]= dp[n-1][j-1] + dp[n-1][j-2] + dp[n-1][j-3] + dp[n-1][j-4] + dp[n-1][j-5] + dp[n-1][j-6]
vector<double> twoSum(int n) {
vector<vector<int>> dp(n + 1, vector<int>(6 * n + 1, 0));
for (int i = 1; i <= 6; ++i)
dp[1][i] = 1;
for (int i = 2; i <= n; ++i) { // i: 投掷i个骰子
for (int j = i; j <= 6 * i ; ++j) { // j: 点数和的范围
for (int k = 1; k <= 6; ++k) { // k: 1~6点数
if (j > k) dp[i][j] += dp[i - 1][j - k];
}
}
}
int total = pow(6, n);
vector<double> res;
for (int j = n; j <= 6 * n; ++j) {
res.push_back(dp[n][j] * 1.0 / total);
}
return res;
}
leetcode 从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。
输入: [0,0,1,2,5]
输出: True
bool isStraight(vector<int>& nums) {
sort(nums.begin(), nums.end());
int cnt = 0;
int off = 0;
for (int i = 0; i < nums.size() - 1; ++i) {
if (nums[i] == 0) {
cnt++;
continue;
}
off = abs(nums[i] - nums[i + 1]);
if (off == 1) continue;
if (off == 0 || off - 1 > cnt ) return false;
}
return true;
}
bool isStraight(vector<int>& nums) {
unordered_set<int> set;
int MIN = 14, MAX = 0;
for (auto num : nums) {
if (num == 0) continue;
MAX = max(MAX, num);
MIN = min(MIN, num);
if (set.find(num) != set.end()) return false;
set.insert(num);
}
return MAX - MIN < 5;
}
leetcode 0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。 例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
输入: n = 5, m = 3
输出: 3
n - 1次 int lastRemaining(int n, int m) {
list<int> myList;
for (int i = 0; i < n; ++i)
myList.push_back(i);
n--;
auto it = myList.begin();
while (n--) {
for (int i = 0; i < m - 1; ++i) {
it++;
if (it == myList.end()) it = myList.begin();
}
it = myList.erase(it);
if (it == myList.end()) it = myList.begin();
}
return myList.front();
}
leetcode假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
dp[i]代表前i天能获得的最大利润，结果返回dp[n-1]
dp[i] 的值与前一天的最大利润dp[i-1]有关，如果前一天的利润比当天卖掉股票的最大利润还要大，那就继续用前一天的利润。 int maxProfit(vector<int>& prices) {
int n = prices.size();
if (n == 0) return 0;
vector<int> dp(n);
int minVal = prices[0];
for (int i = 1; i < n; ++i) {
minVal = min(minVal, prices[i]);
dp[i] = max(dp[i -1], prices[i] - minVal);
}
return dp.back();
}
leetcode 求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
return (int)(pow(n, 2) + n) >> 1;
for (int i = 0; i <= n; ++i)
res += i;
&&的短路效果来代替跳出操作。也因此&& ||这种运算符无法重载n = 1的时候，对于&&运算已经判断为false，就不会执行后面的语句，因此直接return n; 此时n=1
int sumNums(int n) {
n > 1 && (n += sumNums(n - 1));
return n;
}
leetcode
写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。
不考虑进位时：
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 0
正好是异或运算
只考虑进位c
00 + 00 = 00 c = 0
01 + 00 = 01 c = 0
00 + 01 = 01 c = 0
01 + 01 = 10 c = 1
正好是&运算，但是需要左移一位
s + c , s代表a ^ b,c代表a & b << 1
s + c 通过继续循环的方式相加，把s赋值给a,c赋值给b，继续循环计算a + b,直到第二个加数为0结束。<< 的优先级高于 &记得加括号。 int add(int a, int b) {
while (b != 0) {
int c = (unsigned int)(a & b) << 1;
a ^= b;
b = c;
}
return a;
}
leetcode 给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B 中的元素 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。
输入: [1,2,3,4,5]
输出: [120,60,40,30,24]
leftDP[i] = leftDP[i - 1] * a[i - 1]和rightDP[i] = rightDP[i + 1] * a[i + 1]
vector<int> constructArr(vector<int>& a) {
int n = a.size();
if (n == 0) return {};
vector<int> leftDP(n, 0);
vector<int> rightDP(n, 0);
leftDP[0] = 1;
for (int i = 1; i < n; ++i) {
leftDP[i] = leftDP[i - 1] * a[i - 1];
}
rightDP[n - 1] = 1;
for (int i = n - 2; i >= 0; --i) {
rightDP[i] = rightDP[i + 1] * a[i + 1];
}
vector<int> res(n, 0);
for (int i = 0; i < n; ++i) {
res[i] = leftDP[i] * rightDP[i];
}
return res;
}
leetcode 写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。
当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0。
说明：
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。
输入: "42"
输出: 42
输入: " -42"
输出: -42
解释: 第一个非空白字符为 '-', 它是一个负号。
我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42
输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。
输入: "words and 987"
输出: 0
解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
因此无法执行有效的转换。
###示例5:
输入: "-91283472332"
输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。
因此返回 INT_MIN (−231) 。
+-正负号,res * 10之前先判断当前res是否已经大于INT_MAX / 10,或者当前res已经等于INT_MAX / 10,但是最右边新加入的位大于7说明这个字符已经超过了32位整数的最大值，需要直接输出INT_MAX。 int strToInt(string str) {
if(str.empty()) return 0;
int i = 0;
// 跳过空格
while(str[i] == ' ') i++;
// 判断符号
bool isNeg = false;
if (str[i] == '-') {
isNeg = true;
i++;
} else if(str[i] == '+')
i++;
// 转换数字
int res = 0;
while(i < str.size()) {
if (str[i] >= '0' && str[i] <= '9') {
if (res > INT_MAX / 10 || (res == INT_MAX / 10 && str[i] > '7'))
return isNeg == true ? INT_MIN : INT_MAX; // 数字边界处理
res = res * 10 + (str[i] - '0'); // 括号不能省，因为可能会溢出
} else return isNeg == true ? -res : res; // 不是数字直接返回前面转换得数字结果
i++;
}
return isNeg == true ? -res : res;
}
....前面都一样
long res = 0;
for (; i < str.size(); ++i) {
if (res > INT_MAX || res < INT_MIN) return isNeg ? INT_MIN : INT_MAX;
if (str[i] >= '0' && str[i] <= '9') {
res = res * 10 + (str[i] - '0');
continue;
}
return isNeg ? -res : res;
}
if (res > INT_MAX || res < INT_MIN) return isNeg ? INT_MIN : INT_MAX;
return isNeg ? -res : res;
}
leetcode
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == NULL) return NULL;
if (root->val > q->val && root->val > p->val) return lowestCommonAncestor(root->left, p, q);
if (root->val < p->val && root->val < q->val) return lowestCommonAncestor(root->right, p, q);
return root;
}
leetcode
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
null就说明这棵树下面发现了qp节点。null说明另一棵树发现了qp节点，就继续往上返回它，告诉上游此也树发现了pq节点。 TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == NULL) return NULL;
if (root == p || root == q) return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if (left && right) return root;
if (left) return left;
if (right) return right;
return NULL;
}
vector<vector<TreeNode*>> path;
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
vector<TreeNode*> path1;
vector<TreeNode*> path2;
getPath(root, p, path1);
getPath(root, q, path2);
int n = min(path[0].size(), path[1].size()); // 按最短的路径长度比较
TreeNode* res = NULL;
for (int i = 0; i < n; ++i) {
if (path[0][i] == path[1][i])
res = path[0][i];
}
return res;
}
void getPath(TreeNode* root, TreeNode* tar, vector<TreeNode*>& path) {
if (!root) return;
path.push_back(root);
if (root == tar) {
this->path.push_back(path);
return;
}
getPath(root->left, tar, path);
getPath(root->right, tar, path);
path.pop_back();
}
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。