Posts

2044. Count Number of Maximum Bitwise-OR Subsets

 JAVA class Solution { private int mx ; private int ans ; private int [] nums ; public int countMaxOrSubsets ( int [] nums ) { mx = 0 ; for ( int x : nums ) { mx |= x ; } this . nums = nums ; dfs ( 0 , 0 ); return ans ; } private void dfs ( int i , int t ) { if ( i == nums . length ) { if ( t == mx ) { ++ ans ; } return ; } dfs ( i + 1 , t ); dfs ( i + 1 , t | nums [ i ]); } } We can use DP to reduce the time complexity at the cost of space complexity class Solution { private int mx ; private int ans ; private int [] nums ; public int countMaxOrSubsets ( int [] nums ) { mx = 0 ; for ( int x : nums ) { mx |= x ; } this . nums = nums ; dfs ( 0 ...
Post a Comment
Read more

3480. Maximize Subarrays After Removing One Conflicting Pair

 C++ class Solution {   public:   long long maxSubarrays ( int n , vector < vector < int >> & conflictingPairs ) {     long validSubarrays = 0 ;     int maxLeft = 0 ;     int secondMaxLeft = 0 ;         vector< long > gains (n + 1 );     vector<vector< int >> conflicts (n + 1 );     for ( const vector< int >& pair : conflictingPairs) {       const int a = pair [ 0 ];       const int b = pair [ 1 ];       conflicts [ max (a, b)]. push_back ( min (a, b));     }     for ( int right = 1 ; right <= n; ++right) {       for ( const int left : conflicts [right]) {         if (left > maxLeft) {           secondMaxLeft = maxLeft;           maxLeft = left;         } else if (...
Post a Comment
Read more

3487. Maximum Unique Subarray Sum After Deletion

 C++ class Solution { public: int maxSum ( vector < int >& nums ) { int mx = ranges :: max ( nums ); if ( mx <= 0 ) { return mx ; } unordered_set < int > s ; int ans = 0 ; for ( int x : nums ) { if ( x < 0 || s . contains ( x )) { continue ; } ans += x ; s . insert ( x ); } return ans ; } }; JAVA class Solution { public int maxSum ( int [] nums ) { int mx = Arrays . stream ( nums ). max (). getAsInt (); if ( mx <= 0 ) { return mx ; } boolean [] s = new boolean [ 201 ]; int ans = 0 ; for ( int x : nums ) { if ( x < 0 || s [ x ]) { continue ; } ans += x ; s [ x ] = true ; } ...
Post a Comment
Read more

2322. Minimum Score After Removals on a Tree

 C++ class Solution { public: vector < int > nums ; int s ; int s1 ; int n ; int ans = INT_MAX ; vector < vector < int >> g ; int minimumScore ( vector < int >& nums , vector < vector < int >>& edges ) { n = nums . size (); g . resize ( n , vector < int > ()); for ( auto & e : edges ) { int a = e [ 0 ], b = e [ 1 ]; g [ a ]. push_back ( b ); g [ b ]. push_back ( a ); } for ( int & v : nums ) s ^= v ; this -> nums = nums ; for ( int i = 0 ; i < n ; ++ i ) { for ( int j : g [ i ]) { s1 = dfs ( i , - 1 , j ); dfs2 ( i , - 1 , j ); } } return ans ; } int dfs ( int i , int fa , int x ) { int res = nums [ i ]; for ...
Post a Comment
Read more