登录
OAmaster

Given an array arr of n integers, the goodness of a strictly increasing subsequence is the bitwise OR of its elements. The empty subsequence has goodness 0. Return the number of distinct goodness values obtainable.

Example: arr = [4, 2, 4, 1] → distinct goodness {0, 1, 2, 4, 6} → 5.

解法

按下标 DP：dp[i] 是以 i 结尾的严格递增子序列的所有 OR 值集合。对每个 j < i 且 arr[j] < arr[i]，把 dp[j] 内的值与 arr[i] OR 后并入 dp[i]。最后并所有 dp[i] 加上空子序列。复杂度 O(n² · |dp|)，实际中 OR 集合规模很小。

def distinct_goodness(arr):
    n = len(arr)
    dp = []
    all_ = {0}
    for i in range(n):
        cur = {arr[i]}
        for j in range(i):
            if arr[j] < arr[i]:
                for x in dp[j]:
                    cur.add(x | arr[i])
        dp.append(cur)
        all_ |= cur
    return len(all_)
import java.util.*;

class Solution {
    int distinctGoodness(int[] arr) {
        int n = arr.length;
        List<Set<Integer>> dp = new ArrayList<>();
        Set<Integer> all = new HashSet<>();
        all.add(0);
        for (int i = 0; i < n; i++) {
            Set<Integer> cur = new HashSet<>();
            cur.add(arr[i]);
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i]) {
                    for (int x : dp.get(j)) cur.add(x | arr[i]);
                }
            }
            dp.add(cur);
            all.addAll(cur);
        }
        return all.size();
    }
}
#include <vector>
#include <unordered_set>
using namespace std;

int distinctGoodness(vector<int>& arr) {
 int n = arr.size();
 vector<unordered_set<int>> dp(n);
 unordered_set<int> all_;
 all_.insert(0);
 for (int i = 0; i < n; i++) {
 dp[i].insert(arr[i]);
 for (int j = 0; j < i; j++) {
 if (arr[j] < arr[i]) {
 for (int x : dp[j]) dp[i].insert(x | arr[i]);
 }
 }
 for (int v : dp[i]) all_.insert(v);
 }
 return (int) all_.size();
}

Given n users and a friendship matrix friends[n][n] where friends[i][j] = '1' if i and j are friends. For each user, recommend the non-friend with the maximum number of common friends. Break ties by smallest index. Return an array rec[n] where rec[i] = -1 if no candidate exists.

Example: friends = ["010","100","000"] → for user 2 no friend exists; both users 0 and 1 have only each other.

解法

把每行压成位掩码。对每对非好友的下标 (i, j)，共同好友数即 popcount(mask[i] & mask[j])。对每个 i 记录最优 j。复杂度 O(n² · n / 64)。

def friend_recommendation(friends):
    n = len(friends)
    masks = [int(''.join(reversed(s)), 2) for s in friends]
    rec = []
    for i in range(n):
        best, best_cnt = -1, -1
        for j in range(n):
            if i == j or friends[i][j] == '1':
                continue
            cnt = bin(masks[i] & masks[j]).count('1')
            if cnt > best_cnt or (cnt == best_cnt and (best == -1 or j < best)):
                best, best_cnt = j, cnt
        rec.append(best)
    return rec
import java.util.*;
import java.math.BigInteger;

class Solution {
    int[] friendRecommendation(String[] friends) {
        int n = friends.length;
        BigInteger[] masks = new BigInteger[n];
        for (int i = 0; i < n; i++) {
            StringBuilder rev = new StringBuilder(friends[i]).reverse();
            masks[i] = new BigInteger(rev.toString(), 2);
        }
        int[] rec = new int[n];
        for (int i = 0; i < n; i++) {
            int best = -1, bestCnt = -1;
            for (int j = 0; j < n; j++) {
                if (i == j || friends[i].charAt(j) == '1') continue;
                int cnt = masks[i].and(masks[j]).bitCount();
                if (cnt > bestCnt || (cnt == bestCnt && (best == -1 || j < best))) {
                    best = j; bestCnt = cnt;
                }
            }
            rec[i] = best;
        }
        return rec;
    }
}
#include <vector>
#include <string>
#include <bitset>
using namespace std;

vector<int> friendRecommendation(vector<string>& friends) {
 int n = friends.size();
 vector<vector<int>> mask(n, vector<int>(n, 0));
 for (int i = 0; i < n; i++)
 for (int j = 0; j < n; j++)
 mask[i][j] = (friends[i][j] == '1');
 vector<int> rec(n);
 for (int i = 0; i < n; i++) {
 int best = -1, bestCnt = -1;
 for (int j = 0; j < n; j++) {
 if (i == j || friends[i][j] == '1') continue;
 int cnt = 0;
 for (int k = 0; k < n; k++) cnt += mask[i][k] & mask[j][k];
 if (cnt > bestCnt || (cnt == bestCnt && best == -1)) {
 best = j; bestCnt = cnt;
 }
 }
 rec[i] = best;
 }
 return rec;
}

Given a binary string s ('0'/'1'), return the number of length-5 palindromic subsequences modulo 10⁹ + 7.

Example: s = "10110" → count subsequences of the form aXbXa with a, b ∈ {0, 1}.

解法

长度 5 回文形如 a b c b a。固定中间下标 m，定义 leftBA[m][b*2+a] 为 m 左侧按 a 再 b 顺序的选法数，rightBA[m][b*2+a] 为右侧同理。答案 = Σ_{m,a,b} leftBA[m][b*2+a] * rightBA[m+2][b*2+a]。复杂度 O(n)。

def count_palindromic_subseq5(s):
    MOD = 10**9 + 7
    n = len(s)
    leftBA = [[0] * 4 for _ in range(n + 1)]
    leftA = [0, 0]
    for i in range(n):
        for k in range(4): leftBA[i + 1][k] = leftBA[i][k]
        x = int(s[i])
        for b in range(2):
            leftBA[i + 1][b * 2 + x] = (leftBA[i + 1][b * 2 + x] + leftA[b]) % MOD
        leftA[x] += 1
    rightBA = [[0] * 4 for _ in range(n + 2)]
    rightA = [0, 0]
    for i in range(n - 1, -1, -1):
        for k in range(4): rightBA[i + 1][k] = rightBA[i + 2][k]
        x = int(s[i])
        for b in range(2):
            rightBA[i + 1][b * 2 + x] = (rightBA[i + 1][b * 2 + x] + rightA[b]) % MOD
        rightA[x] += 1
    ans = 0
    for m in range(n):
        for a in range(2):
            for b in range(2):
                ans = (ans + leftBA[m][b * 2 + a] * rightBA[m + 2][b * 2 + a]) % MOD
    return ans
class Solution {
    int countPalindromicSubseq5(String s) {
        final int MOD = 1_000_000_007;
        int n = s.length();
        long[][] leftBA = new long[n + 1][4];
        long[] leftA = new long[2];
        for (int i = 0; i < n; i++) {
            for (int k = 0; k < 4; k++) leftBA[i + 1][k] = leftBA[i][k];
            int x = s.charAt(i) - '0';
            for (int b = 0; b < 2; b++)
                leftBA[i + 1][b * 2 + x] = (leftBA[i + 1][b * 2 + x] + leftA[b]) % MOD;
            leftA[x]++;
        }
        long[][] rightBA = new long[n + 2][4];
        long[] rightA = new long[2];
        for (int i = n - 1; i >= 0; i--) {
            for (int k = 0; k < 4; k++) rightBA[i + 1][k] = rightBA[i + 2][k];
            int x = s.charAt(i) - '0';
            for (int b = 0; b < 2; b++)
                rightBA[i + 1][b * 2 + x] = (rightBA[i + 1][b * 2 + x] + rightA[b]) % MOD;
            rightA[x]++;
        }
        long ans = 0;
        for (int m = 0; m < n; m++)
            for (int a = 0; a < 2; a++)
                for (int b = 0; b < 2; b++)
                    ans = (ans + leftBA[m][b * 2 + a] * rightBA[m + 2][b * 2 + a]) % MOD;
        return (int) ans;
    }
}
#include <string>
#include <vector>
using namespace std;

int countPalindromicSubseq5(string s) {
 const int MOD = 1e9 + 7;
 int n = s.size();
 vector<vector<long long>> leftBA(n + 1, vector<long long>(4, 0));
 long long leftA[2] = {0, 0};
 for (int i = 0; i < n; i++) {
 for (int k = 0; k < 4; k++) leftBA[i + 1][k] = leftBA[i][k];
 int x = s[i] - '0';
 for (int b = 0; b < 2; b++)
 leftBA[i + 1][b * 2 + x] = (leftBA[i + 1][b * 2 + x] + leftA[b]) % MOD;
 leftA[x]++;
 }
 vector<vector<long long>> rightBA(n + 2, vector<long long>(4, 0));
 long long rightA[2] = {0, 0};
 for (int i = n - 1; i >= 0; i--) {
 for (int k = 0; k < 4; k++) rightBA[i + 1][k] = rightBA[i + 2][k];
 int x = s[i] - '0';
 for (int b = 0; b < 2; b++)
 rightBA[i + 1][b * 2 + x] = (rightBA[i + 1][b * 2 + x] + rightA[b]) % MOD;
 rightA[x]++;
 }
 long long ans = 0;
 for (int m = 0; m < n; m++)
 for (int a = 0; a < 2; a++)
 for (int b = 0; b < 2; b++)
 ans = (ans + leftBA[m][b * 2 + a] * rightBA[m + 2][b * 2 + a]) % MOD;
 return (int) ans;
}
Pro 会员

解锁剩余 22 道 OA 真题

开通后立即解锁完整题面 + Python / Java / C++ 三语题解。 全站 165 家公司 · 1000+ 道 OA · 月度更新。

开通会员已是会员，去登录

Amazon MERN Frontend

Amazon MERN/full-stack 真实 OA 题面 (前端/后端 bug-fix 题型, 非算法).

Jane Street

Jane Street OA 真题，三语题解(Python / Java / C++)。