leetcode300

时间:2022-02-18 03:43:00

本题使用回溯法,深度优先搜索。使用隐式条件来进行加速。

public class Solution
{
int bestp = ;
int[] x;
Dictionary<int, int> dic = new Dictionary<int, int>(); void Backtrack(int[] nums, int t)
{
if (t >= nums.Length)
{
var sum = ;
for (int i = ; i < nums.Length; i++)
{
if (x[i] == )
{
//Console.Write(nums[i]+" ");
sum++;
}
}
//Console.WriteLine();
bestp = Math.Max(bestp, sum);
return;
} if (dic.Count == || dic.LastOrDefault().Value < nums[t])
{
x[t] = ;
dic.Add(t, nums[t]);
Backtrack(nums, t + );
dic.Remove(t);
}
if (dic.Count + nums.Length - (t + ) > bestp)
{
x[t] = ;
Backtrack(nums, t + );
}
} public int LengthOfLIS(int[] nums)
{
if (nums.Length < )
{
return nums.Length;
} x = new int[nums.Length];
Backtrack(nums, ); return bestp;
}
}

补充一个使用动态规划的方法,使用python实现,但是效率不是很高:

 class Solution:
def lengthOfLIS(self, nums: 'List[int]') -> 'int':
n = len(nums)
if n==0:
return 0
maxnum = 0
dp = [1] * n
for i in range(n):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i],dp[j] + 1)
print(dp[i])
maxnum = max(maxnum,dp[i])
return maxnum

思路分析:双层循环,时间复杂度是O(n^2)。

dp[i]表示在nums中,以nums[i]为结尾的自增子序列的长度。

第13行是在外层循环,每次循环结束的时候更新,全局的最长自增子序列的长度,也就是所求。

内层循环,是从当前位置i,向前寻找[0,i-1]闭区间。如果在nums中,i前面有一个元素j,满足nums[i] > nums[j],则可以在以j为结尾的自增子序列上,增加1的长度,构成新的自增子序列,而dp[i]只保存这些可能构成的新自增子序列中最大的长度。

补充一个java的实现,使用二分查找加速查询,提升效率

 class Solution {
public int lengthOfLIS(int[] nums) {
int n = nums.length;
int[] tails = new int[n];
int len = ;
for (int num : nums) {
int index = binarySearch(tails, len, num);
tails[index] = num;
if (index == len) {
len++;
}
}
return len;
} private int binarySearch(int[] tails, int len, int key) {
int l = , h = len;
while (l < h) {
int mid = l + (h - l) / ;
if (tails[mid] == key) {
return mid;
} else if (tails[mid] > key) {
h = mid;
} else {
l = mid + ;
}
}
return l;
}
}

leetcode300

相关文章