数据结构与算法 --- 【基础入门篇】

1、三个数的最大乘积

三个数的最大乘积

给你一个整型数组 nums ，在数组中找出由三个数组成的最大乘积，并输出这个乘积。乘积不会越界。

输入：nums = [1,2,3]
输出：6

重点考察：线性扫描

思路

1. 如果数组中全是非负数，则排序后的最大的三个数即为最大乘积；如果全是非正数，则最大的三个数相乘同样也是最大乘积。

2. 如果数组中有正数，有负数，则最大乘积可能时三个最大正数的乘积，也可能时两个最小负数（即绝对值最大）与最大正数的乘积。

3. 分别求出三个最大正数的乘积，以及两个最小负数与最大正数的乘积，两者之间的最大值即为所求答案。

解法1：排序

class Solution{
public int maximumProduct(int[]nums){
int n = nums.length;
// 排序
Arrays.sort(nums);
return Math.max(nums[0]*nums[1]*nums[n-1],nums[n-3]*nums[n-2]*nums[n-1]);
}
}

• 时间复杂度：O(NLog(N))
• 空间复杂度：O(1)

解法2：线性扫描

利用for循环，依次找出最大的三个值，和最小的两个值

class Solution {
public int maximumProduct(int[] nums) {
// 线性扫描
// 最小值，min1 < min2
int min1=Integer.MAX_VALUE,min2=Integer.MAX_VALUE;
// 最大值，max1 > max2 > max3
int max1=Integer.MIN_VALUE,max2=Integer.MIN_VALUE,max3=Integer.MIN_VALUE;
for(int num : nums){
if(num<min1){
min2 = min1;
min1 = num;
}else if(num<min2){
min2 = num;
}
if(num>max1){
max3 = max2;
max2 = max1;
max1 = num;
}else if(num>max2){
max3 = max2;
max2 = num;
}else if(num>max3){
max3 = num;
}
}
return Math.max(min1*min2*max1,max1*max2*max3);
}
}

• 时间复杂度：O(N)
• 空间复杂度：O(1)

2、两数之和

两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

解法1：暴力

思路

通过两次for循环，进行依次遍历查找符合的下标。

其中数值不能重复，所以 j = i + 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++){
if(nums[i] + nums[j] == target){
return new int[]{i,j};
}
}
}
return new int[2];
}
}

• 时间复杂度：O(N^2)
• 空间复杂度：O(1)

解法2：哈希表

思路

利用map集合保存对应的值和下标，若target - nums[i]的键值对在集合中已存在，则返回集合中的值的下标，和当前下标i

class Solution {
public int[] twoSum(int[] nums, int target) {
// 定义集合
Map<Integer,Integer> map = new HashMap<>();
for(int i = 0;i < nums.length; i++){
if(map.containsKey(target-nums[i])){
return new int[]{map.get(target-nums[i]),i};
}
map.put(nums[i],i);
}
return new int[2];
}
}

• 时间复杂度：O(N)
• 空间复杂度：O(N)

3、排序数组中的两数之和

排序数组中的两数之和

给定一个已按照 升序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。

解法1：二分查找

思路

通过二分查找，缩小查询范围，直到找到numbers(low) + numbers(mid) == target

class Solution {
public int[] twoSum(int[] numbers, int target) {
// 二分查找
int length = numbers.length;
for(int i =0;i<length;i++){
int low = i+1;
int high = length-1;
while(low<=high){
int mid = low+(high-low)/2;
if(numbers[mid] == target-numbers[i]){
return new int[]{i,mid};
}else if(numbers[mid]>target-numbers[i]){
high = mid - 1;
}else{
low = mid + 1;
}
}
}
return new int[2];
}
}

• 时间复杂度：O(Nlog(N))
• 空间复杂度：O(1)

解法2：双指针

思路

通过两个指针left = 0 , right = nums.length-1 记录两个指针的和 sum = nums[left] + nums[right]
若 sum == target ，则直接返回 left 和 right
若 sum > target，右指针左移一位 right--
若 sum < target，左指针右移一位 left++

class Solution {
public int[] twoSum(int[] numbers, int target) {
// 双指针
int low = 0,high = numbers.length-1;
while(low<high){
int sum = numbers[low] + numbers[high];
if(sum == target){
return new int[]{low,high};
}else if(sum < target){
low++;
}else{
high--;
}
}
return new int[2];
}
}

• 时间复杂度：O(N)
• 空间复杂度：O(1)

4、斐波那契数列

斐波那契数列

斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

• F(0) = 0, F(1) = 1
• F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

解法1：递归

思路

通过F(N) = F(N - 1) + F(N - 2)公式，依次向下递归

直到到达出口n <= 1 时，return n;

class Solution {
public int fib(int n) {
if(n<=1){
return n;
}
return fib(n-1)+fib(n-2);
}
}

• 时间复杂度：O(2^N)
• 空间复杂度：O(N)

解法2：动态规划

思路

利用基本的dp一维数组将已经计算出的值保存在数组中，依次向上递推。

class Solution {
public int fib(int n) {
if(n <= 1){
return n;
}
int MOD = 1000000007;
int[] dp = new int[n+1];
dp[0] = 0;
dp[1] = 1;
for(int i = 2;i <= n;i++){
dp[i] = dp[i-1] + dp[i-2];
dp[i] %=MOD;
}
return dp[n];
}
}

• 时间复杂度：O(N)
• 空间复杂度：O(N)

解法3：优化动态规划

思路

由于题中我们只需要前两个数据即可，我们可以将原来的n+1的数组长度优化为两个变量保存

class Solution {
public int fib(int n) {
int MOD = 1000000007;
if(n <= 1){
return n;
}
// 保存p q 为前两个数据， r为返回数据
int p = 0,q = 0,r=1;
for(int i = 2;i <= n;i++){
p = q;
q = r;
r = (q + p) % MOD;
}
return r;
}
}

• 时间复杂度：O(N)
• 空间复杂度：O(1)

5、排列硬币

排列硬币

你总共有 n 枚硬币，并计划将它们按阶梯状排列。对于一个由k行组成的阶梯，其第i行必须正好有i枚硬币。阶梯的最后一行可能是不完整的。

给你一个数字 n ，计算并返回可形成完整阶梯行的总行数。

解法1：暴力迭代

思路

直接迭代，如果当前剩余的硬币无法满足下一层，则直接返回当前层数

class Solution {
public int arrangeCoins(int n) {
// 迭代
for(int i = 1; i <= n; i++){
n -= i;
if(n <= i){
return i;
}
}
return 0;
}
}

• 时间复杂度：O(N)
• 空间复杂度：O(1)

解法2：二分查找

思路

通过二分查找计算 n 枚硬币可形成的完整阶梯行的总行数。

public static int arrangeCoins(int n) {
int left = 1, right = n;
while (left < right) {
int mid = (right - left + 1) / 2 + left;
if ((long) mid * (mid + 1) <= (long) 2 * n) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}

解法3：数学

class Solution {
public int arrangeCoins(int n) {
return (int)((Math.sqrt((long) 8*n+1)-1)/2);
}
}

6、合并两个有序数组

合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和n，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

解法1：Java API

思路

利用Java中的arraycopy直接进行数组的拷贝

class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
System.arraycopy(nums2,0,nums1,m,n);
Arrays.sort(nums1);
}
}

解法2：双指针

思路

1. 先将原来nums1中的数据拷贝到nums_copy
2. 利用双指针依次比较nums_copy 和 nums2 中的数据，然后插入到nums1中，直到其中一个数组中的元素为空
3. 将剩余元素插入到nums1中

class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
// 双指针
// 备份nums1
int[] nums1_copy = new int[m];
System.arraycopy(nums1,0,nums1_copy,0,m);
// 双指针
int p1 = 0;
int p2 = 0;
int p = 0;
while(p1 < m && p2 < n){
nums1[p++] = nums1_copy[p1] < nums2[p2] ? nums1_copy[p1++] : nums2[p2++];
}
// 插入剩余元素
if(p1 < m){
System.arraycopy(nums1_copy,p1,nums1,p1+p2,m+n-p1-p2);
}
if(p2 < n){
System.arraycopy(nums2,p2,nums1,p1+p2,m+n-p1-p2);
}
}
}

• 时间复杂度：O(M+N)
• 空间复杂度：O(M+N)

解法3：优化双指针

思路

将上述方法对空间上进行优化，利用双指针进行倒序插入，从末尾依次插入进去元素

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--];
}
// 拷贝nums2剩余元素
System.arraycopy(nums2,0,nums1,0,p2+1);
}
}

时间复杂度：O(M+N)
空间复杂度：O(1)

7、环形链表

环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

解法1：Set集合

思路

由于set集合中的key唯一，所以当元素不能放入集合中时，说明列表存在环。

public class Solution {
public boolean hasCycle(ListNode head) {
Set<ListNode> set = new HashSet<>();
while(head!=null){
if(!set.add(head)){
return true;
}
head = head.next;
}
return false;
}
}

• 时间复杂度：O(N)
• 空间复杂度：O(N)

解法2：快慢指针

思路

慢指针一次走一步，快指针一次走两步，直到slow == fast，说明存在环

public class Solution {
public boolean hasCycle(ListNode head) {
if(head == null || head.next == null){
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while(slow != fast){
if(fast == null || fast.next==null){
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}
}

• 时间复杂度：O(N)
• 空间复杂度：O(1)

8、子数组最大平均数

子数组最大平均数

给你一个由n个元素组成的整数数组 nums 和一个整数k。

请你找出平均数最大且 长度为k的连续子数组，并输出该最大平均数。

解法1：滑动窗口

思路

先计算出第一个窗口的值，然后每次移动一个位置，找出两个窗口的最大值进行返回。

class Solution {
public double findMaxAverage(int[] nums, int k) {
// 初始化滑动窗口
int sum =0;
int n = nums.length;
// 第一个窗口的值
for(int i = 0; i < k; i++){
sum += nums[i];
}
int max = sum;
for(int i = k; i < n; i++){
sum = sum - nums[i-k] + nums[i];
max = Math.max(max,sum);
}
return (double)max/k;
}
}

• 时间复杂度：O(N)
• 空间复杂度：O(1)

最后

以上就是等待热狗为你收集整理的数据结构与算法 --- 【基础入门篇】的全部内容，希望文章能够帮你解决数据结构与算法 --- 【基础入门篇】所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。