【代码随想录】【算法训练营】【第35天】 [1005]K次取反后最大化的数组和 [134]加油站 [135]分发糖果

news/2024/6/14 11:39:33 标签: 算法, 数据结构

前言

思路及算法思维,指路 代码随想录。
题目来自 LeetCode。

day 35,连休两天~

题目详情

[1005] K次取反后最大化的数组和

题目描述

1005 K次取反后最大化的数组和
1005 K次取反后最大化的数组和

解题思路

前提:数组
思路:优先负数取反,未取到k次, 两两抵消后,将绝对值最小的正值取反。
重点:两次贪心。

代码实现

C语言
数组大小排序

注意临界导致数组溢出

int cmp(void *p1, void *p2)
{
    return (*(int *)p1 > *(int *)p2);
}

int sum(int *nums, int numsSize)
{
    int sum = 0;
    for (int i = 0; i < numsSize; i++) {
        sum += nums[i];
    }
    return sum;
}

int largestSumAfterKNegations(int* nums, int numsSize, int k) {
    // 排序
    qsort(nums, numsSize, sizeof(int), cmp);
    // 取反, 优先负数取整
    int zeroIdx = 0;
    int curIdx = 0;
    while ((k > 0) && (curIdx < numsSize) && (nums[curIdx] < 0)) {
        nums[curIdx] = 0 - nums[curIdx];
        curIdx++;
        k--;
    }
    // 判断是否未取到k次, 两两抵消后,将绝对值最小的正值取反
    if (k % 2 != 0) {
        if ((curIdx == 0) || (numsSize == 1)) {
            nums[0] = 0 - nums[0];
        }
        else if (curIdx == numsSize) {
            nums[curIdx - 1] = 0 - nums[curIdx - 1];
        }
        else
        {
            if (nums[curIdx] <= nums[curIdx - 1]) {
                nums[curIdx] = 0 - nums[curIdx];
            }
            else
            {
                nums[curIdx - 1] = 0 - nums[curIdx - 1];
            }
        }
    }
    return sum(nums, numsSize);
}
数组绝对值大小排序
int cmp(void *p1, void *p2)
{
    return abs(*(int *)p1) < abs(*(int *)p2);
}

int sum(int *nums, int numsSize)
{
    int sum = 0;
    for (int i = 0; i < numsSize; i++) {
        sum += nums[i];
    }
    return sum;
}

int largestSumAfterKNegations(int* nums, int numsSize, int k) {
    // 按绝对值从大到小排序
    qsort(nums, numsSize, sizeof(int), cmp);
    // 将前k个负数取正
    for (int j = 0; j < numsSize; j++) {
        if (k == 0) {
            break;
        }
        if (nums[j] < 0) {
            nums[j] = 0 - nums[j];
            k--;
        }
    }
    // k未消耗完,将绝对值最小的元素取反,即数组最后一位
    if (k % 2 == 1) {
        nums[numsSize - 1] = 0 - nums[numsSize - 1];
    }
    // 求和
    return sum(nums, numsSize);
}

[134] 加油站

题目描述

134 加油站
134 加油站

解题思路

前提:
思路:
重点:

代码实现

C语言

[135] 分发糖果

题目描述

135 分发糖果
135 分发糖果

解题思路

前提:
思路:
重点:

代码实现

C语言

今日收获

  1. 贪心算法:艰难的应用。

http://www.niftyadmin.cn/n/5514286.html

相关文章

C# —— 显示转换

显示转换: 通过一些方法可以将其他数据类型转换为我们想要的数据类型 1.括号强转 作用: 一般情况下 将高精度的类型转换为低精度 // 语法: 变量类型 变量名 (转换的变量类型名称) 变量; // 注意: 精度问题 范围问题 sbyte sb 1; short s 1; int …

Day48 代码随想录打卡|二叉树篇---合并二叉树

题目&#xff08;leecode T617&#xff09;&#xff1a; 给你两棵二叉树&#xff1a; root1 和 root2 。 想象一下&#xff0c;当你将其中一棵覆盖到另一棵之上时&#xff0c;两棵树上的一些节点将会重叠&#xff08;而另一些不会&#xff09;。你需要将这两棵树合并成一棵新…

【管理咨询宝藏124】通过BLM打通前端业务与财务的双轨制设计方案

本报告首发于公号“管理咨询宝藏”&#xff0c;如需阅读完整版报告内容&#xff0c;请查阅公号“管理咨询宝藏”。 【管理咨询宝藏124】通过BLM打通前端业务与财务的双轨制设计方案 【格式】PDF版本 【关键词】BLM、组织架构设计、流程优化 【核心观点】 - 运用“拉通业务财务…

C++习题精选(4)—— 栈

目录 1. 最小栈2. 栈的压入弹出序列3. 逆波兰表达式求值 1. 最小栈 题目描述&#xff1a;设计一个支持 push &#xff0c;pop &#xff0c;top 操作&#xff0c;并能在常数时间内检索到最小元素的栈。实现 MinStack 类: MinStack() 初始化堆栈对象。 void push(int val) 将元素…

c++入门必备基础

学习内容&#xff1a; 一.命名空间&#xff08;namespace&#xff09; 首先了解三个作用域&#xff1a; &#xff08;1&#xff09;&#xff1a;局部域 &#xff08;2&#xff09;&#xff1a;全局域 &#xff08;3&#xff09;&#xff1a;命名空间域 命名空间是一种避免…

实验三、拓扑布局和建立小型网络《计算机网络》

假期制定的各种计划但凡实施了一点&#xff0c;也不至于一点都没有实施。 目录 一、实验目的 二、实验内容 三、实验小结 一、实验目的 1. 正确识别网络中使用的电缆线&#xff1b; 2. 为点对点网络和交换网络实施物理布线&#xff1b; 3. 验证每个网络的基本连通性。…

第二章:SQL的运算法则

法则1-1 算数运算符是对其两边的列或者值进行运算的符号 括号可以提升优先级 NULL的运算&#xff0c;结果是NULL 比较运算符是判断列或者值是否相等&#xff0c;比较大小 判断是否为NULL使用 IS NULL 或者 IS NOT NULL SELECT子句中可以使用常数或者表达式 select Pro*2 from P…

$(this) 和 this 关键字在 jQuery 中有何不同?

在 jQuery 中&#xff0c;$(this) 和 this 关键字有一些不同之处。 1. $(this) 是将 this 转换为一个 jQuery 对象。这意味着你可以使用 jQuery 提供的方法和功能来操作这个元素。例如&#xff0c;可以使用 $(this).hide() 来隐藏当前元素。 2. this 关键字是指当前上下文中的…