s******e
发帖数: 108 | 1 A partial solution, not finished yet for the existing element.
use two hashtable,
one hashtable used for element value
another hashtable used for element index.
O(n) complexity.
static public int[] longest2(int[] a) {
int start = 0;
int maxLen = 0;
int indexStart =0;
int indexMaxLen =0;
HashMap map = new HashMap();
HashMap indexmap = new HashMap();
for ... 阅读全帖 |
|
s******e
发帖数: 108 | 2 A partial solution, not finished yet for the existing element.
use two hashtable,
one hashtable used for element value
another hashtable used for element index.
O(n) complexity.
static public int[] longest2(int[] a) {
int start = 0;
int maxLen = 0;
int indexStart =0;
int indexMaxLen =0;
HashMap map = new HashMap();
HashMap indexmap = new HashMap();
for ... 阅读全帖 |
|
S******1
发帖数: 216 | 3 //11:55 第3题不是图，是disjoint set
boolean isRight(String[] ss1, String[] ss2) {
if (ss1 == null || ss2 == null)
return false;
Map indexMap = new HashMap();
for (String s : ss1) {
char c1 = s.charAt(0);
char c2 = s.charAt(2);
if (!indexMap.containsKey(c1))
indexMap.put(c1, indexMap.size());
if (!indexMap.containsKey(c2))
indexMap.put(c2, indexMap.size());
}
int[] set = ne... 阅读全帖 |
|
S******1
发帖数: 216 | 4 //11:55 第3题不是图，是disjoint set
boolean isRight(String[] ss1, String[] ss2) {
if (ss1 == null || ss2 == null)
return false;
Map indexMap = new HashMap();
for (String s : ss1) {
char c1 = s.charAt(0);
char c2 = s.charAt(2);
if (!indexMap.containsKey(c1))
indexMap.put(c1, indexMap.size());
if (!indexMap.containsKey(c2))
indexMap.put(c2, indexMap.size());
}
int[] set = ne... 阅读全帖 |
|
C***U
发帖数: 2406 | 5 用了DP 但是过不了judge large
应该哪里再改进改进啊？
谢谢大牛指教
int numDistinct(string S, string T) {
unordered_map > indexMap;
vector indices;
vector tempResult, result;
result.push_back(-1);
for(int i = 0; i < T.size(); i++) {
if(indexMap.find(T[i]) == indexMap.end()) {
indexMap[T[i]] = indices;
}
}
for(int i = 0; i < S.size(); i++) {
if(indexMap.find(S[i]) != indexM... 阅读全帖 |
|
S******1
发帖数: 216 | 6 来自主题: JobHunting版 - FB 面筋
Minimum
写一个考虑顺序的inverted indexing做法
//7:10
//给一个string，比如UAXXBAUB，给一个pattern，比如AB，返回包含pattern的最短
substring，结果是AUB
int findMinWindow(String s, String p) {
if (s == null || p == null || s.length() < p.length())
return -1;
if (p.isEmpty())
return 0;
Map> indexMap = new HashMap
Integer>>();
for (int i = 0; i < s.length(); i++) {
if (!indexMap.containsKey(s.charAt(i)))
indexMap.put(s.charAt(i), new Arra... 阅读全帖 |
|
a*******y
发帖数: 1040 | 7 这个不就是hash这个index就行了吗？
bool FindCycle(int a[], int n)
{
std::map indexmap;
map::iterator it;
for (int i = 0; i < n;i++)
{
indexmap[i] = false;
}
indexmap[0] = true;
for (int i = 0; i < n; i++)
{
if( indexmap[a[i]])
return true;
else
indexmap[a[i]] = true;
}
return false;
} |
|
n*******n
发帖数: 45 | 8 木有用DP....
public int lengthOfLongestSubstring(String s) {
if (s == null) {
return 0;
}
if (s.length() < 2) {
return s.length();
}
int maxLength = 0;
int totalLen = s.length();
int currentLen = 0;
int cStart = 0;
Map indexMap = new HashMap<>();
while((totalLen - cStart) > maxLength) {
for(int i = cStart; i < totalLen; i++) {
Character cur = s.char... 阅读全帖 |
|
I*******g
发帖数: 7600 | 9 第一题：
public static String shortestString(String s, String p){
String result = null;
if (s== null || p == null || p.length() >s.length()) return null;
if (s.length() ==0 || p.length() ==0) return "";
Map indexMap = new HashMap();
List indexList = new ArrayList();
int min = s.length() +1;
for(int i =0 ;i < s.length(); i++){
for(Integer x: indexList){
... 阅读全帖 |
|
I*******g
发帖数: 7600 | 10 第一题：
public static String shortestString(String s, String p){
String result = null;
if (s== null || p == null || p.length() >s.length()) return null;
if (s.length() ==0 || p.length() ==0) return "";
Map indexMap = new HashMap();
List indexList = new ArrayList();
int min = s.length() +1;
for(int i =0 ;i < s.length(); i++){
for(Integer x: indexList){
... 阅读全帖 |
|
p*********g
发帖数: 911 | 11 不错。看明白了。
我也贴一下，求各位大牛给给意见。如果没问题, credits归IFloating和bunnih。
public static String shortestString(String s, String p){
String result = null;
if (s== null || p == null || p.length() >s.length()) return null;
if (s.length() ==0 || p.length() ==0) return "";
Map indexMap = new HashMap();
int min = s.length() +1;
for(int i =0 ;i < s.length(); i++){
for(Entry ent: indexMap.entrySet()){
... 阅读全帖 |
|
j**7
发帖数: 143 | 12 public String window(String S, String P) {
HashMap> indexMap = new HashMap<
Character, LinkedList>();
for (int i = 0; i < S.length(); i++) {
char c = S.charAt(i);
LinkedList list = indexMap.get(c);
if (list == null) {
list = new LinkedList();
list.add(i);
indexMap.put(c, list);
} else {
list.add(i);
}... 阅读全帖 |
|
c********t
发帖数: 5706 | 13 public static int cooldown(String s, int k){
if(s==null || s.isEmpty()) return 0;
int n = s.length();
if(k<=0) return n;
Map indexMap = new HashMap<>();
int inc=0;
for(int i=0; i
char ch = s.charAt(i);
int depart=i+inc-indexMap.getOrDefault(ch, -k-1);
if(depart<=k) inc+=k-depart+1;
indexMap.put(ch, i+inc);
}
return n+inc;
} |
|
h***s
发帖数: 45 | 14 好方法，应该也是 O(nk)吧？ k是pattern的长度，n是s的长度。
indexMap记录的是从index i开始能够最远match到p的index j+1。 |
|
h***s
发帖数: 45 | 15 好方法，应该也是 O(nk)吧？ k是pattern的长度，n是s的长度。
indexMap记录的是从index i开始能够最远match到p的index j+1。 |
|
