thảo luận Leetcode mỗi ngày

class Solution {
public:
    bool canSortArray(vector<int>& nums) {
        int i;
        int prev_max = nums[0];
        for (i = 1; i < nums.size() && countBitOnes(nums[i]) == countBitOnes(nums[i - 1]); i++) {
            if (nums[i] > prev_max) {
                prev_max = nums[i];
            }
        }
        int cur_max;
        int cur_min;
        while (i < nums.size()) {
            cur_min = cur_max = nums[i];
            while (i + 1 < nums.size() && countBitOnes(nums[i]) == countBitOnes(nums[i + 1])) {
                if (nums[i + 1] > cur_max) cur_max = nums[i + 1];
                if (nums[i + 1] < cur_min) cur_min = nums[i + 1];
                i++;
            }

            if (prev_max > cur_min) return false;
            prev_max = cur_max;
            i++;
        }

        return true;
    }

    int countBitOnes(int n) {
        int count = 0;
        while (n != 0) {
            if (n & 1) count++;
            n >>= 1;
        }
        return count;
    }
};

public class Solution
{
    public bool CanSortArray(int[] nums)
    {
        int prevMax = 0;
        int currMax = nums[0];
        int prevSetBit = CountSetBits(nums[0]);
        for (int i = 1; i < nums.Length; i++)
        {
            if (prevSetBit == CountSetBits(nums[i]))
            {
                currMax = Math.Max(currMax, nums[i]);
            }
            else
            {
                prevMax = currMax;
                currMax = nums[i];
            }

            prevSetBit = CountSetBits(currMax);


            if (nums[i] < prevMax)
            {
                return false;
            }
        }

        return true;
    }

    public int CountSetBits(int n)
    {
        int count = 0;

        while (n > 0)
        {
            count += n & 1;
            n >>= 1;
        }

        return count;
    }
}

const countSetBit = (num) => {
    const binaryString = num.toString(2);
    let count = 0;
    for(const c of binaryString){
        if(c === '1') count++;
    }
    return count;
}

var canSortArray = function(nums) {
    const setBitMap = new Map();
    for(const num of nums){
        setBitMap.set(num, countSetBit(num));
    }
    nums.sort((a,b)=>{
        if(setBitMap.get(a) !== setBitMap.get(b)) return 0;
        return a-b;
    })
    for(let i = 0;i < nums.length - 1; i++){
        if(nums[i] > nums[i+1]) return false;
    }
    return true;
};

class Solution {
    public boolean canSortArray(int[] nums) {
        int n = nums.length;

        for(int i = 0;i<n - 1;i++){
            for(int j = i + 1;j< n;j++){
                if(nums[i] > nums[j]){
                    if(Integer.bitCount(nums[i]) != Integer.bitCount(nums[j])) return false;
                }
            }
        }

        return true;
    }
}

func canSortArray(nums []int) bool {
    if len(nums) <= 1 { return true }
    pMax, cMin, cMax := 0, nums[0], nums[0]
    pBc := bits.OnesCount(uint(cMin))
    for _, curr := range nums {
        bc := bits.OnesCount(uint(curr))
        if bc == pBc {
            cMin, cMax = min(curr, cMin), max(curr, cMax)
        } else if pMax > cMin {
            return false
        } else {
            pMax, cMin, cMax = cMax, curr, curr
        }
        pBc = bc
    }
    return pMax <= cMin
}

class Solution {
    public boolean canSortArray(int[] nums) {
        int pre = Integer.bitCount(nums[0]);
        int preMax = 0;
        int min = nums[0];
        int max = nums[0];
        for(int i : nums){
            if(Integer.bitCount(i)==pre){
                min = Math.min(min,i);
                max = Math.max(max,i);
            }else{
                if(min<preMax)
                    return false;
                preMax = max;
                min = i;
                max = i;
            }
            pre = Integer.bitCount(i);
        }
        if(min<preMax)
            return false;
        return true;
    }
}

class Solution {
    struct Segment {
        var max: Int
        var min: Int
        var bits: Int
    }
    func canSortArray(_ nums: [Int]) -> Bool {
        var segments:[Segment] = []
        func addNew(_ num: Int,_ bits: Int) {
            segments.append(Segment(max: num, min: num, bits: bits))
        }
        func countSetBits(_ num: Int) -> Int {
            var count = 0, n = num
            while n > 0 {
                count += n & 1
                n >>= 1
            }
            return count
        }
        addNew(nums[0], countSetBits(nums[0]))
        for num in nums {
            let last = segments.last!
            let bits = countSetBits(num)
            if bits == last.bits {
                segments[segments.count-1].min = min(last.min, num)
                segments[segments.count-1].max = max(last.max, num)
            } else {
                addNew(num, bits)
            }
        }

        var preS = Segment(max: 0, min: 0, bits: 0)
        for s in segments {
            if s.min < preS.max {
                return false
            }
            preS = s
        }
        return true
    }
}

public class Solution {
    public bool CanSortArray(int[] nums) {
        List<int> setBits = nums.Select(n => Convert.ToString(n,2).Count(c => c == '1')).ToList();
        for(int i = 0; i<nums.Count()-1; i++)
        {
            for(int j = i+1; j<nums.Count(); j++)
            {
                if (setBits[i] != setBits[j] && nums[i] > nums[j])
                    return false;
            }
        }
        return true;
    }
}

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        
        // remove val at begin
        while (head!=NULL and head->val==val){
            head=head->next;
        }

        ListNode *start = new ListNode(0);
        start->next = head;


        ListNode *s = start; //slow
        ListNode *f = start; //fast


        while (s->next != NULL ){
            
            f=s->next;
            
            if (f->val == val){
                while (f!=NULL and f->val == val)
                    f=f->next;
                s->next = f;
                s=s->next;
            }
            else{
                s->next = f;
                s=s->next;
            }
            
            


            if (s==NULL) break;
        }
        
        return head;
    }
};

class Solution:
    def largestCombination(self, candidates: List[int]) -> int:
        bitCounts = [0]*32
        ans = 0
        for i in range(len(candidates)):
            for j in range(32):
                if candidates[i] >> j & 1 == 1:
                    bitCounts[j] += 1
                    ans = max(ans, bitCounts[j])

        return ans

class Solution {
public:
    int largestCombination(vector<int>& candidates);
};

int Solution::largestCombination(vector<int>& candidates) {
    vector<int> bitSets(8*sizeof(candidates[0]), 0);
    for (int n : candidates) {
        int i = 0;
        while (n) {
            if (n & 1)
                bitSets[i]++;
            n = n >> 1;
            i++;
        }
    }
    int ans = bitSets[0];
    for (int count : bitSets) {
        if (ans < count)
            ans = count;
    }
    return ans;
}

function largestCombination(arr: number[]): number {
    let res = 0;
    for (let i = 31; i >= 0; i--) {
        const cur = arr.filter(num => (num & (1 << i)) !== 0);
        const temp = cur.reduce((acc, num) => acc & num, cur[0] || 0);
        res = Math.max(res, cur.length);
    }
    return res;
};