跳至主要内容

博文

目前显示的是 二月, 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));
                    }
                    tmp.push_back(p)…

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);

            return max(l1, max(root->val, max(l1 + root->…

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)
            {
                vector<int> ret1;
                ret1.push_back(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 != 0)
        {
            left *= 10;
 …

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;
                    for (int z = 0; z < point…

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++)
            {
                tmp.push_bac…

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;
                ss.erase(i, 1);

                m…

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, 0, -1 };

        tmp[i][j] = 1;

        for (in…

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 <= rightx.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 + "|";
            ret += str;
            if (node->…

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 == INT_MAX)
            {
                break;
 …