基础数据结构思路写法记录，便于回顾

重思路非代码。基础的思路搞懂了，变形题目顺着思考基本都能写出来！

二分查找

    int binarySearch(vector<int> &nums, int target) {// write your code hereif (nums.empty()) {return -1;}int start = 0;int end = nums.size() - 1;while (start + 1 < end) {int mid = start + (end - start) / 2;if (nums[mid] >= target) { // 有重复的输出第一个end = mid;} else {start = mid;}/*if (nums[mid] <= target) { // 有重复的输出最后一个start = mid;} else {end = mid;}*/}if (nums[start] == target) {return start;}if (nums[end] == target) {return end;}return -1;}

链表逆序

class Solution {
public:ListNode* reverseList(ListNode* head) {if (head == nullptr || head->next == nullptr) {return head;}// 注意的是先画图, 代码自然就能写出来ListNode* prev = nullptr;ListNode* cur = head;    while (cur != nullptr) {ListNode* tmp = cur->next;cur->next = prev;prev = cur;cur = tmp;}return prev;}
};

二叉树遍历

// 前序
class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {if (root == nullptr) {return {};}stack<TreeNode*> s;// s.push(root);vector<int> res;while (!s.empty() || root) {if (root) {res.push_back(root->val);s.push(root);root = root->left;} else {root = s.top();s.pop();root = root->right;}}return res;}
};// 中序
class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> res;if (root == nullptr) {res;}stack<TreeNode*> s;// s.push(root);while (!s.empty() || root) {if (root) {s.push(root);root = root->left;} else {root = s.top();res.push_back(root->val);s.pop(); root = root->right;}}return res;}
};// 后序
class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {if (root == nullptr) {return {};}vector<int> res;stack<TreeNode*> s;while (!s.empty() || root) {if (root) {s.push(root);res.push_back(root->val);root = root->right;} else {root = s.top();s.pop();root = root->left;}}std::reverse(res.begin(), res.end());return res;}
};// 层序
class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> res;if (root == nullptr) {return res;}queue<TreeNode*> q;q.push(root);TreeNode split = TreeNode(INT_MAX);q.push(&split);vector<int> layer;while (!q.empty()) {TreeNode *cur = q.front();q.pop();if (cur == &split) {res.push_back(layer);layer.clear(); // 注意别忘记清理if (!q.empty()) {q.push(&split);}} else {layer.push_back(cur->val);if (cur->left) {q.push(cur->left);}if (cur->right) {q.push(cur->right);}}}return res;}
};

N叉树

class Solution {
public:vector<int> preorder(Node* root) {vector<int> res;if (root == nullptr) {return res;}//helper(root, res); // 递归版本stack<Node*> s;s.push(root);while (!s.empty()) {Node* cur = s.top();s.pop();if (cur != nullptr) {res.push_back(cur->val);}std::reverse(cur->children.begin(), cur->children.end());for (auto &node : cur->children) {s.push(node);}}return res;}/*void helper(Node* root, vector<int>& out) {if (root == nullptr) {return;}out.push_back(root->val);for (int i = 0; i < root->children.size(); ++i) {helper(root->children[i], out);}}*/
};

基础排序

/* 归并排序 */// merge
void merge(vector<int>& nums, int low, int high, vector<int>& tmp) {int mid = (low + high) / 2;int leftIndex = low;int rightIndex = mid + 1;int resLeftIndex = leftIndex;while (leftIndex <= mid && rightIndex <= high) {// leftIndex 135 // rightIndex 246// resLeftIndex 123456if (nums[leftIndex] >= nums[rightIndex]) {tmp[resLeftIndex++] = nums[rightIndex++];}else {tmp[resLeftIndex++] = nums[leftIndex++];}}while (leftIndex <= mid) {tmp[resLeftIndex++] = nums[leftIndex++];}while (rightIndex <= high) {tmp[resLeftIndex++] = nums[rightIndex++];}for (int i = low; i <= high; ++i) { // 易错点 <=nums[i] = tmp[i];}
}// 分治
void divideConquer(vector<int>& nums, int low, int high, vector<int>& tmp) {if (low >= high) {return;}// 分而治之divideConquer(nums, low, (high + low) / 2, tmp);divideConquer(nums, (high + low) / 2 + 1, high, tmp);// 合并有序数组merge(nums, low, high, tmp);
}void mergeSort(vector<int>& nums) {if (nums.empty()) {return;}vector<int> tmp(nums.size());divideConquer(nums, 0, nums.size() - 1, tmp);
}int main()
{vector<int> nums = { 2, -1, 4, 55, 0, 67, -23, 5, 9 };//quickSortNotR(nums, 0, nums.size() - 1);mergeSort(nums);for (auto item : nums) {cout << item << " ";}cout << endl;return 0;
}// 快速排序
int getPartSortIndex(vector<int>& nums, int low, int high) {int tmp = nums[low]; // TODO：随机取值int i = low;int j = high;while (i <j) {while (i < j && nums[j] >= tmp) {j--;}nums[i] = nums[j];while (i < j && nums[i] <= tmp) {i++;}nums[j] = nums[i];}nums[i] = tmp;return i;
}// 递归版本
void quickSort(vector<int>& nums, int low, int high) {if (low >= high) {return;}int index = getPartSortIndex(nums, low, high);quickSort(nums, low, index - 1);quickSort(nums, index + 1, high);
}// 非递归版本
void quickSortNotR(vector<int>& nums, int low, int high) { if (low >= high) {return;}stack<int> s;s.emplace(low);s.emplace(high);while (!s.empty()) {int right = s.top();s.pop();int left = s.top();s.pop();int index = getPartSortIndex(nums, left, right);if (index - 1 > left) {s.emplace(left);s.emplace(index - 1);}if (index + 1 < right) {s.emplace(index + 1);s.emplace(right);}}
}