概述
对近期刷题做一些记录，注：思路来源于官方、其他优质解答（或自己）。
1.两数之和
标签：数组
难易程度：简单
题目描述：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
解题思路：
思路1：遍历数组，用目标值减去第一个整数，查找数组中是否存在两数之差，若存在，返回两个整数的数组下标。
class Solution {
public int[] twoSum(int[] nums, int target) {
for(int i = 0;i < nums.length;i++){
for(int j = i+1; j < nums.length;j++){
int component = target - nums[i];
if(nums[j] == component){
return new int[]{i, j};
}
}
}
throw new IllegalArgumentException("No two sum solution");
}
}
运行结果：
思路2：与思路1类似，利用HashMap保存数组的值及其对应下标。
import java.util.*;
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> map = new HashMap<>();
for(int i = 0;i < nums.length;i++){
map.put(nums[i], i);
}
for(int i = 0;i < nums.length;i++){
int component = target - nums[i];
if(map.containsKey(component) && map.get(component) != i){
return new int[]{i, map.get(component)};
}
}
throw new IllegalArgumentException("No two sum solution");
}
}
运行结果：
2.删除排序数组中的重复项
标签：数组
难易程度：简单
给定一个排序数组，你需要在原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组 并在使用 O(1) 额外空间的条件下完成。
解题思路：
设置两个指针，慢指针i和快指针j，用j遍历数组，只要i指向的值等于j指向的值，我们就增加j，以跳过重复项；当j指向的值不等于i指向的值时，将i加1，同时将j指向的值赋给当前i所指向的值。接着我们将再次重复相同的过程，直到 j到达数组的末尾为止。最后移除重复元素后数组的新长度为i+1。
class Solution {
public int removeDuplicates(int[] nums) {
if(nums == null || nums.length == 0){
return 0;
}
int i = 0;
for(int j = 1;j < nums.length;j++){
if(nums[j] != nums[i]){
i++;
nums[i] = nums[j];
}
}
int length = i + 1;
return length;
}
}
运行结果：
3.移除元素
标签：数组
难易程度：简单
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1)额外空间并原地修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
解题思路：
同问题2类似。设置两个指针，慢指针i和快指针j，用j遍历数组，当nums[j] = val时，我们就增加j，以跳过重复项；当nums[j] != val时，将j指向的值赋给当前i所指向的值，i++。接着我们将再次重复相同的过程，直到 j到达数组的末尾为止。最后移除指定元素后数组的新长度为i。
class Solution {
public int removeElement(int[] nums, int val) {
if(nums == null || nums.length == 0){
return 0;
}
int i = 0;
for(int j = 0;j < nums.length;j++){
if(nums[j] != val){
nums[i] = nums[j];
i++;
}
}
return i;
}
}
运行结果：
4.搜索插入位置
标签：数组
难易程度：简单
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。你可以假设数组中无重复元素。
解题思路：
采用二分查找，如果找到目标值，返回其索引；否则返回low。
class Solution {
public int searchInsert(int[] nums, int target) {
if(nums == null || nums.length == 0){
return 0;
}
int low = 0;
int high = nums.length - 1;
while(low <= high){
int mid = (high + low) / 2;
if(nums[mid] == target){
return mid;
}else if(nums[mid] > target){
high = mid - 1;
}else{
low = mid + 1;
}
}
return low;
}
}
运行结果：
5.连续子数组的最大和
标签：数组
难易程度：简单
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
解题思路：
如果当前和小于0，则用当前值代替当前和，如果当前和大于0，则用当前和加上当前值代替当前和，使用result保存当前最大值。
import java.lang.*;
class Solution {
public int maxSubArray(int[] nums) {
if(nums == null || nums.length == 0){
return 0;
}
int sum = 0;
int result = nums[0];
for(int num : nums){
sum = sum > 0 ?sum+num : num;
result = Math.max(result, sum);
}
return result;
}
}
运行结果：
6.加1
标签：数组
难易程度：简单
给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。你可以假设除了整数 0 之外，这个整数不会以零开头。
解题思路：
主要分为两种情况：
1.末尾为9
2.不为9
针对情况1：针对末尾为9的情况，需要进位，模拟它的进位方式，如此循环直到判断没有再进位就退出循环返回结果。还有一些特殊情况就是当出现 999999、999999999 之类的数字时，循环到最后也需要进位，出现这种情况时需要手动将它进一位。
针对情况2：直接将数组的最后数据加1即可。
class Solution {
public int[] plusOne(int[] digits) {
int len = digits.length;
for(int i = len-1;i >= 0;i--){
digits[i]++;
digits[i] %= 10;
if(digits[i] != 0){
return digits;
}
}
digits = new int[len+1];
digits[0] = 1;
return digits;
}
}
运行结果：
7.合并两个有序数组
标签：数组
难易程度：简单
给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。 说明:
1.初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
2.你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
解题思路：
设置两个指针p1,p2，分别指向nums1和nums2的尾部，设置指针p指向nums1和nums2合并后的数组的尾部，如果nums1[p1]>nums2[p2]，则nums1[p]=nums1[p1],p1–,p–.之后如果nums2还有剩余元素，复制到nums1中。
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int p1 = m - 1;
int p2 = n - 1;
int p = m + n - 1;
while(p1 >= 0 && p2 >= 0){
nums1[p--] = nums1[p1]>nums2[p2]?nums1[p1--]:nums2[p2--];
}
System.arraycopy(nums2, 0, nums1, 0, p2+1);
}
}
运行结果：
8.杨辉三角
标签：数组
难易程度：简单
给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
解题思路：
设置双层循环。新建一个列表保存每一行中每一列的数据。当列与行相等时，往list中插入1，否则，插入上一行前一列和本列的和。
import java.util.*;
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
for(int i = 0;i < numRows;i++){
List<Integer> sum = new ArrayList<Integer>();
for(int j = 0;j <= i;j++){
if(j == 0 || j == i){
sum.add(1);
}else{
sum.add(result.get(i-1).get(j-1)+result.get(i-1).get(j));
}
}
result.add(sum);
}
return result;
}
}
运行结果：
9.杨辉三角-II
标签：数组
难易程度：简单
给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。
解题思路：
与问题8相同，只不过返回的时第K行的数据，而不是所有行。
import java.util.*;
class Solution {
public List<Integer> getRow(int rowIndex) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
for(int i = 0;i <= rowIndex;i++){
List<Integer> sum = new ArrayList<Integer>();
for(int j = 0;j <= i;j++){
if(j == 0 || j == i){
sum.add(1);
}else{
sum.add(result.get(i-1).get(j-1)+result.get(i-1).get(j));
}
}
result.add(sum);
}
return result.get(rowIndex);
}
}
运行结果：
10.买卖股票的最佳时机
标签：数组
难易程度：简单
给定一个数组，它的第 i 个元素是一支给定股票第 i
天的价格。如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。
解题思路：
1.暴力法。
class Solution {
public int maxProfit(int[] prices) {
int maxpro = 0;
for(int i=0; i<prices.length-1;i++){
for(int j = i+1;j<prices.length;j++){
if(prices[j]-prices[i]>maxpro){
maxpro = prices[j]-prices[i];
}
}
}
return maxpro;
}
}
运行结果：
2.一次遍历
遍历一次数组，维护一个股票最小值，然后计算之后每天与最小值的差值，最大的即为卖出股票的最好时机。
import java.lang.*;
class Solution {
public int maxProfit(int[] prices) {
int maxpro = 0;
int minpro = Integer.MAX_VALUE;
for(int p : prices){
if(p < minpro){
minpro = p;
}
maxpro = Math.max(maxpro, p-minpro);
}
return maxpro;
}
}
运行结果：
最后
以上就是矮小小蝴蝶为你收集整理的LeetCode刷题-数组-1的全部内容，希望文章能够帮你解决LeetCode刷题-数组-1所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复