前言
Leetcode算法題分類練習(xí)，記錄解題思路和代碼溉躲。
雙指針
題目1： 判斷一個(gè)非負(fù)整數(shù)是否為兩個(gè)整數(shù)的平方和关筒。
思路
看成0-target開平方之間尋找兩個(gè)數(shù)，使得兩個(gè)數(shù)的平方和等于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：反轉(zhuǎn)字符串中的元音字符
思路
代碼
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： 可以刪除一個(gè)字符，判斷是否能構(gòu)成回文字符串歇由。
思路
利用兩個(gè)指針卵牍，left指向頭，right指向位沦泌，left和right的指向的位置如果相同則各自向內(nèi)移動(dòng)一位糊昙，不同則可以分為兩種情況，刪除left指向的位置或刪除right指向的位置谢谦。然后繼續(xù)比較释牺。
代碼
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 中的一些字符，使得它構(gòu)成字符串列表 d 中的一個(gè)字符串回挽，找出能構(gòu)成的最長字符串没咙。如果有多個(gè)相同長度的結(jié)果，返回字典序的最小字符串千劈。
思路
利用雙指針判斷是否是子字符串镜撩。
代碼
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();
}
快速選擇
荷蘭國旗問題
題目：有三種顏色的球，算法的目標(biāo)是將這三種球按顏色順序正確地排列。
思路
三向切分快速排序的一種變種袁梗，在三向切分快速排序中宜鸯，每次切分都將數(shù)組分成三個(gè)區(qū)間：小于切分元素、等于切分元素遮怜、大于切分元素淋袖，而該算法是將數(shù)組分成三個(gè)區(qū)間：等于紅色、等于白色锯梁、等于藍(lán)色即碗。
代碼
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;
}
}
桶排序
題目：返回?cái)?shù)組中出現(xiàn)頻率最高的K的數(shù)， Given [1,1,1,2,2,3] and k = 2, return [1,2].
思路
假設(shè)有若干個(gè)桶陌凳，桶下標(biāo)表示數(shù)出現(xiàn)的頻率剥懒，即低第i個(gè)桶中存放著出現(xiàn)頻率為i的數(shù)。
代碼
public class BucketSorting {
public List<Integer> topKFrequent(int[] nums, int k) {
// 統(tǒng)計(jì)每個(gè)數(shù)出現(xiàn)的次數(shù)
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);
}
}
// 依據(jù)數(shù)出現(xiàn)的次數(shù)將數(shù)放到對應(yīng)的桶中
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);
}
// 從后往前合敦，統(tǒng)計(jì)出現(xiàn)次數(shù)最多的k個(gè)數(shù)
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;
}
}
貪心思想
題目： 每個(gè)孩子都有一個(gè)滿足度 grid初橘，每個(gè)餅干都有一個(gè)大小 size，只有餅干的大小大于等于一個(gè)孩子的滿足度充岛，該孩子才會(huì)獲得滿足保檐。求解最多可以獲得滿足的孩子數(shù)量。
思路
代碼
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;
}
}
題目： 計(jì)算讓一組區(qū)間不重疊所需要移除的區(qū)間個(gè)數(shù)崔梗。 Input: [ [1,2], [1,2], [1,2] ] Output: 2 夜只； Input: [ [1,2], [2,3] ] Output: 0
思路
按照期間的結(jié)尾進(jìn)行升序排序， 選擇的區(qū)間結(jié)尾越小蒜魄，留給后面的區(qū)間的空間越大扔亥，那么后面能夠選擇的區(qū)間個(gè)數(shù)也就越大。
代碼
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;
}
}
題目： 氣球在一個(gè)水平數(shù)軸上擺放谈为，可以重疊砸王，飛鏢垂直投向坐標(biāo)軸，使得路徑上的氣球都被刺破峦阁。求解最小的投飛鏢次數(shù)使所有氣球都被刺破。
思路
也是計(jì)算不重疊的區(qū)間個(gè)數(shù)耘成，不過和 上一題的區(qū)別在于榔昔，[1, 2] 和 [2, 3] 在本題中算是重疊區(qū)間。
代碼
題目： 一個(gè)學(xué)生用兩個(gè)分量 (h, k) 描述瘪菌，h 表示身高撒会，k 表示排在前面的有 k 個(gè)學(xué)生的身高比他高或者和他一樣高。
思路
每個(gè)位置的 k 的值师妙，等于在這個(gè)位置之前 h 比它大的位置的數(shù)量诵肛。如果要向一個(gè)隊(duì)列中插入一個(gè)人，要判斷的就是插入的位置默穴。那么如果可以確定怔檩，當(dāng)前隊(duì)列中的所有人的 h 值都比待插入的這個(gè)人的 h 值大褪秀，那么這個(gè)人的 k 值就是他應(yīng)該插入的位置。（通過身高降序）并且可以確定薛训，如果插入的是一個(gè) h 值小于當(dāng)前隊(duì)列中所有人的 h 值的人媒吗，那么無論他的位置在哪，都不會(huì)影響當(dāng)前隊(duì)列中所有人的 k 值乙埃，即不會(huì)破壞當(dāng)前隊(duì)列的正確性闸英。（相同升高，則按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()][]);
}
}
題目： 題目描述：一次股票交易包含買入和賣出介袜，只進(jìn)行一次交易甫何，求最大收益。
思路
代碼
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 數(shù)組中 1 表示已經(jīng)種下了花朵遇伞≌尬梗花朵之間至少需要一個(gè)單位的間隔，求解是否能種下 n 朵花赃额。
思路
用兩個(gè)指針pre和next加派，分別指向當(dāng)前位置的前后下標(biāo)，當(dāng)當(dāng)前位置為0和前后位置同時(shí)為0時(shí)才可以在當(dāng)前位置種花跳芳。
代碼
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;
}
}
題目： 判斷一個(gè)數(shù)組是否能只修改一個(gè)數(shù)就成為非遞減數(shù)組芍锦。
思路
代碼
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;
}
}
題目：子數(shù)組最大的和
思路
代碼
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;
}
}
題目：分隔字符串使同種字符出現(xiàn)在一起
思路
先用一個(gè)數(shù)組記錄所有字符在字符串中最后出現(xiàn)過的位置，然后遍歷字符串飞盆，假如第一個(gè)字符a最后出現(xiàn)的位置為9娄琉，則當(dāng)前分區(qū)為0-9，如果9之前的字符最后出現(xiàn)的位置都沒超過9的話這分區(qū)為一組吓歇，如果9之前有字符最后出現(xiàn)過的位置（10）超過9的話孽水，則重置分區(qū)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';
}
}
二分查找
題目： 一個(gè)數(shù) 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;
}
}
題目： 給定一個(gè)有序的字符數(shù)組 letters 和一個(gè)字符 target炼鞠，要求找出 letters 中大于 target 的最小字符，如果找不到就返回第 1 個(gè)字符轰胁。
思路
代碼
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){
}
}
--> 題目： 一個(gè)有序數(shù)組只有一個(gè)數(shù)不出現(xiàn)兩次谒主，找出這個(gè)數(shù)。
思路
代碼
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];
}
}
題目：旋轉(zhuǎn)數(shù)組的最小數(shù)字
思路
代碼
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];
}
}
題目：給定一個(gè)有序數(shù)組 nums 和一個(gè)目標(biāo) target赃阀，要求找到 target 在 nums 中的第一個(gè)位置和最后一個(gè)位置霎肯。
思路
代碼
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;
}
}
分治
題目：給定一個(gè)含有數(shù)字和運(yùn)算符的字符串，為表達(dá)式添加括號(hào)，改變其運(yùn)算優(yōu)先級(jí)以求出不同的結(jié)果观游。你需要給出所有可能的組合的結(jié)果搂捧。有效的運(yùn)算符號(hào)包含 +, - 以及 * 。
思路
代碼
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;
}
}
題目： 給定一個(gè)整數(shù) n备典，生成所有由 1 ... n 為節(jié)點(diǎ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表示可以經(jīng)過某個(gè)位置，求解從左上角到右下角的最短路徑長度提佣。
思路
代碼
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;
}
}
題目： 給定正整數(shù) n吮蛹，找到若干個(gè)完全平方數(shù)（比如 1, 4, 9, 16, ...）使得它們的和等于 n。你需要讓組成和的完全平方數(shù)的個(gè)數(shù)最少拌屏。
思路
代碼
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 的平方數(shù)序列
* @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;
}
}
題目：給定兩個(gè)單詞（beginWord 和 endWord）和一個(gè)字典潮针，找到從 beginWord 到 endWord 的最短轉(zhuǎn)換序列的長度。轉(zhuǎn)換需遵循如下規(guī)則：（1）每次轉(zhuǎn)換只能改變一個(gè)字母倚喂。（2）轉(zhuǎn)換過程中的中間單詞必須是字典中的單詞
思路
代碼
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
題目：給定一個(gè)包含了一些 0 和 1 的非空二維數(shù)組 grid 每篷。一個(gè) 島嶼 是由一些相鄰的 1 (代表土地) 構(gòu)成的組合，這里的「相鄰」要求兩個(gè) 1 必須在水平或者豎直方向上相鄰端圈。你可以假設(shè) grid 的四個(gè)邊緣都被 0（代表水）包圍著焦读。找到給定的二維數(shù)組中最大的島嶼面積。(如果沒有島嶼舱权，則返回面積為 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;
}
題目：給定一個(gè)二維的矩陣，包含 'X' 和 'O'（字母 O）宴倍。找到所有被 'X' 圍繞的區(qū)域张症，并將這些區(qū)域里所有的 'O' 用 'X' 填充。
思路
先把與外圍相連的‘O’標(biāo)記為‘T’鸵贬，然后剩下的就是被包圍的‘O‘俗他，遍歷整個(gè)二維數(shù)組，將’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
}
題目：給定一個(gè) m x n 的非負(fù)整數(shù)矩陣來表示一片大陸上各個(gè)單元格的高度阔逼≌仔疲“太平洋”處于大陸的左邊界和上邊界，而“大西洋”處于大陸的右邊界和下邊界嗜浮。規(guī)定水流只能按照上羡亩、下、左周伦、右四個(gè)方向流動(dòng)，且只能從高到低或者在同等高度上流動(dòng)未荒。請找出那些水流既可以流動(dòng)到“太平洋”专挪，又能流動(dòng)到“大西洋”的陸地單元的坐標(biāo)。
思路
代碼
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：給定一個(gè)僅包含數(shù)字 2-9 的字符串，返回所有它能表示的字母組合寨腔。給出數(shù)字到字母的映射如下（與電話按鍵相同）速侈。注意 1 不對應(yīng)任何字母。
思路
代碼
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：給定一個(gè)二維網(wǎng)格和一個(gè)單詞迫卢，找出該單詞是否存在于網(wǎng)格中單詞必須按照字母順序倚搬，通過相鄰的單元格內(nèi)的字母構(gòu)成，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格乾蛤。同一個(gè)單元格內(nèi)的字母不允許被重復(fù)使用每界。
思路
代碼
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;
}
}
題目：給定一個(gè)只包含數(shù)字的字符串，復(fù)原它并返回所有可能的 IP 地址格式家卖。有效的 IP 地址正好由四個(gè)整數(shù)（每個(gè)整數(shù)位于 0 到 255 之間組成）眨层，整數(shù)之間用 '.' 分隔。
思路
代碼
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());
}
}
}
}
題目： 給定一個(gè)二叉樹上荡，返回所有從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑趴樱。
思路
代碼
/**
* 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());
}
}
