【算法集训】基础算法：贪心

1913. 两个数对之间的最大乘积差

void insertSort(int * a, int n) {for(int i = 1; i < n; ++i) {int temp = a[i];int j = i - 1;while(j >= 0 && temp < a[j]) {a[j + 1] = a[j];j--;}a[j + 1] = temp;}
}int maxProductDifference(int* nums, int numsSize){insertSort(nums, numsSize);int a = nums[numsSize - 1] * nums[numsSize - 2];int b = nums[0] * nums[1];return a - b;
}

1323. 6 和 9 组成的最大数字

int maximum69Number (int num) {int stack[7], top = 0;while(num) {stack[top++] = num % 10;num /= 10;}for(int i = top - 1; i >= 0; --i) {if(stack[i] == 6) {stack[i] = 9;break;}}int res = 0;while(top--) {res = res * 10 + stack[top];}return res;
}

2405. 子字符串的最优划分

int partitionString(char* s) {int ans = 0;int hash[26];memset(hash, 0, sizeof(hash));for(int i = 0; s[i]; ++i) {if( hash[ s[i] - 'a' ] ) {memset(hash, 0, sizeof(hash));++ans;}hash[ s[i] - 'a' ] = 1;}return ans + 1;
}

860. 柠檬水找零

bool lemonadeChange(int* bills, int billsSize) {int b5 = 0, b10 = 0;for(int i = 0; i < billsSize; ++i) {if(bills[i] == 5) {b5++;}else if(bills[i] == 10) {if(b5 < 1) {return false;}b5--, b10++;}else if(bills[i] == 20) {if(b10 > 0) {if(b5 < 1) {return false;}b10--,b5--;}else if(b5 >= 3) {b5 -= 3;}else {return false;}}}return true;
}