koenjazh-CNfresde
짬뽕얼큰하게의 맨땅에 헤딩 :: '2025/03/19 글 목록

'2025/03/19'에 해당되는 글 2건

Minimum Operations to Make Binary Array Elements Equal to One I

알고리즘 2025. 3. 19. 23:20

Leetcode Problem:

Summary

  • Given a binary array, find the minimum number of operations to make all elements equal to 1 by flipping 3 consecutive elements at a time.

Approach

  • The approach is to iterate through the array and flip 3 consecutive elements at a time until no more flips are possible
  • If a 3 consecutive elements cannot be found, return -1.

Complexity

  • O(n), where n is the number of elements in the array

Explanation

  • The solution iterates through the array and checks if the current element and the next two elements are 0
  • If they are, it flips them and increments the answer
  • This process continues until no more flips are possible
  • If at any point a 3 consecutive elements cannot be found, the function returns -1.

Solution Code:


class Solution {
public:
    int minOperations(vector& nums) {
        int ans = 0;
        for(int i = 0 ; i < nums.size(); i++){
            if(nums[i] == 0){
                for(int j = i; j < i + 3; j++){
                    if(j >= nums.size()) return -1;
                    nums[j] ^= 1;
                }
                ans++;
            }
        }
        return ans;
    }
};

'알고리즘' 카테고리의 다른 글

Find All Possible Recipes from Given Supplies  (0) 2025.03.21
Minimum Cost Walk in Weighted Graph  (0) 2025.03.20
Split Linked List in Parts  (0) 2025.03.19
Longest Nice Subarray  (0) 2025.03.18
Divide Array Into Equal Pairs  (0) 2025.03.17
블로그 이미지

짬뽕얼큰하게

,

Split Linked List in Parts

알고리즘 2025. 3. 19. 08:37

Leetcode Problem:

Summary

  • Given a singly linked list and an integer k, split the linked list into k consecutive linked list parts.

Approach

  • The approach used is to first store the values of the linked list in a vector
  • Then, for each part, create a new linked list with the required number of nodes
  • The remaining nodes are then added to the next part.

Complexity

  • O(n), where n is the number of nodes in the linked list

Explanation

  • The solution starts by storing the values of the linked list in a vector
  • This is done to easily access the values of the linked list
  • Then, for each part, a new linked list is created with the required number of nodes
  • The remaining nodes are then added to the next part
  • This process is repeated for each part, until all parts have been created
  • The time complexity of the solution is O(n), where n is the number of nodes in the linked list, because each node is visited once
  • The space complexity is also O(n), because in the worst case, all nodes are stored in the vector.

Solution Code:


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    vector splitListToParts(ListNode* head, int k) {
        ListNode* ptr = head;
        vector arr;
        vector ans;
        while(ptr){
            arr.push_back(ptr->val);
            ptr = ptr->next;
        }
        int N = arr.size();
        int more = arr.size() % k;
        int arrIdx = 0;
        for(int i = 0 ; i < k ; i++){
            ListNode* tmp = nullptr;
            ListNode* ptr;
            for(int j = 0; j < N / k; j++){
                if (tmp == nullptr) {
                    tmp = new ListNode(arr[arrIdx++]);
                    ptr = tmp;
                } else{
                    ptr->next = new ListNode(arr[arrIdx++]);
                    ptr = ptr->next;
                }
            }
            if (more){
                if (tmp == nullptr) {
                    tmp = new ListNode(arr[arrIdx++]);
                    ptr = tmp;
                } else{
                    ptr->next = new ListNode(arr[arrIdx++]);
                    ptr = ptr->next;
                }
                more--;
            }
            ans.push_back(tmp);
        }

        return ans;
    }
};

'알고리즘' 카테고리의 다른 글

Minimum Cost Walk in Weighted Graph  (0) 2025.03.20
Minimum Operations to Make Binary Array Elements Equal to One I  (0) 2025.03.19
Longest Nice Subarray  (0) 2025.03.18
Divide Array Into Equal Pairs  (0) 2025.03.17
Minimum Time to Repair Cars  (0) 2025.03.16
블로그 이미지

짬뽕얼큰하게

,

공지사항

글 보관함

달력

«   2025/03   »
일 월 화 수 목 금 토
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31

티스토리툴바