首页 > 试题广场 >

最大子段或

[编程题]最大子段或

热度指数：222 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给出一个正整数序列 $A_{i}$ ，求一个子区间使得这个区间内的数或起来尽可能的大。
或运算指数字按二进制位进行以下运算：
运算规则： $\text 0|0=0,0|1=1,1|0=1,1|1=1$
一个序列的子区间指这个序列中连续的一段数字。
牛牛并不关心这个最大值是多少，他只关心所有满足条件的子区间里，最短的子区间长度是多少。

输入描述:

第一行一个正整数，代表这个序列的长度。 
接下来一行空格分隔的正整数，用来描述这个序列。

输出描述:

仅一行一个正整数代表答案。

示例1

输入

3
1 2 3

输出

说明

最大值是，满足条件的子区间为，
所以最短的长度为。

算法知识视频讲解

wonderson

滑动窗口常规思路：

1）不管左指针，移动右指针，使得区间满足条件；

2）右移左指针，使得区间满足最优化，与当前最优解比较；

3) 右移一位左指针，使得区间不满足条件，进行下一轮滑动。

难点在于`条件`:

由于或的性质，若是所有的数位全部相或，肯定就是最大值，中间不可能有比它更大的解，且任何中间值的数位都是最大值数位的一个子集；

我们可以统计一下最大值的数位个数，那么窗口区间需要满足的条件就是：

区间中或出来的结果的数位必须和最大值的数位个数相等；

在我的解法中，利用canSub()测试左指针右移是否还能让区间满足最大值；利用calc()来复用位运算。

import java.util.*;
public class Main {

        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            int[] nums = new int[n];
            for (int i = 0; i < n; i++) {
                nums[i] = sc.nextInt();
            }
            sc.close();
            // int[] nums = {1,2,3};
            System.out.println(minDistance(nums));
        }

        public static int minDistance(int[] nums) {
            int[] bits = new int[32];
            // boolean[] onePosition = new boolean[32];
            int n = nums.length;
            int cur = 0;
            for (int i = 0; i < n; i++) {
                cur |= nums[i];
            }
            int cntBits = 0;
            int tmp = cur;
            while (tmp > 0) {
                cntBits += (tmp & 1);
                tmp >>>= 1;
            }
            int min = n; //全部相或肯定是最大值
            //滑动窗口：i起始点，j：i作为起始点，能够满足cntBits=0的点
            int i = 0, j = 0;
            while (j < n) {
                while (j < n && cntBits > 0) {
                    cntBits = calcBit(bits, nums[j], true, cntBits);
                    j++;
                }
                if (cntBits > 0) {
                    break;
                }
                while (i < j) {
                    if (!canSub(bits, nums[i])) {
                        min = Math.min(min, j - i);
                        break;
                    }
                    cntBits = calcBit(bits, nums[i], false, cntBits);
                    i++;
                }
                cntBits = calcBit(bits, nums[i], false, cntBits);
                i++;
            }
            return min;
        }

        public static int calcBit(int[] bits, int num, boolean add, int cntBits) {
            int t = 0;
            while (num > 0) {
                if ((num & 1) != 0) {
                    if (add) {
                        if (bits[t] == 0) {
                            cntBits--;
                        }
                        bits[t]++;
                    } else {
                        bits[t]--;
                        if (bits[t] == 0) {
                            cntBits++;
                        }
                    }
                }
                t++;
                num >>>= 1;
            }
            return cntBits;
        }

        public static boolean canSub(int[] bits, int cur) {
            int i = 0;
            while (cur > 0) {
                if ((cur & 1) != 0 && bits[i] == 1) {
                    return false;
                }
                i++;
                cur >>>= 1;
            }
            return true;
        }


    }

发表于 2022-03-14 10:55:40 回复(1)

CharmsGraker

#include <bits/stdc++.h>

using namespace std;
int nBits = 32;

int maxOr = 0;

bool passCheck(const vector<int> &bitMap) {
    for (int b = 0; b < nBits; ++b) {
        if ((maxOr & (1 << b)) && bitMap[b] <= 0) {
//            cout << "check bit: " << b << " failed " << endl;
            return false;
        }

    }
    return true;
}

vector<int> changeBitOfBound(vector<int> &bitMap, const int val, int c) {
    for (int b = 0; b < nBits; ++b) {
        if ((val & (1 << b))) {
//            cout << "add bit: " << b << endl;
            bitMap[b] += c;
        }
    }
    return bitMap;
}

bool passCheckDelta(vector<int> bitMap, int val, int c) {
    changeBitOfBound(bitMap, val, c);
    return passCheck(bitMap);
}

int solve(vector<int> &arr) {
    maxOr = 0;
    int len = arr.size();

    for (auto &x:arr) {
        maxOr |= x;
    }
    int l = 0, r = 0;
    int ans = 0x3ffffff;
    vector<int> Bitmp(nBits, 0);

    while (r < len) {
        changeBitOfBound(Bitmp, arr[r], 1);
        ++r;
        if(passCheck(Bitmp))
            while (l < r && passCheckDelta(Bitmp, arr[l], -1)) {
                changeBitOfBound(Bitmp, arr[l], -1);
                ++l;

            }

        if (passCheck(Bitmp)) {
            ans = min(ans, r - l);
        }
    }
    return ans;
}


int main() {
    int n;

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    using iiter = istream_iterator<int>;

    vector<int> a(n);
    copy_n(iiter(cin), n, begin(a));

    cout << solve(a) << endl;
}

发表于 2022-03-21 16:15:04 回复(0)

只想拿个offer啊

双指针算法

首先我们可以很容易计算出最大值: 所有元素的或
接着我们考虑计算以每一个i为终点的符合区间或为最大值的最大的j, 注意到i和j具有单调性, 即i所对应的j, 与i + 1所对应的j', 一定有j<=j'
最后考虑如何动态维护窗口内的区间或。注意到或运算的按位独立的, 每一位互不影响, 且只要某一位存在, 不论该位出现多少次, 最后的或的结果中该位一定存在。因此考虑用一个32位的数组来记录区间的比特位信息, 新加/删一个数就将该数的比特位信息加上/删去。

// 提交时间：2021-10-18 语言：C++ 运行时间： 685 ms 占用内存：4392K #include <bits/stdc++.h>

using namespace std;
const int N = 1e6 + 10, M = 32;
int w[N];

inline vector<int> change(vector<int> cnt, int num, int c) {
    for (int i = 0; i < M; i ++ )
        if (num >> i & 1)
            cnt[i] += c;
    return cnt;
}

inline bool check(const vector<int>& cnt, int all) {
    for (int i = 0; i < M; i ++ )
        if ((all >> i & 1) and cnt[i] == 0)
            return false;
    return true;
}

void solve(){
    int n;
    cin >> n;
    int all = 0;
    for (int i = 1; i <= n; i ++ )
        cin >> w[i], all |= w[i];

    int ans = INT_MAX;
    vector<int> cnt(M, 0);

    for (int i = 1, j = 1; i <= n; i ++ ) {
        cnt = move(change(cnt, w[i], 1));

        while (j < i and check(cnt, all) and check(change(cnt, w[j], -1), all))
            cnt = change(cnt, w[j], -1), j ++ ;
        if (check(cnt, all))
            ans = min(ans, i - j + 1);
    }
    cout << ans << endl;
}

int main()
{   
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    // cin >> t;
    t = 1;
    while (t -- )
        solve();
    return 0;
}

编辑于 2021-10-19 10:25:21 回复(0)

牛客JYK

import java.util.Scanner;  public class Main { public static int getVal(int[] dp) { int res = 0;  for (int i = 0; i < 32; i++) { if (dp[i] != 0) {
                res |= 1 << i;  }
        } return res;  } public static void add(int[] dp, int val){ for (int i = 0; i < 32; i++) { if ((val & (1 << i)) != 0 ) {
                dp[i] += 1;  }
        }
    } public static void sub(int[] dp, int val) { for (int i = 0; i < 32; i++) { if ((val & (1 << i)) != 0 ) {
                dp[i] -= 1;  }
        }
    } public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);  int n = sc.nextInt();  sc.nextLine();  String[] text = sc.nextLine().split(" ");  int[] arr = new int[text.length];  for (int i = 0; i < arr.length; i++) {
            arr[i] = Integer.parseInt(text[i]);  } int target = 0;  for (int i : arr) {
            target |= i;  } int[] dp = new int[32];  int left = 0;  int ans = arr.length;  for (int right = 0; right < arr.length; right++) { add(dp, arr[right]);  while (getVal(dp) == target) {
                ans = Math.min(ans, right - left + 1);  sub(dp, arr[left]);  left ++;  }
        }
        System.out.println(ans);  }
}

滑动窗口，用32长度的数组记录状态，最大值是数组所有元素参与或运算的结果，窗口两端用left, right表示，枚举right, 如果该子段符合最大值，记录结果并且left增加。此方法用Python只能提供50%的用例。

发表于 2021-09-02 19:50:08 回复(0)

yosoro25252

# 提交时间：2021-08-03 语言：Pypy3 运行时间： 1818 ms 占用内存：364136K 状态：答案正确
n = int(input())
arr = list(map(int, input().split()))
target = 0
targetArr = [0] * 32
for i in range(n):
    target = target | arr[i]
for j in range(32):
    targetArr[j] = (target >> j) & 1
for i in range(n):
    temp = [0] * 32
    for j in range(32):
        temp[j] = (arr[i] >> j) & 1
    arr[i] = temp
def addArr(cur, x):
    for i in range(32):
        cur[i] += x[i]
def minusArr(cur, x):
    for i in range(32):
        cur[i] -= x[i]
def checkArr(cur, target):
    for i in range(32):
        if cur[i] == 0 and target[i] > 0:
            return False
        if cur[i] > 0 and target[i] == 0:
            return False
    return True
curArr = [0] * 32
j = 0
bestLen = n
for i in range(n):
    addArr(curArr, arr[i])
    while j <= i and checkArr(curArr, targetArr):
        bestLen = min(bestLen, i - j + 1)
        minusArr(curArr, arr[j])
        j += 1
print(bestLen)

发表于 2021-08-03 18:21:21 回复(0)

。小吉

import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);

while (sc.hasNext()) {
int n = sc.nextInt();
int[] arr = new int[n];
int max = 0;
int[] maxarr = new int[n];

for (int i = 0; i<=n-1; i++) {
arr[i] = sc.nextInt();
max = max | arr[i];
maxarr[i] = arr[i];
}
boolean bl = false;
for (int i = 0; i<=n-1; i++) {
if (maxarr[i] == max) {
System.out.println(1);
bl = true;
break;
}
}
if (bl) {
continue;
}

int len = 2;
while (true) {
for (int i = 0; i<=n-len; i++) {
int cur = maxarr[i] | arr[i+len-1];
if (cur == max) {
//System.out.println("i "+i+" len "+len);
System.out.println(len);
bl = true;
break;
} else {
maxarr[i] = cur;
}
}
if (bl) {
break;
} else {
len++;
if (len>n) {
System.out.println(n);
break;
}
}
}
}
}
}

发表于 2021-05-05 17:45:34 回复(0)

提交观点

问题信息

C++工程师贝壳找房 2021 Java工程师

来自：贝壳找房2023届校招...

上传者：小小

难度：

6条回答 5收藏 2046浏览

通过挑战的用户

牛客42368...

2022-10-16 18:11:37
牛客13331...

2022-10-16 16:14:30
牛客64954...

2022-05-18 16:34:57
萧__

2022-03-28 10:49:55
CharmsG...

2022-03-21 16:14:31