LC 01
两数之和
// 给定一个整数数组 nums和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个整数，并返回它们的数组下标。
// 输入：nums = [2,7,11,15], target = 9
// 输出：[0,1]
// 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
// 解法1：暴力求解
public class TowSum01 {
public int[] twoSum(int[] nums, int target) {
int[] result = new int[2];
for (int i = 0; i < nums.length; i++) { // 固定指针
for (int j = i + 1; j < nums.length; j++) { // 移动指针
int sum = nums[i] + nums[j];
if (sum == target) {
result[0] = i;
result[1] = j;
return result;
}
}
}
return result;
}
// 解法2：哈希表法
// 把每一个元素作为key，把每一个索引作为value
public int[] twoSum(int[] nums, int target) {
int[] result = new int[2];
Map<Integer, Integer> map = new HashMap<>();
// 把nums数组中的每一个值都添加到map中
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], i);
}
for (int j = 0; j < nums.length; j++) {
int diff = target - nums[j]; // 计算差值
if (map.containsKey(diff) && map.get(diff) != j) { // 如果hash表中有这个差值
result[0] = j;
result[1] = map.get(diff);
return result;
}
}
return result;
}
}LC 26
删除有序数组中的重复项
// 给你一个有序数组nums，请你原地删除重复出现的元素，使每个元素只出现一次 ，返回删除后数组的新长度。
// 不要使用额外的数组空间，你必须在原地修改输入数组 并在使用 O(1) 额外空间的条件下完成。
// 输入：nums = [1,1,2]
// 输出：2, nums = [1,2]
// 解释：函数应该返回新的长度2，并且原数组nums的前两个元素被修改为 1, 2。不需要考虑数组中超出新长度后面的元素。
// 输入：nums = [0,0,1,1,1,2,2,3,3,4]
// 输出：5, nums = [0,1,2,3,4]
// 解释：函数应该返回新的长度5，并且原数组nums的前五个元素被修改为0, 1, 2, 3, 4。不需要考虑数组中超出新长度后面的元素。
// 解法1：
public class RemoveDuplicates26 {
public int removeDuplicates1(int[] nums) {
int l = 0; // 左指针
int r = 1; // 右指针
while (r < nums.length) {
if (nums[l] == nums[r]) {
r ++;
}else {
l ++;
nums[l] = nums[r];
r ++;
}
}
return l + 1;
}
// 解法2：
public int removeDuplicates2(int[] nums){
if (nums.length == 0 || nums.length == 1) {
return nums.length;
}
int count = 0;
for (int i = 1; i < nums.length; i++) {
if (nums[i] != nums[i - 1]){
count ++;
nums[count] = nums[i];
}else {
continue;
}
}
return count + 1;
}
}LC 27
移除元素
// 给你一个数组nums和一个值val，你需要原地移除所有数值等于val的元素，并返回移除后数组的新长度。
// 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
// 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
// 输入：nums = [3,2,2,3], val = 3
// 输出：2, nums = [2,2]
public class RemoveElement27 {
public int removeElement(int[] nums, int val) {
if (nums == null && nums.length == 0)
return 0;
int start = 0; // 前向指针
int end = nums.length - 1; // 后向指针
while (start < end) {
while (start < end && nums[start] != val){
start ++;
}
while (start < end && nums[end] == val){
end --;
}
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
}
return nums[start] == val ? start : start + 1;
}
}LC 35
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
// 解法：二分查找
class Solution {
public int searchInsert(int[] nums, int target) {
int l = 0;
int r = nums.length - 1;
while(l <= r) {
int mid = (l + r) / 2;
if(target == nums[mid]){
return mid;
}else if(target > nums[mid]){
l = mid + 1;
}else{
r = mid - 1;
}
}
return l;
}
}LC 53
// 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
// 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
// 输出：6
// 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
class Solution {
// 动态规划
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;
}
}LC 121
买卖股票的最佳时机
// 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
// 你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。
// 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回0。
public int maxProfit2(int[] prices) {
// 我们只要用一个变量记录一个历史最低价格minprice，我们就可以假设自己的股票是在那天买的
int minPrice = Integer.MAX_VALUE;
int maxProfit = 0;
for (int i = 0; i < prices.length; i++) {
if (prices[i] < minPrice) {
minPrice = prices[i];
} else if (prices[i] - minPrice > maxProfit) {
maxProfit = prices[i] - minPrice;
}
}
return maxProfit;
}LC 283
移动零
// 给定一个数组nums，编写一个函数将所有0移动到数组的末尾，同时保持非零元素的相对顺序。
// 输入: [0,1,0,3,12]
// 输出: [1,3,12,0,0]
// 必须在原数组上操作，不能拷贝额外的数组。尽量减少操作次数。
class Solution {
public void moveZeroes(int[] nums) {
int index = 0;
for(int i = 0; i < nums.length; i++) {
if(nums[i] != 0) {
nums[index] = nums[i];
index ++;
}
}
for (int i = index; i < nums.length; i++) {
nums[i] = 0;
}
}
}LC 485
485 最大连续1的个数
// 给定一个二进制数组，计算其中最大连续1的个数
// 输入：[1,1,0,1,1,1]
// 输出：3
public class FindMaxConsecutiveOnes {
public int findMaxConsecutiveOnes(int[] nums) {
if (nums == null || nums.length == 0)
return 0;
int count = 0; // 用于统计1的个数
int result = 0; // 用于统计连续1的个数
for (int i = 0; i < nums.length; i++) {
if (nums[i] == 1) {
count ++;
}
if (nums[i] == 0) {
result = result > count ? result : count;
count = 0;
}
}
return result > count ? result : count;
}
}LC 496
下一个更大的元素
public class NextGreaterElement {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
int[] arr = new int[nums1.length];
for (int i = 0; i < nums1.length; i++) {
// 先找到nums1[i]在nums2中的位置
int k = 0;
while (k < nums2.length && nums2[k] != nums1[i]) {
k++;
}
// 再往右找到第一个比它大的数
while (k < nums2.length && nums2[k] <= nums1[i]) {
k++;
}
// 构造答案
if (k >= nums2.length) {
arr[i] = -1;
} else {
arr[i] = nums2[k];
}
}
return arr;
}
}
