给一个一直增加的数, 和两个memory, 每次都放到剩余最大的memory里, 求最后的状态

class Solution {
public:
    vector<int> memLeak(int m1, int m2) {
        int n = 1;
        bool run = true;
        while(run){
            run = false;
            if(m1 < m2 && m2 - n >= 0){
                m2 -= n; 
                run = true;
            }else if(m1 >= m2 && m1 - n >= 0){
                m1 -= n; 
                run = true;
            }
            n++;
        }
        vector<int> res{n - 1, m1, m2};
        return res;
    }
};

给一个数组, 求其中subset的xor的和.

class Solution {
public:
    int sum = 0;
    int subsetXORSum(vector<int>& nums) {
        sub(nums, 0, 0);
        return sum;
    }
    void sub(vector<int>& nums, int pos, int n){
        sum += n;
        for(int i = pos; i < nums.size(); i++) {
            n ^= nums[i];
            sub(nums, i + 1, n); 
            n ^= nums[i];
        }
    }
};

给一个数组, 求里面最大的子数组中, 最小元素*子数组和的乘积.

把每个元素看做子数组的最小元素, 这样就变成求由这个元素组成的最长子数组. 用以前的https://leetcode.com/problems/next-greater-element-ii/solution/ 中的stack方法, 找到所求子数组的左界和右界.

class Solution {
    public int maxSumMinProduct(int[] nums) {
        int[] left = new int[nums.length];
        int[] right = new int[nums.length];
        Stack<Integer>lt=new Stack<>();
        Stack<Integer>rt=new Stack<>();
        Arrays.fill(left, -1); // fill with left edge
        Arrays.fill(right, nums.length);// fill with right edge
        for(int i=0;i<nums.length;i++)
        {
            while(rt.size()!=0 && nums[rt.peek()] > nums[i])
            {
              right[rt.pop()]= i;
            }
            rt.push(i);
        }
        for(int i= nums.length - 1;i >= 0;i--)
        {
            while(lt.size()!=0 && nums[lt.peek()] > nums[i])
            {
              left[lt.pop()]= i;
            }
            lt.push(i);
        }
        long[] pre = new long[nums.length + 1];
        for(int i = 1; i < nums.length + 1; i++){
            pre[i] = pre[i - 1] + nums[i - 1];
        }
        
        long sum = 0;
        int mod = (int) Math.pow(10,9) + 7;
        for(int i = 0; i < nums.length; i++) { 
            sum = Math.max(sum, nums[i] * (pre[right[i]] - pre[left[i] + 1]) );
        }
        return (int) (sum % mod);
    }
} 

给一个字符串, 里面的每个words都是打乱顺序的, 要求按照每个words的末尾数字重新排序.

class Solution {
    public String sortSentence(String s) {
        String[] strs = s.split(" ");
        int n = strs.length;
        Map<Integer, String> map = new HashMap<>();
        for(String ss : strs) {
            map.put(ss.charAt(ss.length() - 1) - '0', ss.substring(0, ss.length() - 1));
        }
        StringBuilder sb = new StringBuilder();
        for(int i = 1; i <= n; i++){
            sb.append(map.get(i)+' ');
        }
        return sb.toString().trim();
    }
}

给两个递减数组, 找到最远的逆序对儿.

这题因为是排序好的, 用二叉搜索找, 注意先翻转一下, 然后再用lower_bound. 而且还要减去当前i的不被考虑的情况.

class Solution {
public:
    int maxDistance(vector<int>& nums1, vector<int>& nums2) {
        int res = 0;
        int n = nums1.size();
        int m = nums2.size();
        reverse(nums2.begin(), nums2.end());
        for(int i = 0; i < n; i++) {
            int f = lower_bound(nums2.begin(), nums2.end() - i, nums1[i]) - (nums2.begin());//[0, length - i]
            f = m - f - 1;
            res = max(res, f - i);
        }
        return res;
    }
};

class Solution {
public:
    string sortSentence(string s) {
        stringstream ss(s);
        string w;
        int n = 0;
        unordered_map<int, string> map;
        while(ss >> w){
            map[w.back() - '0'] = w.substr(0, w.length() - 1);
            n++;
        }
        stringstream so;
        for(int i = 1; i <= n; i++){
            so << map[i] << ' ';
        }
        string res = so.str();
        return res.substr(0, res.length() - 1);
    }
};

给一个log, 是[出生年, 死亡年], 求哪个年代人最多.

用扫描线做,

class Solution {
public:
    int maximumPopulation(vector<vector<int>>& logs) {
        vector<int> v(200);
        for(auto l : logs){
            v[l[0] - 1950]++;
            v[l[1] - 1950]--;
        }
        int maxx = 0;
        int tmp = 0;
        int res = 0;
        for(int i = 0; i < 200; i++){
            tmp += v[i];
            if(tmp > maxx){
                maxx = max(maxx, tmp);
                res = i + 1950;
            }
        }
        return res;
    }
};

给一个api,输入一个index, 返回元素值, 问怎么用这个api在一个不知道大小(并不是无限大)的已排序的数组上做二叉搜索.

二叉肯定要有右边的大小, 所以问题变成怎么快速找到右边的值, 用二次倍增法找

/**
 * // This is the ArrayReader's API interface.
 * // You should not implement it, or speculate about its implementation
 * class ArrayReader {
 *   public:
 *     int get(int index);
 * };
 */

class Solution {
public:
    int search(const ArrayReader& reader, int target) {
        int i = 0;
        int j = 1;
        while(reader.get(j) != 2147483647){
            j = j << 1;
        }
        while(i <= j) {
            int mid = i + (j - i) / 2;
            if(reader.get(mid) == target){
                return mid;
            }
            else if(reader.get(mid) > target){
                j = mid - 1;
            }else{
                i = mid + 1;
            }
        }
        return -1;
    }
};

给一个二叉树, 求删除值为0并且左右两边都是nullptr的分支.

/**
 * 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:
    TreeNode* pruneTree(TreeNode* root) {
        if(!root)
            return root;
        root->left = pruneTree(root->left);
        root->right = pruneTree(root->right);
        if(!root->val && !root->left && !root->right)
            return nullptr;
        else
            return root;
    }
};

给一个n-ary的树, 求周长. 就是任意两个node之间的最长距离, 可以不经过root.

最长的路径出现在两个情况, 情况一是路径经过node, 那么就是左右两边的最长路径相加, 要不然就是一侧,就是最长路径. 所以要求出最长路径和次长路径, 然后比较一下.

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
     int res = 0;
     int dfs(Node* root) {
        if (!root) 
            return 0;
        vector<int> v;
        for (auto &c: root->children) {
            v.push_back(f(c));
        }
         sort(v.begin(), v.end(), greater<int>());
        auto l1 = 0, l2 = 0;
         int n = v.size();
         if(n > 0){
             l1 = v[0];
         }
         if(n > 1){
             l2 = v[1];
         }
        res = max(res, l1 + l2);
        return 1 + max(l1, l2);
    }
    
    int diameter(Node* root) {
        dfs(root);
        return res;
    }
    
};

给一个数组, 里面的数字出现一次或者两次, 求出现一次的数字的数组.

这题要用set很简单, 不用的话, 可以把负数当作set查重用. 当数字做为坐标的时候 用abs取下值

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> res;
        int n = nums.size();
        for(int i = 0; i < n; i++){
            if(nums[abs(nums[i]) - 1] < 0){
                res.push_back(abs(nums[i]));
            }else{
                nums[abs(nums[i]) - 1] = -nums[abs(nums[i]) - 1];
            }
        }
        return res;
    }
};