数组，链表，跳表（双指针法）Array例题_链表中双指针法资源-CSDN下载

89 浏览量 2020-12-22 04:33:45 上传评论收藏 60KB PDF 举报

资源详情

资源评论

资源推荐

数组，链表，跳表（双指针法）数组，链表，跳表（双指针法）Array例题例题

核心思路：空间换时间核心思路：空间换时间+升维升维

数组

连续的内存空间，支持随机访问，时间复杂度 O(1)

插入、删除操作比较低效O(n)

链表

单链表、双向链表、循环链表、双向循环链表

更适合插入、删除操作频繁的场景，时间复杂度 O(1)

访问时遍历链表，平均情况时间复杂度为O(n)

跳表

空间换时间，多级索引来提高查询的效率，实现了基于链表的“二分查找”，是一种动态数据结构，支持快速的插入、删除、查

找操作，时间复杂度为O(nlogn)

283.移动零移动零

解法一双指针 (j始终记录下一个非零元素的位置)

public void moveZeroes(int[] nums){

int j = 0;

for(int i = 0 ;i < nums.length; ++i){

if (nums[i] != 0){

nums[j] = nums[i];

if(i!=j){

nums[i] = 0;

}

j++;

}

}

}

输入: [0,1,0,3,12] 输出: [1,3,12,0,0]

解法二遇零交换注意python交换的特殊用法

def moveZeroes(self , nums):

zero = 0

for i in xrange( len(nums) ):

if nums[i] != 0:

nums[i], nums[zero] = nums[zero], num[i] zero += 1

11.盛最多水的容器盛最多水的容器

解法一暴力求解枚举O(n^2)

public int maxArea(int[] a){

int max = 0;

for(int i = 0;i <a.length -1; ++i){

for(int j = i+1; j<a.length; ++j){

int area = (j-i)*Math.min(a[i],a[j]);

max = Math.max(max,area);

}

}return max;

}

输入：[1,8,6,2,5,4,8,3,7] 输出：49

解法二从两边往中间筛选更高的(左右夹逼法）O(N)

public int maxArea(int[] a){

int max = 0;

for(int i = 0, j = a.length- 1 ; i <j ;){

int minHight = a[i] < a[j] ? a[i++] : a[j--];

int area = (j - i + 1)* minHight;

max = Math.max(max,area);

}return max;

}

70.爬楼梯爬楼梯

1：1

2：2

3：f(1)+f(2)

n : f(n)=f(n-1)+f(n-2)

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余2页未读，立即下载

评论0

内容反馈

weixin_38591615

粉丝: 8

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip