首页 > 其他分享 >[LeetCode] 2485. Find the Pivot Integer

[LeetCode] 2485. Find the Pivot Integer

时间:2023-06-26 23:25:57浏览次数:51  
标签:integer 中枢 int 2485 整数 pivot Pivot LeetCode

Given a positive integer n, find the pivot integer x such that:

  • The sum of all elements between 1 and x inclusively equals the sum of all elements between x and n inclusively.

Return the pivot integer x. If no such integer exists, return -1. It is guaranteed that there will be at most one pivot index for the given input.

Example 1:

Input: n = 8
Output: 6
Explanation: 6 is the pivot integer since: 1 + 2 + 3 + 4 + 5 + 6 = 6 + 7 + 8 = 21.

Example 2:

Input: n = 1
Output: 1
Explanation: 1 is the pivot integer since: 1 = 1.

Example 3:

Input: n = 4
Output: -1
Explanation: It can be proved that no such integer exist. 

Constraints:

  • 1 <= n <= 1000

找出中枢整数。

给你一个正整数 n ,找出满足下述条件的 中枢整数 x :

1 和 x 之间的所有元素之和等于 x 和 n 之间所有元素之和。
返回中枢整数 x 。如果不存在中枢整数,则返回 -1 。题目保证对于给定的输入,至多存在一个中枢整数。

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/find-the-pivot-integer
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

这是一道数学题,请你找到一个比 n 小的数字 x,满足 1 + 2 + 3 + ... + x  = x + (x + 1) + (x + 2) + ... + n。

小学数学告诉我们(首项 + 末项)* 项数 / 2 = 一个连续数组的和,我们把它记为 total。接着我们从 1 遍历到 n,同时记录从 1 到 n 的前缀和,看看计算到哪个数字的时候能满足题目给的公式,即左半边的和 = 右半边。

时间O(n)

空间O(1)

Java实现

 1 class Solution {
 2     public int pivotInteger(int n) {
 3         int total = (1 + n) * n / 2;
 4         int sum = 0;
 5         for (int i = 1; i <= n; i++) {
 6             sum += i;
 7             if (sum == total - sum + i) {
 8                 return i;
 9             }
10         }
11         return -1;
12     }
13 }

 

LeetCode 题目总结

标签:integer,中枢,int,2485,整数,pivot,Pivot,LeetCode
From: https://www.cnblogs.com/cnoodle/p/17507417.html

相关文章

  • 力扣---2485. 找出中枢整数
    给你一个正整数 n ,找出满足下述条件的 中枢整数 x :1 和 x 之间的所有元素之和等于 x 和 n 之间所有元素之和。返回中枢整数 x 。如果不存在中枢整数,则返回 -1 。题目保证对于给定的输入,至多存在一个中枢整数。 示例1:输入:n=8输出:6解释:6是中枢整数,因......
  • LeetCode 128. 最长连续序列
    为什么这题我都不会,脑袋有点累,状态真差classSolution{public:intlongestConsecutive(vector<int>&nums){unordered_set<int>s(nums.begin(),nums.end());//记录数字是否出现过intres=0;for(autoi:nums)//枚举每个数字,查看以当前数字......
  • leetcode-前缀和数组&差分数组
    前缀和数组:前缀和技巧适用于快速、频繁地计算一个索引区间内的元素之和。(仅仅适用于原数组不变的情况,如果原数组经常修改,则需要考虑差分数组。)模版如下:classPrefixSum{//前缀和数组privateint[]preSum;/*输入一个数组,构造前缀和*/publicPrefixSu......
  • 二叉树-快排-leetcode912
    给你一个整数数组nums,请你将该数组升序排列。示例1:输入:nums=[5,2,3,1]输出:[1,2,3,5]示例2:输入:nums=[5,1,1,2,0,0]输出:[0,0,1,1,2,5]提示:1<=nums.length<=5*104-5*104<=nums[i]<=5*104思路:快排,或者叫前序二叉树,排序后端结果是一个二叉搜索树//lee......
  • leetcode 48 旋转图像 rotate-image【ct】
    ====思路:1.对角线翻折  i=0;i<matrix.lengthj=i;j<matrix.lengthmatrix[i][j]matrix[j][i]=matrix[j][i]matrix[i][j]2.左右翻折i=0i<matrix.lengthj=0j<Math.floor(matrix.length/2)matrix[i][j]matrix[i][matrix.lengt......
  • 【LeetCode摩尔投票】有趣的简单题:数组中出现次数超过一半的数字
    数组中出现次数超过一半的数字https://leetcode.cn/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。你可以假设数组是非空的,并且给定的数组总是存在多数元素。示例1:输入:[1,2,3,......
  • #yyds干货盘点# LeetCode程序员面试金典:各位相加
    1.简述:给定一个非负整数num,反复将各个位上的数字相加,直到结果为一位数。返回这个结果。 示例1:输入:num=38输出:2解释:各位相加的过程为:38-->3+8-->1111-->1+1-->2由于 2是一位数,所以返回2。示例2:输入:num=0输出:02.代码实现:classSolution{pu......
  • #yyds干货盘点# LeetCode程序员面试金典:单词拆分 II
    题目:给定一个字符串s和一个字符串字典 wordDict ,在字符串 s 中增加空格来构建一个句子,使得句子中所有的单词都在词典中。以任意顺序返回所有这些可能的句子。注意:词典中的同一个单词可能在分段中被重复使用多次。 示例1:输入:s="catsanddog",wordDict=["cat","cats","......
  • [leetcode]114. 二叉树展开为链表
    总结:怎样写递归函数?关键是把递归函数的功能定义清楚,并在递归函数体中使用自身来做事,此时不要关注递归函数执行的细节。也就是写高层级代码的时候不要关注低层级的事情,这就叫抽象。关注也没有用,想不清楚的。 1classSolution{2publicvoidflatten(TreeNoderoot){......
  • leetcode 16 最接近的三数之和 3sum-closest【ct】
    ===思路:在遍历中去计算,每一轮循环中都去计算,如果distance更小就去更新distance。如果sum>target,end--,如果sum<target,start++,如果等于,就可以直接返回target  ......