optimjie

### 算法：遍历一遍 $O(n)$

#### C++

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode *dummy = new ListNode(-1);
ListNode *tail = dummy;
int t = 0;
while (l1 && l2) {
int sum = t + l1->val + l2->val;
t = sum / 10;
l1 = l1->next, l2 = l2->next;
}
while (l1) {
int sum = t + l1->val;
t = sum / 10;
l1 = l1->next;
}
while (l2) {
int sum = t + l2->val;
t = sum / 10;
l2 = l2->next;
}
return dummy->next;
}
void addTail(ListNode* &tail, int x) {
ListNode *p = new ListNode(x);
tail->next = p;
tail = p;
}
};


#### Java

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int t = 0;
ListNode p1 = l1, p2 = l2;
while (p1 != null && p2 != null) {
t += p1.val;
t += p2.val;
tail = add(tail, t % 10);
t /= 10;
p1 = p1.next;
p2 = p2.next;
}
while (p1 != null) {
t += p1.val;
tail = add(tail, t % 10);
t /= 10;
p1 = p1.next;
}
while (p2 != null) {
t += p2.val;
tail = add(tail, t % 10);
t /= 10;
p2 = p2.next;
}
if (t > 0) {
}
}
public ListNode add(ListNode tail, int val) {
ListNode tmp = new ListNode(val);
tail.next = tmp;
tail = tmp;
return tail;
}
}


### 算法一：暴力 $O(n^2)$

class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int n = nums.size();
for (int i = 1; i < n; i++)
for (int j = 0; j < i; j++)
if (nums[i] + nums[j] == target) return vector<int>{j, i};
return vector<int>();
}
};


### 算法二：哈希 $O(n)$

#### C++:

class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int n = nums.size();
unordered_map<int, int> hash;
for (int i = 0; i < n; i++) {
if (hash.find(target - nums[i]) != hash.end())
return vector<int>{hash[target - nums[i]], i};
hash.insert({nums[i], i});
}
return vector<int>();
}
};


#### Java:

class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> hash = new HashMap<>();
int n = nums.length;
for (int i = 0; i < n; i++) {
if (hash.containsKey(target - nums[i]))
return new int[]{hash.get(target - nums[i]), i};
hash.put(nums[i], i);
}
return new int[2];
}
}


const int N = 5e4 + 10;

class Solution {
public:

int h[N] = {0}, e[2 * N] = {0}, ne[2 * N] = {0}, idx = 0;
int ans = 0;
unordered_set<string> hash;

int minReorder(int n, vector<vector<int>>& connections) {
memset(h, -1, sizeof h);
for (auto v : connections) {
hash.insert(to_string(v[0]) + "#" + to_string(v[1]));
}
dfs(0, -1);
return ans;
}

void dfs(int u, int fa) {
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (j == fa) continue;
if (hash.find(to_string(u) + "#" + to_string(j)) != hash.end()) ans++;
dfs(j, u);
}
}

void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
};


/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int goodNodes(TreeNode* root) {
return dfs(root, (int)-1e5);
}
int dfs(TreeNode *p, int maxv) {
if (p == nullptr) return 0;
int res = 0;
if (p->val >= maxv) res++;
res += dfs(p->left, max(maxv, p->val));
res += dfs(p->right, max(maxv, p->val));
return res;
}
};


optimjie
12天前

### 做法：

1. dfs找到所有的路径
2. 对于每一个路径判断能否构成回文，我这里的做法是用一个set，如果之前有当前的数字，那么从set中删掉（相当于抵消），否则添加，最后看set的长度，若小于等于1则可以构成回文，等于0代表：所有的数字都抵消则将每一个数字分别放在两边可构成回文；等于1代表：还剩一个数字，将这个数放在中间，其余数字放在两边可构成回文。
/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int ans = 0;
vector<int> path;
int pseudoPalindromicPaths (TreeNode* root) {
dfs(root);
return ans;
}
void dfs(TreeNode *root) {
if (root == NULL) return;
path.push_back(root->val);
if (root->left == NULL && root->right == NULL) {
set<int> s;
for (auto v : path) {
if (s.find(v) == s.end()) s.insert(v);
else s.erase(v);
}
if (s.size() <= 1) ans++;
}
if (root->left) dfs(root->left);
if (root->right) dfs(root->right);
path.pop_back();
}
};


optimjie
12天前

### 做法：

• i指针在后，j指针在前，当j~i的长度大于k时将j向后移动，并判断是否为元音，来修改当前窗口元音的数量，若区间i~j的长度等于k则更新答案。
class Solution {
public:
int maxVowels(string s, int k) {
int n = s.size();
if (n == 0) return 0;
int ans = 0;
for (int i = 0, j = 0, cnt = 0; i < n; i++) {
if (i - j + 1 > k) {
if (check(s[j++])) cnt--;
}
if (check(s[i])) cnt++;
if (i - j + 1 == k) ans = max(ans, cnt);
}
return ans;
}
// a, e, i, o, u
bool check(char c) {
if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') return true;
return false;
}
};


optimjie
12天前

### 暴力

class Solution {
public:
int isPrefixOfWord(string sentence, string searchWord) {
int n = sentence.size();
if (n == 0) return -1;
vector<string> word;
for (int i = 0; i < n; ) {
string s;
while (i < n && sentence[i] != ' ') s += sentence[i++];
word.push_back(s);
i++;
}
for (int i = 0; i < word.size(); i++) {
if (searchWord.size() > word[i].size()) continue;
if (word[i].substr(0, searchWord.size()) == searchWord) return i + 1;
}
return -1;
}
};


optimjie
13天前

### 这不是个物理题吗？？？😰

#include <bits/stdc++.h>

using namespace std;

const double g = 9.8;

int t;
int v, d;

int main() {
cin >> t;
for (int u = 1; u <= t; u++) {
cin >> v >> d;
double s = d * g / v / v;
double l = 0, r = 45;
while (r - l > 1e-8) {
double mid = (l + r) / 2;
if (sin(2 * mid * M_PI / 180) > s) r = mid;
else l = mid;
}
printf("Case #%d: %.7lf\n", u, l);
}
return 0;
}


optimjie
13天前
#include <bits/stdc++.h>

using namespace std;

const int N = 110;

int t, n;

int main() {
cin >> t;
for (int u = 1; u <= t; u++) {
vector<string> str;
int ans = 0;
cin >> n;
getchar();
while (n--) {
string s;
getline(cin, s);
if (str.size() == 0) str.push_back(s);
else {
if (s < str.back()) ans++;
str.push_back(s);
sort(str.begin(), str.end());
}
}
printf("Case #%d: %d\n", u, ans);
}
return 0;
}


optimjie
17天前

#### 看leetcode上的题解都是DP，分享一下分治的做法

class Solution {
public:
int maxProduct(vector<int>& nums) {
int n = nums.size();
if (n == 0) return 0;
return merge(nums, 0, n - 1);
}
int merge(vector<int>& nums, int l, int r) {
if (l >= r) return nums[l];
int mid = l + r >> 1;
int res = max(merge(nums, l, mid), merge(nums, mid + 1, r));
int leftPos, leftNeg, rightPos, rightNeg;
leftPos = rightPos = 0;
leftNeg = rightNeg = 0;
for (int i = mid + 1, s = 1; i <= r; i++) {
s *= nums[i];
if (s > rightPos) rightPos = s;
if (s < rightNeg) rightNeg = s;
}
for (int i = mid, s = 1; i >= l; i--) {
s *= nums[i];
if (s > leftPos) leftPos = s;
if (s < leftNeg) leftNeg = s;
}
return max(res, max(leftNeg * rightNeg, leftPos * rightPos));
}
};