字符串&数组 2016-7-27

[dayang]

43 Multiply Strings 15 3Sum

[wolfogre]

43 Multiply Strings，超时，我得优化一下

public class Solution {

    public String multiply(String num1, String num2) {
        return mul(new StringBuilder(num1).reverse().toString(), new StringBuilder(num2).reverse().toString()).reverse().toString();
    }

    private StringBuilder mul(String a, String b)
    {
        StringBuilder result = new StringBuilder();
        for(int i = 0; i < a.length(); ++i)
            for (int j = 0; j < b.length(); ++j)
            {
                StringBuilder temp = make((a.charAt(i) - '0') * (b.charAt(j) - '0'), i + j);
                result = add(result, temp);
            }
        return result;
    }

    private StringBuilder make(Integer num, int zero_num)
    {
        StringBuilder result = new StringBuilder();
        while (zero_num-- > 0)
            result.append("0");
        result.append(new StringBuilder().append(num).reverse());
        return result;
    }

    private StringBuilder add(StringBuilder a, int a_zero_num, StringBuilder b, int b_zero_num,)
    {
        StringBuilder result = new StringBuilder();
        int carry = 0;
        for(int i = 0; i < a.length() || i < b.length() || carry != 0; ++i)
        {
            Integer sum = (i < a.length() ? (a.charAt(i) - '0') : 0) + (i < b.length() ? (b.charAt(i) - '0') : 0) + carry;
            carry = sum / 10;
            sum %= 10;
            result.append(sum);
        }
        while(result.length() > 1 && result.charAt(result.length() - 1) == '0'){
            result.deleteCharAt(result.length() - 1);
        }
        return result;
    }
}

[wolfogre]

43 Multiply Strings，AC，模拟了乘法运算器的原理。

public class Solution {

    public String multiply(String num1, String num2) {

        String number1 = new StringBuilder(num1).reverse().toString();
        String number2 = new StringBuilder(num2).reverse().toString();

        int [][] mat = new int[number1.length() * number2.length()][number1.length() + number2.length()];

        int index = 0;
        for(int i = 0; i < number1.length(); ++i)
            for(int j = 0; j < number2.length(); ++j){
                int temp = (number1.charAt(i) - '0') * (number2.charAt(j) - '0');
                mat[index][i + j] = temp % 10;
                mat[index][i + j + 1] = temp / 10;
                ++index;
            }
        StringBuilder result = new StringBuilder();
        int carry = 0;
        for(int j = 0; j < number1.length() + number2.length(); ++j){
            int temp = carry;
            for(int i = 0; i < number1.length() * number2.length(); ++i){
                temp += mat[i][j];
            }
            carry = temp / 10;
            temp = temp % 10;
            result.append(temp);
        }
        result = result.reverse();
        while(result.charAt(0) == '0' && result.length() > 1)
            result.deleteCharAt(0);
        return result.toString();
    }
}

[SnackMen]

/*
*[AC]15 3Sum
*排序之后查找
*/
public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
         List<List<Integer>> listList = new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        for(int i=0;i<nums.length-2;i++){
            if(i==0 || nums[i]!=nums[i-1]){
                int num=nums[i];
                int blow=i+1;
                int high=nums.length-1;
                while (blow<high) {
                    if (nums[blow] + num + nums[high] == 0) {
                        listList.add(Arrays.asList(num, nums[blow], nums[high]));
                        while(blow<high && nums[blow]==nums[blow+1]){
                            ++blow;
                        }
                        while(blow<high && nums[high]==nums[high-1]){
                            --high;
                        }
                        blow++;
                        high--;
                    }
                    else if (num + nums[blow] + nums[high] > 0)
                        --high;
                    else
                        ++blow;
                }
            }
        }
        return listList;
    }
}

[dayang]

/**
 * [AC] LeetCode 15 3Sum
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    if(nums.length <= 2)
      return [];
    let res = [];
    nums.sort();
    for(let i = 0; i < nums.length - 2; i++){
      if(i > 0 && nums[i] === nums[i-1])
        continue;
      for(let j = i + 1; j < nums.length - 1; j++){
         if(j > i + 1 && nums[j] === nums[j - 1])
          continue;
        for(let k = j + 1; k < nums.length; k++){
          if(k > j + 1 && nums[k] === nums[k - 1])
            continue;
          if(nums[k] + nums[i] + nums[j] === 0)
            res.push([nums[i],nums[j],nums[k]]);
        }
      }
    }
    return res;
};

[zhaokuohaha]

43 - C# - 高精度乘法

public class Solution
{
    public string Multiply(string num1, string num2)
    {
        int[] a = new int[num1.Length];
        int[] b = new int[num2.Length];
        int[] c = new int[a.Length+b.Length];
        for (int i = 0; i < a.Length; i++)
            a[i] = num1[a.Length  - i - 1] - '0';
        for (int i = 0; i < b.Length; i++)
            b[i] = num2[b.Length - i - 1] - '0';

        for(int i=0; i < a.Length; i++)
        {
            for(int j=0; j < b.Length; j++)
            {
                c[i + j] += a[i] * b[j];
            }
        }

        int len = c.Length-1;
        for(int i=0; i < len; i++)
        {
            if(c[i] > 9)
            {
                c[i + 1] += c[i] / 10;
                c[i] %= 10;
            }
        }

        while (c[len] == 0 && len > 0) len--;
        StringBuilder sb = new StringBuilder();
        for (int i = len; i >= 0; --i)
            sb.Append(c[i].ToString());
        return sb.ToString();
    }
}