【LeetCode】未分类（tag里面没有）（共题）

【334】Increasing Triplet Subsequence （2019年2月14日，google tag）（greedy）

给了一个数组 nums，判断是否有三个数字组成子序列，使得子序列递增。题目要求time complexity: O(N)，space complexity: O(1)

Return true if there exists i, j, k 
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.

题解：可以dp做，LIS 最少 nlog(n)。 这个题可以greedy，可以做到O(N). 我们用两个变量，min1 表示当前最小的元素，min2表示当前第二小的元素。可以分成三种情况讨论：

（1）nums[i] < min1, -> min1 = nums[i]

（2）nums[i] > min1 && nums[i] < min2 -> min2 = nums[i]

（3）nums[i] > min2 -> return true

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int min1 = INT_MAX, min2 = INT_MAX;
        for (auto& num : nums) {
            if (num > min2) {return true;}
            else if (num < min1) {
                min1 = num;
            } else if (min1 < num && num < min2) {
                min2 = num;
            }
        }
        return false;
    }
};

【388】Longest Absolute File Path (2019年3月13日) （google tag，没分类）

给了一个string代表一个文件目录的层级。

The string "dir subdir1 file1.ext subsubdir1 subdir2 subsubdir2 file2.ext" represents:

dir
    subdir1
        file1.ext
        subsubdir1
    subdir2
        subsubdir2
            file2.ext

返回一个文件的绝对路径最长的长度，文件层级之间用slash分割。

Note:

• The name of a file contains at least a . and an extension.
• The name of a directory or sub-directory will not contain a ..

Time complexity required: O(n) where n is the size of the input string.

Notice that a/aa/aaa/file1.txt is not the longest file path, if there is another path aaaaaaaaaaaaaaaaaaaaa/sth.png.

题解：题目要求用O(N)的解法。看清题意，用tab表示当前的层级。一行一行处理，用' '分割行，用' '的个数来决定层级。

class Solution {
public:
    int lengthLongestPath(string input) {
        const int n = input.size();
        vector<int> stk; //
        int start = 0, end = 0;
        int res = 0;
        while (end < n) { //这个while循环处理一行
            int level = 0;
            if (input[end] == '	') { //处理前面的 /t 的个数，决定当前的层级
                while (end < n && input[end] == '	') { ++level; ++end;}
            }         
            while (stk.size() > level) { stk.pop_back(); }     
            string word = "";
            while (end < n && input[end] != '
') { //归档当前的文件夹的名称，和文件名称
                word += input[end];
                ++end;
            }
            int temp = word.size() + (stk.empty() ? 0 : stk.back()) + 1;
            stk.push_back(temp);
            if (temp > res) {
                int p = word.find('.');
                if (p != string::npos && p < word.size() - 1) {
                    res = temp;
                }
            }
            if (end < n && input[end] == '
') {++end;}
        }
        return res == 0 ? res : res - 1;
    }
};

【419】Battleships in a Board （2018年11月25日）（谷歌的题，没分类。）

给了一个二维平面，上面有 X 和 . 两种字符。 一行或者一列连续的 X 代表一个战舰，问图中有多少个战舰。（题目要求one pass， 空间复杂度是常数）

题目说了每两个战舰之间起码有一个 . 作为分隔符，所以不存在正好交叉的情况。

题解：我提交了一个 floodfill 的题解，能过但是显然不满足要求。

discuss里面说，我们可以统计战舰的最上方和最左方，从而来统计战舰的个数。（这个解法是满足要求的。）

class Solution {
public:
    int countBattleships(vector<vector<char>>& board) {
        n = board.size();
        m = board[0].size();
        int ret = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (board[i][j] == '.') {continue;}
                if ((i == 0 || board[i-1][j] != 'X') && (j == 0 || board[i][j-1] != 'X')) {ret++;}
            }
        }
        return ret;
    }
    int n, m;
};

【427】Construct Quad Tree（2019年2月12日）

建立四叉树。https://leetcode.com/problems/construct-quad-tree/description/

题解：递归

/*
// Definition for a QuadTree node.
class Node {
public:
    bool val;
    bool isLeaf;
    Node* topLeft;
    Node* topRight;
    Node* bottomLeft;
    Node* bottomRight;

    Node() {}

    Node(bool _val, bool _isLeaf, Node* _topLeft, Node* _topRight, Node* _bottomLeft, Node* _bottomRight) {
        val = _val;
        isLeaf = _isLeaf;
        topLeft = _topLeft;
        topRight = _topRight;
        bottomLeft = _bottomLeft;
        bottomRight = _bottomRight;
    }
};
*/
class Solution {
public:
    Node* construct(vector<vector<int>>& grid) {
        const int n = grid.size();
        vector<int> tl = {0, 0}, br = {n-1, n-1};
        return construct(grid, tl, br);
    }
    Node* construct(vector<vector<int>>& grid, vector<int> tl, vector<int> br) {
        if (tl == br) {
            Node* root = new Node(grid[tl[0]][tl[1]], true, nullptr, nullptr, nullptr, nullptr);
            return root;
        }
        int t = tl[0], b = br[0], l = tl[1], r = br[1];
        bool split = false;
        for (int i = t; i <= b; ++i) {
            for (int j = l; j <= r; ++j) {
                if (grid[i][j] != grid[t][l]) {
                    split = true;
                }
            }
        }
        if (!split) {
            Node* root = new Node(grid[tl[0]][tl[1]], true, nullptr, nullptr, nullptr, nullptr);
            return root;
        }
        Node* root = new Node(0, false, nullptr, nullptr, nullptr, nullptr);
        int newx = (t + b) / 2, newy = (l + r) / 2;
        root->topLeft = construct(grid, tl, {newx, newy});
        root->topRight = construct(grid, {t, newy+1}, {newx, r});
        root->bottomLeft = construct(grid, {newx + 1, l}, {b, newy});
        root->bottomRight = construct(grid, {newx+1, newy+1}, br);
        return root;
    }
};

【433】 Minimum Genetic Mutation（2018年12月28日，周五）（谷歌的题，没分类）

给了两个字符串基因序列start 和 end，和一个 word bank，每次操作需要把当前序列，通过一次变异转换成word bank里面的另外一个词，问从 start 转换成 end，至少需要几步？

题解：问最少几步，直接bfs解

class Solution {
public:
    int minMutation(string start, string end, vector<string>& bank) {
        const int n = bank.size();
        vector<int> visit(n, 0);
        queue<string> que;
        que.push(start);
        int step = 0;
        int ret = -1;
        while (!que.empty()) {
            step++;
            const int size = que.size();
            for (int i = 0; i < size; ++i) {
                string cur = que.front(); que.pop();
                for (int k = 0; k < n; ++k) {
                    if (visit[k]) {continue;}
                    if (diff(bank[k], cur) == 1) {
                        visit[k] = 1;
                        que.push(bank[k]);
                        if (bank[k] == end) {
                            ret = step;
                            return ret;
                        }
                    }
                }
            }
        }
        return ret;
    }
    int diff (string s1, string s2) {
        if (s1.size() != s2.size()) {return -1;}
        int cnt = 0;
        for (int i = 0; i < s1.size(); ++i) {
            if (s1[i] != s2[i]) {
                ++cnt;
            }
        } 
        return cnt;
    }
};

【481】 Magical String （2019年3月28日）（google tag）

给定一个string，S = "1221121221221121122……"，生成规则是

If we group the consecutive '1's and '2's in S, it will be:

1 22 11 2 1 22 1 22 11 2 11 22 ......

and the occurrences of '1's or '2's in each group are:

1 2 2 1 1 2 1 2 2 1 2 2 ......

You can see that the occurrence sequence above is the S itself.

题目的问题是：给定一个数字 n，代表 s 的长度，问在长度为 n 的 s 中，有多少个 1。

题解：其实这道题可以归类为 2 pointers，我们想象一下，fast 可以每次走一步或者走两步，slow 每次走一步，slow 每次走一步，它指向的数字，就代表fast每次要走一步还是走两步。

比如一开始 s = "122", slow = 2 (代表 slow 指向 index = 2 的位置）这个时候，我们需要在 s 的末尾增加两个数字，增加2还是1呢，需要和当前 s 的末尾不相同就可以了。

这样的话，我们就能生成长度为 n 的 s 序列，然后数一下里面有多少个 1 就可以了。

class Solution {
public:
    int magicalString(int n) {
        if (n == 0) {return 0;}
        string s = "122";
        int idx = 2, res = 1;
        while (s.size() < n) {
            char c = '3' - s.back() + '0';
            if (s[idx] == '1') {
                s.push_back(c);  
                if (s.size() <= n && c == '1') {++res;}
            } else {
                s.push_back(c);  
                if (s.size() <= n && c == '1') {++res;}
                s.push_back(c);  
                if (s.size() <= n && c == '1') {++res;}
            }
            ++idx;
        }
        return res;
    }
};

【504】Base 7 （2018年11月25日）

Given an integer, return its base 7 string representation.

Example 1:
Input: 100
Output: "202"

Example 2:
Input: -7
Output: "-10"

Note: The input will be in range of [-1e7, 1e7].

题解：直接按照进制转换

class Solution {
public:
    string convertToBase7(int num) {
        bool negative = false;
        if (num < 0) {
            negative = true;
            num = -num;
        }
        string ret = "";
        while (num != 0) {
            int mod = num % 7;
            num = num / 7;
            ret = to_string(mod) + ret;
        }
        ret = negative ? "-" + ret : ret;
        ret = ret == "" ? "0" : ret;
        return ret;
    }
};

【506】Relative Ranks（2018年11月25日）

Given scores of N athletes, find their relative ranks and the people with the top three highest scores, who will be awarded medals: "Gold Medal", "Silver Medal" and "Bronze Medal".

Example 1:
Input: [5, 4, 3, 2, 1]
Output: ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]
Explanation: The first three athletes got the top three highest scores, so they got "Gold Medal", "Silver Medal" and "Bronze Medal". 
For the left two athletes, you just need to output their relative ranks according to their scores.

Note:

1. N is a positive integer and won't exceed 10,000.
2. All the scores of athletes are guaranteed to be unique.

class Solution {
public:
    vector<string> findRelativeRanks(vector<int>& nums) {
        const int n = nums.size();
        map<int, int, greater<int>> mp;
        for (int i = 0; i < nums.size(); ++i) {
            int score = nums[i];
            mp[score] = i;
        }
        vector<string> ret(n);
        int cnt = 1;
        for (auto e : mp) {
            int idx = e.second;
            if (cnt <= 3) {
                if (cnt == 1) {
                    ret[idx] = "Gold Medal";
                }
                if (cnt == 2) {
                    ret[idx] = "Silver Medal";
                }
                if (cnt == 3) {
                    ret[idx] = "Bronze Medal";
                }
                ++cnt;
            } else {
                ret[idx] = to_string(cnt++);
            }
        }
        return ret;
    }
};

【540】Single Element in a Sorted Array（2018年12月8日，本题不是自己想的，看了花花酱的视频，需要review）

给了一个有序数组，除了一个数字外，其他所有数字都出现两次。用 O(logN) 的时间复杂度，O(1) 的空间复杂度把只出现一次的那个数字找出来。

题解：二分。怎么二分。我们的目的的找到第一个不等于它partner的数字。如何定义一个数的 partner，如果 i 是偶数，那么 nums[i] 的partner是 nums[i+1]。如果 i 是奇数，nums[i] 的partner 是 i-1。

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        const int n = nums.size();
        int left = 0, right = n;
        while (left < right) {
            int mid = (left + right) / 2;
            int partner = mid % 2 == 0 ? mid + 1 : mid - 1;
            if (nums[mid] == nums[partner]) {
                left = mid + 1;
            } else {
                right = mid;   
            }
        }
        return nums[left];
    }
};

【797】All Paths From Source to Target （2018年11月27日）

给了一个 N 个结点的 DAG，结点标号是0 ～ N-1，找到从 node 0 到 node N-1 的所有路径，并且返回。

Example:
Input: [[1,2], [3], [3], []] 
Output: [[0,1,3],[0,2,3]] 
Explanation: The graph looks like this:
0--->1
|    |
v    v
2--->3
There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.

题解：dfs可以解。

class Solution {
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        n = graph.size();
        vector<vector<int>> paths;
        vector<int> path(1, 0);
        dfs(graph, paths, path);
        return paths;
    }
    void dfs(const vector<vector<int>>& graph, vector<vector<int>>& paths, vector<int>& path) {
        if (path.back() == n-1) {
            paths.push_back(path);
            return;
        }
        int node = path.back();
        for (auto adj : graph[node]) {
            path.push_back(adj);
            dfs(graph, paths, path);
            path.pop_back();
        }
    }
    int n;
};