[day7] [LeetCode] [title22，3，26]

22.括号生成

给出n代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出n = 3，生成结果为：

[

  "((()))",

  "(()())",

  "(())()",

  "()(())",

  "()()()"

]

超时程序（结果是正确的）

超时程序 Part 1 超时程序 Part 2 超时程序 Part 3

功能：

超时程序 Part 1：将返回的多维字符list转换为一维字符串list，并将字符串list输出

超时程序 Part 2：采用递归调用的方式，输入初始list,输出需要得到的list

超时程序 Part 3：网上的程序，主要功能将多维降为一维list

需要注意的是：

两者之间的区别 红框中代码的运行结果 蓝框中代码的运行结果

正确的程序

Part 1 Part 2 Part 3

此通过的程序和上一个程序大体是一样的，但是在加括号的过程中（addParenthesis()里），就开始剪枝了，将list中没有的项进行append(),若已经拥有的项，则跳过而执行其他的程序。

（本来程序做出来是超时的，没准备今天能够做完，吃完晚饭后想了想：可以直接先剪枝，动态规划中避免重复子序列就是用这个方法剪枝的。于是跑完步后修改了下，惊喜出现了，当我再次执行，通过了），但是这个方法的时间复杂度太高了。应该是可以排在通过人中的最后一名了。

嘚瑟下 时间复杂度

看了条形图，别人的执行时间差不多否在50左右，自己却差不多需要用差不多一秒，惭愧啊。不过好歹通过了，之后再想有没有别的办法进行优化。降低时间复杂度。

3. 无重复字符的最长子串

给定一个字符串，找出不含有重复字符的最长子串的长度。

示例：

给定"abcabcbb"，没有重复字符的最长子串是"abc"，那么长度就是3。

给定"bbbbb"，最长的子串就是"b"，长度是1。

给定"pwwkew"，最长子串是"wke"，长度是3。请注意答案必须是一个子串，"pwke"是子序列  而不是子串。

超时程序

超时程序 超时 超时

正确的程序（双指针法）

Part 1
Part 2
时间复杂度

26. 删除排序数组中的重复项

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1:

给定数组nums=[1,1,2], 函数应该返回新的长度2, 并且原数组nums 的前两个元素被修改为1,2。 你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums =[0,0,1,1,1,2,2,3,3,4],函数应该返回新的长度5, 并且原数组nums 的前五个元素被修改为0,1,2,3,4。你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

//nums是以“引用”方式传递的。也就是说，不对实参做任何拷贝int len = removeDuplicates(nums);// 在函数里修改输入数组对于调用者是可见的。// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。for (int i = 0; i < len; i++) {    print(nums[i]);}

超时程序

超时程序 超时