LeetCode problem solving essay: greedy algorithm

catalogue

Zero. Preface

1, Simple questions

455. distribution of biscuits

1005. maximized array sum after K negations

860. lemonade change

2, Sequence problem

376. swing sequence [*]

 738. Monotonically increasing number

Zero. Preface

Principle of using greedy algorithm: manually simulate it. If you can deduce the overall optimization through local optimization, and you can't think of a counterexample, then try greedy

General steps of greedy algorithm:

  • Decompose the problem into several sub problems
  • Find the right greedy strategy
  • Solve the optimal solution of each subproblem
  • Stack local optimal solutions into global optimal solutions

1, Simple questions

455. distribution of biscuits

int findContentChildren(vector<int>& g, vector<int>& s) {
        int i = 0;
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        for (int j = 0; j < s.size(); j++) {
            if (i <= g.size() && g[i] <= s[j]) {
                i++;
            }
        }
        return i;
    }

Small biscuits can satisfy the children with small appetite first / large biscuits can satisfy the children with large appetite first.

1005. maximized array sum after K negations

int largestSumAfterKNegations(vector<int>& nums, int k) {
        // Make all negative numbers positive as much as possible
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] < 0) {
                if (k > 0) {
                    nums[i] = -nums[i];
                    k--;
                }
            }
        }
        // At this time, if k>0, the array must be all positive numbers, and only the case where k is an odd number needs to be handled
        sort(nums.begin(), nums.end());
        if (k > 0 && k % 2 != 0) {
            nums[0] = -nums[0];
        }
        return accumulate(nums.begin(), nums.end(), 0);
    }

This topic uses the greedy thought, as far as possible changes all negative numbers into positive numbers. If K is still greater than 0 after this operation, just deal with the case where k is an odd number and reverse the smallest element.

860. lemonade change

bool lemonadeChange(vector<int>& bills) {
        int fiveCnt = 0;
        int tenCnt = 0;
        for (auto i : bills) {
            if (i == 5)  fiveCnt++;
            else if (i == 10) {
                if (fiveCnt < 1)   return false;
                fiveCnt--;
                tenCnt++;
            }
            else {
                // Give priority to 10 yuan
                if (fiveCnt >= 1 && tenCnt >= 1) {
                    fiveCnt--;
                    tenCnt--;
                }
                else if (fiveCnt >= 3) {
                    fiveCnt -= 3;
                }
                else   return false;
            }
        }
        return true;
    }

This question is simple. You can deal with three situations respectively. The greedy thought was used in the change of 20 yuan.

2, Sequence problem

376. swing sequence [*]

int wiggleMaxLength(vector<int>& nums) {
        // A sequence with only one element or two unequal elements is also considered a wobble sequence
        if (nums.size() <= 1)    return nums.size();
        int deltaOld = 0;
        // Count the number of peaks in the array (there is a peak by default)
        int res = 1;
        for (int i = 1; i < nums.size(); i++) {
            int deltaNew = nums[i] - nums[i - 1];
            if ((deltaOld <= 0 && deltaNew > 0) || (deltaOld >= 0 && deltaNew < 0)) {
                res++;
                deltaOld = deltaNew;
            }
        }
        return res;
    }

As shown in the above figure (source: Code Capriccio), this question only needs to count the number of peaks in the array, that is, the former difference ≤ 0, the latter difference > 0, or the former difference ≥ 0, the latter difference < 0.

As shown in the following figure (source: Code Capriccio), pay attention to the "=" symbol in it. Such a situation should also be legally included in the results.

 738. monotonically increasing numbers

int monotoneIncreasingDigits(int n) {
        if (n < 10)  return n;
        string strNum = to_string(n);
        int index = strNum.size();
        for (int i = strNum.size() - 1; i > 0; i--) {
            if (strNum[i - 1] > strNum[i]) {
                index = i;
                strNum[i - 1]--;
            }
        }
        for (int j = index; j < strNum.size(); j++) {
            strNum[j] = '9';
        }
        return stoi(strNum);
    }

There are two skills in this question:

  • Comparing the size of adjacent digits, it can be converted into a string for operation without opening up an additional array to store each digit;
  • Operate from right to left. Greed is reflected in the fact that the result string strNum is directly equal to the original number (as large as possible) and operates from right to left. If the previous digit minus one is smaller than the previous digit, you can continue to iterate and modify the number.

If this question is circulated from left to right, the code is as follows:

if (n < 10)    return n;
        // Greedy, take the maximum value on the corresponding digit as far as possible
        string strNum = to_string(n);
        for (int i = 1; i < strNum.size(); i++) {
            // If not, the previous position will be reduced by one, and all subsequent positions will be set to 9
            if (strNum[i - 1] > strNum[i]) {
                int index = i;
                for (int j = index + 1; j < strNum.size(); j++) {
                    strNum[j] = '9';
                }
                while (index - 1 >= 0 && strNum[index - 1] > strNum[index]) {
                    strNum[index] = '9';
                    strNum[index - 1]--;
                    index--;
                }
                break;
            }
        }
        return stoi(strNum);

If there are elements that do not meet the conditions, you can exit the loop directly to reduce the number of cycles.

Tags: Algorithm C++ data structure

Posted by Mikedean on Sat, 04 Jun 2022 02:38:11 +0530