剑指offer

删除链表的节点

class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        ListNode *last = head;	//保存上一个节点
        ListNode *q = head;	
        if(q -> val == val){	//如果头结点就需要被删除，直接返回next就好了
            return head -> next;
        }
        while(q != NULL)
        {
            if (q -> val != val){	//该节点不是要被删除的节点
                last = q;	
                q = q -> next;
            }
            else{	//要删除的节点的上一个节点的next需要连接被删除节点的next
                last -> next = q -> next;
                q = last -> next;    
            }
        }
        return head;
    }
};

连续子数组的最大和

class Solution {
public:
    int maxSubArray(vector<int>& nums) {  
        int *dp = new int[nums.size()];
        dp[0] = nums[0];
        int ans = dp[0];
        int len = nums.size();
        for(int i = 1; i < len; i++){
              dp[i] = max(nums[i], dp[i-1] + nums[i]);
              ans = max(ans, dp[i]);
        }
        return ans;
    }
};

第一个只出现一次的字符

class Solution {
public:
    char firstUniqChar(string s) {
        map<char,int>vis;
        for(int i = 0; i < s.size(); i++){
            vis[s[i]]++;
        }
        for(int i = 0; i < s.size(); i++){
            if(vis[s[i]] == 1){
                return s[i];
            }
        }
        return ' ';
    }
};

两个链表的第一个公共节点

我们使用两个指针 a,b 分别指向两个链表 headA，headB 的头结点，然后同时分别逐结点遍历，当 a 到达链表 headA 的末尾时，重新定位到链表 headB 的头结点；当 b 到达链表 headB 的末尾时，重新定位到链表 headA 的头结点。
这样，当它们相遇时，所指向的结点就是第一个公共结点。
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == NULL || headB == NULL){
            return NULL;
        }
        ListNode *a = headA;
        ListNode *b = headB;
        while (a != b){
            a = a == NULL ? headB : a -> next;
            b = b == NULL ? headA : b -> next;
        }
        return a;
    }
};

圆圈中最后剩下的数字

第一次去除的答案就是x=m%n，这时候序列长度成为n-1,这个时候的序列构成就成了x后面的一串排在了初始串的前面，这样下次的答案就是(m%n+x)%n=(m+x)%n。
class Solution {
private:
    int f(int n, int m){
        if(n == 1){
            return 0;
        }
        int x = f(n - 1,m);
        return (m + x)%n;
    }
public:
    int lastRemaining(int n, int m) {
        return f(n, m);
    }
};

调整数组顺序使奇数位于偶数前面

class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
        int i = 0, j = nums.size()-1;
        while(i <= j){
            while(i <= j && nums[i] % 2 == 1){
                i++;
            }
            while(i <= j && nums[j] % 2 == 0){
                j--;
            }
            if(i <= j){
                swap(nums[i], nums[j]);
                i++;j--;
            }
        }
        return nums;
    }
};

和为s的两个数字

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, bool>vis;
        vector<int>ans;
        for(int i = 0; i < nums.size(); i++){
            if(!vis[target - nums[i]]){
                vis[nums[i]] = 1;
            }
            else{
                ans.push_back(nums[i]);
                ans.push_back(target - nums[i]);
                break;
            }
        }
        return ans;
    }
};

数组中重复的数字

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        unordered_map<int, bool> vis;
        int ans;
        for(int i = 0; i < nums.size(); i++){
            if(!vis[nums[i]]){
                vis[nums[i]] = 1;
            }
            else{
                ans = nums[i];
                break;
            }
        }
        return ans;
    }
};

数组中出现次数超过一半的数字

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> vis;
        int ans;
        for(int i = 0; i < nums.size(); i++){
            vis[nums[i]]++;
        }
        for(auto it = vis.begin(); it != vis.end(); ++it){
            if (it -> second > nums.size()/2){
                ans = it -> first;
                break;
            }
        }
        return ans;
    }
};

层序遍历二叉树

class Solution {
private:
    void dfs(TreeNode *root){
        if (root == NULL){
            return ;
        }
        if(deep >= ans.size()){
            ans.emplace_back(vector<int>());
        }
        ans[deep].push_back(root -> val);
        deep++;
        dfs(root -> left);
        dfs(root -> right);
        deep--;
    }
public:
    vector<vector<int>>ans;
    int deep = 0;
    vector<vector<int>> levelOrder(TreeNode* root) {
        dfs(root);
        return ans;
    }
};

二叉搜索树的最近公共祖先

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root -> val > max(p -> val, q ->val)){
            return lowestCommonAncestor(root -> left, p, q);
        }
        else if (root -> val < min(p -> val, q -> val)){
            return lowestCommonAncestor(root -> right, p, q);
        }
        else{
            return root;
        }
    }
};

和为s的连续正数序列

class Solution {
public:
    vector<vector<int>> ans;
    int sum = 0;
    int l = 1,r = 1;
    vector<vector<int>> findContinuousSequence(int target) {
        while(l <= target/2){
            if(sum == target){
                vector<int>vec;
                for(int i = l; i < r; i++){
                    vec.push_back(i);
                }
                ans.push_back(vec);
                sum -= l;
                l++;
            }
            else if(sum < target){
                sum += r;
                r++;
            }
            else if(sum > target){
                sum -= l;
                l++;
            }
        }
        return ans;
    }
};

用两个栈实现队列

class CQueue {
private:
    stack<int>del;	//负责删除
    stack<int>insert;	//负责添加
public:
    CQueue() {
        while(!del.empty()){
            del.pop();
        }
        while(!insert.empty()){
            insert.pop();
        }
    }
    
    void appendTail(int value) {
        insert.push(value);
    }
    
    int deleteHead() {
        if(del.size()+insert.size() == 0){
            return -1;
        }
        else{
            //只有当del里面没有东西的时候，再把insert里面的值全部导入del里面
            if(del.empty()){
                while(!insert.empty()){
                    del.push(insert.top());
                    insert.pop();
                }
            }
        }
        int ans = del.top();
        del.pop();
        return ans;;
    }
};

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue* obj = new CQueue();
 * obj->appendTail(value);
 * int param_2 = obj->deleteHead();
 */

二进制中1的个数

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int ans = 0;
        while(n){
            if(n&1){
                ans++;
            }
            n>>=1;
        }
        return ans;
    }
};

合并两个排序的链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *root = new ListNode(-1), *ans = root;
        while (l1 != NULL && l2 != NULL){
            if (l1 -> val > l2 -> val){
                ans -> next = l2;
                ans = ans -> next;
                l2 = l2 -> next;
            }
            else if (l1 -> val <= l2 -> val){
                ans -> next = l1;
                ans = ans -> next;
                l1 = l1 -> next;
            } 
        }
        if (l1 != NULL){
            ans -> next = l1;
        }
        else {
            ans -> next = l2;
        }
        return root -> next;
    }
};

二叉搜索树的第k大节点

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    int temp = 0;
    void dfs(TreeNode *root, int k){
        if (root -> right != NULL){
            dfs(root -> right, k);
        }
        if (++temp == k){
            ans = root -> val;
            return ;
        }
        if (root -> left != NULL){
            dfs(root -> left, k);
        }
    }
public:
    int ans = 0;
    int kthLargest(TreeNode* root, int k) {
        dfs(root, k);
        return ans;
    }
};

反转链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *pre = NULL, *cur = head, *next = NULL;
        while (cur != NULL){
            next = cur -> next;
            cur -> next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
};

从尾到头打印链表

class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        vector<int> ans;
        while (head != NULL){
            ans.push_back(head -> val);
            head = head ->next;
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

替换空格

class Solution {
public:
    string replaceSpace(string s) {
        string ans;
        for (int i = 0; i < s.size(); i++){
            if (s[i] != ' '){
                ans.push_back(s[i]);
            }
            else{
                ans.push_back('%');
                ans.push_back('2');
                ans.push_back('0');
            }
        }
        return ans;
    }
};
class Solution {
public:
    string replaceSpace(string s) {
        int count = 0, len = s.size();
        // 统计空格数量
        for (char c : s) {
            if (c == ' ') count++;
        }
        // 修改 s 长度
        s.resize(len + 2 * count);
        // 倒序遍历修改
        for(int i = len - 1, j = s.size() - 1; i < j; i--, j--) {
            if (s[i] != ' ')
                s[j] = s[i];
            else {
                s[j - 2] = '%';
                s[j - 1] = '2';
                s[j] = '0';
                j -= 2;
            }
        }
        return s;
    }
};

打印从1到最大的n位数

class Solution {
public:
    vector<int> printNumbers(int n) {
        int temp = 0;
        while (n--){
            temp = temp*10 + 9;
        }
        vector<int>ans;
        for (int i = 1; i <= temp; i++){
            ans.push_back(i);
        }
        return ans;
    }
};

二叉树的镜像

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if (root == NULL){
            return root;
        }
        TreeNode *temp = root -> left;
        root -> left = root -> right;
        root -> right = temp;
        mirrorTree(root -> left);
        mirrorTree(root -> right);
        return root;
    }
};

二叉树的深度

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    void dfs(TreeNode *root, int temp){
        if (!root){
            return ;
        }
        temp++;
        deep = max(deep, temp);
        dfs(root -> left, temp);
        dfs(root -> right, temp);
        temp--;
    }
public:
    int deep = 0;
    int maxDepth(TreeNode* root) {
        dfs(root, 0);
        return deep;
    }
};

链表中倒数第k个节点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode *temp = head;
        while (k--){
            head = head -> next;
        }
        while (head){
            head = head -> next;
            temp = temp -> next;
        }
        return temp;
    }

};

左旋转字符串

class Solution {
public:
    string reverseLeftWords(string s, int n) {
        string ans;
        for(int i = n; i < s.size(); i++){
            ans.push_back(s[i]);
        }
        for(int i = 0; i < n; i++){
            ans.push_back(s[i]);
        }
        return ans;
    }
};

是否为平衡二叉树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    int get_deep(TreeNode *root){
        if(!root){
            return 0;
        }
        return 1 + max(get_deep(root -> left),get_deep(root -> right));
    }
public:
    bool isBalanced(TreeNode* root) {
        if (!root){
            return 1;
        }
        else if (abs(get_deep(root -> left) - get_deep(root -> right)) > 1){
            return 0;
        }
        return isBalanced(root -> left) && isBalanced(root -> right);
    }
};

是否为对称的二叉树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    bool judge(TreeNode *node_left, TreeNode *node_right){
        if (!node_left && node_right){
            return 0;
        }
        else if (!node_right && node_left){
            return 0;
        }
        else if (!node_left && !node_right){
            return 1;
        }
        else if (node_left -> val != node_right -> val){
            return 0;
        }
        return judge(node_left -> left, node_right -> right) && judge(node_left -> right, node_right -> left);
    }
public:
    bool isSymmetric(TreeNode* root) {
        if (!root){
            return 1;
        }
        return judge(root -> left, root -> right);
    }
};

包含min函数的栈

class MinStack {
public:
    /** initialize your data structure here. */
    stack<int>s;
    stack<int>s_min;
    MinStack() {
        while(!s.empty()){
            s.pop();
        }
        while(!s_min.empty()){
            s_min.pop();
        }
    }
    void push(int x) {
        s.push(x);
        if (s_min.empty() || x <= s_min.top()){
            s_min.push(x);
        }
    }
    void pop() {
        if (s.empty()){
            return ;
        }
        if (s_min.top() == s.top()){
            s.pop();
            s_min.pop();
        }
        else{
            s.pop();
        }
    }
    int top() {
        return s.top();
    }
    int min() {
        return s_min.top();
    }
};

最小的k个数

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        vector<int>ans;
        sort(arr.begin(), arr.end());
        for(int i = 0; i < k; i++){
            ans.push_back(arr[i]);
        }
        return ans;
    }
};

不用加减乘除做加法

class Solution {
public:
    int add(int a, int b) {
        while (b != 0){
            int tmp = a^b;
            b = ((unsigned int)(a & b) << 1);
            a = tmp;
        } 
        return a;
    }
};

n个骰子的点数

class Solution {
public:
    vector<double> twoSum(int n) {
        int dp[15][70] = {0};
        vector<double>ans;
        int all = pow(6,n);
        for (int i = 1; i <= 6; i++){
            dp[1][i] = 1;
        }
        for (int i = 2; i <= n; i++){
            for (int j = i; j <= 6*n; j++){
                for (int k = 1; k <= 6; k++){
                    if (j <= k){
                        break;
                    }
                    dp[i][j] += dp[i-1][j-k];
                }
            }
        }
        for (int i = n; i <= 6*n; i++){
            ans.push_back((double)dp[n][i]/all);
        }
        return ans;
    }
};

在排序数组中查找数字个数

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size()-1;
        while (l <= r){
            int mid = (l + r)>>1;
            if(nums[mid] < target){
                l = mid + 1;
            }
            else{
                r = mid - 1;
            }
        }
        int ans = 0;
        while(l < nums.size() && nums[l++] == target){
            ans++;
        }
        return ans;
    }
};

旋转数组的最小数字

class Solution {
public:
    int minArray(vector<int>& numbers) {
        int l = 0, r = numbers.size()-1;
        if (r == 0){
            return numbers[0];
        }
        while (l < r){
            int mid = (r + l) >> 1;
            //只要右边比中间大，右边一定是有序的
            if (numbers[r] > numbers[mid]){
                r = mid;
            }
            else if(numbers[r] < numbers[mid]){
                l = mid + 1;
            }
            else{
                r--;
            }
        }
        return numbers[l];
    }
};

扑克牌中的顺子

class Solution {
public:
    bool isStraight(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int num_0 = 0;
        int i;
        for (i = 0; i < nums.size(); i++){
            if (nums[i]){
                break;
            }
            num_0++;
        }
        int temp = 0;
        for (i; i < nums.size() - 1; i++){
            if (nums[i + 1] - nums[i] == 1){
                continue;
            }
            else if (nums[i] == nums[i + 1]){
                return false;
            }
            else{
                temp += (nums[i + 1] - nums[i] - 1);
            }
            
        }
        if(num_0 < temp){
            return false;
        }
        return true;
    }
};

顺时针打印矩阵

class Solution {
private:
public: 
    vector<int> ans;
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if (matrix.empty()){
            return ans;
        }
        int l = 0, r = matrix[0].size() - 1; //矩阵的左右边界
        int u = 0, d = matrix.size() - 1; //矩阵的上下边界
        while(1){
            for (int i = l; i <= r; i++) ans.push_back(matrix[u][i]);
            if (++u > d) break;
            for (int i = u; i <= d; i++) ans.push_back(matrix[i][r]);
            if (--r < l) break;
            for (int i = r; i >= l; i--) ans.push_back(matrix[d][i]);
            if (--d < u) break;
            for (int i = d; i >= u; i--) ans.push_back(matrix[i][l]);
            if (++l > r) break;
        }
        return ans;
    }
};

滑动窗口的最大值

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
		vector<int>ans;
		deque<int>tmp;
		int len = nums.size();
		for (int i = 0; i < len; i++){
			if (!tmp.empty() && i - tmp.front() >= k){
				tmp.pop_front();
			}
			while(!tmp.empty() && nums[i] > nums[tmp.back()]){
				tmp.pop_back();
			}
			tmp.push_back(i);
			if (i >= k - 1){
				ans.push_back(nums[tmp.front()]);
			}
		}
		return ans;
    }
};

0～n-1中缺失的数字

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while (l <= r){
            int mid = (l + r) >> 1;
            if (nums[mid] == mid){
                l = mid + 1;
            }
            else{
                r = mid - 1;
            }
        }
        return l;
    }
};

翻转单词顺序

class Solution {
public:
    string reverseWords(string s) {
        string ans;
        int n = s.size();
        for (int i = n - 1; i >= 0; i--){
            if (s[i] != ' '){
                continue;
            }
            if (ans.size() && s[i + 1] != ' '){
                ans.push_back(' ');
            }
            for (int j = i + 1; j < n; j++){
                if (s[j] == ' '){
                    break;
                }
                ans.push_back(s[j]);
            }
        }
		if(ans.size() && s[0] != ' '){
			ans.push_back(' ');
		}
		for (int i = 0; i < n; i++){
			if (s[i] ==' '){
				break;
			}
			ans.push_back(s[i]);
		}
        return ans;
    }
};

青蛙跳台阶问题

class Solution {
public:
    int numWays(int n) {
        int a = 1;
        int b = 2;
        int mod = 1000000007;
        if (n == 1 || n == 0){
            return a;
        }
        if (n == 2){
            return b;
        }
        for (int i = 3; i <= n; i++){
            int temp = b;
            b = (a + b)%mod;
            a = temp;
        }
        return b;
    }
};

二维数组中的查找

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        int x = matrix.size() - 1, y = 0;
        while (x >= 0 && y < matrix[0].size()){
            if (target == matrix[x][y]){
                return true;
            }
            else if (target < matrix[x][y]){
                x--;
            }
            else{
                y++;
            }
        }
        return false;
    }
};

斐波那契数列

class Solution {
public:
    int fib(int n) {
        int mod = 1e9+7;
        int ans = 0;
        int a = 0, b = 1;
        if (n == 0){
            return a;
        }
        else if (n == 1){
            return b;
        }
        for(int i = 2; i <= n; i++){
            ans = (a + b)%mod;
            a = b;
            b = ans;
        }
        return ans;
    }
};

求1+2+…+n

class Solution {
public:
    int sumNums(int n) {
        int ans = n;
        n && (ans += sumNums(n - 1));
        return ans;
    }
};

数组中数字出现的次数 II

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for (int i = 0; i < 32; i++){
            int temp = 0;
            for (auto j : nums){
                if (j & (1 << i)){
                    temp++;
                }
            }
            if (temp % 3 == 1){
                ans ^= (1 << i);
            }
        }
        return ans;
    }
};

复杂链表的复制

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (head == NULL){
            return head;
        }
        //将拷贝节点放到原节点后面
        for (Node *node = head, *copy = NULL; node != NULL; node = node->next->next){
            copy = new Node(node->val);
            copy->next = node->next;
            node->next = copy;
        }
        //将random节点安排
        for (Node *node = head; node != NULL; node = node->next->next){
            if (node->random != NULL){
                node->next->random = node->random->next;
            }
        }
        //分离拷贝节点和原节点
        Node *newHead = head->next;
        for (Node *node = head, *temp = NULL; node != NULL && node->next != NULL;){
            temp = node->next;
            node->next = temp->next;
            node = temp;
        }
        return newHead;
    }
};

通过前序和中序重建二叉树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    TreeNode* build(vector<int>&preorder, vector<int>& inorder, int root, int l, int r){
        if (l > r){
            return NULL;
        }
        TreeNode *tree = new TreeNode(preorder[root]);
        int i = l;
        while (i < r && preorder[root] != inorder[i]){
            i++;
        }
        tree -> left = build(preorder, inorder, root + 1, l, i - 1);
        tree -> right = build(preorder, inorder, root + 1 + i - l, i + 1, r);
        return tree;
    }
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return build(preorder, inorder, 0, 0, inorder.size() - 1);
    }
};

找出出现次数不为2的两个数

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int tmp = 0;
        for (auto x : nums){
            tmp ^= x;
        }
        int index = 0;
        while ((tmp & 1) == 0){
            index++;
            tmp >>= 1;
        }
        int ans1 = 0, ans2 = 0;
        for (auto x : nums){
            if ((x >> index) & 1){
                ans1 ^= x;
            }
            else{
                ans2 ^= x;
            }
        }
        return {ans1, ans2};
    }
};

二维dp取礼物的最大价值

class Solution {
public:
    int maxValue(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        for (int i = 1; i < n; i++){
            grid[0][i] += grid[0][i - 1];
        }
        for (int i = 1; i < m; i++){
            grid[i][0] += grid[i - 1][0];
        }
        for (int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                grid[i][j] += max(grid[i - 1][j], grid[i][j - 1]);
            }
        }
        return grid[m - 1][n - 1];
    }
};

从上到下打印二叉树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    void dfs(TreeNode *root, int deep){
        if (root == NULL){
            return ;
        }
        if (deep >= vec.size()){
            vec.emplace_back(vector<int>());
        }
        vec[deep].push_back(root -> val);
        dfs(root -> left, deep + 1);
        dfs(root -> right, deep + 1);
    }
public:
    vector<vector<int>>vec;
    vector<int> levelOrder(TreeNode* root) {
        vector<int>ans;
        dfs(root, 0);
        for (int i = 0; i < vec.size(); i++){
            for (int j = 0; j < vec[i].size(); j++){
                ans.push_back(vec[i][j]);
            }
        }
        return ans;
    }
};

丑数

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int>dp(n, 0);
        dp[0] = 1;
        int p2 = 0, p3 = 0, p5 = 0;
        for (int i = 1; i < n ; i++){
            dp[i] = min(min(dp[p2] * 2, dp[p3] * 3), dp[p5] * 5);
            if (dp[i] == dp[p2] * 2){
                p2++;
            }
            if (dp[i] == dp[p3] * 3){
                p3++;
            }
            if (dp[i] == dp[p5] * 5){
                p5++;
            }
        }
        return dp[n - 1];
    }
};

二叉搜索树转为有序双向链表

class Node {
public:
    int val;
    Node* left;
    Node* right;

    Node() {}

    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
//中序遍历办法
class Solution {
private:
    void inorderTraverse(Node *root, vector<Node *>&nodes){
        if (root == NULL){
            return ;
        }
        inorderTraverse(root -> left, nodes);
        nodes.push_back(root);
        inorderTraverse(root -> right, nodes);
    }
public:
    Node* treeToDoublyList(Node* root) {
        if (root == NULL){
            return NULL;
        }
        //存放中序遍历的结果
        vector<Node *>nodes;
        inorderTraverse(root, nodes);
        int n = nodes.size();
        for (int i = 0; i < n; i++){
            nodes[i] -> left = nodes[(i + n - 1) % n];
            nodes[i] -> right = nodes[(i + 1) % n];
        }
        return nodes[0];
    }
};
//修改节点的方式
class Solution {
private:
    void inorderTraverse(Node *root){
        if (root == NULL){
            return ;
        }
        inorderTraverse(root -> left);
        {
            //处理当前节点
            if (first == nullptr){
                first = root;
            }
            //当前节点和previous节点相互指向对方，双向链表
            root -> left = previous;
            if (previous != nullptr){
                previous -> right = root;
            }
            //更新previous和last节点
            previous = root;
            last = root;
        }
        inorderTraverse(root -> right);
    }
    Node *previous = nullptr; //记录前一个被访问的节点
    Node *last = nullptr; //记录第一个被访问的节点
    Node *first = nullptr; //记录最后一个被访问的节点
public:
    Node* treeToDoublyList(Node* root) {
        if (root == NULL){
            return NULL;
        }
        inorderTraverse(root);
        first -> left = last;
        last -> right = first;
        return first;
    }
};

股票的最大利润

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.size() == 0){
            return 0;
        }
        int ans = 0;
        int minn = prices[0];
        for (int i = 1; i < prices.size(); i++){
            if (prices[i] < minn){
                minn = prices[i];
            }
            if (prices[i] > minn){
                ans = max(ans, prices[i] - minn);
            }
        }
        return ans;
    }
};

栈的压入、弹出序列

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int>a;
        int index = 0;
        for (int i = 0; i < pushed.size(); i++){
            a.push(pushed[i]);
            while(index < popped.size() && !a.empty() && a.top() == popped[index]){
                a.pop();
                index++;
            }
        }
        return a.empty();
    }
};