- 博客(15)
- 收藏
- 关注
原创 字典树
创建字典树class Trie {private: vector<Trie*> children; bool isEnd;public: /** Initialize your data structure here. */ Trie() : children(26), isEnd(false) {} /** Inserts a word into the trie. */ void insert(string word) {
2021-04-14 15:12:15
161
原创 中缀表达式计算器
中缀表达式直接计算计算器class Solution {private: stack<char> opt; stack<long> nums;public: bool isOperator(char op){ return (op=='+')|| (op=='*') || (op=='/') ||op==('-')||(op=='(')||(op==')'); } //栈内优先级 int isp(char ch)
2021-03-11 11:33:02
175
原创 中序遍历二叉树迭代方法
class Solution {public: vector<int> inorderTraversal(TreeNode* root) { vector<int> res; TreeNode *predecessor = nullptr; while (root != nullptr) { if (root->left != nullptr) { // pred
2020-10-15 20:25:32
393
转载 快速幂方法求X的n次幂
快速幂:链接:https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/solution/mian-shi-ti-16-shu-zhi-de-zheng-shu-ci-fang-kuai-s/double myPow(double x, int n) { if(n == 0 || x == 1.0) return 1; if(x == 0.0 && n < 0) return
2020-10-14 14:35:28
889
原创 堆解决topK问题
数据量过大会超时class Solution {public: vector<int> getLeastNumbers(vector<int>& arr, int k) { vector<int> ans; while(k>0){ heap(arr); ans.push_back(arr[0]); arr[0]=arr.back();
2020-09-25 16:10:35
210
原创 根据后序遍历和中序遍历建树的方法
一,递归,每次将中序和后序重新按照根节点分割/** * 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
2020-09-25 11:00:56
778
原创 leetcode-滑动窗口最大值问题
class Solution {private: class MyQueue { //单调队列(从大到小) public: deque<int> que; // 使用deque来实现单调队列 // 每次弹出的时候,比较当前要弹出的数值是否等于队列出口元素的数值,如果相等则弹出。 // 同时pop之前判断队列当前是否为空。 void pop (int value) { if (!que.emp
2020-09-24 22:21:32
470
原创 动态规划求n个骰子掷出的点数概率集合问题
class Solution {//动态规划 public: vector<double> twoSum(int n) { int dp[12][70]={0};//dp[i][j] 表示投掷i个骰子之后j点数出现的次数 for(int i=1;i<7;i++){//初始化第一次 dp[1][i] = 1; } // 对于状态转移 dp[n][j] = dp[n-1][j-1]+dp[n-1]
2020-09-24 21:40:16
324
原创 学好计组——加法模拟
class Solution {public: int add(int a, int b) { while (b) { int carry = (unsigned int)(a & b) << 1;//取得相加进位项并且移位 a ^= b;//取得不进位项 b = carry; } return a; }};...
2020-09-24 16:37:44
134
原创 最低公共祖先
class Solution {public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {//返回最低公共祖先 if(root == NULL || p== NULL || q == NULL){ return NULL; } if(root == p || root == q){ return
2020-09-24 16:17:11
105
原创 一种比单纯数组hash效率更高的方式
相比一般的设置数组hash,消耗更少的空间class Solution {public: bool isUnique(string s) { int x = 0; for(char c : s) { if(x & (1 << (c - 'a'))) { // c - 'a':将字符转换为0-25的数字 return false; } else {
2020-09-24 15:46:26
137
原创 递增序列使用Morris投票减少hash空间使用
写的比较丑陋…/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ //DFS&HASH 有额外空间开销 //中序遍历 , 树变顺序表 , 摩尔斯投票clas
2020-09-24 15:27:00
85
原创 KMP算法与AC自动机(一):KMP算法的实现
字符串模式匹配的一种高效方式,KMP算法int* buildNext(char* P) //构造模式串P的next表{ size_t m = strlen(P), j = 0; int* N = new int[m];//next表 int t = N[0] = -1;//模式串指针 while (j < m - 1) { if (0 > t || P[j] == P[t])//匹配 { j++;
2020-09-23 23:14:08
410
原创 有序数组建立高度最低二叉排序树
class Solution {public: TreeNode* sortedArrayToBST(vector<int>& nums) { int right = nums.size()-1; return helper(nums,0,right); } TreeNode * helper(vector<int>&nums,int left,int right){ if(left>ri
2020-09-22 20:20:27
331
原创 回溯法zsbd
回溯法解搜索问题`class Solution {public:bool canTransformed(string A, string B) {if (A.size() != B.size()) {return false;}int count = 0;for (int i = 0; i < A.size(); i++) {if (A[i] != B[i]) {count++;}}return count == 1;}bool hasRoutine(string cur
2020-09-21 00:33:18
110
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人