Chinaunix首页 | 论坛 | 博客
  • 博客访问: 112528
  • 博文数量: 41
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 407
  • 用 户 组: 普通用户
  • 注册时间: 2013-06-27 13:42
文章分类

全部博文(41)

文章存档

2016年(1)

2015年(18)

2014年(22)

我的朋友

分类: Java

2015-02-10 01:15:46

-- ZigZag Convertion
    >> 题目:给定一个字符串和n(代表zigzag的高度),输出zigzag以后的字符串
    >> 解题思路:就是简单的转换了。注意特殊情况处理

-- word latter II
    >> 题目:给定两个单词和一个词典,输出所有可能从单词1到单词2的路径
    >> 解题思路:广度优先搜索并记录路径,但是由于要输出路径,所以要记录,只用广度优先,至少内存开销会很大。继续深挖题目信息,就算是所有最短路径,那么每个单词也只会出现一次,所有只要继续



点击(此处)折叠或打开

  1.     private void bfs(String start, String end, Set<String> dict, Map<String, Integer> depthMap) {
  2.         // define
  3.         Queue<String> visiting, nextVisiting, tempQ;
  4.         Set<String> visited;
  5.         char c = 'a';
  6.         int depth;
  7.         
  8.         // init
  9.         visiting = new LinkedList<String>();
  10.         nextVisiting = new LinkedList<String>();
  11.         visited = new HashSet<String>();
  12.         depth = 2;
  13.         
  14.         // cal
  15.         visited.add(start);
  16.         visiting.add(start);
  17.         depthMap.put(start, 1);
  18.         while (!visiting.isEmpty()) {
  19.             String item = visiting.poll();
  20.             
  21.             if (item.equals(end)) {
  22.                 return;
  23.             }
  24.             
  25.             char []cs = item.toCharArray();
  26.             for (int i = 0; i < item.length(); i++) {
  27.                 for (c = 'a'; c <= 'z'; c++) {
  28.                     if (cs[i] == c) {
  29.                         continue;
  30.                     }
  31.                     cs[i] = c;
  32.                     String temp = new String(cs);
  33.                     if (dict.contains(temp) && !visited.contains(temp)) {
  34.                         nextVisiting.add(temp);
  35.                         visited.add(temp);
  36.                         depthMap.put(temp, depth);
  37.                     }             
  38.                     cs[i] = item.charAt(i);
  39.                 }
  40.             }
  41.             
  42.             if (visiting.isEmpty()) {
  43.                 tempQ = nextVisiting;
  44.                 nextVisiting = visiting;
  45.                 visiting = tempQ;
  46.                 depth++;
  47.             }
  48.         }
  49.     }
  50.     
  51.     private void dfs(String start, String end, Set<String> dict, Map<String, Integer> depthMap, List<String> path, List<List<String>> result) {
  52.         // define
  53.         List<String> newPath;
  54.         char c = 'a';
  55.         int depth;
  56.         
  57.         // init
  58.         
  59.         //special
  60.         if (start.equals(end)) {
  61.             path.add(end);
  62.             result.add(path);
  63.             return;
  64.         }
  65.         if (!depthMap.containsKey(start)) {
  66.             return;
  67.         }
  68.         path.add(start);
  69.         depth = depthMap.get(start);
  70.         char []cs = start.toCharArray();
  71.         for (int i = 0; i < start.length(); i++) {
  72.             for (c = 'a'; c <= 'z'; c++) {
  73.                 if (c == cs[i]) {
  74.                     continue;
  75.                 }
  76.                 cs[i] = c;
  77.                 
  78.                 String temp = new String(cs);
  79.                 if (depthMap.containsKey(temp) && depthMap.get(temp) == depth + 1) {
  80.                     newPath = new ArrayList<String>(path);
  81.                     dfs(temp, end, dict, depthMap, newPath, result);
  82.                 }
  83.                 cs[i] = start.charAt(i);
  84.             }
  85.         }
  86.         
  87.     }
  88.     
  89.     public List<List<String>> findLadders(String start, String end, Set<String> dict) {
  90.         // define
  91.         List<List<String>> result = new ArrayList<List<String>>();
  92.         Map<String, Integer> depthMap = new HashMap<String, Integer>();
  93.         List<String> path = new ArrayList<String>();
  94.         
  95.         // special
  96.         if (start == null || end == null) {
  97.             return result;
  98.         }
  99.         
  100.         // init
  101.         
  102.         // cal
  103.         bfs(start, end, dict, depthMap);
  104.         dfs(start, end, dict, depthMap, path, result);
  105.         
  106.         // ret
  107.         return result;
  108.     }




-- Wildcard Matching    
    >> 题目:实现通配符模式匹配,包括对?和*的支持
'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).
    >> 解题思路:模式串中会出现三种字符,然后对于java 的处理,在最后添加一位标志位。
            ++ 对于?字符,直接匹配,后移
            ++ 对于普通字符,直接匹配,如果之前没有'*',可以使用最简单的来处理;如果之前已经出现了'*',而且没有匹配上,则从最后一个'*'后(模式串) 与 第一次碰到最后一块'*'的位置后移一位开始匹配(原字符串的某个位置),每次遇到匹配不上,将将原字符串中的记录位置后移一位,然后与模式串最后'*'后面的字符进行匹配。

点击(此处)折叠或打开

  1.     public boolean isMatch(String s, String p) {
  2.         int i = 0, j = 0, tempI = 0, tempJ = 0;
  3.         boolean firstFlag = true;
  4.         String ss = s + '\0', pp = p + '\0';
  5.         for (i = 0, j = 0; ss.charAt(i) != '\0'; i++, j++) {
  6.             switch(pp.charAt(j)) {
  7.             case '?':
  8.                 break;
  9.             case '*':
  10.                 firstFlag = false;
  11.                 tempI = i;     // record the index
  12.                 tempJ = j;
  13.                 while (pp.charAt(tempJ) == '*') tempJ++; //skip continuous '*'
  14.                 i = tempI - 1; // back one position to rematch;
  15.                 j = tempJ - 1; // last '*'
  16.                 break;
  17.             default:
  18.                 if (ss.charAt(i) != pp.charAt(j)) {
  19.                     if (firstFlag) return false;
  20.                     tempI++; // there is a '*' before this j
  21.                     i = tempI - 1;
  22.                     j = tempJ - 1;
  23.                 }
  24.             }
  25.         }
  26.         while (pp.charAt(j) == '*') j++;
  27.         return pp.charAt(j) == '\0';
  28.     }
-- Valid Parentheses
    >> 题目:给定一个字符串,判断是否括号匹配
    >> 解题思路:使用栈,对于暂时没有匹配上的先入栈,匹配上的出栈,遍历完判断即可。

-- Valid Palindrome
    >> 题目:给定一个字符串,判断其是否是回文。
    >> 解题思路:注意需要处理掉特殊字符,然后根据前后两个index来判断。

-- Valid Number
    >> 题目:给定一个字符串,判断其是否是一个数字
    >> 解题思路:有限状态机

-- Text Justification     
    >> 题目:文本对齐,给定一个数组和长度L,使字符串对齐。    You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly L characters.    Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.
    >> 解题思路:

-- Substring with Concatenation of All Words
    >> 题目:

-- String to Integer(atoi)
    >> 题目:给定一个字符串,将其转换为int
    >> 解题思路:主要是异常处理,空格处理,可能是负数(- +处理),可能超出int的范围

点击(此处)折叠或打开

  1.     int atoi(const char *str) {
  2.         int ret = 0, i = 0, len = strlen(str), flag = 1, num = 0;
  3.         long long tmp = 0;
  4.         for (i = 0; i < len && str[i] == ' '; i++) ;
  5.         if (i == len) return 0;
  6.         if (str[i] == '-') flag = -1;
  7.         if (str[i] == '-' || str[i] == '+') i++;
  8.         for ( ; i < len && (str[i] >= '0' && str[i] <= '9'); i++) {
  9.             num = str[i] - '0';
  10.             tmp = tmp * 10 + num;
  11.         }
  12.         if (tmp >= 2147483647 && flag == 1)
  13.             ret = 2147483647;
  14.         else if (tmp > 2147483648 && flag == -1)
  15.             ret = 2147483648;
  16.         else
  17.             ret = tmp;
  18.         ret *= flag;
  19.         return ret;
  20.     }
-- Simplify Path
    >> 题目:给定一个unix路径,对其进行简化
    >> 地址:https://oj.leetcode.com/problems/simplify-path/
    >> 解题思路:利用list模拟stack和queue。

点击(此处)折叠或打开

  1.     public String simplifyPath(String path) {
  2.         List<String> queue = new ArrayList<String>();
  3.         if (path.length() == 1) return path;
  4.         int i = 0, j = 1;
  5.         String paths = path + '/';
  6.         String temp = null;
  7.         for (i = 0, j = 1; j < paths.length(); ) {
  8.             if (paths.charAt(j) == '/') {
  9.                 temp = paths.substring(i, j);
  10.                 if (temp.equals("/.")) {
  11.                     
  12.                 } else if (temp.equals("/")) {
  13.                     
  14.                 } else if (temp.equals("/..")) {
  15.                     if (queue.size() > 0) {
  16.                         queue.remove(queue.size() - 1);
  17.                     }
  18.                 } else {
  19.                     queue.add(temp);
  20.                 }
  21.                 i = j;
  22.                 j++;
  23.             } else {
  24.                 j++;
  25.             }
  26.         }
  27.         StringBuilder sb = new StringBuilder("");
  28.         for (String str : queue) {
  29.             sb.append(str);
  30.         }
  31.         if (sb.length() == 0) {
  32.             sb.append("/");
  33.         }
  34.         return sb.toString();
  35.     }



阅读(348) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册