JAVA 牛牛

Home

20. 有效的括号

  • 难度：简单
  • 本题涉及算法： 哈希表 暴力
  • 思路： 哈希表 暴力
  • 类似题型:

题目 20. 有效的括号

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true

示例 2:

输入: "()[]{}"
输出: true

示例 3:

输入: "(]"
输出: false

示例 4:

输入: "([)]"
输出: false

示例 5:

输入: "{[]}"
输出: true

方法一 暴力

解题思路

  • 当左括号 则记录对于的右括号 比如 字符串 ‘[]]’ ，出现 ‘[’ 则在数组 ‘s_list’ 中记录 ‘]’
  • 通过 s_list.insert(0,’右括号’) 可以保证，每次插入的括号和 左括号对称
  • 当出现 右括号 则先判断数组 ‘len(s_list) ==0 ‘ ，因为有可能出现 ‘[]]]’ 或 ‘]’ 的情况
  • 当循环中 出现右括号 则和数组中 ‘s_list.pop(0)’ 进行对比，如果相同，则对于的删除，继续执行，否则返回false
  • 时间复杂度 $O(n)$ 空间复杂度 $O(n)$

    代码

class Solution(object):
    def isValid(self, s):
        # 初始化判断条件
        if s is None:
            return False
        if len(s) == 0:
            return True
        # 当左括号 则记录对于的右括号
        s_list = []
        for a in s:
            if a == '(':
                s_list.insert(0,')')
            elif a == '[':
                s_list.insert(0,']')
            elif a == '{':
                s_list.insert(0,'}')
            elif len(s_list) != 0 and a == s_list.pop(0): # len(s_list) != 0 出现 '[]]'清空的判断
                continue
            else: # 当 不匹配则 返回 False
                return False
        return True # 最后要清空 s_list 才是一个完整的闭环

方法二 升级版 哈希表


class Solution:
    def isValid(self, s: str) -> bool:
        dic = {'{': '}',  '[': ']', '(': ')', '?': '?'}
        stack = ['?']
        for c in s:
            if c in dic: stack.append(c)
            elif dic[stack.pop()] != c: return False
        return len(stack) == 1


public class IsValid {
    /**
     * 哈希表
     *
     * @param s
     * @return
     */
    private static Map<Character, Character> map = new HashMap<>() {
        {
            put('[', ']');
            put('{', '}');
            put('(', ')');
            put('?', '?');
        }
    };

    public boolean isValid(String s) {
        LinkedList<Character> stack = new LinkedList<>() {
            {
                add('?');
            }
        };
        for (Character ch : s.toCharArray()) {
            if (map.containsKey(ch))
                stack.add(ch);
            else if (map.get(stack.removeLast()) != ch)
                return false;
        }

        return stack.size() == 1;

    }
}

方法三 无敌版

class Solution:
    def isValid(self, s):
        while '{}' in s or '()' in s or '[]' in s:
            s = s.replace('{}', '')
            s = s.replace('[]', '')
            s = s.replace('()', '')
        return s == ''

Read more

  • May 04, 2020
  • 0 views

C++ vector 容器浅析

  • 转载自 菜鸟技术-C++ vector 容器浅析

    一、什么是vector？

    向量（Vector）是一个封装了动态大小数组的顺序容器（Sequence Container）。跟任意其它类型容器一样，它能够存放各种类型的对象。可以简单的认为，向量是一个能够存放任意类型的动态数组。

    二、容器特性

    1.顺序序列

    顺序容器中的元素按照严格的线性顺序排序。可以通过元素在序列中的位置访问对应的元素。

    2.动态数组

    支持对序列中的任意元素进行快速直接访问，甚至可以通过指针算述进行该操作。操供了在序列末尾相对快速地添加/删除元素的操作。

    3.能够感知内存分配器的（Allocator-aware）

    容器使用一个内存分配器对象来动态地处理它的存储需求。

    三、基本函数实现

    1.构造函数

  • vector():创建一个空vector
  • vector(int nSize):创建一个vector,元素个数为nSize
  • vector(int nSize,const t& t):创建一个vector，元素个数为nSize,且值均为t
  • vector(const vector&):复制构造函数
  • vector(begin,end):复制[begin,end)区间内另一个数组的元素到vector中

    2.增加函数

  • void push_back(const T& x):向量尾部增加一个元素X
  • iterator insert(iterator it,const T& x):向量中迭代器指向元素前增加一个元素x
  • iterator insert(iterator it,int n,const T& x):向量中迭代器指向元素前增加n个相同的元素x
  • iterator insert(iterator it,const_iterator first,const_iterator last):向量中迭代器指向元素前插入另一个相同类型向量的[first,last)间的数据

    3.删除函数

  • iterator erase(iterator it):删除向量中迭代器指向元素
  • iterator erase(iterator first,iterator last):删除向量中[first,last)中元素
  • void pop_back():删除向量中最后一个元素
  • void clear():清空向量中所有元素

    4.遍历函数

  • reference at(int pos):返回pos位置元素的引用
  • reference front():返回首元素的引用
  • reference back():返回尾元素的引用
  • iterator begin():返回向量头指针，指向第一个元素
  • iterator end():返回向量尾指针，指向向量最后一个元素的下一个位置
  • reverse_iterator rbegin():反向迭代器，指向最后一个元素
  • reverse_iterator rend():反向迭代器，指向第一个元素之前的位置

    5.判断函数

  • bool empty() const:判断向量是否为空，若为空，则向量中无元素

    6.大小函数

  • int size() const:返回向量中元素的个数
  • int capacity() const:返回当前向量所能容纳的最大元素值
  • int max_size() const:返回最大可允许的vector元素数量值

    7.其他函数

  • void swap(vector&):交换两个同类型向量的数据
  • void assign(int n,const T& x):设置向量中第n个元素的值为x
  • void assign(const_iterator first,const_iterator last):向量中[first,last)中元素设置成当前向量元素

    8.看着清楚

    1.push_back 在数组的最后添加一个数据
2.pop_back 去掉数组的最后一个数据
3.at 得到编号位置的数据
4.begin 得到数组头的指针
5.end 得到数组的最后一个单元+1的指针
6．front 得到数组头的引用
7.back 得到数组的最后一个单元的引用
8.max_size 得到vector最大可以是多大
9.capacity 当前vector分配的大小
10.size 当前使用数据的大小
11.resize 改变当前使用数据的大小，如果它比当前使用的大，者填充默认值
12.reserve 改变当前vecotr所分配空间的大小
13.erase 删除指针指向的数据项
14.clear 清空当前的vector
15.rbegin 将vector反转后的开始指针返回(其实就是原来的end-1)
16.rend 将vector反转构的结束指针返回(其实就是原来的begin-1)
17.empty 判断vector是否为空
18.swap 与另一个vector交换数据

    四、基本用法

    #include < vector>
using namespace std;

    五、简单介绍

  • Vector<类型>标识符
  • Vector<类型>标识符(最大容量)
  • Vector<类型>标识符(最大容量,初始所有值)
  • Int i[5]={1,2,3,4,5}
    • Vector<类型>vi(I,i+2);//得到i索引值为3以后的值
  • Vector< vector< int> >v; 二维向量//这里最外的<>要有空格。否则在比较旧的编译器下无法通过

    实例

    1.pop_back()&push_back(elem)实例在容器最后移除和插入数据

#include <string.h>
#include <vector>
#include <iostream>
using namespace std;

int main()
{
    vector<int>obj;//创建一个向量存储容器 int
    for(int i=0;i<10;i++) // push_back(elem)在数组最后添加数据
    {
        obj.push_back(i);
        cout<<obj[i]<<",";    
    }

    for(int i=0;i<5;i++)//去掉数组最后一个数据
    {
        obj.pop_back();
    }

    cout<<"\n"<<endl;

    for(int i=0;i<obj.size();i++)//size()容器中实际数据个数
    {
        cout<<obj[i]<<",";
    }

    return 0;
}


输出结果为：

0,1,2,3,4,5,6,7,8,9,

0,1,2,3,4,

#### 2.clear()清除容器中所有数据
```c++
#include <string.h>
#include <vector>
#include <iostream>
using namespace std;

int main()
{
    vector<int>obj;
    for(int i=0;i<10;i++)//push_back(elem)在数组最后添加数据
    {
        obj.push_back(i);
        cout<<obj[i]<<",";
    }

    obj.clear();//清除容器中所以数据
    for(int i=0;i<obj.size();i++)
    {
        cout<<obj[i]<<endl;
    }

    return 0;
}

输出结果为：

0,1,2,3,4,5,6,7,8,9,

###$ 3.排序

#include <string.h>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    vector<int>obj;

    obj.push_back(1);
    obj.push_back(3);
    obj.push_back(0);

    sort(obj.begin(),obj.end());//从小到大

    cout<<"从小到大:"<<endl;
    for(int i=0;i<obj.size();i++)
    {
        cout<<obj[i]<<",";  
    }

    cout<<"\n"<<endl;

    cout<<"从大到小:"<<endl;
    reverse(obj.begin(),obj.end());//从大到小
    for(int i=0;i<obj.size();i++)
    {
        cout<<obj[i]<<",";
    }
    return 0;
}

输出结果为：

从小到大:

0,1,3,

从大到小:
3,1,0,

1.注意 sort 需要头文件 __#include __ 2.如果想 sort 来降序，可重写 sort

bool compare(int a,int b)
{
    return a< b; //升序排列，如果改为return a>b，则为降序
}
int a[20]={2,4,1,23,5,76,0,43,24,65},i;
for(i=0;i<20;i++)
    cout<< a[i]<< endl;
sort(a,a+20,compare);

4.访问（直接数组访问&迭代器访问）

#include <string.h>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    //顺序访问
    vector<int>obj;
    for(int i=0;i<10;i++)
    {
        obj.push_back(i);   
    }

    cout<<"直接利用数组：";
    for(int i=0;i<10;i++)//方法一
    {
        cout<<obj[i]<<" ";
    }

    cout<<endl;
    cout<<"利用迭代器：" ;
    //方法二，使用迭代器将容器中数据输出
    vector<int>::iterator it;//声明一个迭代器，来访问vector容器，作用：遍历或者指向vector容器的元素
    for(it=obj.begin();it!=obj.end();it++)
    {
        cout<<\*it<<" ";
    }
    return 0;
}

输出结果为：

直接利用数组：0 1 2 3 4 5 6 7 8 9
利用迭代器：0 1 2 3 4 5 6 7 8 9

5.二维数组两种定义方法（结果一样）

方法一

#include <string.h>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main()
{
    int N=5, M=6;
    vector<vector<int> > obj(N); //定义二维动态数组大小5行
    for(int i =0; i< obj.size(); i++)//动态二维数组为5行6列，值全为0
    {
        obj[i].resize(M);
    }

    for(int i=0; i< obj.size(); i++)//输出二维动态数组
    {
        for(int j=0;j<obj[i].size();j++)
        {
            cout<<obj[i][j]<<" ";
        }
        cout<<"\n";
    }
    return 0;
}

方法二

#include <string.h>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main()
{
    int N=5, M=6;
    vector<vector<int> > obj(N, vector<int>(M)); //定义二维动态数组5行6列

    for(int i=0; i< obj.size(); i++)//输出二维动态数组
    {
        for(int j=0;j<obj[i].size();j++)
        {
            cout<<obj[i][j]<<" ";
        }
        cout<<"\n";
    }
    return 0;
}

输出结果为：

0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

Read more

  • 0 views

Python3 内置函数

参考链接

菜鸟Python3 内置函数

zip()

zip() 函数用于将可迭代的对象作为参数，将对象中对应的元素打包成一个个元组，然后返回由这些元组组成的列表。
如果各个迭代器的元素个数不一致，则返回列表长度与最短的对象相同，利用 * 号操作符，可以将元组解压为列表。

divmod()

Python divmod() 函数接收两个数字类型（非复数）参数，返回一个包含商和余数的元组(a // b, a % b)。

List pop()

pop() 函数用于移除列表中的一个元素（默认最后一个元素），并且返回该元素的值。
可以通过 list.pop(index) index 表示下标，意思是删除指定位置的值 并返回

List remove()

remove() 函数用于移除列表中某个值的第一个匹配项。
list.remove('abc')

enumerate()

enumerate() 函数用于将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列，同时列出数据和数据下标，一般用在 for 循环当中。
for i, element in enumerate(seq):
...     print i, element

Tuple名为元组

Tuple名为元组，可以看做是一种“不变”的List，即tuple一旦创建完毕，就不能修改了

通过 self.属性 self.函数 来调用外部的属性或函数

class Solution:
    cur = float("-inf")
    def isValidBST(self, root: TreeNode) -> bool:
        if root is None:
            return True
        # 访问左子树
        if  not self.isValidBST(root.left):
            return False
        # 访问当前节点：如果当前节点小于等于中序遍历的前一个节点，说明不满足BST，返回 false；否则继续遍历。
        if (root.val <= self.cur):
            return False
        self.cur = root.val
        # 访问右子树
        return self.isValidBST(root.right)

Read more

  • 0 views

5385. 改变一个整数能得到的最大差值

  • 难度：中等
  • 本题涉及算法： 循环
  • 思路： 循环
  • 类似题型:
  • 反思:当对比了自己一开始写的题解代码后，发现一个问题，写代码存在，用机器的方式编写，和以人脑的方式编写

题目 5385. 改变一个整数能得到的最大差值

给你一个整数 num 。你可以对它进行如下步骤恰好 两次 ：

  • 选择一个数字 x (0 <= x <= 9).
  • 选择另一个数字 y (0 <= y <= 9) 。数字 y 可以等于 x 。
  • 将 num 中所有出现 x 的数位都用 y 替换。
  • 得到的新的整数 不能 有前导 0 ，得到的新整数也 不能 是 0 。
  • 令两次对 num 的操作得到的结果分别为 a 和 b 。

请你返回 a 和 b 的 最大差值 。

 

示例

示例 1：

输入：num = 555
输出：888
解释：第一次选择 x = 5 且 y = 9 ，并把得到的新数字保存在 a 中。
第二次选择 x = 5 且 y = 1 ，并把得到的新数字保存在 b 中。
现在，我们有 a = 999 和 b = 111 ，最大差值为 888

示例 2：

输入：num = 9
输出：8
解释：第一次选择 x = 9 且 y = 9 ，并把得到的新数字保存在 a 中。
第二次选择 x = 9 且 y = 1 ，并把得到的新数字保存在 b 中。
现在，我们有 a = 9 和 b = 1 ，最大差值为 8

示例 3：

输入：num = 123456
输出：820000

示例 4：

输入：num = 10000
输出：80000

示例 5：

输入：num = 9288
输出：8700

解题思路

  • 使用方法 str.replace() 替换相同的元素
  • 每个元素都从 0 到 9 都替换一遍 ，并记录最大值和最小值，最后返回最大差值
    • 排除 前导 != 0

      代码

      class Solution(object):
  def maxDiff(self, num):
  num_max ,num_min = int(num) , int(num)
  st = str(num)
  for i in range(10):
      for j in range(10):
          a,b = str(i),str(j)
          x = st.replace(a,b)
          if x.startswith('0'):
              continue
          x = int(x)
          num_max = max(num_max,x)
          num_min = min(num_min,x)
  return num_max - num_min

Read more

  • May 03, 2020
  • 0 views

53. 最大子序和

  • 难度：简单
  • 本题涉及算法： 贪心 动态规划
  • 思路： 贪心 动态规划
  • 类似题型:

题目 53. 最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

方法一 贪心

  • 这道题用动态规划的思路并不难解决，比较难的是后文提出的用分治法求解，但由于其不是最优解法，所以先不列出来
  • 动态规划的是首先对数组进行遍历，当前最大连续子序列和为 sum，结果为 ans
  • 如果 sum > 0，则说明 sum 对结果有增益效果，则 sum 保留并加上当前遍历数字
  • 如果 sum <= 0，则说明 sum 对结果无增益效果，需要舍弃，则 sum 直接更新为当前遍历数字
  • 每次比较 sum 和 ans 的大小，将最大值置为 ans ，遍历结束返回结果
  • 时间复杂度：$O(n)$
class Solution(object):
    def maxSubArray(self, nums):
        ans = nums[0]
        numsSum = 0
        for num in nums:
            if numsSum >0:
                numsSum += num
            else:
                numsSum = num
            ans = max(numsSum,ans)
        return ans

动态规划

  • 最重要的是搞清楚 dp 数组所存储元素的意义,这里要明确 dp[i] 存储的不是从 0 到 i 这个范围内所得到的最大的连续子数组的和，而是 以 nums[i] 为结尾的子数组所能达到的最大的和
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        if len(nums) == 1:
            return nums[0]
        # 下面为nums长度至少为2的情况
        res = nums[0]  # 先设定一个初始值（假设第一个数是可获得的最小值）
        for i in range(1, len(nums)):
            nums[i] = max(nums[i], nums[i] + nums[i - 1])  # 更新后的nums[i]存储 以原始num[i]为结尾的子数组和的最大值
            res = max(res, nums[i])  # 更新最大值
        return res

Read more

  • May 03, 2020
  • 0 views

152. 乘积最大子数组

  • 难度：中等
  • 本题涉及算法： 贪心 动态规划
  • 思路： 贪心 动态规划
  • 类似题型:

题目 152. 乘积最大子数组

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字）。

示例 1:

输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

方法一 动态规划

  • 解题思路:
    • 如果 数组 中不包含负数，只需要维护一个最大值
    • 当出现负数的时候 ，我们可以再维护一个最小值，
    • 通过维护最大值最小值，可以保证当前乘积下，最大与最小值
  • 算法流程：
    • 通过动态规划，记录每次乘积下的最大值和最小值，并在当前遍历结束前判断__最大值__
  • 复杂度分析：
    • 时间复杂度 $O(N)$ ，$N$ 为数组的长度
    • 空间复杂度 $O(N)$， 我们使用了两个长度为 $N$ 数组，记录最大值和最小值

python

class Solution(object):
    def maxProduct(self, nums):
        le = len(nums)
        if nums is None:
            return 0
        if le == 1:
            return nums[0]

        res = nums[0]
        dp_max ,dp_min = [0] * le ,[0] * le
        dp_max[0] = nums[0]
        dp_min[0] = nums[0]
        for i in range(1,le):
            if nums[i] >= 0:
                dp_max[i] = max(dp_max[i-1] * nums[i],nums[i])
                dp_min[i] = min(dp_min[i-1] * nums[i],nums[i])
            else:
                dp_max[i] = max(dp_min[i-1] * nums[i],nums[i])
                dp_min[i] = min(dp_max[i-1] * nums[i],nums[i])
            res = max(dp_max[i],res)
        return res

java

class Solution {
    public int maxProduct(int[] nums) {
        int len = nums.length;
        int[] dp_max = new int[len];
        int[] dp_min = new int[len];
        int ans = nums[0];
        dp_max[0] = nums[0];
        dp_min[0] = nums[0];

        for(int i=1;i<len;i++) {
            if (nums[i] >=0) {
                dp_max[i] = Math.max(dp_max[i-1] * nums[i],nums[i]);
                dp_min[i] = Math.min(dp_min[i-1] * nums[i],nums[i]);
            }else {
                dp_max[i] = Math.max(dp_min[i-1] * nums[i],nums[i]);
                dp_min[i] = Math.min(dp_max[i-1] * nums[i],nums[i]);
            }
            ans = Math.max(dp_max[i],ans);
        }
        return ans;

    }
}

贪心算法

  • 简化思路：
    • 我们只需要记录每次遍历的最大值最小值，并替换原来的最大值和最小值
  • 复杂度分析：
    • 时间复杂度 $O(N)$ ，$N$ 为数组的长度
    • 空间复杂度 $O(1)$， 我们使用了两个长度为 $N$ 数组，记录最大值和最小值

python

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        imax ,imin= 1,1
        ans = nums[0]
        for num in nums:
            if num < 0:
                imax ,imin = imin, imax
            imax = max(imax * num,num)
            imin = min(imin * num,num)
            ans = max(imax,ans)
        return ans

java

class Solution {
    public int maxProduct(int[] nums) {
        int imax = 1,imin = 1 ,ans = nums[0];
        for (int num:nums) {
            if (num<0){
                int temp = imax;
                imax = imin;
                imin = temp;
            }
            imax = Math.max(imax * num,num);
            imin = Math.min(imin * num,num);
            ans = Math.max(imax,ans);
        }
        return ans;

    }
}
  • 如果你觉得本文对你有帮助，请点赞👍支持
  • 如果有疑惑或者表达不到位的额地方 ，请在下面👇评论区指出

Read more

  • May 03, 2020
  • 0 views

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

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

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

示例 1:

输入: "abcabcbb"
输出: 3
解释 : 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

方法一 滑动窗口

解题思路

  • 这种数组类型题目很容易会想到通过 暴力 去解决问题，当然可以，而且为新的方法提供思路
  • 暴力解法时间复杂度较高，会达到 $O(n^2)$，所以我们借用空间 哈希表 采取 滑动窗口 的方法降低时间复杂度 (借用空间降时间)
  • 通过 map 记录元素及下标，同时通过 left 记录左边界
  • 如图(新手，图做的不好)))

pic

代码

python
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left = 0
        len_max = 0
        sub_dict = {}
        sub_len = len(s)
        for i in range(len(s)):
            if s[i] in sub_dict:
                len_max = max(len_max,i-left) # 当出现重复的元素，先判断最长子串的长度
                left_curr = sub_dict.get(s[i]) + 1 # 记录零时的左边界
                # 判断当前左边界和上一个左边界的大小 当前边界下雨上一个边界 则左边界不变
                # 如 字符串 "abba"
                left = left_curr if left_curr > left else left
            sub_dict[s[i]] = i
        return max(len_max,sub_len-left)
java
class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character,Integer> map = new HashMap<>();
        int max = 0;
        int left = 0;
        int len = s.length();
        for(int i=0;i<s.length();i++) {
            if (map.containsKey(s.charAt(i))) {
                max = Math.max(max,i - left); // 当出现重复的元素，先判断最长子串的长度
                int cur = map.get(s.charAt(i))+1; // 记录零时的左边界
                // 判断当前左边界和上一个左边界的大小 当前边界下雨上一个边界 则左边界不变
                // 如 字符串 "abba"
                left =  cur > left? cur :left;
            }
            map.put(s.charAt(i),i);
        }
        return Math.max(max, len-left);
    }
}

复杂度分析

  • 时间复杂度：$O(n)$ 如字符串长度为 $n$ 则所有元素执行一遍
  • 空间复杂度：$O(n)$ 如所有的字符串都不重复，则 map 需要保存 $n$ 个元素

方法二 滑动窗口

解题思路

  • 我们只要把队列的左边的元素移出就行了，直到满足题目要求！(不在出现重复字符串)
  • 一直维持这样的队列，找出队列出现最长的长度时候，求出解！
  • 时间复杂度：$O(n)$

代码

python

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        if not s: return 0
        left = 0
        curLen = 0 # 当前长度
        maxLen = 0 # 最长字符串
        lookup = set() # 用来存储滑动的字符串
        for i in range(len(s)):
            curLen +=1

            # 这里是while循环，当重复字符串一直在集合当中，会一直删除左边的字符串，直到删除重复字符串   
            while s[i] in lookup:
                lookup.remove(s[left])
                left += 1
                curLen -= 1

            #比较当前长度和最长长度
            if curLen > maxLen:maxLen=curLen
            lookup.add(s[i])
        return maxLen

java

class Solution {
    public int lengthOfLongestSubstring(String s) {
       int left = 0;
        Set<Character> lookup = new HashSet<>();
        int cul_len = 0;
        int max_len = 0;
        for (int i=0;i<s.length();i++) {
            cul_len += 1;
            while (lookup.contains(s.charAt(i))) {
                lookup.remove(s.charAt(left));
                left += 1;
                cul_len -= 1;
            }

            if(cul_len>max_len)
                max_len = cul_len;
            lookup.add(s.charAt(i));
        }
        return max_len;
    }
}
  • 如果你觉得本文对你有帮助，请点赞👍支持
  • 如果有疑惑或者表达不到位的额地方 ，请在下面👇评论区指出

Read more

  • May 02, 2020
  • 0 views

229. 求众数 II

  • 难度：中等
  • 本题涉及算法： 摩尔投票法
  • 思路： 摩尔投票法
  • 类似题型:

题目 229. 求众数 II

给定一个大小为 n 的数组，找出其中所有出现超过 n/3 次的元素。

说明: 要求算法的时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。

示例 1:

输入: [3,2,3]
输出: [3]

示例 2:

输入: [1,1,1,3,3,2,2,2]
输出: [1,2]

摩尔投票法的基本思想

在每一轮投票过程中，从数组中找出一对不同的元素，将其从数组中删除。这样不断的删除直到无法再进行投票，如果数组为空，则没有任何元素出现的次数超过该数组长度的一半。如果只存在一种元素，那么这个元素则可能为目标元素。

在算法执行过程中，我们使用常量空间实时记录一个候选元素c以及其出现次数 $f(c)$，c即为当前阶段出现次数超过半数的元素。根据这样的定义，我们也可以将摩尔投票法看作是一种动态规划算法。

程序开始之前，元素c为空，$f(c)=0$。遍历数组A：

  • 如果f(c)为0，表示截至到当前子数组，并没有候选元素。也就是说之前的遍历过程中并没有找到超过 n/3 的元素。那么，如果超过n/3 的元素c存在，那么c在剩下的子数组中，出现次数也一定超过n/3。因此我们可以将原始问题转化为它的子问题。此时c赋值为当前元素, 同时f(c)=1。
  • 如果当前元素 A[i] == c, 那么 $f(c) += 1$。(没有找到不同元素，只需要把相同元素累计起来)
  • 如果当前元素 A[i] == c, 那么 $f(c) += 1$。(没有找到不同元素，只需要把相同元素累计起来)
  • 如果当前元素 A[i] != c，那么 $f(c) -= 1$ (相当于删除1个c)，不对A[i]做任何处理(相当于删除A[i])

解题思路

  1. 根据题型，需要返回出现次数超过 n/3 次的元素，可知最多有两个这样的元素
  2. 我们假设有两个这种元素，根据 摩尔投票法 设这两个元素为候选人

python

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        res = [] # 返回数组
        majorityO = -1 # 候选人1
        majorityT = -1 # 候选人2
        countO = 0 # 候选人1 票数
        countT = 0 # 候选人2 票数
        for num in nums:
            if countO == 0 and num != majorityT:
                majorityO = num
                countO += 1
                continue
            elif countT == 0 and num != majorityO:
                majorityT = num
                countT += 1
                continue
            else:
                if majorityO == num:
                    countO += 1
                elif majorityT == num:
                    countT += 1
                else:
                    countO -= 1
                    countT -= 1
        counterO = 0
        counterT = 0

        if countO > 0:
            for num in nums:
                if num == majorityO:
                    counterO += 1
        if counterO > len(nums)//3:
            res.append(majorityO)
        if countT > 0:
            for num in nums:
                if num == majorityT:
                    counterT += 1
        if counterT > len(nums)//3:
            res.append(majorityT)

        return res

Read more

  • May 02, 2020
  • 0 views
Search