1、最大子数组和:
给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
子数组 是数组中的一个连续部分。
示例 1:
输入:nums = [-2,1,-3,4,-1,2,1,-5,4]
输出:6
解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。
示例 2:
输入:nums = [1]
输出:1
示例 3:
输入:nums = [5,4,-1,7,8]
输出:23
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/maximum-subarray
class Solution {
public int maxSubArray(int[] nums) {
int ans = nums[0];
int sum = 0;
for(int num: nums) {
if(sum > 0) {
//只要sum还没有小于0,就还有希望成为最大值
sum += num; //有效状态
} else {
//当sum<=0了,说明有两种情况,一种是刚开始记录,另一种就
//是出现了极大负值或者连续负值使连续和小于等于0,那么这个
//连续和目前无法再次成为最大和,重新开始记录并寻找
sum = num; //无效状态
}
//不断比较每次的最大值和历史最大值的大小
ans = Math.max(ans, sum); //使用ans记录最值
}
return ans;
}
}
2、只出现一次的数字
个人解法,暴力遍历:
class Solution {
public int singleNumber(int[] nums) {
Arrays.sort(nums);
for(int i = 0;i < nums.length-2;i+=2){
if(nums[i]!=nums[i+1]){
return nums[i];
}
}
return nums[nums.length-1];
}
}
官方解法,利用异或运算
class Solution {
public int singleNumber(int[] nums) {
int single = 0;
for (int num : nums) {
single ^= num;
}
return single;
}
}
3、合并两个有序链表:
1、迭代法:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode prehead = new ListNode(-1);
ListNode prev = prehead;
while (l1 != null && l2 != null) {
//比较大小选择连接的对象
if (l1.val <= l2.val) {
prev.next = l1;
l1 = l1.next;
} else {
prev.next = l2;
l2 = l2.next;
}
prev = prev.next;
}
//将剩余元素接入链表尾
prev.next = l1 == null ? l2 : l1;
return prehead.next;
}
}
2、递归
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
} else if (l2 == null) {
return l1;
} else if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}
版权声明:本文为qq_51383106原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。