LC Array

695. Max Area of Island:

寻路或者算面积就简单的用queue即可,排出一个,进来周围。

 

689. Maximum Sum of 3 Non-Overlapping Subarrays

求和之后,从前往后做一个递增的取最大的(最大值,最大值位置)数组,然后再从后往前递增的数组,此时对位置k来说,k-r,k,k+r这3个位置之和即取包含k位置的最大值。因此只需遍历[k, len()-k]找出最大值即为所想要的最大值。

 

667. Beautiful Arrangement II
由于一下数列必定含有n-1个不同的差[1,n,2,n-1,3,…..],我们只需做出这么个数列之后,将剩下的部分按顺序排一下即可。
621. Task Scheduler
假设有K个任务出现了最多的M次,而任务最小间隔为N,则总共最少需要(N+1)*(M-1)+K->间隔N即N+1为一轮回,除了最后一轮外都是满轮回,最后一轮只需要跑完K即可。若此长度小于所有任务总数,则说明所有中间间隔必定能被填满,所以只需返回任务总数即可。
560. Subarray Sum Equals K
本质上来说就是3-sum问题,前n1个数之和减去前n2个数之和即为n1到n2这个subarray之和。所以只需构建一个maptable,放入K-sum(n)并在maptable中寻找sum(n)的值加到个数上即可。
414. Third Maximum Number
Python 可以用 set(list) 的方式来迅速构建一个不重复的集,然后可以用set.remove(val)来移除。
289. Game of Life
对于一个无限大小的地图,可以只存有东西的地点的坐标来存下整张地图。
287. Find the Duplicate Number
这道题的本质就是link list cycle 2,由于有n+1个数,数的范围是1-n,我们可将num[i]的值视为node->next。此题中由于数不为0,nums[0]一定是环外面的起始点。而所谓的重复即为寻找环开始的点,那完全就是link list cycle 2。
39. Combination Sum
穷举本质上来讲就是DFS,而DFS就是recursion。
238. Product of Array Except Self
由于不能使用除法,而有需要算除了该数之外的乘积,我们可以将该数之乘积拆成该数之前的乘积乘以该数之后的乘积,由此只需求从前往后乘和从后往前乘的数值即可。
229. Majority Element II
寻找出现前n多的元素(比如1个大于1/2总数的或者两个大于1/3总数的)可以用 Boyer-Moore Majority Vote algorithm,简单来说,此方法先建n类,遇到同类则该类+1,遇到不同则全体-1,减到零遇到新的换新的,最终剩下的元素即为所求。
53. Maximum Subarray
此题只需建立两个变量,一个cursum,一个maxsum,其中cursum为max(cursum+num[i], num[i]),由此可保证每次取到的都是包括当前的数的连续array中最大的,而maxsum则为max(maxsum,xursum),最终返回maxsum即可。
55. Jump Game
由后至前,每次更新能跳到最后的最小位置,最终若最小位置小于等于0,则可以。

发表评论

电子邮件地址不会被公开。 必填项已用*标注