跳至主要内容

博文

目前显示的是 二月, 2019的博文

68. 文本左右对齐

class Solution { public:     vector<string> fullJustify(vector<string>& words, int L) {         vector<string> ans;         const int n = words.size();         for (int i = 0; i < n;) {             int num = 0, len = 0;             while (i + num < n && words[i + num].size() + len <= L - num) {                 len += words[i + num].size();                 ++num;             }             string tmp = words[i];             for (int j = 1; j < num; ++j) {                 if (i + num >= n) tmp += " ";                 else tmp += string((L - len) / (num - 1) + (j  <= (L - len) % (num - 1)), ' ');                 tmp += words[i + j];             }             tmp += string(L - tmp.size(), ' ');             ans.push_back(tmp);             i += num;         }         return ans;     } };

40. 组合总和 II

class Solution { public:     vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {         vector<vector<pair<int, vector<int>>>> dp;         for (int i = 0; i < candidates.size(); i++)         {             vector<pair<int, vector<int>>> tmp;             int cur = candidates[i];             if (i > 0)             {                 vector<pair<int, vector<int>>> & pre = dp[i - 1];                 for (int j = 0; j < pre.size(); j++)                 {                     pair<int, vector<int>> & p = pre[j];                     int n = p.first;                     vector<int> & v = p.second;                     if (n + cur <= target)                     {                         vector<int> vv = v;                         vv.push_back(cur);                         tmp.push_back(make_pair(n + cur, vv));                     }                

124. 二叉树中的最大路径和

/**  * 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:     int maxPathSum(TreeNode* root) {                 if (root->left != 0 && root->right != 0)         {             int l = maxPathSum(root->left);             int r = maxPathSum(root->right);             int l1 = maxPathSum3(root->left);             int r1 = maxPathSum3(root->right);             int m1 = l1 + r1 + root->val;             int m2 = l1 + root->val;             int m3 = r1 + root->val;             int m4 = root->val;             int m5 = max(l, r);             int m6 = max(l1, r1);                         return max(m1, max(m2, max(m3, max(m4, max(m5, m6)))));         }                 if (root->left != 0)         {             int l = maxPathSum(root->left);             int l1 = maxPathSum3(root->left);      

336. 回文对

class Solution { public:     bool isPalindrome(string word, int left, int right) {         while (left < right)             if(word[left++] != word[right--]) return false;         return true;     }         string reverse(string tmp)     {         string ret;         for (int i = tmp.length() - 1; i >= 0; i--)         {             ret.push_back(tmp[i]);         }         return ret;     }         vector<vector<int>> palindromePairs(vector<string>& words) {                 vector<vector<int>> ret;                 map<string, int> index;         set<int> st;                 for (int i = 0; i < words.size(); i++)         {             index[words[i]] = i;             st.insert(words[i].size());         }                 for (int i = 0; i < words.size(); i++)         {             string tmp = words[i];             tmp = reverse(tmp);             if (index.find(tmp) != index.end() && index[tmp] != i)             {          

386. 字典序排数

class Solution { public:     vector<int> lexicalOrder(int n) {         vector<int> ret;         lexicalOrder2(n, 0, ret);         return ret;     }         void lexicalOrder2(int n, int pre, vector<int> & ret)     {         if (ret.size() >= n)         {             return;         }                 for (int i = (pre==0?1:0);i<=9;i++)         {             if ((long long)pre*10+i <= (long long)n)             {                 ret.push_back(pre*10+i);                 lexicalOrder2(n, pre*10+i, ret);             }         }     } };

242. 有效的字母异位词

class Solution { public:     bool isAnagram(string s, string t) {         char data1[26] = {0};         char data2[26] = {0};                 if (s.length() != t.length())             return false;                 for (int i = 0; i < s.length(); i++)         {             data1[s[i] - 'a']++;         }         for (int i = 0; i < t.length(); i++)         {             data2[t[i] - 'a']++;         }                 for (int i = 0; i < 26; i++)         {             if (data1[i] != data2[i])             {                 return false;             }         }         return true;     } };

344. 反转字符串

class Solution { public:     void reverseString(vector<char>& s) {         int i = 0;         int j = s.size() - 1;         while (i < j)         {             char tmp = s[i];             s[i] = s[j];             s[j] = tmp;             i++;             j--;         }     } };

387. 字符串中的第一个唯一字符

class Solution { public:     int firstUniqChar(string s) {         map<char, pair<int, int>> tmp;         for (int i = 0; i < s.length(); i++)         {             if (tmp.find(s[i]) != tmp.end())             {                 tmp[s[i]].second++;             }             else             {                 tmp[s[i]] = make_pair(i, 0);             }         }                 int ret = INT_MAX;         for (map<char, pair<int, int>>::iterator it = tmp.begin(); it != tmp.end(); it++)         {             if (it->second.second == 0 && it->second.first < ret)             {                 ret = it->second.first;             }         }                 return ret != INT_MAX?ret:-1;     } };

125. 验证回文串

class Solution { public:         bool isValid(char c)     {         if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9'))         {             return true;         }         return false;     }         bool isPalindrome(string s) {         int i = 0;         int j = s.length() - 1;         while (i < j)         {             if (!isValid(s[i]))             {                 i++;                 continue;             }             if (!isValid(s[j]))             {                 j--;                 continue;             }             if (tolower(s[i]) != tolower(s[j]))             {                 return false;             }             i++;             j--;         }         return true;     } };

326. 3的幂

class Solution { public:     bool isPowerOfThree(int n) {         while (n > 0)         {             if (n == 1)                 return true;             if (n % 3 != 0)                 return false;             n /= 3;         }         return false;     } };

268. 缺失数字

class Solution { public:     int missingNumber(vector<int>& nums) {         int sum = nums.size() * (nums.size() + 1) / 2;                 int sum2 = 0;         for (int i = 0; i < nums.size(); i++)         {             sum2 += (nums[i]);         }                 return sum - sum2;     } };

204. 计数质数

class Solution { public:     int countPrimes(int n)     {         if (n <= 1)         {             return 0;         }         bool * isPrime = new bool[n + 1];         for (int i = 0; i < n + 1; i++)         {             isPrime[i] = true;         }         vector<int> prime;         int res = 0;         for (int i = 2; i < n; i++)         {             if (isPrime[i])             {                 prime.push_back(i);             }             for (int j = 0; j < prime.size() && i * prime[j] < n; j++)             {                 isPrime[i * prime[j]] = false;                 if (i % prime[j] == 0)                 {                     break;                 }             }         }         return prime.size();     } };

191. 位1的个数

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

190. 颠倒二进制位

class Solution { public:     uint32_t reverseBits(uint32_t n) {                 int ret = 0;         for (int i = 0; i < 32; i++)         {             int mask = 1 << i;             int tmp = mask & n;             tmp = (tmp >> i) & 1;             tmp = tmp << (32 - i - 1);             ret = ret | tmp;         }         return ret;     } };

172. 阶乘后的零

class Solution { public:     int trailingZeroes(int n) {         int total = 0;         while (n >= 1)         {             n /= 5;             total += n;         }         return total;     } };

166. 分数到小数

class Solution { public:         string itoa(long long i)     {         char buff[100];         sprintf(buff, "%lld", i);         return buff;     }     string fractionToDecimal(int num, int den) {         long long numerator = num;         long long denominator = den;         int neg = 1;         if (numerator > 0 && denominator < 0)         {             neg = -1;         }         if (numerator < 0 && denominator > 0)         {             neg = -1;         }         numerator = abs(numerator);         denominator = abs(denominator);         long long a = numerator / denominator;         if (numerator == a * denominator)         {             return (neg<0?"-":"")+itoa(a);         }         string ret = (neg<0?"-":"")+itoa(a);         ret += ".";         long long left = numerator - a * denominator;         vector<pair<int, int>> c;         int loop = -1;         while (left !=

149. 直线上最多的点数

/**  * Definition for a point.  * struct Point {  *     int x;  *     int y;  *     Point() : x(0), y(0) {}  *     Point(int a, int b) : x(a), y(b) {}  * };  */ class Solution { public:     int maxPoints(vector<Point>& points) {                 if (points.size() <= 2)         {             return points.size();         }                 set<double> find;         set<double> findx;         set<double> findy;         int max = 0;         for (int i = 0; i < points.size() - 1; i++)         {             for (int j = i + 1; j < points.size(); j++)             {                 if (points[j].x != points[i].x && points[j].y != points[i].y)                 {                     double d = (double)(points[j].x - points[i].x) / (points[j].y - points[i].y);                     if (find.find(d)!=find.end())                     {                         continue;                     }                     find.insert(d);                     int num = 1;

136. 只出现一次的数字

class Solution { public:     int singleNumber(vector<int>& nums) {         int ret = 0;         for (int i = 0; i < nums.size(); i++)         {             ret ^= nums[i];         }         return ret;     } };

200. 岛屿的个数

class Solution { public:         void numIslands2(vector<vector<char>>& grid, int i, int j, int & nn, vector<vector<char>> & find) {         int m = grid.size();         int n = grid[0].size();         if (i >= 0 && i < m && j >= 0 && j < n && grid[i][j] == '1' && find[i][j] == 0)         {             find[i][j] = nn;             numIslands2(grid, i + 1, j, nn, find);             numIslands2(grid, i, j + 1, nn, find);             numIslands2(grid, i - 1, j, nn, find);             numIslands2(grid, i, j - 1, nn, find);         }     }     int numIslands(vector<vector<char>>& grid) {         if (grid.empty())             return 0;                 int m = grid.size();         int n = grid[0].size();         vector<vector<char>> find;         for (int i = 0; i < m; i++)         {             vector<char> tmp;             for (int j = 0; j < n; j++)       

127. 单词接龙

class Solution { public:     int ladderLength(string beginWord, string endWord, vector<string>& wordList) {                 map<int, map<string, vector<string>>> tree;         for (int i = 0; i < wordList.size(); i++)         {             for (int j = 0; j < wordList[i].size(); j++)             {                 string s = wordList[i];                 s.erase(j, 1);                 map<string, vector<string>> & m = tree[j];                 m[s].push_back(wordList[i]);             }         }         list<pair<string, int>> queue;         queue.push_back(make_pair(beginWord,1 ));         set<string> tmp;         while (true)         {             if (queue.empty())                 return 0;             string s = queue.front().first;             int curstep = queue.front().second;             queue.pop_front();             for (int i = 0; i < s.size(); i++)             {                 string ss = s;               

329. 矩阵中的最长递增路径

class Solution { public:         int longestIncreasingPath(vector<vector<int>> &matrix)     {         if (matrix.size() == 0)             return 0;                 int xmax = matrix.size();         int ymax = matrix[0].size();         int ** tmp = new int*[xmax];         for (int i = 0; i < xmax; i++)         {             tmp[i] = new int[ymax];             for (int j = 0; j < ymax; j++)             {                 tmp[i][j] = 0;             }         }         int maxlen = 0;         for (int i = 0; i < xmax; i++)         {             for (int j = 0; j < ymax; j++)             {                 maxlen = max(maxlen, dp(matrix, i, j, tmp, xmax, ymax));             }         }         return maxlen;     }     int dp(vector<vector<int>> &matrix, int i, int j, int ** tmp, int xmax, int ymax)     {         if (tmp[i][j] != 0)         {             return tmp[i][j];         }         int xdir[4] = { 1, 0, -1, 0 };         int ydir[4] = { 0, 1,

322. 零钱兑换

class Solution { public:     int coinChange(vector<int>& coins, int amount) {              if (amount == 0)             return 0;                 vector<int> dp;         int max = amount;         for (int i = 0; i < coins.size(); i++)         {             if (coins[i] > max && coins[i] != INT_MAX)             {                 max = coins[i];             }         }         dp.resize(max + 1, -1);         for (int i = 0; i < coins.size(); i++)         {             if (coins[i] < dp.size())                 dp[coins[i]] = 1;         }         for (int i = 1; i <= amount; i++)         {             int mi = INT_MAX;             for (int j = 0; j < coins.size(); j++)             {                 if (i > coins[j] && dp[i - coins[j]] != -1)                 {                     int num = min(dp[i - coins[j]] + 1, dp[i]!=-1? dp[i]:INT_MAX);                     if (mi > num)                     {                         mi = num;      

300. 最长上升子序列

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

279. 完全平方数

class Solution { public:     int numSquares(int n) {         int * dp = new int[max(n + 1, 3)];         dp[0] = 0;         dp[1] = 1;         dp[2] = 2;         for (int i = 3; i <= n; i++)         {             int min = INT_MAX;             for (int j = sqrt(i); j >= 1; j--)             {                 int mm = dp[i - j * j] + 1;                 if (min > mm)                 {                     min = mm;                 }             }             dp[i] = min;         }         return dp[n];     }     };

198. 打家劫舍

class Solution { public:     int rob(vector<int>& nums) {         vector<int> ret;         int mm = 0;         for (int i = 0; i < nums.size(); i++)         {             int m = max(i>=2?(ret[i-2]+nums[i]):nums[i], i>=1?ret[i-1]:0);             ret.push_back(m);             if (m > mm)             {                 mm = m;             }         }         return mm;     }         int max(int a, int b)     {         return a>b?a:b;     } };

maven发布到中心仓库

gpg生成公钥私钥 在maven里添加 < servers > < server > < id > sonatype-nexus-snapshots </ id > < username > Sonatype网站的账号 </ username > < password > Sonatype网站的密码 </ password > </ server > < server > < id > sonatype-nexus-staging </ id > < username > Sonatype网站的账号 </ username > < password > Sonatype网站的密码 </ password > </ server > </ servers > 执行mvn clean deploy -P sonatype-oss-release 登录https://oss.sonatype.org/#stagingRepositories

utuntu添加启动项

Make sure /etc/rc.local is executable and that the script it calls is also executable. $ ls -l /etc/rc.local -rwxr-xr-x 1 root root 419 2010-08-27 11:26 /etc/rc.local   Make sure rc.local has a shebang line (which is the default): $ head -n1 /etc/rc.local #!/bin/sh -e

128. 最长连续序列

class Solution { public:     int longestConsecutive(vector<int>& nums) {         map<int,int> tmp;         int max = 0;         for (int i = 0; i < nums.size(); i++)         {             if (tmp.find(nums[i]) == tmp.end())             {                 int l = tmp.find(nums[i]-1) != tmp.end()?tmp[nums[i]-1]:0;                 int r = tmp.find(nums[i]+1) != tmp.end()?tmp[nums[i]+1]:0;                 int n = l+r+1;                 if (n>max)                 {                     max = n;                 }                 tmp[nums[i]] = n;                 tmp[nums[i] - l] = n;                 tmp[nums[i] + r] = n;             }         }         return max;     } };

324. 摆动排序 II

class Solution { public:     void wiggleSort(vector<int>& nums) {                 if (nums.size() <= 1)         {             return;         }         sort(nums.begin(), nums.end());         int right = nums.size() - 1;         int start = right / 2;         int left = start - 1;         vector<int> ret;         ret.push_back(nums[start]);         while (ret.size() < nums.size())         {             if (ret.size() < nums.size())                 ret.push_back(nums[right--]);             if (ret.size() < nums.size())                 ret.push_back(nums[left--]);         }         nums = ret;     } };

179. 最大数

class Solution { public:     string largestNumber(vector<int>& nums) {         std::sort(nums.begin(), nums.end(), [](int a, int b)         {             int a1 = a;             int n = 1;             long a2 = 10;             while (a1 >= 10)             {                 a1 /= 10;                 a2 *= 10;                 n++;             }             int b1 = b;             int m = 1;             long b2 = 10;             while (b1 >= 10)             {                 b1 /= 10;                 b2 *= 10;                 m++;             }             return a*b2+b>b*a2+a;         });                 if (nums[0] == 0)         {             return "0";         }         string ret = "";         for (int i = 0; i < nums.size(); i++)         {             char buff[100];             sprintf(buff, "%d", nums[i]);             ret += buff;         }         return ret;     } };

218. 天际线问题

class Solution { public:     vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {                priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> leftx;         for (int i = 0; i < buildings.size(); i++)         {             vector<int> b = buildings[i];             leftx.push(make_pair(b[0], i));         }         priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> rightx;         for (int i = 0; i < buildings.size(); i++)         {             vector<int> b = buildings[i];             rightx.push(make_pair(b[1], i));         }         map<int, int> h;         int lasth = 0;         int x = 0;         vector<pair<int, int>> ret;         while (!leftx.empty() || !rightx.empty())         {             int next = 0;             if (!leftx.empty() && leftx.top().first <=

297. 二叉树的序列化与反序列化

/**  * Definition for a binary tree node.  * struct TreeNode {  *     int val;  *     TreeNode *left;  *     TreeNode *right;  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}  * };  */ class Codec { public:     string itoa(long i)     {         char buff[100];         sprintf(buff, "%lld", i);         return buff;     }         // Encodes a tree to a single string.     string serialize(TreeNode* root) {         string ret = "";         if (root == 0)             return ret;                 stack<TreeNode*> tmp;         tmp.push(root);                 while (!tmp.empty())         {             TreeNode* node = tmp.top();             tmp.pop();             string idstr = itoa((long)node);             string data = itoa(node->val);             string left = itoa((long)node->left);             string right = itoa((long)node->right);             string str = idstr + "," + data + "," + left + ","+ right + "|&quo

378. 有序矩阵中第K小的元素

class Solution { public:     int kthSmallest(vector<vector<int>>& matrix, int k) {         for (int i = 0; i < k-1; i++)         {             pop(matrix);         }         return matrix[0][0];     }             void swap(std::vector<std::vector<int>>& matrix, int i, int j, int ii, int jj)     {         int tmp = matrix[i][j];         matrix[i][j] = matrix[ii][jj];         matrix[ii][jj] = tmp;     }     void pop(std::vector<std::vector<int>>& matrix)     {         int n = matrix.size();         int i = 0;         int j = 0;         matrix[i][j] = INT_MAX;         while (i < n - 1 || j < n - 1)         {             int a = INT_MAX;             if (i < n - 1)             {                 a = matrix[i + 1][j];             }             int b = INT_MAX;             if (j < n - 1)             {                 b = matrix[i][j + 1];             }             if (a == b && a == I