给一个字符串, 里面有0,1和?, ?可以是1或者0, 求这个字符串的子字符串中可以变成1和0 交替出现的字符串的个数.

这题就是counting问题, 做的时候用的dp, 想了半天都有错, 后来想想, ?基本没啥用的地方, 因为0和1交替出现的字符串就两种, 一种是0101或者1010…所以如果我们强制替换奇数位上的1变成0, 0变成1, 那么如果是以上两种, 就会变成0000或者1111, 所以我们只需要用两个指针count一下每个substring是否是答案即可.

package readman;

import net.egork.io.InputReader;
import net.egork.io.OutputWriter;

public class TaskC {
    public void solve(int testNumber, InputReader in, OutputWriter out) {
        String s = in.readLine();
        StringBuffer sb = new StringBuffer(s);
        for (int i = 1; i < sb.length(); i+=2){
            if (sb.charAt(i) == '1')
                sb.setCharAt(i, '0');
            else if (sb.charAt(i) == '0')
                sb.setCharAt(i, '1');
        }
        long count=0;
        int[] cc = new int[255];
       int left = 0;
       int right = 0;
       while(right < sb.length()) {
           cc[sb.charAt(right++) - '0'] ++;
           if (cc[0]  != 0 && cc[1] != 0) { // if right pointer found first '1' or '0'
               while(cc[0] != 0 && cc[1] != 0){
                   cc[sb.charAt(left++) - '0']--;
               }
           }
           count += (right  - left);
       }
       out.printLine(count);
    }
}

给两个鸡蛋和n层楼, 已知一个鸡蛋从x层楼掉下去不会碎,但是从x+1层就会碎 求最少多少次扔鸡蛋可以知道x是多少.

典型的dp题, 可以用一个memo存当前的状态: 首先, 如果只有一个鸡蛋, 那么测n层楼需要测n次. 这里不用binary search, 因为我们的求的是最少多少次扔鸡蛋, 而binary search不一定能找到正确的解, 最坏情况我们还是要扔n次. 转移方程中, 两个状态是:1. 扔了没有碎, x肯定在当前i floor的上边: drop(egg, floor - i), 2. 扔了碎了, x肯定在当前i floor的下边 drop(egg - 1, i - 1). 因为同样数量的move下,我们需要找的是两个解中, 最”高”的一层所以取两个状态的max. 然后和当前的所有状态中的每个状态取min.

class Solution {
public:
    int memo[3][1001]; 
    int twoEggDrop(int n) { 
         return dfs(2, n);;
    }
    int dfs(int egg, int floor){
        if(floor == 1 || floor == 0 || egg == 1)
            return floor; 
        if(memo[egg][floor])
            return memo[egg][floor]; 
        int res = 2000;
        for(int i = 1; i <= floor; i++) {
            res = min(res, max(dfs(egg - 1, i - 1), dfs(egg, floor - i)) + 1);
        } 
        memo[egg][floor] = res;
        return res;
    }
};

给三个字符串, 问前两个的值转换成数字是否加起来等于第三个.

class Solution {
public:
    bool isSumEqual(string f, string s, string t) {
        return convert(f) + convert(s) == convert(t);
    }
    int convert(string s) {
        int base = 1;
        int res = 0;
        for(int i = s.length() - 1; i >= 0; i--){
            res += base * (s[i] - 'a');
            base *= 10;
        }
        return res;
    }
};

给一个二叉树, 然后给一个node的值是coin的数量, 求把这个coins分给每个node需要几步, 一步只能往下推一个node.

这题就是divide and conquer, 例题给的很明确, 如果是root有3个, 左右是0, 那么分下去需要2步(给左边一个, 给右边一个), 这题还给了一共n个node和n个coin, 所以不存在溢出的情况. 所以只需要计算left和right的和-1 就是需要的步骤.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int res = 0;
    int distributeCoins(TreeNode* root) {
        dfs(root);
        return res;
    }
    int dfs(TreeNode* root){
        if(!root)
            return 0;
        int l = dfs(root->left);
        int r = dfs(root->right);
        res += abs(l) + abs(r);
        return root->val + l + r - 1; //1 for itself
    }
};

给两个数组设计一个数据结构, 可以add一个数字到第二个数组, 还有count两个数组的数字等于total有几对儿.

这个就是第一个数组大, 第二个小, 所以先处理大的数组. 然后count的时候直接减一下即可.

class FindSumPairs {
public:
    unordered_map<int, int> map;
    vector<int> n1;
    vector<int> n2;
    FindSumPairs(vector<int>& nums1, vector<int>& nums2) {
        n1 = nums1;
        n2 = nums2;
        for(auto n : n2)
            map[n]++;
    }
    
    void add(int index, int val) {
        map[n2[index]]--;
        map[n2[index] + val]++;
        n2[index] += val;
    }
    
    int count(int tot) {
        int res = 0;
        for(int n : n1)
            res += map[tot - n];
        return res;
    }
};

/**
 * Your FindSumPairs object will be instantiated and called as such:
 * FindSumPairs* obj = new FindSumPairs(nums1, nums2);
 * obj->add(index,val);
 * int param_2 = obj->count(tot);
 */

给一个binary字符串, 求是否最长的1比最长的0长.

class Solution {
public:
    bool checkZeroOnes(string s) {
        int longestOne = 0;
        int longestZero = 0;
        int curOne = 0;
        int curZero = 0;
        for(auto c : s) {
            if(c == '0'){
                longestOne = max(longestOne, curOne);
                curOne = 0;
                curZero++;
            }else{
                longestZero = max(longestZero, curZero);
                curZero = 0;
                curOne++;
            }
        }
        longestOne = max(longestOne, curOne);
        longestZero = max(longestZero, curZero);
        return longestOne > longestZero;
    }
};

各一个2d数组, 里面有石头, 空格和障碍, 求右转90度后, 石头落下, 数组的状态.

这题先转90度, 然后从下往上看到空格就往上找石头然后swap, 注意检查边界.

class Solution {
public:
    vector<vector<char>> rotateTheBox(vector<vector<char>>& box) {
        int n = box[0].size();
        int m = box.size();
        vector<vector<char>> res = rotate(box, n, m);
        for(int j = 0; j < m; j++) {
            for(int i = n - 1; i >= 0; i--){
                if(res[i][j] == '.'){// find the space
                    int k = i - 1;
                    while(k >= 0 && res[k][j] == '.') // skip all space above
                        k--;
                    if(k >= 0 && res[k][j] == '#')// find the stone
                        swap(res[k][j], res[i][j]); // swap
                }
            }
        }
        return res;
     }
    vector<vector<char>> rotate(vector<vector<char>>& box, int n, int m){
        vector<vector<char>> res(n, vector<char>(m));
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                res[i][j] = box[m - 1 - j][i];
            }
        }
        return res;
    }
};

给一个string组, 求是否有一个string的所有prefix都出现在组里.

Trie找一下

struct TrieNode
{ 
    bool leaf;
    TrieNode *v[128]; 
}; 
TrieNode* newNode(){
    TrieNode* n = new TrieNode;
    for (int i = 0; i < 128; i++)
    {
        n->leaf = false;
        n->v[i] = NULL;
    }
    return n;
}
class Solution {
public:
    void insert (TrieNode* root, string s) {
        TrieNode* cur = root;
        for (auto ch : s){
            if (!cur->v[ch])
                cur->v[ch] = newNode();
            cur = cur->v[ch];      
        }   
        cur->leaf = true; 
    } 
    bool find (TrieNode* root, string s) {
        int count = 0;
        TrieNode* cur = root;
        for (int i = 0; i < s.size() - 1; i++){
           if(cur->v[s[i]]){
               if(cur->v[s[i]]->leaf)
                   count++;
               cur = cur->v[s[i]];
           }
        }   
        return count == s.size() - 1;
    } 
    string longestWord(vector<string>& words) {
        TrieNode* node = newNode();
        for(auto w : words){
            insert(node, w);
        }
        sort(words.begin(), words.end(),[](string a, string b){return a.length() == b.length() ? a < b : b.length() < a.length();});
        for(auto w : words){
            if(find(node, w))
                return w;
        }
        return "";
    } 
};