找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 4971|回复: 16
收起左侧

[米群网刷题小分队] [LeetCode] Two Pointer 题目

[复制链接]

90

主题

46

精华

1908

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1908

热心会员突出贡献优秀版主最佳新人精华帖之王活跃会员

发表于 12-12-2014 12:15 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 MengMa 于 12-12-2014 08:46 PM 编辑

Longest Substring Without Repeating Characters


思路:max存当前最长的无重复子串长度。HashSet存当前的最长无重复子串里包含的字符。
滑动窗口:

用两个指针访问数组:一个快指针,一个慢指针。
简单记法:快指针 字符,慢指针 字符。

快指针一直往右走,尽可能的把没有出现的字符加入到HashSet里。

当出现了重复字符时,即HashSet中已经包含了当前的fast指向的字符,fast指针 停止。
这时候要进行下列处理:
首先记录当前长度,如果比已有max长,则更新max。
否则slow指针开始吐字符,当charAt(slow)并非重复字符时,slow++,直到停止在charAt(slow) == charAt(fast)
这时候不要忘记再slow++一次。确保窗口里只出现一次charAt(fast)那个字符。

时间 O(n) 空间 O(n)

代码:
  1. public class Solution {
  2.     public int lengthOfLongestSubstring(String s)
  3.     {
  4.         if(s == null || s.length() == 0) return 0;
  5.         HashSet<Character> set = new HashSet<Character>();
  6.         int max = 0;
  7.         int slow = 0;
  8.         int fast = 0;
  9.         while(fast < s.length())
  10.         {
  11.             if(!set.contains(s.charAt(fast)))
  12.             {
  13.                 set.add(s.charAt(fast));
  14.             }
  15.             else
  16.             {
  17.                 max = Math.max(max, fast - slow);
  18.                 while(s.charAt(slow) != s.charAt(fast))
  19.                 {
  20.                     set.remove(s.charAt(slow));
  21.                     slow ++;
  22.                 }
  23.                 slow ++;
  24.             }
  25.             fast ++;
  26.         }
  27.         max = Math.max(max, fast - slow);
  28.         return max;
  29.     }
  30. }
复制代码


本帖被以下淘专辑推荐:

90

主题

46

精华

1908

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1908

热心会员突出贡献优秀版主最佳新人精华帖之王活跃会员

 楼主| 发表于 12-14-2014 11:56 PM | 显示全部楼层
Remove Duplicates from Sorted Array
思路:
//

代码:
  1. public class Solution {
  2.     public int removeDuplicates(int[] A) {
  3.         if(A == null || A.length <= 0) return 0;
  4.         int index = 0;
  5.         for(int i = 0; i < A.length; i++)
  6.         {
  7.            while(i != A.length -1 && A[i + 1] == A【i】) i++;
  8.            A[index++] = A【i】;
  9.         }
  10.         return index;
  11.     }
  12. }
复制代码


90

主题

46

精华

1908

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1908

热心会员突出贡献优秀版主最佳新人精华帖之王活跃会员

 楼主| 发表于 12-16-2014 12:39 AM | 显示全部楼层
Remove Duplicates from Sorted Array II
allowDups 的意思是表示当前情况下是否允许 重复元素。
时间O(n) 空间O(1)
  1. public class Solution {
  2.     public int removeDuplicates(int[] A) {
  3.         int len = A.length;
  4.         if(A==null) return 0;
  5.         if(len == 0 || len == 1 || len ==2) return len;
  6.         int index = 1;
  7.         int prevElem = A[0];
  8.         boolean allowDups = true;
  9.         for(int i = 1; i < len; i++)
  10.         {
  11.             if(A【i】 == prevElem)
  12.             {
  13.                 if(allowDups == true)
  14.                 {
  15.                     A[index ++] = prevElem;
  16.                     allowDups = false;
  17.                 }
  18.                 else
  19.                     continue;
  20.             }
  21.             else
  22.             {
  23.                 A[index++] = A【i】;
  24.                 prevElem = A【i】;
  25.                 allowDups = true;
  26.             }
  27.         }
  28.         return index;
  29.     }
  30. }
复制代码


您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表