程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> leetCode解題報告5道題(六)

leetCode解題報告5道題(六)

編輯：C++入門知識

題目一：

Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

分析：

這道題目的其實考察的就是指針問題而已，由於我是用java,就相當於兩個變量對應兩個下標，來移動這兩個下標就可以解決這個問題了。

我拿一個例子來說明這道題目吧：

如：字符串：wlrbbmqbhcdarzowkkyhiddqscdxrjmowfrxsjybldbefsarcbynecdyggxxpklorellnmpapqfwkhopkmco

思想：我們可以知道，按照順序下去，當下標pos指向 “4” （第二個字符b）時，我們知道，這樣子的話，前面的長度就被確定了，就是4了，下次，當我們要再算下一個不重復子串的長度的時候便只能從這個下標為4的字符開始算了。

根據這樣的簡要分析，我們要注意這道題目的陷阱

1、字符並不只是a-z的字母，有可能是其他的特殊字符或者阿拉伯數字等等，這樣子我們可以想到我們也許需要256個空間(ASCII碼總數)來存儲每個字符上一次出現的位置下標信息。我們記作 position[i], i 表示字符 c 的 ASCII編碼, position[i] 表示字符 c 上一次出現的位置下標。

2、我們需要一個下標變量來指向此次子串的開始位置，記做 start 變量，當下次 pos 指向的當前字符對應的值 position[i] 的位置在 start 變量的前面的話，那麼我們就忽略不考慮（因為我們這次計算子串是從start開始的，所以前面的出現重復的字符就不管了）

分析完了之後，我們就看下代碼裡面的解釋吧！

AC代碼：

package cn.xym.leetcode;

/**
 * @Description:  [計算不重復子串]
 * @Author:       [胖虎]   
 * @CreateDate:   [2014-4-26 下午7:19:25]
 * @CsdnUrl:      [http://blog.csdn.net/ljphhj]
 */
public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.equals("")){
            return 0;
        }
        int len = s.length();
        int[] position = new int[256];//256:對應ASCII碼總數
        int maxLength = 0;
        
        //子串開始位置默認為-1
        int start = -1;
        //初始化所有字符的位置下標都為-1
        for (int i=0; i<256; ++i){
        	position[i] = -1;
        }
        //遍歷字符串
        for (int pos=0; pos start){
                start = position[c];
            }
        	if (pos - start> maxLength){
                maxLength = pos - start;
            }
            position[c] = pos;
        }
        return maxLength;
    }
    public static void main(String[] args) {
		int result = new Solution().lengthOfLongestSubstring("wlrbbmqbhcdarzowkkyhiddqscdxrjmowfrxsjybldbefsarcbynecdyggxxpklorellnmpapqfwkhopkmco");
		System.out.println(result);
    }
}

題目二：

Rotate Image

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Follow up:
Could you do this in-place?

分析：題目要求我們把一個二維的矩陣在原數組上做順時針90度的旋轉。這道題目其實只需要在草稿紙上把圖一畫，不難發現，其實矩陣只需要通過一次對角線(“ \ ”) 的翻轉，然後再經過一次豎直線(" | ")的翻轉就可以得到我們最終想要的結果!

AC代碼：

public class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i=1; i



題目三：


Restore IP Addresses
 

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:

Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)
分析：做這道題目之前我們首先要明白一些基本概念。首先ipV4地址一共由4位組成，4位之前用"."隔開，每一位必須滿足是數字從0到255的范圍內。如果字符串任意組合之後，滿足了一共有4位，並且每一位都合法的話，那麼這個字符串便是滿足題意的字符串了。我們可以將它加入結果集。
解題思路：居然是做這種多種情況的，很明顯我們要用遞歸的方法來解決，而遞歸有個終止狀態，終止狀態我們很容易知道就是剩下要處理的字符串的長度為0了，這時候我們再判斷已經得到的字符串是否是合法的Ip即可。詳細的看代碼和注釋理解！



AC代碼：（436ms）
package cn.xym.leetcode;

import java.util.ArrayList;
import java.util.List;
/**
 * 
 * @Description:  [求合法的IP Address]
 * @Author:       [胖虎]   
 * @CreateDate:   [2014-4-28 下午1:56:22]
 * @CsdnUrl:      [http://blog.csdn.net/ljphhj]
 */
public class Solution {
	private ArrayList list = new ArrayList();
    public ArrayList restoreIpAddresses(String s) {
    	/*預處理，防止一些無謂的計算*/
        if (s == null)
            return list;
        int len = s.length();
        //此條件的字符串都不可能是合法的ip地址
        if (len == 0 || len < 4 || len > 12)
            return list;
        //遞歸
        solveIpAddress("", s);
        return list;
    }
    /**
     * 遞歸求解ipAddress
     * @param usedStr 當前已經生成的字符串
     * @param restStr 當前還剩余的字符串
     */
    public void solveIpAddress(String usedStr, String restStr){
    	/* 遞歸結束條件：當剩余的字符串restStr長度為0時,並且已經生成的字符串usedStr是合法的IP地址時，
    	 * 加入到結果集合list中。
    	 * */
        if (restStr.length() == 0 && isVaildIp(usedStr)){
        	list.add(usedStr);
        }else{
        	/* 剩余的字符串長度如果大於等於3，由於每一個位的Ip地址最多是0~~255,所以我們只需要循環3次
        	 * 但如果剩余的字符串長度len不大於3，我們只需要循環len次就可。
        	 * */
            int len = restStr.length() >= 3 ? 3 : restStr.length();
            
            for (int i=1; i<=len; ++i){
            	//判斷子串是否符合ip地址的每一位的要求
                if (isVaild(restStr.substring(0,i))){
                    String subUsedStr = "";
                    if (usedStr.equals("")){
                        subUsedStr = restStr.substring(0,i);
                    }else{
                        subUsedStr = usedStr + "." + restStr.substring(0,i);
                    }
                    String subRestStr = restStr.substring(i);
                    
                    solveIpAddress(subUsedStr,subRestStr);
                }
                
            }
        }
    }
    /**
     * 驗證字符串ip_bit是否滿足ip地址中一位的要求
     * @param ip_bit
     * @return
     */
    public boolean isVaild(String ip_bit){
    	if (ip_bit.charAt(0) == '0' && ip_bit.length() > 1){
    		return false;
    	}
        Integer ip_bit_number = Integer.parseInt(ip_bit);
        if (ip_bit_number >= 0 && ip_bit_number <= 255){
            return true;
        }else{
            return false;
        }
    }
    /**
     * 驗證ipAddress是否滿足一個合法Ip的要求
     * @param ipAddress
     * @return
     */
    public boolean isVaildIp(String ipAddress){
        int count = 0;
    	for (int i=0; i list = s.restoreIpAddresses("010010");
    	for (String str : list){
    		System.out.println(str);
    	}
	}
}







AC代碼：（網友提供，392ms）
public class Solution {
public ArrayList restoreIpAddresses(String s) {
    ArrayList result = new ArrayList();
    String tempIP = null;
    for (int i = 1;i=3){
            for (int j=i+1;j=2){
                    for (int k=j+1;k1)&&
                             !(n2.charAt(0) =='0'&& n2.length()>1)&&
                             !(n3.charAt(0) =='0'&& n3.length()>1)&&
                             !(n4.charAt(0) =='0'&& n4.length()>1)&&
                             Integer.parseInt(n1)<256&&Integer.parseInt(n2)<256&&
                             Integer.parseInt(n3)<256&&Integer.parseInt(n4)<256){
                                tempIP = n1+"."+n2+"."+n3+"."+n4;
                                result.add(tempIP);
                            }
                        }
                    }
                }
            }
        }
    }
    return result;
}
}




題目四：


ZigZag Conversion（挺惡心的，題目看懂就相當於做完了）
 

The string "PAYPALISHIRING" is written in a zigzag pattern on a given
 number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"



Write the code that will take a string and make this conversion given a number of rows:
string convert(string text, int nRows);
convert("PAYPALISHIRING",
 3) should return "PAHNAPLSIIGYIR".
分析：只是把字符串先按照" 反N " [即： | / |  ]的形狀“平鋪”，然後把之後得到的一行的字符串串起來就得到了最後的結果字符串。
需要注意的是，兩豎之間的“過度” " / " 那一列的行數為 nRows - 2; 而其他的列為nRows行
這樣講太難理解了，看圖解理解一下吧！
圖解：






仔細觀察這個題目的規律是解決這道題目的關鍵，比如它有幾個陷阱，一個是中間夾著的短邊" / " 的長度問題，另一個是方向問題，“ | ”的方向是從上往下，而“ / ” 的方向是從下往上的.



AC代碼：
package cn.xym.leetcode;
/**
 * 
 * @Description:  [ZigZag Conversion]
 * @Author:       [胖虎]   
 * @CreateDate:   [2014-4-28 下午11:52:27]
 * @CsdnUrl:      [http://blog.csdn.net/ljphhj]
 */
public class Solution {
    public String convert(String s, int nRows) {
        if (s == null || s.equals("") || nRows == 1){
            return s;
        }
        //定義行數nRows對應的字符串數組, arrays[0] 表示第一行對應的字符串
        String[] arrays = new String[nRows];
        for (int i=0; i



題目五：


Set Matrix Zeroes
 

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

click to show follow up.

Follow up:
Did you use extra space?

A straight forward solution using O(mn) space is probably a bad idea.（1）

A simple improvement uses O(m + n) space, but still not the best solution.（之後補上）

Could you devise a constant space solution?（之後補上）
分析：題意比較容易理解，但是它的條件我並沒完全滿足，但是可以AC,明天再看看哈！
AC代碼：（1）

public class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        boolean[][] flags = new boolean[m][n];
   
        for(int row=0; row