[MeetCoder] Crossing Bridge - Eason Liu - 博客园


[MeetCoder] Crossing Bridge - Eason Liu - 博客园
N people wish to cross a bridge at night. It's so dark around there that they have to cross the bridge under the help of a little lamp. Only one little lamp is available (Oh, Men...) and they have to have the little lamp walking with them. The bridge is of a width such that a maximum of 2 people may cross at a time.

Each person walks at his/her fixed speed. If two people cross the bridge together, they must walk at the pace of the slower one. How fast can you get all N people over the bridge?
Input

The input should be a list of N positive integers, where N is less than or equal to 1,000. And each integer of the list should be less than or equal to 100.
Output

The output should be the minimum time that all the people can cross the bridge.过桥问题!主要参考:http://blog.csdn.net/morewindows/article/details/7481851

X. Brute Force:
 3     int _bridge(vector<int> &v, int n) {
 4         if (n == 0) return 0;
 5         if (n == 1) return v[0];
 6         if (n == 2) return v[1];
 7         if (n == 3) return v[0] + v[1] + v[2];
 8         int res = 0;
 9         int a = v[0], b = v[1], x = v[n-2], y = v[n-1];
10         if (2 * b > a + x) res += 2 * a + x + y;
11         else res += a + 2 * b + y;
12         return res + _bridge(v, n - 2);
13     }
14 public:
15     int bridge(vector<int> &v) {
16         sort(v.begin(), v.end());
17         return _bridge(v, v.size());
18     }

http://www.huangxc.com/cross-bridge/
小明和爸爸、妈妈、弟弟、爷爷一起要通过一座桥,由于是夜晚,必须打灯才能通过。桥上一次最多只能通过两人。小明过桥需要 1 分钟,爸爸需要 2 分钟,弟弟需要 3 分钟,妈妈需要 6 分钟,爷爷需要 18 分钟,两人一起过桥时时间按速度较慢者过桥时间算。他们只有一盏灯,且等只能点亮 30 分钟,问怎样过桥所用时间最短,并用程序实现。
当时第一反应是让速度最快的人来回护送其他人通过,那么所用总时间就是送爷爷的时间 + 小明返回时间 + 送妈妈时间 + 小明返回时间 + 送弟弟时间 + 小明返回时间 + 和爸爸一起通过时间,设小明、爸爸、弟弟、妈妈、爷爷过桥所用时间分别为 T1、T2、T3、T4、T5,所用总时间为 TS,则:
  1. TS = T5 + T1 + T4 + T1 + T3 + T1 + T2
  2. = 18 + 1 + 6 + 1 + 3 + 1 + 2
  3. = 32
然而这样计算的总时间已经超过了 30 分钟,因此显然并不是最优的方法。这里暂时将这个方法定义为「方法一」。
回家仔细思考后发现有更快地通过方式。这里约定每过一次桥为「一趟」,则过桥方式文字表述如下:
第一趟:小明和爸爸一起通过,所用时间为T2
第二趟:小明返回,所用时间为T1
第三趟:爷爷和妈妈一起通过,所用时间为T5
第四趟:爸爸返回,所用时间为T2
第五趟:小明和弟弟一起通过,所用时间为T3
第六趟:小明返回,所用时间为T1
第七趟:小明和爸爸一起通过,所用时间为T2
因此总时间为:
  1. TS = T2 + T1 + T5 + T2 + T3 + T1 + T2
  2. = 2 + 1 + 18 + 2 + 3 + 1 + 2
  3. = 29
以上方法定义为「方法二」。这样更快之所以更快是因为最慢的人和次慢的人一起通过,就可以减少总时间。总时间的决定因素在于速度慢的人需要花费多少时间而不是速度快的人花费多少,这有点类似于木桶原理。
将此问题一般化,假设有 N 个人过桥,所需时间从少到多依次为 T1, T2, T3, ···, TN-1, TN,(同时 N 个人分别表示为 1, 2, 3, ···, N-1, N),那么问题要稍微复杂一些,不能单纯的使用「方法二」让最慢的和次慢的一起通过,因为如果次慢者的速度和次快者速度相差不大,那么这也许就不再是最优的方法,考虑如下情况:
四个人所需时间分别为:
T1 = 1
T2 = 2
T3 = 2
T4 = 3
则「方法二」过桥方式如下图,约定 A 地为未过桥时的地方,B 地为过桥后的位置, ====> 符号表示从 A 地过桥至 B 地,<==== 表示从 B 地过桥返回 A 地,两侧数字分别表示这一趟过桥结束后两地所有的人:
  1. A B
  2. 3, 4 ====> 1, 2
  3. 1, 3, 4 <==== 2
  4. 1 ====> 2, 3, 4
  5. 1, 2 <==== 3, 4
  6. ====> 1, 2, 3, 4
所需时间为:
  1. TS2 = T2 + T1 + T4 + T2 + T2
  2. = 2 + 1 + 3 + 2 + 2
  3. = 10
而「方法一」方式如下图:
  1. A B
  2. 2, 3 ====> 1, 4
  3. 1, 2, 3 <==== 4
  4. 2 ====> 1, 3, 4
  5. 1, 2 <==== 3, 4
  6. ====> 1, 2, 3, 4
所需时间为:
  1. TS1 = T4 + T1 + T3 + T1 + T2
  2. = 3 + 1 + 2 + 1 + 2
  3. = 9
此时「方法一」所用时间就短于「方法二」,思考后发现这两种方法的区别在于前三趟,列出公式比较:
  1. TS1 - TS2 = (T1 + T3) - (T2 + T2)
因此当最快者和次慢者所用时间之和大于 2 倍次快者所用时间时,「方法二」所用时间短,反之则「方法一」所用时间短。当然四个人时还有更多的方法可以过桥,但其余方法所用时间都明显会大于「方法一」和「方法二」。
推广到更多人时,依然以每四个人为最小单位(当人数为三人时最短时间就是单纯的三人所需时间相加)进行如上的判断,使用「方法一」或者「方法二」,这样看作一个整体计算一次后,A 地剩余人数就减少 2,再递归调用,直至 A 地剩余人数少于四人。
http://blog.csdn.net/morewindows/article/details/7481851
 for (i = 0; i < n; i++)
  cin>>a[i];
 qsort(a, n, sizeof(a[0]), cmp);
 sum = 0;
 for (i = n - 1; i > 2; i = i - 2)
 {  
  //最小者将最大2个送走或最小2个将最大2个送走
  if (a[0] + a[1] + a[1] + a[i] < a[0] + a[0] + a[i - 1] + a[i])
   sum = sum + a[0] + a[1] + a[1] + a[i];
  else
   sum = sum + a[0] + a[0] + a[i - 1] + a[i]; 
 }
 if (i == 2)
  sum = sum + a[0] + a[1] + a[2];
 else if (i == 1) 
  sum = sum + a[1];
 else 
  sum = a[0];
 cout<<"最短过桥时间为:"<<sum<<endl;
http://m.blog.csdn.net/blog/asuxiexie/38533379
    sort(s,s+a);
    int ans=a,cne,sum=0,d,e;
    while(ans>3)
    {
        int sum1=2*s[0]+s[ans-2]+s[ans-1];
        int sum2=2*s[1]+s[0]+s[ans-1];
        if(sum1>sum2)
            sum+=sum2;
        else
            sum+=sum1;
        ans-=2;
    }
    if(ans==3)
        printf("%d\n",sum+=s[0]+s[1]+s[2]);
    else
        printf("%d\n",sum+=s[1]);
    while(a>3)
    {
        if(s[0]+s[a-2]<2*s[1])
            printf("%d %d\n%d\n%d %d\n%d\n",s[0],s[a-1],s[0],s[0],s[a-2],s[0]);
        else
            printf("%d %d\n%d\n%d %d\n%d\n",s[0],s[1],s[0],s[a-2],s[a-1],s[1]);
        a-=2;
    }
    if(a==3)
        printf("%d %d\n%d\n%d %d\n",s[0],s[2],s[0],s[0],s[1]);
    else
        printf("%d %d\n",s[0],s[1]);
http://www.acmerblog.com/POJ-2573-Bridge-blog-798.html
微软过桥问题的图论解法
 微软的过桥问题说的是4个人在晚上过一座小桥,过桥时必须要用到手电筒,只有一枚手电筒,每次最多只可以有两人通过, 4个人的过桥速度分别为1分钟、2分钟、5分钟、10分钟,试问最少需要多长时间4人才可以全部通过小桥?
这个问题如果用图论来建模的话,就可以以4个人在桥两端的状态来作为节点来构造一个有向图,如下图所示,以已经过桥了的人的状态作为图的节点,初始时没有人过桥,所以以空表示,第一轮有两个人过桥,有6种可能的组合,(1,2)(1,5)(1,10)(2,5)(2,10)(5,10),从空的状态转换到这些状态的需要的时间分别为2,5,10,5,10,10分钟,时间就作为有向边的权值。当有两个人过桥后,需要一个人拿手电筒回去接其他人,这时有四种可能的情况,分别是1,2,5,10中的一人留在了河的对岸,(1,2)这种状态只能转换到(1)(2)两种状态,对应的边的权值分别为2,1分钟,(1,2)转换到(1)时也就是2返回了,返回需要耗时2分钟,以此类推可以建立以下的图论模型。
要求出最少需要多长时间4人全部通过小桥实际上就是在图中求出(空)节点到(1,2,5,10)节点间的最短路径。
   
根据Dijkstra最短路径算法很容易求出其最短路径,如图中的粗线所示。
这样总时间为2+1+10+2+2=17分钟
所以能够活学图论的话,这类智力问题就变成了图论的入门级的问题。
Read full article from [MeetCoder] Crossing Bridge - Eason Liu - 博客园

[CTCI] 子串判断 - Eason Liu - 博客园


[CTCI] 子串判断 - Eason Liu - 博客园

现有一个小写英文字母组成的字符串s和一个包含较短小写英文字符串的数组p,请设计一个高效算法,对于p中的每一个较短字符串,判断其是否为s的子串。

给定一个string数组p和它的大小n,同时给定string s,为母串,请返回一个bool数组,每个元素代表p中的对应字符串是否为s的子串。保证p中的串长度小于等于8,且p中的串的个数小于等于500,同时保证s的长度小于等于1000。

测试样例:
["a","b","c","d"],4,"abc"
返回:[true,true,true,false]

Read full article from [CTCI] 子串判断 - Eason Liu - 博客园

[CTCI] 最大子方阵 - Eason Liu - 博客园


[CTCI] 最大子方阵 - Eason Liu - 博客园
有一个方阵,其中每个单元(像素)非黑即白(非0即1),请设计一个高效算法,找到四条边颜色相同的最大子方阵。
给定一个01方阵mat,同时给定方阵的边长n,请返回最大子方阵的边长。保证方阵变长小于等于100。
测试样例:
[[1,1,1],[1,0,1],[1,1,1]],3
返回:3

要看清题目,题目说的是四条边同一种颜色,不是四条边都是1。想法就是记录每个点右侧与下侧的连续0或1的个数,这样在给定一个左上角坐标与边长时,可以以O(1)的时间判断是否构成矩形。总的时候复杂度为O(N^3)。

class SubMatrix {
 2 public:
 3     struct cell {
 4         int right, down;
 5         cell() : right(0), down(0){}
 6     };
 7     int maxSubMatrix(vector<vector<int> > mat, int n) {
 8         // write code here
 9         vector<vector<cell>> mmat1(n, vector<cell>(n));
10         vector<vector<cell>> mmat2(n, vector<cell>(n));
11         int tmp1, tmp2, res;
12         for (int i = n - 1; i >= 0; --i) {
13             for (int j = n - 1; j >= 0; --j) {
14                 if (j == n - 1) tmp1 = tmp2 = 0;
15                 else tmp1 = mmat1[i][j+1].right, tmp2 = mmat2[i][j+1].right;
16                 if (mat[i][j] == 1) mmat1[i][j].right = tmp1 + 1;
17                 else mmat2[i][j].right = tmp2 + 1;
18                 if (i == n - 1) tmp1 = tmp2 = 0;
19                 else tmp1 = mmat1[i+1][j].down, tmp2 = mmat2[i+1][j].down;
20                 if (mat[i][j] == 1) mmat1[i][j].down = tmp1 + 1;
21                 else mmat2[i][j].down = tmp2 + 1;
22             }
23         }
24         for (int i = n; i > 0; --i) {
25             if (isOK(mmat1, n, i) || isOK(mmat2, n, i)) return i;
26         }
27         return 0;
28     }
29     bool isOK(vector<vector<cell>> &mat, int n, int size) {
30         for (int i = 0; i <= n - size; ++i) {
31             for (int j = 0; j <= n - size; ++j) {
32                 if (isSquare(mat, i, j, size)) return true;
33             }
34         }
35         return false;
36     }
37     bool isSquare(vector<vector<cell>> &mat, int x, int y, int size) {
38         cell &lefttop = mat[x][y], &leftdown = mat[x+size-1][y], &righttop = mat[x][y+size-1];
39         if (lefttop.right < size) return false;
40         if (lefttop.down < size) return false;
41         if (leftdown.right < size) return false;
42         if (righttop.down < size) return false;
43         return true;
44     }
45 };
Read full article from [CTCI] 最大子方阵 - Eason Liu - 博客园

LeetCode 205 - Isomorphic Strings


Isomorphic Strings – Leetcode Java | Welkin Lan
Given two strings s and t, determine if they are isomorphic.
Two strings are isomorphic if the characters in s can be replaced to get t.
All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

For example,
Given "egg", "add", return true.
Given "foo", "bar", return false.
Given "paper", "title", return true.

X. Normalize
https://blog.csdn.net/NoMasp/article/details/50611168
翻译完这题目就很自然的想到一个方法,我希望将字符串全部输出成数字序列:

For example,

Given "paper", return "01023".

Given "foo", return "011".

Given "isomorphic", return "0123245607".
  private ArrayList getArrayOrder(String str) {
    HashMap<Character, Integer> strM = new HashMap<>();
    int index = 0;
    ArrayList order = new ArrayList(str.length());
    for (int i = 0; i < str.length(); i++) {
      char c = str.charAt(i);
      if (strM.containsKey(c)) {
        order.add(strM.get(c));
      } else {
        strM.put(c, index);
        order.add(index);
        index += 1;
      }
    }
    return order;
  }

  public boolean isIsomorphic(String s, String t) {
    if (s.length() != t.length())
      return false;
    ArrayList s0 = getArrayOrder(s), t0 = getArrayOrder(t);
    for (int i = 0; i < s0.size(); i++)
      if (s0.get(i) != t0.get(i))
        return false;
    return true;

  }

X.
https://leetcode.com/problems/isomorphic-strings/discuss/57802/Java-solution-using-HashMap
Check twice with helper method. O(n) time and O(n) space.
public boolean isIsomorphic(String s, String t) {
        if(s == null && t == null) return true;
        else if(s == null || t == null) return false;
        if(s.length() != t.length()) return false;
        return helper(s,t) && helper(t,s);
    }
    private boolean helper(String s, String t){
        Map<Character,Character> map = new HashMap<>();
        for(int i = 0;i<s.length();i++){
            if(!map.containsKey(s.charAt(i))){
                map.put(s.charAt(i),t.charAt(i));
            }else{
                if(map.get(s.charAt(i)) != t.charAt(i) ) return false;
            }
        }
        return true;
    }

X.
https://segmentfault.com/a/1190000016865879
    public boolean isIsomorphic(String s, String t) {
        int[] stmap = new int[256];
        int[] tsmap = new int[256];
        Arrays.fill(stmap, -1);
        Arrays.fill(tsmap, -1);
        for (int i = 0; i < s.length(); i++) {
            if (stmap[s.charAt(i)] != tsmap[t.charAt(i)]) return false;
            stmap[s.charAt(i)] = i;
            tsmap[t.charAt(i)] = i;
        }
        return true;
    }

https://discuss.leetcode.com/topic/13001/short-java-solution-without-maps
The main idea is to store the last seen positions of current (i-th) characters in both strings. If previously stored positions are different then we know that the fact they're occuring in the current i-th position simultaneously is a mistake. We could use a map for storing but as we deal with chars which are basically ints and can be used as indices we can do the whole thing with an array.
    public boolean isIsomorphic(String s1, String s2) {
        int[] m = new int[512];
        for (int i = 0; i < s1.length(); i++) {
            if (m[s1.charAt(i)] != m[s2.charAt(i)+256]) return false;
            m[s1.charAt(i)] = m[s2.charAt(i)+256] = i+1;
        }
        return true;
    }
X. http://www.cnblogs.com/grandyang/p/4465779.html
根据一对一映射的特点,我们需要用两个哈希表分别来记录原字符串和目标字符串中字符出现情况,由于ASCII码只有256个字符,所以我们可以用一个256大小的数组来代替哈希表,并初始化为0,我们遍历原字符串,分别从源字符串和目标字符串取出一个字符,然后分别在两个哈希表中查找其值,若不相等,则返回false,若想等,将其值更新为i + 1
    bool isIsomorphic(string s, string t) {
        int m1[256] = {0}, m2[256] = {0}, n = s.size();
        for (int i = 0; i < n; ++i) {
            if (m1[s[i]] != m2[t[i]]) return false;
            m1[s[i]] = i + 1;
            m2[t[i]] = i + 1;
        }
        return true;
    }
X. 
We could use extra space – hashtable to save mapped values and check time is O(1)
https://segmentfault.com/a/1190000003709248
用一个哈希表记录字符串s中字母到字符串t中字母的映射关系,一个集合记录已经映射过的字母。或者用两个哈希表记录双向的映射关系。这里不能只用一个哈希表,因为要排除egg->ddd这种多对一的映射。

    
public boolean isIsomorphic(String s, String t) {
        HashMap<Character,Character> map = new HashMap<>();
        HashSet<Character> mapped = new HashSet<>();
        for (int i=0; i<s.length(); i++){
            if (map.containsKey(s.charAt(i))){
                if (t.charAt(i)==map.get(s.charAt(i))) continue;
                else return false;
            }
            else if (mapped.contains(t.charAt(i))) return false;
            map.put(s.charAt(i),t.charAt(i));
            mapped.add(t.charAt(i));
        }
        return true;
    }
A:
A simple HashMap<s.char, t.char> question, only rule is that No two characters may map to the same character.
We could use map.containsValue() => O(n) time to check whether value is existed
http://www.programcreek.com/2014/05/leetcode-isomorphic-strings-java/
- Not efficient

    
public boolean isIsomorphic(String s, String t) {
        HashMap<Character,Character> map = new HashMap<>();
        for (int i=0; i<s.length(); i++){
            if (map.containsKey(s.charAt(i))){
                if (t.charAt(i)==map.get(s.charAt(i))) continue;
                else return false;
            }
            else if (map.containsValue(t.charAt(i))) return false;
            map.put(s.charAt(i),t.charAt(i));
        }
        return true;
    }

https://sisijava.wordpress.com/2015/05/05/leetcode-isomorphic-strings/
    public boolean isIsomorphic(String s, String t) {
            if(s == null && t == null){
                return true;
            }
            else if(s == null ||t == null){
                return false;
            }
            else{
                if(s == t){
                    return true;
                }
                else{
                    if(s.length() != t.length()){
                        return false;
                    }
                    else{
                        int l = s.length();
                        HashMap<Character, Character> a = new HashMap<Character, Character>();
                        HashMap<Character, Character> b = new HashMap<Character, Character>();
                        for(int i = 0; i < l; i++){
                            char sc = s.charAt(i);
                            char tc = t.charAt(i);
                                if(!a.containsKey(tc) && !b.containsKey(sc)){
                                    a.put(tc, sc);
                                    b.put(sc, tc);
                                }
                                else{
                                    if(a.containsKey(tc) ? a.get(tc)!=sc : b.get(sc)!=tc) 
                                        return false;
                                }
                        }
                    }
                }
            }
            return true;
    }
X. http://www.cnblogs.com/easonliu/p/4465650.html
就是记录遍历s的每一个字母,并且记录s[i]到t[i]的映射,当发现与已有的映射不同时,说明无法同构,直接return false。但是这样只能保证从s到t的映射,不能保证从t到s的映射,所以交换s与t的位置再重来一遍上述的遍历就OK了。
     bool isIsomorphic(string s, string t) {
 4         if (s.length() != t.length()) return false;
 5         map<char, char> mp;
 6         for (int i = 0; i < s.length(); ++i) {
 7             if (mp.find(s[i]) == mp.end()) mp[s[i]] = t[i];
 8             else if (mp[s[i]] != t[i]) return false;
 9         }
10         mp.clear();
11         for (int i = 0; i < s.length(); ++i) {
12             if (mp.find(t[i]) == mp.end()) mp[t[i]] = s[i];
13             else if (mp[t[i]] != s[i]) return false;
14         }
15         return true;
16     }
http://www.cnblogs.com/zhuli19901106/p/4469153.html
 6     bool isIsomorphic(string s, string t) {
 7         return check(s, t) && check(t, s);
 8     }
 9 private:
10     bool check(string s, string t) {
11         char a[256];
12         
13         memset(a, 0, sizeof(a));
14         int i;
15         int n = s.length();
16         
17         for (i = 0; i < n; ++i) {
18             if (a[s[i]] == 0) {
19                 a[s[i]] = t[i];
20             }
21             s[i] = a[s[i]];
22         }
23         
24         return s == t;
25     }
http://www.zhuangjingyang.com/leetcode-isomorphic-strings/

X.
http://likesky3.iteye.com/blog/2237360
思路1:维护两个哈希表,char[] map, boolean[] used, 长度均为256,map[charS] = charT, 表示将字符charS 映射为charT, used[charT]==true 表示charT已经被某个字符映射过了。同步遍历字符串s & t,记两者当前的字符分别为charS, charT, 若charS是新字符,且charT没有被使用,则我们可将其同charT建立映射关系,否则说明有两个不同的字符试图映射到同一个字符上,不符合要求;若charS已被建立映射关系,则检查charT是否和charS的映射字符相等,不相等不符合题目要求的“All occurrences of a character must be replaced with another character ”。 
思路2:参考https://leetcode.com/discuss/33854/my-6-lines-solution,又是一个怎巧妙了得~ 这个思路也是用两个哈希表,不同于思路1直接将s中的字符映射到t中字符,它是将s 和 t中的字符同时映射到下标上,因为若个字符若存在映射关系,则必然是出现在相同的下标位置,实现中由于初始值为0,建立映射时使用 i + 1,以区分未映射状态和映射到下标为0的状态。 
  1.     // Method 2 https://leetcode.com/discuss/33854/my-6-lines-solution  
  2.     public boolean isIsomorphic(String s, String t) {  
  3.         int[] map1 = new int[256];  
  4.         int[] map2 = new int[256];  
  5.         for (int i = 0; i < s.length(); i++) {  
  6.             if (map1[s.charAt(i)] != map2[t.charAt(i)])  
  7.                 return false;  
  8.             map1[s.charAt(i)] = i + 1;  
  9.             map2[t.charAt(i)] = i + 1;  
  10.         }  
  11.         return true;  
  12.     }  
  13.     // Method 1  
  14.     public boolean isIsomorphic1(String s, String t) {  
  15.         if (s == null || t == nullreturn false;  
  16.         char[] map = new char[256];  
  17.         boolean[] used = new boolean[256];  
  18.         for (int i = 0; i < s.length(); i++) {  
  19.             char charS = s.charAt(i);  
  20.             char charT = t.charAt(i);  
  21.             if (map[charS] == 0) {  
  22.                 if (used[charT]) return false// No two characters may map to the same character   
  23.                 map[charS] = charT;  
  24.                 used[charT] = true;  
  25.             } else if (map[charS] != charT){  
  26.                 return false// All occurrences of a character must be replaced with another character   
  27.             }  
  28.         }  
  29.         return true;  
  30.     }  
https://leetcode.com/discuss/34174/my-simple-java-solution
public boolean isIsomorphic(String s, String t) { char[] map1 = new char[256], map2 = new char[256]; for (int i = 0; i < s.length(); i++) { char a = s.charAt(i); char b = t.charAt(i); if (!this.map(a, b, map1) || !this.map(b, a, map2)) { return false; } } return true; } private boolean map(char a, char b, char[] map) { if (map[a] == 0) { map[a] = b; } return map[a] == b; }
The problem is that a char in Java takes up two bytes. Since the inputs are not limited to ASCII strings in the question, you may have two char[65536] for this solution.
public boolean isIsomorphic(String s1, String s2) { int[] m = new int[512]; for (int i = 0; i < s1.length(); i++) { if (m[s1.charAt(i)] != m[s2.charAt(i)+256]) return false; m[s1.charAt(i)] = m[s2.charAt(i)+256] = i+1; } return true; }

public boolean isIsomorphic(String s, String t) { int[] map = new int[128]; int[] book = new int[128]; for (int i = 0; i < s.length(); i++) { int cs = (int) s.charAt(i); int ts = (int) t.charAt(i); if (map[cs] == 0 && book[ts] == 0) { map[cs] = ts; book[ts] = 1; } else if (map[cs] != ts) return false; } return true; }
https://leetcode.com/discuss/33854/my-6-lines-solution
bool isIsomorphic(string s, string t) { int m1[256] = {0}, m2[256] = {0}, n = s.size(); for (int i = 0; i < n; ++i) { if (m1[s[i]] != m2[t[i]]) return false; m1[s[i]] = i + 1; m2[t[i]] = i + 1; } return true; }
X. 在这里面我用了两个HashMap,一个HashMap用来记s的字符到t的映射,用于判断s中的两个字符不能用t中的同一个字符替换,另一个HashMap用来记t的字符到s的映射,用于判断t中的两个字符不能由s中同一个字符映射而来
http://my.oschina.net/Tsybius2014/blog/489587
    public boolean isIsomorphic(String s, String t) {
         
        if (s.length() != t.length()) {
            return false;
        }
        HashMap<Character, Character> hashMapS = new HashMap<Character, Character>();
        HashMap<Character, Character> hashMapT = new HashMap<Character, Character>();
         
        for (int i = 0; i < s.length(); i++) {
            if (hashMapS.containsKey(s.charAt(i))) {
                if (hashMapS.get(s.charAt(i)) != t.charAt(i)) {
                    return false;
                }
            else {
                if (hashMapT.containsKey(t.charAt(i))) {
                    return false;
                }
                hashMapS.put(s.charAt(i), t.charAt(i));
                hashMapT.put(t.charAt(i), s.charAt(i));
            }
        }
         
        return true;
    }

}

    public boolean isIsomorphic(String s, String t) {
         
        if (s.length() != t.length()) {
            return false;
        }
        //虽然不考虑英文大小写,但因为不仅仅有26个英文字母,还可能有其他符号,所以数组要开得足够大
        int len = 40;  //这里数组长度开到40,可以满足题目AC
        char[] charInS = new char[len];
        char[] charInT = new char[len];
        for (int i = 0; i < len; i++) {
            charInS[i] = '0';
            charInT[i] = '0';
        }
         
        boolean bTrue;
        for (int i = 0; i < s.length(); i++) {
            bTrue = false;
            //在数组s中找到当前字符串s的字母,如果数组t中相同位置字母不一致,则字符串不同构
            for (int j = 0; j < len; j++) {
                if (charInS[j] == '0') {
                    break;
                else if (charInS[j] == s.charAt(i)) {
                    if (charInT[j] != t.charAt(i)) {
                        return false;
                    }
                    bTrue = true;
                
            }
            if (!bTrue) {
                //在数组t中找到当前字符串t的字母,如果数组s中相同位置字母不一致,则字符串不同构
                for (int j = 0; j < len; j++) {
                    if (charInT[j] == '0') {
                        break;
                    else if (charInT[j] == t.charAt(i)) {
                        return false;
                    
                }
                //记录新的组合
                for (int k = 0; k < len; k++) {
                    if (charInS[k] == '0') {
                        charInS[k] = s.charAt(k);
                        charInT[k] = t.charAt(k);
                        break;
                    }
                }
            }
        }
         
        return true;
    }
Read full article from Isomorphic Strings – Leetcode Java | Welkin Lan

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts