Chinaunix首页 | 论坛 | 博客

crazymind

首页　| 　博文目录　| 　关于我

unicorn-ww

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

全部博文（41）

文章存档

2016年（1）

2015年（18）

2014年（22）

我的朋友
最近访客
推荐博文
相关博文
Array例题分析(1)

分类： Java

2015-02-06 12:07:46

-- word search
    >> 题目：给定一个二维数组和一个字符串，判断一个字符串是不是可以由二维数组中的相邻字母组成，相邻是指横向或纵向，数组中的每个字母只能使用一次。
    >> 解题思路：首先找到字符串首字母在数组中的位置，然后依次遍历。问题1：如果一次没找到，应该重新找起始位置；问题2：每个点只能访问一次，如果重新找需要将访问次数清0.

点击(此处)折叠或打开

  1.     public boolean exist(char[][] board, String word) {
  2.         if (word == null || word.length() == 0)
  3.             return true;
  4.         if (board == null || board.length == 0 || board[0].length == 0)
  5.             return false;
  6.         boolean[][] used = new boolean[board.length][board[0].length];
  7.         for (int i = 0; i < board.length; i++) {
  8.             for (int j = 0; j < board[0].length; j++) {
  9.                 if (search(board, word, 0, i, j, used))
  10.                     return true;
  11.             }
  12.         }
  13.         return false;
  14.     }

  16.     private boolean search(char[][] board, String word, int index, int i,
  17.             int j, boolean[][] used) {
  18.         if (index == word.length())
  19.             return true;
  20.         if (i < 0 || j < 0 || i >= board.length || j >= board[0].length
  21.                 || used[i][j] || board[i][j] != word.charAt(index))
  22.             return false;
  23.         used[i][j] = true;
  24.         boolean res = search(board, word, index + 1, i - 1, j, used)
  25.                 || search(board, word, index + 1, i + 1, j, used)
  26.                 || search(board, word, index + 1, i, j - 1, used)
  27.                 || search(board, word, index + 1, i, j + 1, used);
  28.         used[i][j] = false;
  29.         return res;
  30.     }
-- word latter
    >> 题目：给定两个单词和一个词典，输出从单词1到单词2的最短路径长度
    >> 解题思路：其实就是广度优先搜索就ok了，但是有一些细节需要处理，比如每一层可能会出现多个一样的，不应该将其放入队列

点击(此处)折叠或打开

  1.     public int ladderLength(String start, String end, Set<String> dict) {
  2.         // special
  3.         if (start.equals(end)) {
  4.             return 0;
  5.         }
  6.         
  7.         // define
  8.         Queue<String> visiting, nextVisiting, tempQ;
  9.         Set<String> visited;
  10.         char c;
  11.         int depth;
  12.         
  13.         // init
  14.         visited = new HashSet<String>();
  15.         visiting = new LinkedList<String>();
  16.         nextVisiting = new LinkedList<String>();
  17.         c = 'a';
  18.         depth = 1;
  19.         
  20.         // cal
  21.         visiting.add(start);
  22.         visited.add(start);
  23.         while (!visiting.isEmpty()) {
  24.             String item = visiting.poll();
  25.             
  26.             if (item.equals(end)) {
  27.                 return depth;
  28.             }
  29.             
  30.             char []cs = item.toCharArray();
  31.             for (int i = 0; i < item.length(); i++) {
  32.                 for (c = 'a'; c < 'z'; c++) {
  33.                     if (item.charAt(i) == c) {
  34.                         continue;
  35.                     }
  36.                     cs[i] = c;
  37.                     String temp = new String(cs);
  38.                 
  39.                     if (dict.contains(temp) && !visited.contains(temp)) {
  40.                         nextVisiting.add(temp);
  41.                         visited.add(temp);
  42.                     }
  43.                 }
  44.                 cs[i] = item.charAt(i);
  45.             }
  46.             
  47.             if (visiting.isEmpty()) {
  48.                 depth++;
  49.                 tempQ = nextVisiting;
  50.                 nextVisiting = visiting;
  51.                 visiting = tempQ;
  52.             }
  53.         }
  54.         
  55.         // ret
  56.         return 0;
  57.     }

-- 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.     }


-- unique path
    >> 题目：从二维数组的左上角到右下角一共有多少种可能的路径
     >> 解题思路：实现最简单的，暴力解法，但是时间复杂度较高 ；使用动态规划，降低时间复杂度到m * n;

点击(此处)折叠或打开

  1.     // 暴力解法
  2.     public int uniquePaths(int m, int n) {
  3.         if (m == 1 || n == 1)
  4.             return 1;
  5.         return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
  6.     }

点击(此处)折叠或打开

  1.     public int uniquePaths(int m, int n)
  2.     {
  3.         if (m == 1 || n == 1) {
  4.             return 1;
  5.         }
  6.         int [][]A = new int[m][n];
  7.         for (int i = 0; i < m; i++) {
  8.             A[i][0] = 1;
  9.         }
  10.         for (int j = 0; j < n; j++) {
  11.             A[0][j] = 1;
  12.         }
  13.         
  14.         for (int i = 1; i < m; i++) {
  15.             for (int j = 1; j < n; j++) {
  16.                 A[i][j] = A[i - 1][j] + A[i][j - 1];
  17.             }
  18.         }
  19.         return A[m - 1][n - 1];
  20.   
  21.     }




-- unique pathII
    >> 题目：现在增加障碍
    >> 解题思路：对于障碍位置特殊处理，但是要注意对边的处理和非边的处理是不一样的。

点击(此处)折叠或打开

  1.     public int uniquePathsWithObstacles(int[][] obstacleGrid) {
  2.         int m = obstacleGrid.length;
  3.         if (m == 0) return 0;
  4.         int n = obstacleGrid[0].length;
  5.         if (n == 0) return 0;
  6.         int [][]A = new int[m][n];
  7.         boolean flag = true;
  8.         for (int i = 0; i < m; i++) {
  9.             if (flag) {
  10.                 if (obstacleGrid[i][0] == 1) {
  11.                     A[i][0] = 0;
  12.                     flag = false;
  13.                 } else {
  14.                     A[i][0] = 1;
  15.                 }
  16.             } else {
  17.                 A[i][0] = 0;
  18.             }
  19.         }
  20.         flag = true;
  21.         for (int j = 0; j < n; j++) {
  22.             if (flag) {
  23.                  if (obstacleGrid[0][j] == 1) {
  24.                      A[0][j] = 0;
  25.                      flag = false;
  26.                  } else {
  27.                      A[0][j] = 1;
  28.                  }
  29.             } else {
  30.                  A[0][j] = 0;
  31.             }
  32.         }
  33.         for (int i = 1; i < m; i++) {
  34.             for (int j = 1; j < n; j++) {
  35.                 if (obstacleGrid[i][j] == 1) {
  36.                     A[i][j] = 0;
  37.                 } else {
  38.                     A[i][j] = A[i - 1][j] + A[i][j - 1];
  39.                 }
  40.             }
  41.         }
  42.         return A[m - 1][n - 1];
  43.     }


-- two sum
    >> 题目：给定一个数组，和一个数，假定肯定可以找到两个数，使其和为给定的数，求出这两个数在数组中的index
    >> 解题思路：首先将数组和index存入map，然后依次匹配，主要有重复问题，注意一个数字不能使用两次，就算数组中有两个一样的也可以使用下面的解法，因为map是唯一key模式，只会记录后一个。

点击(此处)折叠或打开

  1.     public int[] twoSum(int[] numbers, int target) {
  2.         int []ret = new int[2];
  3.         Map<Integer, Integer> map = new HashMap<Integer, Integer>();
  4.         for (int i = 0; i < numbers.length; i++) {
  5.             map.put(numbers[i], i + 1);
  6.         }
  7.         for (int i = 0; i < numbers.length; i++) {
  8.             if (map.containsKey(target - numbers[i]) && map.get(target - numbers[i]) != i + 1) {
  9.                 ret[0] = i + 1;
  10.                 ret[1] = map.get(target - numbers[i]);
  11.                 break;
  12.             }
  13.         }
  14.         return ret;
  15.     }
-- triangle
    >> 题目：给定一个三角形， 找出从上到下由相邻数组成的路径上点和的最小值

-- trapping raining water
    >> 题目：给定一个数组，每个元素代表其高度，计算最多可以乘多少水。
    >> 解题思路：这道题的解法是基于单调栈（就是栈中的数据按从小到大或从大到小），然后入栈前对于栈顶元素进行判断，是否小于等于自己，计算响应的有效面积，中间计算过的小面积应该删掉。

点击(此处)折叠或打开

  1.     public int trap(int[] A) {
  2.         int sum = 0, midHeight = 0, index = 0;
  3.         Stack<Integer> posStack = new Stack<Integer>();
  4.         
  5.         for (int i = 0; i < A.length; i++) {
  6.             while (!posStack.isEmpty()) {
  7.                 index = posStack.peek();
  8.                 int temp = A[i] < A[index] ? A[i] : A[index];
  9.                 // 减去midHeight 就是去掉已经算过的
  10.                 sum += (temp - midHeight) * (i - index - 1);
  11.                 midHeight = A[index];
  12.                 if (A[i] >= A[index]) {
  13.                     posStack.pop();
  14.                 } else {
  15.                     break;
  16.                 }
  17.             }
  18.             posStack.push(i);
  19.         }
  20.         
  21.         return sum;
  22.     }

-- subset
    >> 题目：给定一个不同数的集合，请求所有可能的子集
    >> 解题思路：遍历根据放入和不放入两种情况进行深度优先遍历。

-- subset II
    >> 题目：给定一个可能包含重复数的集合，求出所有的子集
    >> 解题思路：首先先排序，然后遍历的时候也会稍后不同，如果全部都是不一样的，挨个遍历每个字母就ok了。但是如果有了重复的，每一次会依次选遍历节点后的每个节点作为每个集合中遍历节点的后续节点，这样对于每一层的遍历就可以去掉相同的就ok了。

-- spiral matrix
    >> 题目：给定一个矩阵，输出它的绕圈遍历顺序
    >> 解题思路：略简单，就是遍历。

-- spiral matrix2
    >> 题目：给定一个正数n，输出n^2个数按spiral顺序的matrix
    >> 解题思路：类似于1

-- sort colors
    >> 题目：给一个数组，标记为不同数组，进行排序，使相同数字相邻。
    >> 解题思路：包含重复数的排序。

-- set matrix zeroes
    >> 题目：给定一个数组，如果某一个元素为0， 两个将其所在的行和列都设置为0
    >> 解题思路：首先遍历一遍，记录需要置位的行和列，然后遍历zhi'wei

-- search insert position
    >> 题目：给定一个排好序数组和一个数字，如果存在，找出其位置否则找出其插入位置，无重复
    >> 解题思路：暴力搜索，加快速度可以二分查找

-- search in rotated sorted array
    >> 题目：数组中的某几位被循环移位，查找
    >> 解题思路： 暴力搜索，加快速度可以二分查找

-- search in rotated sorted array II
    >> 题目：数组中的某几位被循环移位，查找
    >> 解题思路： 暴力搜索，加快速度可以二分查找

-- Search for a Range 
    >> 题目：从一个包含重复的数组中找到某个数的范围
    >> 解题思路：二分查找

点击(此处)折叠或打开

  1.     public int[] searchRange(int[] A, int target) {
  2.         
  3.         int mid = 0, start = 0, end = A.length;
  4.         int []index = new int[2];
  5.         for ( ; start >= end; ) {
  6.             mid = start + (end - start) / 2;
  7.             if (target == A[mid]) {
  8.                 break;
  9.             } else if (target < A[mid]) {
  10.                 end = mid - 1;
  11.             } else {
  12.                 start = mid + 1;
  13.             }
  14.         }
  15.         if (target == A[mid]) {
  16.             index[0] = mid;
  17.             index[1] = mid;
  18.             for (int i = mid - 1; i > -1; i--) {
  19.                 if (target == A[i]) {
  20.                     index[0] = i;
  21.                 } else {
  22.                     break;
  23.                 }
  24.             }
  25.             for (int i = mid + 1; i < A.length; i++) {
  26.                 if (target == A[i]) {
  27.                     index[1] = i;
  28.                 } else {
  29.                     break;
  30.                 }
  31.             }
  32.         } else {
  33.             index[0] = -1;
  34.             index[1] = -1;
  35.         }
  36.         
  37.         
  38.         
  39.         return index;
  40.     }
-- Search a 2D Matrix 
    >> 题目：给定一个matrix，求该matrix是否每一行是增序的且后一行的首大于上一行的尾
    >> 解题思路：遍历

-- Rotate Image
    >> 题目：给定各一个matrix，转90度
    >> 解题思路：可以通过两步对换得到

-- Remove Elemet
    >> 题目：从数组中移除元素，返回长度
    >> 解题思路：遍历，移除以后需要调整后续的位置。

-- Remove Duplicates from Sorted Array 
    >> 题目：从有序数组中删除重复元素，只留其中一个
    >> 解题思路：遍历，每次删除元素后，调整后续的位置。

-- Remove Duplicates from Sorted Array II    
    >> 题目：从有序数组中删除超过两次重复元素，只留其中两次
    >> 解题思路：遍历，记录次数，每次删除元素后，调整后续的位置。

-- Plus One 
    >> 题目：给数加1 ，但是每一位站数组中的一个元素
    >> 解题思路：注意进位

-- Pascal's Triangle
    >> 题目：构造二维数组
    >> 解题思路：注意边界问题

-- Pascal's Triangle II
    >> 题目：构造二维数组，输出其中的某一行
    >> 解题思路：注意边界问题

-- Next Permutation
    >> 题目：返回一个数组的下一个字典序
    >> 解题思路： 从后往前找到第一个降序的位置，然后将这个位置与其后第一个比他大的交换，将这个位置后的排序（升序）

点击(此处)折叠或打开

  1.     void nextPermutation(vector<int> &num) {
  2.         int i = num.size() - 1, tmp = 0, idx = 0;
  3.         for ( ; i > 0; i--) {
  4.             if (num[i] > num[i - 1]) {
  5.                 idx = i - 1;
  6.                 for (i = num.size() - 1; ; i--) {
  7.                     if (num[i] > num[idx]) break;
  8.                 }
  9.                 tmp = num[idx];
  10.                 num[idx] = num[i];
  11.                 num[i] = tmp;
  12.                 sort(num.begin() + idx + 1, num.end());
  13.                 return;
  14.             }
  15.         }
  16.         if (i == 0) {
  17.             sort(num.begin(), num.end());
  18.         }
  19.     }



    

阅读(1390) | 评论(0) | 转发(0) |
0

上一篇：设计模式

下一篇：虚函数与多态--C语言实现面向对象

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6