Posted on | In , |
Words count in article: 98 | Reading time ≈ 1 
1
2
Input: num1 = "2", num2 = "3"
Output: "6"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    string multiply(string num1, string num2) {
        string sum(num1.size()+num2.size(), '0');
        
        for(int i = num1.size() - 1; 0 <= i; --i){
            int carry = 0;    
            for(int j = num2.size()-1; 0 <= j; --j){
                int tmp = (sum[i+j+1]-'0') + (num1[i]-'0')*(num2[j]-'0') + carry;
                sum[i+j+1] = tmp % 10 + '0';
                carry = tmp / 10;
            }
            sum[i] += carry;
        }
        
        size_t start = sum.find_first_not_of('0');
        if(string::npos != start){
            return sum.substr(start);
        }
        return "0";
    }
};

Posted on | In , |
Words count in article: 141 | Reading time ≈ 1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Example 1:

Input: [1,7,4,9,2,5]
Output: 6
Explanation: The entire sequence is a wiggle sequence.
Example 2:

Input: [1,17,5,10,13,15,10,5,16,8]
Output: 7
Explanation: There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].
Example 3:

Input: [1,2,3,4,5,6,7,8,9]
Output: 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if(nums.size() < 2)
            return nums.size();
        
        int prevdiff = nums[1]-nums[0];
        int count = prevdiff != 0 ? 2 : 1;
        for(int i=2; i<nums.size(); i++){
            int diff = nums[i]-nums[i-1];
            if((diff > 0 && prevdiff <= 0) || (diff < 0 && prevdiff >= 0)){
                count++;
                prevdiff = diff;
            }
        }
        return count;
    }
};

Posted on | In , |
Words count in article: 548 | Reading time ≈ 3

Given a list of strings words representing an English Dictionary, find the longest word in words that can be built one character at a time by other words in words. If there is more than one possible answer, return the longest word with the smallest lexicographical order.

If there is no answer, return the empty string.

Example 1:

Input:

words = [“w”,”wo”,”wor”,”worl”, “world”]

Output: “world”

Explanation:

The word “world” can be built one character at a time by “w”, “wo”, “wor”, and “worl”.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    string longestWord(vector<string>& words) {
        sort(words.begin(), words.end());
        string ret;
        unordered_set<string> tri;
        
        for(auto str: words){
            if(str.size() == 1 || tri.count(str.substr(0, str.size()-1))){
                ret = str.size() > ret.size() ? str : ret;
                tri.insert(str);
            }
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    struct Node{
        bool isWord;
        Node* next[26];
    };
    string ret = "";
    
    string longestWord(vector<string>& words) {
        Node* root = new Node();
        root->isWord = true;
        
        for(int i=0 ;i<words.size(); i++){
            Node* tmp = root;
            for(int j=0; j<words[i].size(); j++){
                if(tmp->next[words[i][j]-'a']==NULL)
                    tmp->next[words[i][j]-'a'] = new Node();
                tmp = tmp->next[words[i][j]-'a'];
            }
            tmp->isWord = true;
        }
        
        DFS(root, "");
        return ret;
    }
    
    void DFS(Node* root, string path){
        if(root == NULL || root->isWord == false){
            path.pop_back();
            if(path.size() > ret.size()) ret = path;
            else if(path.size() == ret.size()  &&  ret > path) ret = path;
            return;
        }
        for(int i=0; i<26; i++){
            path.append(1, 'a'+i);
            DFS(root->next[i], path);
            path.pop_back();
        }
    }
};

648. Replace Words

1
2
3
Input: dict = ["cat", "bat", "rat"]
sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class Solution {
public:
    struct Node{
        bool isWord;
        Node* next[26];
    };
   
    string replaceWords(vector<string>& dict, string sentence) {
        Node* root = new Node();
        root->isWord = true;
        string ret = "";
        
        for(int i=0; i<dict.size(); i++)
        {
            Node* tmp = root;
            for(int j=0; j<dict[i].size(); j++){
                if(tmp->next[dict[i][j]-'a'] == NULL)
                    tmp->next[dict[i][j]-'a'] = new Node();
                tmp = tmp->next[dict[i][j]-'a'];
            }
            tmp->isWord = true;
        }
        
        string tmpstr = "";
        
        for(int i=0; i<sentence.size(); i++){
            if(sentence[i] == ' ' || i == sentence.size()-1){
                if(i == sentence.size()-1)
                    tmpstr += sentence[i];
                Node* t = root;
                int flag = 0;
                int curj = 0;
                for(int j=0; j<tmpstr.size(); j++){
                    if(t->isWord == true && t != root)
                    {
                        flag = 1;
                        curj = j;
                        break;
                    }
                    if(t->next[tmpstr[j]-'a'] != NULL)
                        t = t->next[tmpstr[j]-'a'];
                    else
                        break;
                }
                if(flag == 1){
                    for(int z=0; z<curj; z++)
                        ret += tmpstr[z];
                    tmpstr = "";
                }
                else{
                    ret += tmpstr;
                    tmpstr = "";
                }
                
                if(i != sentence.size()-1)
                    ret += " ";
                
            }
            else{
                tmpstr += sentence[i];
            }
        }
        
        return ret;
    }
};

Posted on | In , |
Words count in article: 660 | Reading time ≈ 3

1221. Split a String in Balanced Strings

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int balancedStringSplit(string s) {
        int l=0, r=0;
        int count = 0;
        for(auto i: s){
            if(i == 'L')
                l++;
            else
                r++;
            if(l == r && l!=0){
                count++;
                l = 0;
                r = 0;
            }
        }
        return count;
    }
};

1222. Queens That Can Attack the King

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    vector<vector<int>> ret;
    void helper(vector<vector<int>> &queens, int i, int j, int deli, int delj){
        if(i<0 || j<0 || i>=8 || j>=8)
            return;
        if(queens[i][j]){
            vector<int> ret1;
            ret1.push_back(i);
            ret1.push_back(j);
            ret.push_back(ret1);
            return;
        }
        helper(queens, i+deli, j+delj, deli, delj);
    }
    vector<vector<int>> queensAttacktheKing(vector<vector<int>>& queens, vector<int>& king) {
        vector<vector<int>> gh(10, vector<int>(10, 0));
        for(auto i: queens){
            gh[i[0]][i[1]] = 1;
        }
        helper(gh, king[0], king[1], -1, -1);
        helper(gh, king[0], king[1],  0, -1);
        helper(gh, king[0], king[1],  1, -1);
        helper(gh, king[0], king[1],  1,  0);
        helper(gh, king[0], king[1],  1,  1);
        helper(gh, king[0], king[1],  0,  1);
        helper(gh, king[0], king[1], -1,  1);
        helper(gh, king[0], king[1], -1,  0);
        return ret;
    }
};

1223. Dice Roll Simulation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    typedef long long LL;
    LL dp[5002][16][6];
    LL mod = 1000000000 + 7;
    vector<int> rollMax;
    
    LL dfs(int k, int index, int n){
        if(n==0){
            return 1;
        }
        if(dp[n][k][index] != -1){
            return dp[n][k][index];
        }
        LL ans = 0;
        for(int i=0; i<6; i++){
            if(index != i){
                ans += dfs(1, i, n-1);
            }
            else if(k < rollMax[i]){
                ans += dfs(k+1, i, n-1);
            }
            else{
                
            }
        }
        return dp[n][k][index] = ans % mod;
    }
    
    int dieSimulator(int n, vector<int>& rollMax) {
        this->rollMax = rollMax;
        LL ans = 0;
        memset(dp, -1, sizeof(dp));
        return dfs(0, 0, n);
    }
};

1224. Maximum Equal Frequency

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class Solution {
    map<int, int>count;
    map<int, int> m;
    bool check() const{
        
        if(m.size() == 1){//只出现一个数字
            return true;
        }
        
        //出现很多数字，但是都次数都是1
        if(count.size() == 1 && count.begin()->first == 1){
            return true;
        }
        
        if(count.size() != 2){
            return false;
        }
        
        auto one = count.begin();
        auto two = one;
        two++;
        
        //只有一个数字出现一次，其他都出现多次，且次数相等
        if(one->second == 1 && one->first ==1){
            return true;
        }
        if(two->second == 1 && two->first ==1){
            return true;
        }
        
        //所有数字都出现多次，但是大多数次数都相等，只有一个特殊多了一次
        if(one->second == 1 && one->first - 1 == two->first){
            return true;
        }
        if(two->second == 1 && two->first - 1 == one->first){
            return true;
        }
        
        return false;
    }
public:
    int maxEqualFreq(vector<int>& nums) {
        int ans = 1;
        for(int i=0;i<nums.size();i++){
            int old = m[nums[i]];
            m[nums[i]]++;
            
            //维护前缀
            if(count.find(old) != count.end()){
                count[old]--;
                if(count[old] == 0){
                    count.erase(old);
                }
            }
            count[m[nums[i]]]++;
            
            if(check()){
                ans = i + 1;
            }
        }
        
        return ans;
    }
};

Posted on |
Words count in article: 294 | Reading time ≈ 1

Implement Queue using Stacks

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class MyQueue {
public:
    stack<int> s1;
    stack<int> s2;
public:
    MyQueue(){
        
    }
    // Push element x to the back of queue.
    void push(int x) {
        while(s1.size()>0){
            s2.push(s1.top());
            s1.pop();
        }
        s1.push(x);
        while(s2.size()>0){
            s1.push(s2.top());
            s2.pop();
        }
    }

    // Removes the element from in front of queue.
    int pop(void) {
        int rem = s1.top();
        s1.pop();
        return rem;
    }

    // Get the front element.
    int peek(void) {
        return s1.top();
    }

    // Return whether the queue is empty.
    bool empty(void) {
        return (s1.size()==0);
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

Implement Stack using Queues

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class MyStack {
public:
    queue<int> q1;
    queue<int> q2;
    
    /** Initialize your data structure here. */
    MyStack() {
    
    }
    
    /** Push element x onto stack. */
    void push(int x) {
        q2.push(x);
        while(q1.size() > 0){
            q2.push(q1.front());
            q1.pop();
        }
        while(q2.size() > 0){
            q1.push(q2.front());
            q2.pop();
        }
    }
    
    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int ret = q1.front();
        q1.pop();
        return ret;
    }
    
    /** Get the top element. */
    int top() {
        return q1.front();
    }
    
    /** Returns whether the stack is empty. */
    bool empty() {
        return q1.empty();
    }
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */

Posted on | In , |
Words count in article: 305 | Reading time ≈ 1

Design a data structure that supports the following two operations:

  • void addWord(word)
  • bool search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

Example:

1
2
3
4
5
6
7
addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

Note:

  • You may assume that all words are consist of lowercase letters a-z.

字典树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class TrieNode{
public:
    bool word;
    TrieNode* children[26];
    TrieNode(){
        word = false;
        memset(children, NULL, sizeof(children));
    }
};



class WordDictionary {
public:
    /** Initialize your data structure here. */
    WordDictionary() {
        
    }
    
    /** Adds a word into the data structure. */
    void addWord(string word) {
        TrieNode* node = root;
        for(char c: word)
        {
            if(!node->children[c-'a']){
                node->children[c-'a'] = new TrieNode();
            }
            node = node->children[c-'a'];
        }
        node->word = true;
    }
    
    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    bool search(string word) {
        return search(word.c_str(), root);
    }

private:
    TrieNode* root = new TrieNode();
    
    bool search(const char* word, TrieNode* node){
        for(int i=0; word[i] && node; i++){
            if(word[i] != '.'){
                node = node->children[word[i]-'a'];
            }
            else{
                TrieNode* tmp = node;
                for(int j=0; j<26; j++){
                    node = tmp->children[j];
                    if(search(word+i+1, node)){
                        return true;
                    }
                }
            }
        }
        return node && node->word;
    }
};

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary* obj = new WordDictionary();
 * obj->addWord(word);
 * bool param_2 = obj->search(word);
 */

Posted on | In , |
Words count in article: 215 | Reading time ≈ 1

There are 2N people a company is planning to interview. The cost of flying the i-th person to city A is costs[i][0], and the cost of flying the i-th person to city B is costs[i][1].

Return the minimum cost to fly every person to a city such that exactly N people arrive in each city.

1
2
3
4
5
6
7
8
9
10
11
Example 1:

Input: [[10,20],[30,200],[400,50],[30,20]]
Output: 110
Explanation: 
The first person goes to city A for a cost of 10.
The second person goes to city A for a cost of 30.
The third person goes to city B for a cost of 50.
The fourth person goes to city B for a cost of 20.

The total minimum cost is 10 + 30 + 50 + 20 = 110 to have half the people interviewing in each city.
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int twoCitySchedCost(vector<vector<int>>& cs, int res = 0) {
      sort(begin(cs), end(cs), [](vector<int> &v1, vector<int> &v2) {
        return (v1[0] - v1[1] < v2[0] - v2[1]);
      });
      for (auto i = 0; i < cs.size() / 2; ++i) {
        res += cs[i][0] + cs[i + cs.size() / 2][1];
      }
      return res;
    }
};

Posted on | In , |
Words count in article: 370 | Reading time ≈ 2

An undirected, connected tree with N nodes labelled 0…N-1 and N-1 edges are given.

The ith edge connects nodes edges[i][0] and edges[i][1] together.

Return a list ans, where ans[i] is the sum of the distances between node i and all other nodes.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
Input: N = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
Output: [8,12,6,10,10,10]
Explanation: 
Here is a diagram of the given tree:
  0
 / \
1   2
   /|\
  3 4 5
We can see that dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5)
equals 1 + 1 + 2 + 2 + 2 = 8.  Hence, answer[0] = 8, and so on.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    vector<vector<int>> gh;
    vector<int> dist; //i点的所有子结点到i的距离之和
    vector<int> size; //以i点为根的树的结点数量和(包括i结点本身)
    vector<int> res;
    vector<int> sumOfDistancesInTree(int n, vector<vector<int>>& edges) {
        gh.resize(n); dist.resize(n); size.resize(n); res.resize(n);
        for (const auto& v : edges) {
            gh[v[0]].emplace_back(v[1]);
            gh[v[1]].emplace_back(v[0]);
        }
        dfs1(0, -1);
        res[0] = dist[0];
        dfs2(n, 0, -1);
        return res;
    }
    //求出以0为根的距离之和且求出了分别以i为根的子树结点数量和
    void dfs1(int cur, int par) {
        dist[cur] = 0;
        size[cur] = 1;
        for (auto i : gh[cur]) {
            if (i == par) continue;
            dfs1(i, cur);
            dist[cur] += dist[i] + size[i];
            size[cur] += size[i];
        }
    }
    //从0开始往下递归推出子树。再子树推算出子子树直到所有。
    void dfs2(int n, int cur, int par) {
        for (auto i : gh[cur]) {
            if (i == par) continue;
            res[i] = res[cur] + (n - size[i]) - size[i];
            dfs2(n, i, cur);
        }
    }
};

Posted on | In , |
Words count in article: 593 | Reading time ≈ 3

1213. Intersection of Three Sorted Arrays

Given three integer arrays arr1, arr2 and arr3 sorted in strictly increasing order, return a sorted array of only the integers that appeared in all three arrays.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<int> arraysIntersection(vector<int>& arr1, vector<int>& arr2, vector<int>& arr3) {
        vector<int> ret;
        for(int i=0; i<arr1.size(); i++)
        {
            int cur = arr1[i];
            if(find(arr2.begin(), arr2.end(), cur) != arr2.end() && find(arr3.begin(), arr3.end(), cur) != arr3.end())
                ret.push_back(arr1[i]);
        }
        return ret;
    }
};

1214. Two Sum BSTs

Given two binary search trees, return True if and only if there is a node in the first tree and a node in the second tree whose values sum up to a given integer target.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * 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:
    set<int> s;
    void dfs(TreeNode* root)
    {
        if(!root) return;
        dfs(root->left);
        dfs(root->right);
        s.insert(root->val);
    }
    
    bool helper(TreeNode* root, int target)
    {
        if(!root) return false;
        if(find(s.begin(), s.end(), target-root->val) != s.end())
            return true;
        return helper(root->left, target) || helper(root->right, target);
    }
    
    bool twoSumBSTs(TreeNode* root1, TreeNode* root2, int target) {
        s.clear();
        dfs(root1);
        return helper(root2, target);
    }
};

1215. Stepping Numbers

A Stepping Number is an integer such that all of its adjacent digits have an absolute difference of exactly 1. For example, 321 is a Stepping Number while 421 is not.

Given two integers low and high, find and return a sorted list of all the Stepping Numbers in the range [low, high] inclusive.

Constraints:

0 <= low <= high <= 2 * 10^9

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> countSteppingNumbers(int low, int high) {
        vector<int> ans;
        queue<int> q;
        int i, j;
        for(i=1; i<10 && i<=high; i++)
            q.push(i);
        if(!low) ans.push_back(0);
        while(!q.empty())
        {
            i = q.front();
            q.pop();
            if(i >= low) ans.push_back(i);
            j = i % 10;
            if(j && i*10LL+j-1 <= high) q.push(i*10+j-1);
            if(j<9 && i*10LL+j+1 <= high) q.push(i*10+j+1);
        }
        sort(ans.begin(), ans.end());
        return ans;
    }
};

1216. Valid Palindrome III

Given a string s and an integer k, find out if the given string is a K-Palindrome or not.

A string is K-Palindrome if it can be transformed into a palindrome by removing at most k characters from it.

Constraints:

1 <= s.length <= 1000

s has only lowercase English letters.

1 <= k <= s.length

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool isValidPalindrome(string s, int k) {
        int n = s.size();
        vector<vector<int>> dp(n+2, vector<int>(n+2));
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                if(s[i-1] == s[n-j+1-1])
                    dp[i][j] = dp[i-1][j-1]+1;
                else
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
        int ret = n-dp[n][n];
        return ret <= k;
    }
};

Posted on | In , |
Words count in article: 685 | Reading time ≈ 4

1217. Play with Chips

There are some chips, and the i-th chip is at position chips[i].

You can perform any of the two following types of moves any number of times (possibly zero) on any chip:

  • Move the i-th chip by 2 units to the left or to the right with a cost of 0.
  • Move the i-th chip by 1 unit to the left or to the right with a cost of 1.

There can be two or more chips at the same position initially.

Return the minimum cost needed to move all the chips to the same position (any position).

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int minCostToMoveChips(vector<int>& chips) {
        int cnt[2] = {0, 0};
        for(auto p: chips)
            cnt[p % 2]++;
        return cnt[0] < cnt[1] ? cnt[0] : cnt[1];
    }
};

1218. Longest Arithmetic Subsequence of Given Difference

Given an integer array arr and an integer difference, return the length of the longest subsequence in arr which is an arithmetic sequence such that the difference between adjacent elements in the subsequence equals difference.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {
        unordered_map<int, int> m;
        int ret = 0;
        
        for(int i=arr.size()-1; i>=0; i--)
        {
            m[arr[i]] = 1 + m[arr[i] + difference];
            ret = max(ret, m[arr[i]]);
        }
        return ret;
    }
};

1219. Path with Maximum Gold

In a gold mine grid of size m * n, each cell in this mine has an integer representing the amount of gold in that cell, 0 if it is empty.

Return the maximum amount of gold you can collect under the conditions:

  • Every time you are located in a cell you will collect all the gold in that cell.
  • From your position you can walk one step to the left, right, up or down.
  • You can’t visit the same cell more than once.
  • Never visit a cell with 0 gold.
  • You can start and stop collecting gold from any position in the grid that has some gold.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int dfs(vector<vector<int>>& g, int i, int j) {
      if (i < 0 || j < 0 || i >= g.size() || j >= g[i].size() || g[i][j] <= 0)  return 0;
      g[i][j] = -g[i][j];
      auto res = max({ dfs(g, i + 1, j), dfs(g, i, j + 1), dfs(g, i - 1, j), dfs(g, i, j - 1) });
      g[i][j] = -g[i][j];
      return g[i][j] + res;
    }
    int getMaximumGold(vector<vector<int>>& grid, int res = 0) {
      for (auto i = 0; i < grid.size(); ++i)
        for (auto j = 0; j < grid[i].size(); ++j)
          res = max(res, dfs(grid, i, j));
      return res;
    }
};

1220. Count Vowels Permutation

Given an integer n, your task is to count how many strings of length n can be formed under the following rules:

  • Each character is a lower case vowel (‘a’, ‘e’, ‘i’, ‘o’, ‘u’)
  • Each vowel ‘a’ may only be followed by an ‘e’.
  • Each vowel ‘e’ may only be followed by an ‘a’ or an ‘i’.
  • Each vowel ‘i’ may not be followed by another ‘i’.
  • Each vowel ‘o’ may only be followed by an ‘i’ or a ‘u’.
  • Each vowel ‘u’ may only be followed by an ‘a’.

Since the answer may be too large, return it modulo 10^9 + 7.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int countVowelPermutation(int n) {
      int[][] moves = { {1}, {0, 2}, {0, 1, 3, 4}, {2, 4}, { 0 } };
      int[] v = { 1, 1, 1, 1, 1 };
      while (--n > 0) {
        int[] v1 = { 0, 0, 0, 0, 0 };
        for (int i = 0; i < 5; ++i) {
          for (int j : moves[i])
            v1[j] = (v1[j] + v[i]) % 1000000007;
        }
        v = v1;
      }
      return (int)(((long)v[0] + v[1] + v[2] + v[3] + v[4]) % 1000000007);
    }
}