前言
Leetcode算法题分类练习，记录解题思路和代码。
双指针
题目1： 判断一个非负整数是否为两个整数的平方和。
思路
看成0-target开平方之间寻找两个数，使得两个数的平方和等于target。
代码
public class DoublePointer1 {
public boolean judgeSquareSum(int target) {
if (target < 0) return false;
int left = 0;
int right = (int) Math.sqrt(target);
while (left <= right) {
int sum = Math.abs(left) + Math.abs(right);
if (sum == target) {
return true;
} else if (sum > target) {
right--;
} else {
left++;
}
}
return false;
}
}
题目2：反转字符串中的元音字符
思路
代码
public class DoublePointer2 {
private HashSet<Character> vowels = new HashSet<Character>(Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'));
public String reverseVowels(String s) {
if (s.length() == 0)
return null;
char[] cs = s.toCharArray();
int i = 0, j = cs.length-1;
while(i < j){
if(vowels.contains(cs[i]) && vowels.contains(cs[j])){
char temp = cs[i];
cs[i] = cs[j];
cs[j] = temp;
i++;
j++;
}
if (!vowels.contains(cs[i])){
i++;
}
if (!vowels.contains(cs[j])){
j--;
}
}
return cs.toString();
}
}
题目3： 可以删除一个字符，判断是否能构成回文字符串。
思路
利用两个指针，left指向头，right指向位，left和right的指向的位置如果相同则各自向内移动一位，不同则可以分为两种情况，删除left指向的位置或删除right指向的位置。然后继续比较。
代码
public class DoublePointer3 {
public boolean validPalindrome(String s) {
char[] cs = s.toCharArray();
int i = 0, j = cs.length-1;
while(i < j){
if(cs[i] != cs[j])
return isPalindrome(cs, i+1, j) || isPalindrome(cs, i, j+1);
i++;
j--;
}
return true;
}
private boolean isPalindrome(char[] cs, int i, int j) {
while (i < j) {
if (cs[i] != cs[j]) {
return false;
}
i++;
j--;
}
return true;
}
}
题目4： 删除 s 中的一些字符，使得它构成字符串列表 d 中的一个字符串，找出能构成的最长字符串。如果有多个相同长度的结果，返回字典序的最小字符串。
思路
利用双指针判断是否是子字符串。
代码
public String findLongestWord(String s, List<String> d) {
String res = "";
for (String target : d) {
int l1 = res.length(), l2 = target.length();
if (l1 > l2 || (l1 == l2 && res.compareTo(target) < 0)) {
continue;
}
if (isSubstr(s, target)) {
res = target;
}
}
return res;
}
private boolean isSubstr(String s, String target) {
int i = 0, j = 0;
while (i < s.length() && j < target.length()) {
if (s.charAt(i) == target.charAt(j)) {
j++;
}
i++;
}
return j == target.length();
}
快速选择
荷兰国旗问题
题目：有三种颜色的球，算法的目标是将这三种球按颜色顺序正确地排列。
思路
三向切分快速排序的一种变种，在三向切分快速排序中，每次切分都将数组分成三个区间：小于切分元素、等于切分元素、大于切分元素，而该算法是将数组分成三个区间：等于红色、等于白色、等于蓝色。
代码
public class ThreeSlices {
public void sortColors(int[] nums) {
int zero = -1, one = 0, two = nums.length;
while(one < two){
if (nums[one] == 2){
swap(nums, one, --two);
}else if (nums[one] == 0){
swap(nums, one++, ++zero);
}else{
one++;
}
}
}
private void swap(int[] nums, int i, int j) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
}
桶排序
题目：返回数组中出现频率最高的K的数， Given [1,1,1,2,2,3] and k = 2, return [1,2].
思路
假设有若干个桶，桶下标表示数出现的频率，即低第i个桶中存放着出现频率为i的数。
代码
public class BucketSorting {
public List<Integer> topKFrequent(int[] nums, int k) {
// 统计每个数出现的次数
HashMap<Integer, Integer> statistics = new HashMap<>();
for (int num : nums) {
if (statistics.containsKey(num)){
statistics.put(num, statistics.get(num)+1);
}else{
statistics.put(num, 1);
}
}
// 依据数出现的次数将数放到对应的桶中
ArrayList[] als = new ArrayList[nums.length + 1];
for (int key : statistics.keySet()){
int count = statistics.get(key);
if (als[count] == null)
als[count] = new ArrayList();
als[count].add(key);
}
// 从后往前，统计出现次数最多的k个数
List<Integer> res = new ArrayList<>();
for (int i = als.length-1; i >= 0 && res.size() < k; i--){
if (als[i] == null){
continue;
}
if (als[i].size() <= k - res.size()){
res.addAll(als[i]);
}else{
res.addAll(als[i].subList(0, k - res.size()));
}
}
return res;
}
}
贪心思想
题目： 每个孩子都有一个满足度 grid，每个饼干都有一个大小 size，只有饼干的大小大于等于一个孩子的满足度，该孩子才会获得满足。求解最多可以获得满足的孩子数量。
思路
代码
public class DistributeCookies {
public int findContentChildren(int[] grid, int[] size) {
if (grid == null || size == null)
return 0;
Arrays.sort(grid);
Arrays.sort(size);
int i = 0, j = 0;
while(i < grid.length && j < size.length){
if (grid[i] < size[j]){
i++;
}
j++;
}
return j;
}
}
题目： 计算让一组区间不重叠所需要移除的区间个数。 Input: [ [1,2], [1,2], [1,2] ] Output: 2 ； Input: [ [1,2], [2,3] ] Output: 0
思路
按照期间的结尾进行升序排序， 选择的区间结尾越小，留给后面的区间的空间越大，那么后面能够选择的区间个数也就越大。
代码
public class DistributeCookies {
public int eraseOverlapIntervals(int[][] intervals) {
if (intervals.length == 0) {
return 0;
}
Arrays.sort(intervals, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[1] - o2[1];
}
});
int cur = intervals[0][1];
int count = 1;
for(int i = 1; i < intervals.length; i++){
if(intervals[i][0] < cur)
continue;
cur = intervals[i][1];
count++;
}
return intervals.length - count;
}
}
题目： 气球在一个水平数轴上摆放，可以重叠，飞镖垂直投向坐标轴，使得路径上的气球都被刺破。求解最小的投飞镖次数使所有气球都被刺破。
思路
也是计算不重叠的区间个数，不过和 上一题的区别在于，[1, 2] 和 [2, 3] 在本题中算是重叠区间。
代码
题目： 一个学生用两个分量 (h, k) 描述，h 表示身高，k 表示排在前面的有 k 个学生的身高比他高或者和他一样高。
思路
每个位置的 k 的值，等于在这个位置之前 h 比它大的位置的数量。如果要向一个队列中插入一个人，要判断的就是插入的位置。那么如果可以确定，当前队列中的所有人的 h 值都比待插入的这个人的 h 值大，那么这个人的 k 值就是他应该插入的位置。（通过身高降序）并且可以确定，如果插入的是一个 h 值小于当前队列中所有人的 h 值的人，那么无论他的位置在哪，都不会影响当前队列中所有人的 k 值，即不会破坏当前队列的正确性。（相同升高，则按k值升序）
代码
public class HeightAndNumber {
public int[][] reconstructQueue(int[][] people) {
if (people == null || people.length == 0 || people[0].length == 0) {
return new int[0][0];
}
Arrays.sort(people, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0];
}
});
List<int[]> res = new ArrayList<>();
for(int[] inser : people){
res.add(inser[1], inser);
}
return res.toArray(new int[res.size()][]);
}
}
题目： 题目描述：一次股票交易包含买入和卖出，只进行一次交易，求最大收益。
思路
代码
public class StockMaxIncome {
public int maxProfit(int[] prices) {
if (prices.length == 0)
return 0;
int mix = 0;
int min = prices[0];
for (int i = 1; i < prices.length; i++){
if (prices[i] < min){
min = prices[i];
}
int curIncome = prices[i] - min;
if (curIncome > mix){
mix = curIncome;
}
}
return mix;
}
}
题目： flowerbed 数组中 1 表示已经种下了花朵。花朵之间至少需要一个单位的间隔，求解是否能种下 n 朵花。
思路
用两个指针pre和next，分别指向当前位置的前后下标，当当前位置为0和前后位置同时为0时才可以在当前位置种花。
代码
public class PlantFlowers {
public boolean canPlaceFlowers(int[] flowerbed, int n) {
int pre = 0, next = 0, count = 0, len = flowerbed.length;
for (int i = 0; i < len && count < n; i++){
if (flowerbed[i] == 1){
continue;
}
pre = i == 0 ? 0 : flowerbed[i - 1];
next = i == len - 1 ? 0 : flowerbed[i + 1];
if(pre == 0 && next == 0){
flowerbed[i] = 1;
count++;
}
}
return count >= n;
}
}
题目： 判断一个数组是否能只修改一个数就成为非递减数组。
思路
代码
public class NonDecreasingArray {
public boolean checkPossibility(int[] nums) {
int count = 0;
for (int i = 1; i < nums.length; i++){
if (nums[i] >= nums[i - 1])
continue;
if(i - 2 >= 0 && nums[i] < nums[i - 2]){
nums[i] = nums[i - 1];
}else{
nums[i - 1] = nums[i];
}
if (++count > 1)
break;
}
return count <= 1;
}
}
题目：子数组最大的和
思路
代码
public class MaxSumSubarray {
public int maxSubArray(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int curSum = nums[0];
int mixSum = curSum;
for (int i = 1; i < nums.length; i++){
curSum = curSum > 0 ? curSum + nums[i] : nums[i];
mixSum = Math.max(mixSum, curSum);
}
return mixSum;
}
}
题目：分隔字符串使同种字符出现在一起
思路
先用一个数组记录所有字符在字符串中最后出现过的位置，然后遍历字符串，假如第一个字符a最后出现的位置为9，则当前分区为0-9，如果9之前的字符最后出现的位置都没超过9的话这分区为一组，如果9之前有字符最后出现过的位置（10）超过9的话，则重置分区0-10。
代码
public class SplitString {
public List<Integer> partitionLabels(String S) {
int[] list26 = new int[26];
for (int i = 0; i < S.length(); i++){
list26[charToIndex(S.charAt(i))] = i;
}
List<Integer> res = new ArrayList<>();
int firstIndex = 0;
while (firstIndex < S.length()){
int lastIndex = firstIndex;
for(int i = firstIndex; i < S.length() && i <= lastIndex; i++){
if (list26[charToIndex(S.charAt(i))] > lastIndex)
lastIndex = list26[charToIndex(S.charAt(i))];
}
res.add(lastIndex - firstIndex + 1);
firstIndex = lastIndex + 1;
}
return res;
}
private int charToIndex(char c) {
return c - 'a';
}
}
二分查找
题目： 一个数 x 的开方 sqrt 一定在 0 ~ x 之间，并且满足 sqrt == x / sqrt。可以利用二分查找在 0 ~ x 之间查找 sqrt。
思路
代码
public class SqrtX {
public int mySqrt(int x) {
if (x <= 1) {
return x;
}
int low = 1, high = x;
while(low <= high){
int mid = low + (high - low)/2;
int sqrt = x/mid;
if (sqrt == mid){
return mid;
}else if (sqrt < mid){
high = mid - 1;
}else{
low = mid + 1;
}
}
return high;
}
}
题目： 给定一个有序的字符数组 letters 和一个字符 target，要求找出 letters 中大于 target 的最小字符，如果找不到就返回第 1 个字符。
思路
代码
public class SmallestLargerThanTarget {
public char nextGreatestLetter(char[] letters, char target) {
int low = 0, high = letters.length - 1;
while (low <= high){
int mid = low + (high - low)/2;
if (letters[mid] <= target){
low = mid + 1;
}else{
high = mid - 1;
}
}
return low < letters.length ? letters[low] : letters[0];
}
public static void main(String[] args){
}
}
--> 题目： 一个有序数组只有一个数不出现两次，找出这个数。
思路
代码
public class SingleNonDuplicate {
public int singleNonDuplicate(int[] nums) {
int low = 0, high = nums.length - 1;
while(low < high){
int mid = low + (high - low)/2;
mid = mid%2 == 0 ? mid : mid--;
if (nums[mid] == nums[mid + 1]){
low = mid + 2;
}else{
high = mid;
}
}
return nums[high];
}
}
题目：旋转数组的最小数字
思路
代码
public class RotateArray {
public int findMin(int[] nums) {
int low = 0, high = nums.length - 1;
while (low < high){
int mid = low + (high - low)/2;
if (nums[mid] > nums[high]){
low = mid + 1;
}else{
high = mid;
}
}
return nums[low];
}
}
题目：给定一个有序数组 nums 和一个目标 target，要求找到 target 在 nums 中的第一个位置和最后一个位置。
思路
代码
public class FindInterval {
public int[] searchRange(int[] nums, int target) {
int first = find(nums, target);
int last = find(nums, target + 1) - 1;
if (first == nums.length || nums[first] != target) {
return new int[]{-1, -1};
} else {
return new int[]{first, last};
}
}
private int find(int[] nums, int target) {
int low = 0, high = nums.length; // 注意 h 的初始值
while (low < high){
int mid = low + (high - low)/2;
if (nums[mid] >= target){
high = mid;
}else{
low = mid + 1;
}
}
return low;
}
}
分治
题目：给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。
思路
代码
public class Parenthood {
public List<Integer> diffWaysToCompute(String input) {
List<Integer> res = new ArrayList<>();
for (int i = 0; i < input.length(); i++){
if (input.charAt(i) == '+' || input.charAt(i) == '-' || input.charAt(i) == '*'){
List<Integer> left = diffWaysToCompute(input.substring(0, i));
List<Integer> right = diffWaysToCompute(input.substring(i+1));
for (Integer l : left){
for (Integer r : right){
switch (input.charAt(i)){
case '+' : res.add(l + r); break;
case '-' : res.add(l - r); break;
case '*' : res.add(l * r); break;
}
}
}
}
}
if (res.isEmpty())
res.add(Integer.valueOf(input));
return res;
}
}
题目： 给定一个整数 n，生成所有由 1 ... n 为节点所组成的 二叉搜索树 。
思路
代码
public class TreeNode {
public int val = 0;
public TreeNode left = null;
public TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public class AllBinaryTree {
public List<TreeNode> generateTrees(int n) {
if (n < 1) {
return new LinkedList<TreeNode>();
}
return generateSubtrees(1, n);
}
private List<TreeNode> generateSubtrees(int start, int end) {
List<TreeNode> res = new LinkedList<>();
if (start > end){
res.add(null);
return res;
}
for (int i = start; i <= end; i++){
List<TreeNode> lefts = generateSubtrees(start, i - 1);
List<TreeNode> rights = generateSubtrees(i + 1, end);
for (TreeNode left : lefts){
for (TreeNode right : rights){
TreeNode root = new TreeNode(i);
root.left = left;
root.right = right;
res.add(root);
}
}
}
return res;
}
}
搜索
BFS
题目： 0表示可以经过某个位置，求解从左上角到右下角的最短路径长度。
思路
代码
public class ShortestPath {
public int shortestPathBinaryMatrix(int[][] grids) {
if (grids == null || grids.length == 0 || grids[0].length == 0) {
return -1;
}
int[][] next = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}, {1, 1}, {-1, -1}, {1, -1}, {-1, 1}};
int mixY = grids.length, mixX = grids[0].length, path = 0;
Queue<Pair<Integer, Integer>> que = new LinkedList<>();
que.add(new Pair<>(0, 0));
while(!que.isEmpty()){
int size = que.size();
path++;
while(size-- > 0){
Pair<Integer, Integer> cur = que.poll();
int curX = cur.getKey(), curY = cur.getValue();
if (grids[curX][curY] == 1)
continue;
if(curX == mixX - 1 && curY == mixY - 1)
return path;
grids[curX][curY] = 1;
for (int[] ne : next){
int nextX = curX + ne[0], nextY = curY + ne[1];
if (nextX < 0 || nextX >= mixX || nextY < 0 || nextY >= mixY){
continue;
}
que.add(new Pair<Integer, Integer>(nextX, nextY));
}
}
}
return -1;
}
}
题目： 给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
思路
代码
public class MinimumSquareQuantity {
public int numSquares(int n) {
List<Integer> allSquareNumber = generateSquares(n);
Queue<Integer> que = new LinkedList<>();
boolean[] visited = new boolean[n + 1];
visited[n] = true;
que.add(n);
int res = 0;
while (!que.isEmpty()){
res++;
int size = que.size();
while (size-- > 0){
int cur = que.poll();
for (int i : allSquareNumber){
int next = cur - i;
if (next < 0)
break;
if (next == 0)
return res;
if (visited[next])
continue;
que.add(next);
visited[next] = true;
}
}
}
return -1;
}
/**
* 生成小于 n 的平方数序列
* @return 1,4,9,...
*/
private List<Integer> generateSquares(int n) {
List<Integer> squares = new ArrayList<>();
int square = 1;
int diff = 3;
while (square <= n) {
squares.add(square);
square += diff;
diff += 2;
}
return squares;
}
}
题目：给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：（1）每次转换只能改变一个字母。（2）转换过程中的中间单词必须是字典中的单词
思路
代码
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
wordList.add(beginWord);
int start = wordList.size() - 1, end = 0;
while (end < start && !wordList.get(end).equals(endWord)){
end++;
}
if (end == start)
return 0;
ArrayList<Integer>[] graphic = buildGraphic(wordList);
return getShortestPath(graphic, start, end);
}
private ArrayList<Integer>[] buildGraphic(List<String> wordList) {
ArrayList<Integer>[] res = new ArrayList[wordList.size()];
for (int i = 0; i < wordList.size(); i++){
res[i] = new ArrayList<Integer>();
for (int j = 0; j < wordList.size(); j++){
int dif = 0;
for (int k = 0; k < wordList.get(j).length() && dif <= 1; k++){
if (wordList.get(i).charAt(k) != wordList.get(j).charAt(k)){
dif++;
}
}
if (dif == 1)
res[i].add(j);
}
}
return res;
}
private int getShortestPath(List<Integer>[] graphic, int start, int end) {
Queue<Integer> que = new LinkedList<>();
boolean[] visited = new boolean[graphic.length];
que.add(start);
visited[start] = true;
int path = 1;
while (!que.isEmpty()){
int size = que.size();
path++;
while (size-- > 0){
int cur = que.poll();
for (int next : graphic[cur]){
if (next == end){
return path;
}
if (visited[next]){
continue;
}
que.add(next);
visited[next] = true;
}
}
}
return 0;
}
DFS
题目：给定一个包含了一些 0 和 1 的非空二维数组 grid 。一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 。)
思路
代码
private int[][] direcction= {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
public int maxAreaOfIsland(int[][] grid) {
if (grid == null || grid.length == 0)
return 0;
int mixRow = grid.length, mixColumn = grid[0].length;
int mixSize = 0;
for (int curRow = 0; curRow < mixRow; curRow++){
for (int curColum = 0; curColum < mixColumn; curColum++){
if (grid[curRow][curColum] == 1){
int curSize = DFS(grid, curRow, curColum);
mixSize = curSize > mixSize ? curSize : mixSize;
}
}
}
return mixSize;
}
public int DFS(int[][] grid, int curRow, int curColumn){
int mixArea = 1;
grid[curRow][curColumn] = 0;
for (int[] dire : direcction){
int nextRow = curRow + dire[0];
int nextColumn = curColumn + dire[1];
if (nextRow >= 0 && nextRow < grid.length && nextColumn >= 0 && nextColumn < grid[0].length && grid[nextRow][nextColumn] == 1)
mixArea += DFS(grid, nextRow, nextColumn);
}
return mixArea;
}
题目：给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
思路
先把与外围相连的‘O’标记为‘T’，然后剩下的就是被包围的‘O‘，遍历整个二维数组，将’O‘改为’X‘,'T'改为‘O’
代码
int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
public void solve(char[][] board) {
if (board == null || board.length == 0)
return;
int maxRow = board.length, maxColumn = board[0].length;
for (int curRow = 0; curRow < maxRow; curRow++){
if (board[curRow][0] == 'O')
DFS(board, curRow, 0);
if (board[curRow][maxColumn - 1] == 'O')
DFS(board, curRow, maxColumn - 1);
}
for (int curColumn = 0; curColumn < maxColumn; curColumn++){
if (board[0][curColumn] == 'O')
DFS(board, 0, curColumn);
if (board[maxRow - 1][curColumn] == 'O')
DFS(board, maxRow - 1, curColumn);
}
for (int curRow = 0; curRow < maxRow; curRow++){
for (int curColumn = 0; curColumn < maxColumn; curColumn++){
if (board[curRow][curColumn] == 'O')
board[curRow][curColumn] = 'X';
if (board[curRow][curColumn] == 'T')
board[curRow][curColumn] = 'O';
}
}
}
public void DFS(char[][] board, int curRow, int curColumn){
board[curRow][curColumn] = 'T';
for (int[] dire : direction){
int nextRow = curRow + dire[0], nextColumn = curColumn + dire[1];
if (nextRow >= 0 && nextRow < board.length && nextColumn >= 0 && nextColumn < board[0].length && board[nextRow][nextColumn] == 'O')
DFS(board, nextRow, nextColumn);
}s
}
题目：给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。
思路
代码
class Solution {
int mixRow, mixColumn;
int[][] matrix;
int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
public List<List<Integer>> pacificAtlantic(int[][] matrix) {
List<List<Integer>> res = new ArrayList<>();
if (matrix == null || matrix.length == 0)
return res;
this.mixRow = matrix.length;
this.mixColumn = matrix[0].length;
this.matrix = matrix;
boolean[][] reachP = new boolean[mixRow][mixColumn];
boolean[][] reachA = new boolean[mixRow][mixColumn];
for (int i = 0; i < mixRow; i++){
DFS(i, 0, reachP);
DFS(i, mixColumn - 1, reachA);
}
for (int i = 0; i < mixColumn; i++){
DFS(0, i, reachP);
DFS(mixRow - 1, i, reachA);
}
for (int i = 0; i < mixRow; i++){
for (int j = 0; j < mixColumn; j++){
if (reachP[i][j] && reachA[i][j])
res.add(new ArrayList<>(Arrays.asList(i, j)));
}
}
return res;
}
public void DFS(int curRow, int curColum, boolean[][] reachX){
if (reachX[curRow][curColum])
return;
reachX[curRow][curColum] = true;
for (int[] next : direction){
int nextRow = curRow + next[0], nextColum = curColum + next[1];
if (nextRow >= 0 && nextRow < mixRow && nextColum >= 0 && nextColum < mixColumn && matrix[nextRow][nextColum] >= matrix[curRow][curColum])
DFS(nextRow, nextColum, reachX);
}
}
}
Backtracking
题目17：给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
思路
代码
class Solution {
String[] phone = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
public List<String> letterCombinations(String digits) {
List<String> res = new ArrayList<>();
if (digits.length() == 0 || digits == null)
return res;
StringBuffer sb = new StringBuffer();
backtrack(res, digits, sb);
return res;
}
public void backtrack(List<String> res, String digits, StringBuffer sb){
if (sb.length() == digits.length()){
res.add(sb.toString());
return;
}
String curStr = phone[digits.charAt(sb.length()) - '0'];
for (char c : curStr.toCharArray()){
sb.append(c);
backtrack(res, digits, sb);
sb.deleteCharAt(sb.length()-1);
}
}
}
题目79：给定一个二维网格和一个单词，找出该单词是否存在于网格中单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
思路
代码
class Solution {
public boolean exist(char[][] board, String word) {
if (word.length() == 0 || word == null)
return false;
boolean[][] visited = new boolean[board.length][board[0].length];
for (int i = 0; i < board.length; i++){
for (int j = 0; j < board[0].length; j++){
if (myExist(word, board, visited, i, j, 0)){
return true;
}
}
}
return false;
}
public boolean myExist(String word, char[][] board, boolean[][] visited, int curRow, int curColumn, int curIndex){
if (curIndex == word.length())
return true;
boolean flag = false;
if (curRow >= 0 && curRow < board.length && curColumn >= 0 && curColumn < board[0].length && !visited[curRow][curColumn] && board[curRow][curColumn] == word.charAt(curIndex)){
visited[curRow][curColumn] = true;
flag = myExist(word, board, visited, curRow + 1, curColumn, curIndex + 1) ||
myExist(word, board, visited, curRow - 1, curColumn, curIndex + 1) ||
myExist(word, board, visited, curRow, curColumn + 1, curIndex + 1) ||
myExist(word, board, visited, curRow, curColumn - 1, curIndex + 1);
visited[curRow][curColumn] = false;
}
return flag;
}
}
题目：给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。有效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成），整数之间用 '.' 分隔。
思路
代码
class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> res = new ArrayList<>();
StringBuffer sb = new StringBuffer();
divide(0, sb, res, s);
return res;
}
public void divide(int k, StringBuffer sb, List<String> res, String s){
if (k == 4 && s.length() == 0){
res.add(sb.toString());
return;
}
if (k < 4 && s.length() > (4 - k)*3 || k == 4 && s.length() != 0)
return;
for (int i = 0; i < s.length() && i <= 2; i++){
if (i != 0 && s.charAt(0) == '0') {
break;
}
String part = s.substring(0, i+1);
if (Integer.valueOf(part) <= 255){
if (sb.length() != 0)
part = "." + part;
sb.append(part);
divide(k + 1, sb, res, s.substring(i+1));
sb.delete(sb.length() - part.length(), sb.length());
}
}
}
}
题目： 给定一个二叉树，返回所有从根节点到叶子节点的路径。
思路
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new LinkedList<>();
StringBuffer sb = new StringBuffer();
DFS(sb, root, res);
return res;
}
public void DFS(StringBuffer sb, TreeNode root, List<String> res){
if (root == null)
return;
String part;
if (sb.length() == 0){
part = String.valueOf(root.val);
}else {
part = "->" + String.valueOf(root.val);
}
sb.append(part);
if (root.left == null && root.right == null){
res.add(sb.toString());
}else {
DFS(sb, root.left, res);
DFS(sb, root.right, res);
}
sb.delete(sb.length() - part.length(), sb.length());
}
}
