303. 區(qū)域和檢索 - 數(shù)組不可變
題目
給定一個(gè)整數(shù)數(shù)組 nums，求出數(shù)組從索引 i 到 j（i ≤ j）范圍內(nèi)元素的總和替裆，包含 i荣倾、j 兩點(diǎn)。
實(shí)現(xiàn) NumArray 類：
NumArray(int[] nums) 使用數(shù)組 nums 初始化對(duì)象
int sumRange(int i, int j) 返回?cái)?shù)組 nums 從索引 i 到 j（i ≤ j）范圍內(nèi)元素的總和秧骑，包含 i渣淤、j 兩點(diǎn)（也就是 sum(nums[i], nums[i + 1], ... , nums[j])）
示例：
輸入：
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
輸出：
[null, 1, -1, -3]
code
class NumArray {
int[] nums;
int[] prefix;
public NumArray(int[] nums) {
this.nums=nums;
prefix=new int[nums.length+1];
prefix(prefix,nums);
}
public int sumRange(int i, int j) {
return prefix[j+1]-prefix[i];
}
public void prefix(int[] prefix,int[] nums){
for(int i=0;i<nums.length;i++){
prefix[i+1]=prefix[i]+nums[i];
}
}
}
/**
* Your NumArray object will be instantiated and called as such:
* NumArray obj = new NumArray(nums);
* int param_1 = obj.sumRange(i,j);
*/
754. 到達(dá)終點(diǎn)數(shù)字
題目
在一根無限長的數(shù)軸上均抽，你站在0的位置。終點(diǎn)在target的位置取具。
每次你可以選擇向左或向右移動(dòng)脖隶。第 n 次移動(dòng)（從 1 開始），可以走 n 步暇检。
返回到達(dá)終點(diǎn)需要的最小移動(dòng)次數(shù)产阱。
示例 1:
輸入: target = 3
輸出: 2
解釋:
第一次移動(dòng)，從 0 到 1 块仆。
第二次移動(dòng)构蹬，從 1 到 3 王暗。
示例 2:
輸入: target = 2
輸出: 3
解釋:
第一次移動(dòng)，從 0 到 1 庄敛。
第二次移動(dòng)俗壹，從 1 到 -1 。
第三次移動(dòng)藻烤，從 -1 到 2 绷雏。
思路
其實(shí)相當(dāng)于給定數(shù)字1到k，你可以用加號(hào)或者減號(hào)怖亭，使得1到k的一種組合之和是n之众。
code
class Solution {
public int reachNumber(int target) {
target=Math.abs(target);
int k=0;
int sum=0;
while(sum<target){
k++;
sum+=k;
}
if(sum==target) return k;
//sum>target
int deta=sum-target;
if(deta%2==0) return k;
if(k%2==0) return k+1;
return k+2;
}
}
