亲宝软件园·资讯

展开

LeetCode数组移除数组中目标元素等题目

CoderRdf 人气:0
一种自己解题,一种高赞解题 
/**
* 移除数组中目标元素,返回新数组长度
* @param nums
* @param val
* @return
*/
public int removeElement(int[] nums, int val) {
int result = 0;
for (int i = 0; i < nums.length; i++) {
if(nums[i] != val) {
nums[result++] = nums[i];
}
}
return result;
}
public int removeElement2(int[] nums, int val) {
int result = 0;
int length = nums.length;
while(result <length) {
if(nums[result] == val){
nums[result] = nums[length-1];
length--;
continue;
}
result ++;
}
return result;
}

/**
* 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
* @param nums
* @param target
* @return
*/
public int searchInsert(int[] nums, int target) {
//return searchInsertByIndex(nums,0,nums.length-1,target);
int n = nums.length;
int left = 0, right = n - 1, ans = n;
while (left <= right) {
int mid = ((right - left) >> 1) + left;
if (target <= nums[mid]) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;
}

private int searchInsertByIndex(int[] nums, int start,int end, int target) {
int half = (start+end) / 2;
if(target <= nums[start]){
return start;
}
if(target == nums[end]){
return end;
}
if(target > nums[end]){
return end+1;
}
if(nums[half]>=target){
if(nums[half-1] <target) {
return half;
}else{
return searchInsertByIndex(nums,0,half-1,target);
}
}else{
if(nums[half+1] >=target) {
return half+1;
}else{
return searchInsertByIndex(nums,half,end,target);
}
}
}

/**
* 给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
* @param nums
* @return
*/
public int maxSubArray(int[] nums) {
int pre = 0, maxAns = nums[0];
for (int x : nums) {
pre = Math.max(pre + x, x);
maxAns = Math.max(maxAns, pre);
}
return maxAns;
}

public int maxSubArray2(int[] nums) {
int maxAns = nums[0];
int[] result = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
if (i == 0) {
result[i] = nums[i];
} else {
result[i] = Math.max(result[i - 1] + nums[i], nums[i]);
}
maxAns = Math.max(result[i],maxAns);
}
// for (int x : result) {
// if (x > maxAns) {
// maxAns = x;
// }
// }
return maxAns;
}

/**
* 给定一个由 整数 组成的 非空 数组所表示的非负整数,在该数的基础上加一。
* 最高位数字存放在数组的首位, 数组中每个元素只存储单个数字
* @param digits
* @return
*/
public int[] plusOne(int[] digits) {
int flag = 0;
int sum = 0 ;
for(int i = digits.length-1 ;i>=0 ;i--){
if(i == digits.length -1) {
sum = digits[i] + flag +1;
}else{
sum = digits[i] + flag;
}
flag = (sum)/10;
digits[i] = sum%10;
}
if(flag > 0){
digits = new int[digits.length + 1];
digits[0] = 1;
}

return digits;
}

public int[] plusOne2(int[] digits) {

for (int i = digits.length - 1; i >= 0; i--) {
digits[i]++;
digits[i] = digits[i] % 10;
if (digits[i] != 0) {
return digits;
}
}
digits = new int[digits.length + 1];
digits[0] = 1;

return digits;
}

加载全部内容

相关教程
猜你喜欢
用户评论