- Bitwise AND of Numbers Range
#include <bits/stdc++.h>
using namespace std;
/**
* 原题链接
* https://leetcode.com/problems/bitwise-and-of-numbers-range/description/
*/
class Solution {
public:
int rangeBitwiseAnd(int m, int n) {
int res = 1;
while (m != n) {
m >>= 1;
n >>= 1;
res <<= 1;
}
return m * res;
}
};
- Happy Number
#include <bits/stdc++.h>
using namespace std;
/**
* 原题链接
* https://leetcode.com/problems/happy-number/description/
*/
class Solution {
public:
bool isHappy(int n) {
int walker = n, runner = n;
do {
walker = digitSquareSum(walker);
runner = digitSquareSum(runner);
runner = digitSquareSum(runner);
} while (walker != runner);
}
int digitSquareSum(int n) {
int sum = 0;
while (n) {
int temp = n % 10;
sum += temp * temp;
n /= 10;
}
return sum;
}
};
- Remove Linked List Elements
Remove all elements from a linked list of integers that have value val.
#include <bits/stdc++.h>
using namespace std;
/**
* 原题链接
* https://leetcode.com/problems/remove-linked-list-elements/description/
*/
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode *removeElements(ListNode *head, int val) {
ListNode *result = new ListNode(-1);
result->next = head;
ListNode *pre = result, *cur = head;
while (cur) {
while (cur && cur->val == val) {
cur = cur->next;
}
pre->next = cur;
pre = cur;
cur = cur ? cur->next : cur;
}
return result->next;
}
};
class Solution_0 {
public:
ListNode *removeElements(ListNode *head, int val) {
if (head == NULL) {
return head;
}
if (head->val == val) {
return removeElements(head->next, val);
}
head->next = removeElements(head->next, val);
return head;
}
};
- Count Primes
#include <bits/stdc++.h>
using namespace std;
/**
* 原题链接
* https://leetcode.com/problems/count-primes/discuss/57588/My-simple-Java-solution
*/
class Solution {
public:
int countPrimes(int n) {
vector<bool> prime(n, true);
prime[0] = false, prime[1] = false;
for (int i = 0; i < sqrt(n); ++i) {
if (prime[i]) {
for (int j = i; i * j < n; j++) {
prime[i * j] = false;
}
}
}
return count(prime.begin(), prime.end(), true);
}
};
- Isomorphic Strings
Given two strings s and t, determine if they are isomorphic.Two strings are isomorphic if the characters in s can be replaced to get t.All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.
#include <bits/stdc++.h>
using namespace std;
/**
* 原题链接
* https://leetcode.com/problems/isomorphic-strings/description/
*/
class Solution {
public:
bool isIsomorphic(string s, string t) {
int m = s.size();
vector<int> dir1(256, 0), dir2(256, 0);
for (int i = 0; i < m; i++) {
if (dir1[s[i]] != dir2[t[i]]) {
return false;
}
dir1[s[i]] = i + 1;
dir2[t[i]] = i + 1;
}
return true;
}
};
- Reverse Linked List [面试必备]
#include <bits/stdc++.h>
using namespace std;
/**
* 原题链接
* https://leetcode.com/problems/reverse-linked-list/description/
*/
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode *reverseList(ListNode *head) {
if (head == NULL || head->next == NULL) {
return head;
}
ListNode *pre = NULL, *cur = head;
while (cur) {
auto temp = cur->next;
cur->next = pre;
pre = cur;
cur = temp;
}
return pre;
}
};
- Course Schedule
#include <bits/stdc++.h>
using namespace std;
/**
* 原题链接
* https://leetcode.com/problems/course-schedule/description/
*/
class Solution {
public:
bool canFinish(int numCourses, vector<pair<int, int>> &prerequisites) {
int counter = 0;
queue<int> nodeQueue;
vector<set<int>> graphPaths = createGraph(prerequisites, numCourses);
vector<int> degrees = compute_indegree(graphPaths);
for (int i = 0; i < degrees.size(); i++) { //把度数为0的点加入队列
if (!degrees[i]) {
nodeQueue.push(i);
}
}
while (!nodeQueue.empty()) {
int course = nodeQueue.front();
nodeQueue.pop();
counter++;
for (auto element : graphPaths[course]) {
if (--degrees[element] == 0) {
nodeQueue.push(element);
}
}
}
return counter == numCourses;
}
vector<set<int>> createGraph(vector<pair<int, int>> &prerequisites,
int numCourses) {
vector<set<int>> graphPaths(numCourses);
for (auto element : prerequisites) {
graphPaths[element.second].insert(element.first);
}
return graphPaths;
}
vector<int> compute_indegree(vector<set<int>> &graphPaths) {
vector<int> degrees(graphPaths.size(), 0);
for (auto neighbors : graphPaths) {
for (auto neighbor : neighbors) {
degrees[neighbor]++;
}
}
return degrees;
}
};
- Implement Trie (Prefix Tree)
#include <bits/stdc++.h>
using namespace std;
/**
* 原题链接
* https://leetcode.com/problems/implement-trie-prefix-tree/description/
*/
class Trie {
class TrieNode {
public:
TrieNode *next[26] = {NULL};
bool is_word;
TrieNode(bool b = false) { is_word = b; }
};
public:
TrieNode *root;
Trie() { root = new TrieNode(); }
void insert(string word) {
TrieNode *curr = root;
for (auto c : word) {
if (curr->next[c - 'a'] == NULL) {
curr->next[c - 'a'] = new TrieNode();
}
curr = curr->next[c - 'a'];
}
curr->is_word = true;
}
bool search(string word) {
TrieNode *p = find(word);
return p != NULL && p->is_word;
}
bool startsWith(string prefix) {
TrieNode *p = find(prefix);
return p != NULL;
}
private:
TrieNode *find(string word) {
TrieNode *curr = root;
for (int i = 0; i < word.size() && curr != NULL; i++)
curr = curr->next[word[i] - 'a'];
return curr;
}
};
- Minimum Size Subarray Sum
#include <bits/stdc++.h>
using namespace std;
/**
* 题目链接
* https://leetcode.com/problems/minimum-size-subarray-sum/description/
*/
class Solution {
public:
int minSubArrayLen(int s, vector<int> &nums) {
int m = nums.size(), left = 0, right = 0;
int sum = 0, res = -1;
while (right < m) {
sum += nums[right];
while (sum >= s) {
res = res == -1 ? right - left + 1 : min(res, right - left + 1);
sum -= nums[left];
left++;
}
right++;
}
return res == -1 ? 0 : res;
}
};
- Course Schedule II
#include <bits/stdc++.h>
using namespace std;
/**
* 原题链接
* https://leetcode.com/problems/course-schedule-ii/description/
*/
class Solution {
public:
vector<int> findOrder(int numCourses,
vector<pair<int, int>> &prerequisites) {
int counter = 0;
vector<int> res;
queue<int> nodeQueue;
vector<set<int>> graphPaths = createGraph(prerequisites, numCourses);
vector<int> degrees = compute_indegree(graphPaths);
for (int i = 0; i < degrees.size(); i++) { //把度数为0的点加入队列
if (!degrees[i]) {
nodeQueue.push(i);
}
}
while (!nodeQueue.empty()) {
int course = nodeQueue.front();
res.push_back(course);
nodeQueue.pop();
counter++;
for (auto element : graphPaths[course]) {
if (--degrees[element] == 0) {
nodeQueue.push(element);
}
}
}
return counter == numCourses ? res : vector<int>();
}
vector<set<int>> createGraph(vector<pair<int, int>> &prerequisites,
int numCourses) {
vector<set<int>> graphPaths(numCourses);
for (auto element : prerequisites) {
graphPaths[element.second].insert(element.first);
}
return graphPaths;
}
vector<int> compute_indegree(vector<set<int>> &graphPaths) {
vector<int> degrees(graphPaths.size(), 0);
for (auto neighbors : graphPaths) {
for (auto neighbor : neighbors) {
degrees[neighbor]++;
}
}
return degrees;
}
};
- Add and Search Word - Data structure design
Design a data structure that supports the following two operations:
void addWord(word) bool search(word)
search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.
待定
- Word Search II
待定
- House Robber II
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
#include <bits/stdc++.h>
using namespace std;
/**
* 原题链接
* https://leetcode.com/problems/house-robber-ii/description/
*/
class Solution {
public:
int rob(vector<int> &nums) {
int m = nums.size();
if (m <= 1) {
return m == 0 ? 0 : nums[0];
}
return max(rob(nums, 0, m - 2), rob(nums, 1, m - 1));
}
int rob(vector<int> &nums, int left, int right) {
int pre = 0, cur = 0;
for (int i = left; i <= right; i++) {
int temp = cur;
cur = max(cur, pre + nums[i]);
pre = temp;
}
return cur;
}
};
Shortest Palindrome
Given a string s, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.
···
待定
···
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
#include <bits/stdc++.h>
using namespace std;
/**
* 原题链接
* https://leetcode.com/problems/kth-largest-element-in-an-array/description/
*/
class Solution {
public:
int partion(vector<int> &nums, int left, int right) {
int low = left, pivot = nums[right];
while (left < right) {
if (nums[left] < nums[right]) {
swap(nums[left], nums[low]);
low++;
}
left++;
}
swap(nums[low], nums[right]);
return low;
}
int findKthLargest(vector<int> &nums, int k) {
int m = nums.size();
k = m - k;
return helper(nums, 0, m - 1, k);
}
int helper(vector<int> &nums, int left, int right, int k) {
int pos = partion(nums, left, right);
if (pos == k) {
return nums[pos];
}
if (pos < k) {
return helper(nums, pos + 1, right, k);
}
return helper(nums, left, pos - 1, k);
}
};
- Combination Sum III
#include <bits/stdc++.h>
using namespace std;
/**
* 题目链接
* https://leetcode.com/problems/combination-sum-iii/description/
*/
class Solution {
public:
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> answers;
vector<int> answer;
combinationSum3(answers, answer, 1, k, n);
return answers;
}
void combinationSum3(vector<vector<int>> &answers, vector<int> &answer,
int start, int k, int n) {
if (k == 0 || n < 0) {
if (n == 0) {
answers.push_back(answer);
}
return;
}
for (int i = start; i <= 9; i++) {
answer.push_back(i);
combinationSum3(answers, answer, i + 1, k - 1, n - i);
answer.pop_back();
}
}
};
- Contains Duplicate
Given an array of integers, find if the array contains any duplicates.
Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.
#include <bits/stdc++.h>
using namespace std;
/**
* 原题链接
* https://leetcode.com/problems/contains-duplicate/description/
*/
class Solution {
public:
bool containsDuplicate(vector<int> &nums) {
set<int> dir(nums.begin(), nums.end());
return dir.size() < nums.size();
}
};
- The Skyline Problem
待定
- Contains Duplicate II
Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.
#include <bits/stdc++.h>
using namespace std;
/**
* 原题链接
* https://leetcode.com/problems/contains-duplicate-ii/description/
*/
class Solution {
public:
bool containsNearbyDuplicate(vector<int> &nums, int k) {
set<int> windows;
for (int i = 0; i < nums.size(); i++) {
if (i > k) {
windows.erase(nums[i - k - 1]);
}
if (windows.count(nums[i])) {
return true;
}
windows.insert(nums[i]);
}
return false;
}
};
- Contains Duplicate III
#include <bits/stdc++.h>
using namespace std;
/**
* 原题链接
* https://leetcode.com/problems/contains-duplicate-iii/description/
*/
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int> &nums, int k, int t) {
multiset<long> windows;
for (int i = 0, m = nums.size(); i < m; i++) {
if (i > k) {
windows.erase(nums[i - k - 1]);
}
auto pos = windows.lower_bound((long)nums[i] - t);
if (pos != windows.end() && *pos - nums[i] <= t) {
return true;
}
windows.insert(nums[i]);
}
return false;
}
};
- Maximal Square
Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.
#include <bits/stdc++.h>
using namespace std;
/**
* 题目链接
* https://leetcode.com/problems/maximal-square/description/
*/
class Solution {
public:
int maximalSquare(vector<vector<char>> &matrix) {
if (matrix.empty()) {
return 0;
}
int m = matrix.size(), n = matrix[0].size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
int res = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (matrix[i - 1][j - 1] == '1') {
dp[i][j] =
min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) +
1;
res = max(res, dp[i][j]);
}
}
}
return res * res;
}
};
- Count Complete Tree Nodes
Given a complete binary tree, count the number of nodes.
#include <bits/stdc++.h>
using namespace std;
/**
* 题目链接
* https://leetcode.com/problems/count-complete-tree-nodes/description/
*/
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
int get_height(TreeNode *root) {
if (root == NULL) {
return 0;
}
return 1 + get_height(root->left);
}
int countNodes(TreeNode *root) {
int height = get_height(root);
return height <= 0 ? 0
: get_height(root->right) == height - 1
? (1 << height - 1) + countNodes(root->right)
: (1 << height - 2) + countNodes(root->left);
}
};
class Solution_0 {
public:
int countNodes(TreeNode *root) {
if (root == nullptr) {
return 0;
}
int height = 0;
TreeNode *left = root, *right = root;
while (right) {
left = left->left;
right = right->right;
height++;
}
if (left == NULL)
return (1 << height) - 1;
return 1 + countNodes(root->left) + countNodes(root->right);
}
};
- Rectangle Area
Find the total area covered by two rectilinear rectangles in a 2D plane.
Each rectangle is defined by its bottom left corner and top right corner as shown in the figure.
#include <bits/stdc++.h>
using namespace std;
/**
* 题目链接
* https://leetcode.com/problems/rectangle-area/description/
*/
class Solution {
public:
int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
int left = max(A, E), right = max(left, min(C, G));
int bottom = max(B, F), top = max(min(D, H), bottom);
return (D - B) * (C - A) + (G - E) * (H - F) -
(right - left) * (top - bottom);
}
};
- Basic Calculator
Implement a basic calculator to evaluate a simple expression string.
The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .
#include <bits/stdc++.h>
using namespace std;
/**
* 原题链接
* https://leetcode.com/problems/basic-calculator/description/
*/
class Solution {
public:
int calculate(string s) {
stack<int> stk;
int res = 0, number = 0, sign = 1, m = s.size();
stk.push(sign);
for (int i = 0; i < m; i++) {
if (s[i] != ' ') {
while (i < m && isdigit(s[i])) {
number = 10 * number + (int)(s[i] - '0');
i++;
}
if (s[i] == '+' || s[i] == '-') {
res += sign * number;
sign = stk.top() * (s[i] == '+' ? 1 : -1);
number = 0;
} else if (s[i] == '(') {
stk.push(sign);
} else if (s[i] == ')') {
stk.pop();
}
}
}
res += sign * number;
return res;
}
};
- Implement Stack using Queues
Implement the following operations of a stack using queues.
push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
empty() -- Return whether the stack is empty.
#include <bits/stdc++.h>
using namespace std;
/**
* 原题链接
* https://leetcode.com/problems/implement-stack-using-queues/description/
*/
class MyStack {
private:
queue<int> myQueue;
public:
/** Initialize your data structure here. */
MyStack() {}
/** Push element x onto stack. */
void push(int x) { myQueue.push(x); }
/** Removes the element on top of the stack and returns that element. */
int pop() {
int x = myQueue.back(), m = myQueue.size();
for (int i = 0; i < m - 1; i++) {
myQueue.push(myQueue.front());
myQueue.pop();
}
auto res = myQueue.front();
myQueue.pop();
return res;
}
/** Get the top element. */
int top() { return myQueue.back(); }
/** Returns whether the stack is empty. */
bool empty() { return myQueue.empty(); }
};
- Invert Binary Tree
Invert a binary tree.
#include <bits/stdc++.h>
using namespace std;
/**
* 原题链接
* https://leetcode.com/problems/invert-binary-tree/description/
*/
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
TreeNode *invertTree(TreeNode *root) {
if (root) {
invertTree(root->right);
invertTree(root->left);
swap(root->left, root->right);
}
return root;
}
};
- Basic Calculator II
Implement a basic calculator to evaluate a simple expression string.
The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.
#include <bits/stdc++.h>
using namespace std;
/**
* 原题链接
* https://leetcode.com/problems/basic-calculator-ii/description/
*/
class Solution {
public:
int calculate(string s) {
int m = s.size();
long res = 0, prevNum = 0;
char preOp = '+';
for (int i = 0; i < m; i++) {
if (s[i] != ' ') {
int number = 0;
while (i < m && isdigit(s[i])) {
number = 10 * number + (int)(s[i] - '0');
i++;
}
if (preOp == '+') {
res += prevNum;
prevNum = number;
} else if (preOp == '-') {
res += prevNum;
prevNum = -number;
} else if (preOp == '*') {
prevNum = prevNum * number;
} else if (preOp == '/') {
prevNum = prevNum / number;
}
if (i < m) {
preOp = s[i];
}
}
}
return (res += prevNum);
}
};
- Summary Ranges
Given a sorted integer array without duplicates, return the summary of its ranges.
#include <bits/stdc++.h>
using namespace std;
/**
* 题目链接
* https://leetcode.com/problems/summary-ranges/description/
*/
class Solution_0 {
public:
vector<string> summaryRanges(vector<int> &nums) {
vector<string> res;
for (int i = 0; i < nums.size(); i++) {
int num = nums[i];
while (i + 1 < nums.size() && nums[i + 1] == nums[i] + 1)
i++;
if (num != nums[i]) {
res.push_back(to_string(num) + "->" + to_string(nums[i]));
} else {
res.push_back(to_string(nums[i]));
}
}
return res;
}
};
class Solution {
public:
vector<string> summaryRanges(vector<int> &nums) {
if (nums.empty()) {
return {};
}
vector<string> res;
int start = nums[0], end = nums[0];
for (int i = 1; i < nums.size(); i++) {
if (nums[i] != nums[i - 1] + 1) {
res.push_back(start == end
? to_string(start)
: to_string(start) + "->" + to_string(end));
start = nums[i];
}
end = nums[i];
}
res.push_back(start == end ? to_string(start)
: to_string(start) + "->" + to_string(end));
return res;
}
};
- Majority Element II
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.Note: The algorithm should run in linear time and in O(1) space.
#include <bits/stdc++.h>
using namespace std;
/**
* 题目链接
* https://leetcode.com/problems/majority-element-ii/description/
*/
class Solution {
public:
vector<int> majorityElement(vector<int> &nums) {
vector<int> res;
if (nums.empty()) {
return res;
}
int candidate1 = nums[0], candidate2 = -1, t1 = 0, t2 = 0;
int m = nums.size();
for (int i = 0; i < m; i++) {
if (candidate1 == nums[i]) {
t1++;
} else if (candidate2 == nums[i]) {
t2++;
} else if (t1 == 0) {
candidate1 = nums[i];
t1++;
} else if (t2 == 0) {
candidate2 = nums[i];
t2++;
} else {
t1--;
t2--;
}
}
if (count(nums.begin(), nums.end(), candidate1) > m / 3) {
res.push_back(candidate1);
}
if (count(nums.begin(), nums.end(), candidate2) > m / 3) {
res.push_back(candidate2);
}
return res;
}
};
- Kth Smallest Element in a BST
Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.
Note: You may assume k is always valid, 1 ≤ k ≤ BST's total elements.
#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
/**
* 题目链接
* https://leetcode.com/problems/kth-smallest-element-in-a-bst/description/
*/
class Solution {
public:
void helper(TreeNode *root, int &k, int &res) {
if (root && k) {
helper(root->left, k, res);
if (--k == 0) {
res = root->val;
}
helper(root->right, k, res);
}
}
int kthSmallest(TreeNode *root, int k) {
int res = 0;
helper(root, k, res);
return res;
}
};
- Power of Two
Given an integer, write a function to determine if it is a power of two.
#include <bits/stdc++.h>
using namespace std;
/**
* 题目链接
* https://leetcode.com/problems/power-of-two/description/
*/
class Solution {
public:
bool isPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; }
};
- Implement Queue using Stacks
Implement the following operations of a queue using stacks.
push(x) -- Push element x to the back of queue.
pop() -- Removes the element from in front of queue.
peek() -- Get the front element.
empty() -- Return whether the queue is empty.
#include <bits/stdc++.h>
using namespace std;
/**
* 原题链接
* https://leetcode.com/problems/implement-queue-using-stacks/description/
*/
class MyQueue {
public:
/** Initialize your data structure here. */
MyQueue() {}
/** Push element x to the back of queue. */
void push(int x) { stk1.push(x); }
/** Removes the element from in front of queue and returns that element. */
int pop() {
if (stk2.empty()) {
while (!stk1.empty()) {
stk2.push(stk1.top());
stk1.pop();
}
}
auto res = stk2.top();
stk2.pop();
return res;
}
/** Get the front element. */
int peek() {
if (stk2.empty()) {
while (!stk1.empty()) {
stk2.push(stk1.top());
stk1.pop();
}
}
return stk2.top();
}
/** Returns whether the queue is empty. */
bool empty() { return stk1.empty() && stk2.empty(); }
private:
stack<int> stk1, stk2;
};
- Number of Digit One
Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.
#include <bits/stdc++.h>
using namespace std;
/**
* 题目链接
* https://leetcode.com/problems/number-of-digit-one/description/
*/
class Solution {
public:
int countDigitOne(int n) {
int res = 0;
for (long m = 1; m <= n; m *= 10) {
int a = n / m, b = n % m;
res += (a + 8) / 10 * m + (a % 10 == 1) * (b + 1);
}
return res;
}
};
- Palindrome Linked List
Given a singly linked list, determine if it is a palindrome.
#include <bits/stdc++.h>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
/**
* 题目链接
* https://leetcode.com/problems/palindrome-linked-list/description/
*/
class Solution {
public:
ListNode *reverse(ListNode *head) {
ListNode *temp = NULL, *curNode = head;
while (curNode) {
ListNode *curNext = curNode->next;
curNode->next = temp;
temp = curNode;
curNode = curNext;
}
return temp;
}
bool isPalindrome(ListNode *head) {
if (head == NULL || head->next == NULL) {
return true;
}
ListNode *faster = head, *walker = head;
while (faster && faster->next) {
walker = walker->next;
faster = faster->next->next;
}
ListNode *cur1 = faster ? walker->next : walker, *cur2 = head;
cur1 = reverse(cur1);
while (cur1 && cur2) {
if (cur1->val != cur2->val) {
return false;
}
cur1 = cur1->next;
cur2 = cur2->next;
}
return true;
}
};
- Lowest Common Ancestor of a Binary Search Tree
Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”Given binary search tree: root = [6,2,8,0,4,7,9,null,null,3,5]
#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
/**
* 原题地址
* https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/description/
*/
class Solution {
public:
TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
if (root == NULL || root == p || root == q) {
return root;
}
if ((root->val - p->val) * (root->val - q->val) <= 0) {
return root;
}
if (root->val > p->val) {
return lowestCommonAncestor(root->left, p, q);
}
return lowestCommonAncestor(root->right, p, q);
}
};
class Solution_0 {
public:
TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
while ((root->val - p->val) * (root->val - q->val) > 0)
root = p->val < root->val ? root->left : root->right;
return root;
}
};
- Lowest Common Ancestor of a Binary Tree
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
/**
* 原题链接
* https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/
*/
class Solution {
public:
TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
if (root == NULL || root == p || root == q) {
return root;
}
TreeNode *left = lowestCommonAncestor(root->left, p, q);
TreeNode *right = lowestCommonAncestor(root->right, p, q);
return left == NULL ? right : right == NULL ? left : root;
}
};
- Delete Node in a Linked List
Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.
#include <bits/stdc++.h>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
/**
* 原题链接
* https://leetcode.com/problems/delete-node-in-a-linked-list/description/
*/
class Solution {
public:
void deleteNode(ListNode *node) {
ListNode *next = node->next;
*node = *next;
delete next;
}
};
- Product of Array Except Self
Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
#include <bits/stdc++.h>
using namespace std;
/**
* 原题链接
* https://leetcode.com/problems/product-of-array-except-self/description/
*/
class Solution {
public:
vector<int> productExceptSelf(vector<int> &nums) {
int m = nums.size();
vector<int> res(m, 1);
for (int i = 1; i < m; i++) {
res[i] = res[i - 1] * nums[i - 1];
}
int right = 1;
for (int i = m - 1; i >= 0; i--) {
res[i] = res[i] * right;
right *= nums[i];
}
return res;
}
};
- Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.
#include <bits/stdc++.h>
using namespace std;
/**
* 原题链接
* https://leetcode.com/problems/sliding-window-maximum/description/
*/
class Solution {
public:
vector<int> maxSlidingWindow(vector<int> &nums, int k) {
vector<int> res;
deque<int> dq;
int m = nums.size();
for (int i = 0; i < m; i++) {
while (!dq.empty() && dq.front() <= i - k) {
dq.pop_front();
}
while (!dq.empty() && nums[dq.back()] < nums[i]) {
dq.pop_back();
}
dq.push_back(i);
if (i >= k - 1) {
res.push_back(nums[dq.front()]);
}
}
return res;
}
};
- Search a 2D Matrix II
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
- Integers in each row are sorted in ascending from left to right.
- Integers in each column are sorted in ascending from top to bottom.
#include <bits/stdc++.h>
using namespace std;
/**
* 原题地址
* https://leetcode.com/problems/search-a-2d-matrix-ii/description/
*/
class Solution {
public:
bool searchMatrix(vector<vector<int>> &matrix, int target) {
if (matrix.empty()) {
return false;
}
int m = matrix.size(), n = matrix[0].size();
int i = 0, j = n - 1;
while (i < m && j >= 0) {
if (matrix[i][j] == target) {
return true;
}
if (matrix[i][j] < target) {
i++;
} else {
j--;
}
}
return false;
}
};
- Different Ways to Add Parentheses
Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.
#include <bits/stdc++.h>
using namespace std;
/*
* 原题地址
* https://leetcode.com/problems/different-ways-to-add-parentheses/description/
*/
class Solution {
public:
vector<int> diffWaysToCompute(string input) {
vector<int> res;
for (int i = 0; i < input.size(); i++) {
if (ispunct(input[i])) {
for (auto a : diffWaysToCompute(input.substr(0, i))) {
for (auto b : diffWaysToCompute(input.substr(i + 1))) {
res.push_back(input[i] == '+'
? a + b
: input[i] == '-' ? a - b : a * b);
}
}
}
}
return res.empty() ? vector<int>{stoi(input)} : res;
}
};
- Valid Anagram
Given two strings s and t , write a function to determine if t is an anagram of s.
#include <bits/stdc++.h>
using namespace std;
/*
* 原题地址
* https://leetcode.com/problems/valid-anagram/description/
*/
class Solution {
public:
bool isAnagram(string s, string t) {
if (s.length() != t.length()) {
return false;
}
vector<int> dir(26, 0);
for (int i = 0; i < s.size(); i++) {
dir[s[i] - 'a']++;
}
for (int i = 0; i < t.size(); i++) {
if (--dir[t[i] - 'a'] < 0) {
return false;
}
}
return true;
}
};
