leetCode解题报告5道题(六) - c++编程基础

件：当剩余的字符串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;k
         
          1)&& !(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

leetCode解题报告5道题(六)(二)

ZigZag Conversion（挺恶心的，题目看懂就相当于做完了）

Set Matrix Zeroes