LeetCode Online Judge-1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution.
Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1]. 

//Java Program: Two Sum

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] a = new int[2];
        for(int i=0;i<nums.length-1;i++)
        {
            for(int j=i+1;j<nums.length;j++)

            if (nums[i]+nums[j]==target)
            {
                a[0] = i;
                a[1] = j;
                return a;
            }
        }
        return a;
    }
}

//C Program: Two Sum

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target) {
    int i, j;
    int *a = (int *) malloc(2*sizeof(int));
    for(i=0;i<numsSize-1;i++)
    {
        for(j=i+1;j<numsSize;j++)
        {
            if (nums[i]+nums[j]==target)
            {
                a[0] = i;
                a[1] = j;
                return a;
            }
        }
    }
    return a;
}

//C++ Program: Two Sum

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        
        vector<int> result(2);
        
        for(int i=0;i<nums.size()-1;++i) {
            for(int j=i+1;j<nums.size();++j) {
                if (nums[i] + nums[j] == target) {
                    result[0] = i;
                    result[1] = j;
                    return result;
                }
            }
        }
        
    }
};

C Program: Maximum Subsequence Sum

Maximum Subsequence Sum

Given a sequence of $K$K integers { $N_1$​​, $N_2$​​, ..., $N_K$​​ }. A continuous subsequence is defined to be { $N_i$​​, $N_{i+1}$, ..., $N_j$​ } where $1 \le i \le j \le K$. The Maximum Subsequence is the continuous subsequence which has the largest sum of its elements. For example, given sequence { -2, 11, -4, 13, -5, -2 }, its maximum subsequence is { 11, -4, 13 } with the largest sum being 20.
Now you are supposed to find the largest sum, together with the first and the last numbers of the maximum subsequence.

Input Specification:

Each input file contains one test case. Each case occupies two lines. The first line contains a positive integer $K$ ($\le 10000$). The second line contains $K$ numbers, separated by a space.

Output Specification:

For each test case, output in one line the largest sum, together with the first and the last numbers of the maximum subsequence. The numbers must be separated by one space, but there must be no extra space at the end of a line. In case that the maximum subsequence is not unique, output the one with the smallest indices $i$ and $j$ (as shown by the sample case). If all the $K$ numbers are negative, then its maximum sum is defined to be 0, and you are supposed to output the first and the last numbers of the whole sequence.

Sample Input:

10
-10 1 2 3 4 -5 -23 3 7 -21

Sample Output:

10 1 4

I wrote a program like this:

//Maximum Subsequence Sum

#include <stdio.h>
int maxSum(int a[], int K, int &first);
int main(void)
{
 int K, i, first = 0, max, sum = 0;
 scanf("%d", &K);
 if (K>=1&&K<=100000)
 {
  int a[100000];
  for(i=0;i<K;i++)
   scanf("%d",&a[i]);
  max = maxSum(a, K, first);
  if (max>0)
  {
   for(i=first;sum!=max;i++)
    sum += a[i];
  }
  else if (a[first] == 0)
   ++i;
  else
   i = K;
  printf("%d %d %d\n",max,a[first],a[i-1]);
  return 0;
 }
}

int maxSum(int a[], int K, int &first)
{
 int i;
 int ThisSum = 0;
 int MaxSum = 0;
 for(i=K-1;i>=0;--i)
 {
  ThisSum += a[i];
  if (ThisSum>=MaxSum)
  {
   MaxSum = ThisSum;
   first = i;
  }
  else if (ThisSum<0)
  {
   ThisSum = 0;
  }
 }
 return MaxSum;
}

Acturally, I've tried to transform this C program into Java program with the same algorithm, but failed to pass the Online Judge, due to the poor time efficiency of Java compared to C language. Do you hava a good idea? Relative limits are following.

Time Limit: 200ms

Memory limit: 64MB

Code length restriction: 16kB

Expecting your better methods. 

Java Program: Word Length

The program is to read a line of text, which is divided into several words by spaces and ends with '.'. You should output the length of each word in this line of text. The words here have nothing to do with language, which include a variety of symbols. For example, "it's" is a word, whose length is 4. Note that there may be continuous spaces in the row.

 

Input format:

 

Enter a line of text ending with '.' in a row, but '.' can not be calculated in the last word length.

 

Output format:

 

Output the lengths of each word corresponding to this line of text in one line, every 2 length divided by a space. There are no spaces at the end of the line.

 

Input sample:

 

It's great to see you here.

 

Output sample:

4 5 2 3 3 4

Here is my program.

 //Word Length

import java.util.Scanner;

public class Main {
   
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        int count = 0, i;
        boolean isFirst = true;
        for (i=0;i<s.length()-1;)
        {
            while (s.charAt(i)==(' '))
                i++;
            while (s.charAt(i)!=('.')&&s.charAt(i++)!=(' '))
                count++;
            if (isFirst)
            {
                System.out.print(count);
                isFirst = false;
            }
            else
                System.out.print(" "+count);
            count = 0;
        }
    }
}

Java Program: Polynomial Addition

A polynomial can be expressed as the sum of every product， of the power of x and the coefficient. For example:

2x6+3x5+12x3+6x+20

Now, your program should read two polynomials, then output their sum, which is to add up corresponding coefficients and print the new polynomial.

The program is to deal with the power to a maximum of 100.

Input format:

Two polynomials are to be entered, the input format of each polynomial is as follows:

In each row two integers will be input, the first of which represents a power, the second represents the coefficient of this power, and all the coefficients are integers. The first row must be the highest power, the last row must be the 0 power.

Note that rows between the first and last row are not in accordance with the order of powers; if a power(not 0 power) coefficient is 0, this power will not appear in the input data; if 0 power coefficient is 0, it will appear in the input data.

Output format:

From the beginning of the highest power down to the 0 power, such as:

2x6+3x5+12x3-6x+20

Note that the x is a lowercase x, and there are no spaces between all of the symbols. If the coefficient of a power is 0, don't need to print it.

Sample input:

6 2
5 3
3 12
1 6
0 20
6 2
5 3
2 12
1 6
0 20

Sample output

 

4x6+6x5+12x3+12x2+12x+40

Can you write this program?Whether you  hava had a try, I had one.

//Polynomial Addition
import java.util.Scanner;

public class Main {
   
    public static void main(String[] args) {
        Scanner in = new Scanner (System.in);
        final int SIZE = 101;
        int[] m = new int[SIZE];
        int i, j;
        i=in.nextInt();
        j = i;
        while (i>0)
        {
            m[i]=in.nextInt();
            i=in.nextInt();
        }
        m[0] = in.nextInt();
        i=in.nextInt();
        if (j<i)
            j = i;
        while (i>0)
        {
            m[i] += in.nextInt();
            i=in.nextInt();
        }
        m[0] += in.nextInt();
        while (m[j]==0)
        {
            j--;
            if (j<0)
            {
                System.out.print(0);
                break;
            }
        }
        if (j==0)
            System.out.print(m[0]);
        else if (j==1)
        {
            if (m[j]!=-1&&m[j]!=1)
                System.out.print(m[j]);
            if (m[j]==-1)
                System.out.print("-");
            System.out.print("x");
        }
        else if (j>1)
        {
            if (m[j]!=-1&&m[j]!=1)
                System.out.print(m[j]);
            if (m[j]==-1)
                System.out.print("-");
            System.out.print("x"+j);
        }
        while (--j>=0)
        {
            while (j>=0&&m[j]==0)
                j--;
            if (j<0)
                break;
            if (m[j]>0)
                System.out.print("+");
            if (j>1)
            {
                if (m[j]!=-1&&m[j]!=1)
                    System.out.print(m[j]);
                if (m[j]==-1)
                    System.out.print("-");
                System.out.print("x"+j);
            }
               
            else if (j==1)
            {
                if (m[j]!=-1&&m[j]!=1)
                    System.out.print(m[j]);
                if (m[j]==-1)
                    System.out.print("-");
                System.out.print("x");
            }
            else
                System.out.print(m[j]);
        }   
    }
}

Java Program: Spelling An Integer In Chinese PinYin

The program is to input an integer, whose scope is [-100000, 100000], then, printing out every digit of this integer in Chinese PinYin.

For instance, if the input is 1234, then the output should be as following:

yi er san si

Note that there is a space between the Pinyin of every two digits, but there is no space behind the last digit. When encountering a negative number, add the "fu" at the beginning of the output. For example, -2341 should be output as:

fu er san si yi

Have you had a try?Here is my program.

//Spelling An Integer In Chinese PinYin
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int number = in.nextInt(), digit = 0;
        if (number>=-100000&&number<=100000)
        {
            if (number == 0)
                System.out.print("ling");
            else
            {
                if (number < 0)
                {
                    System.out.print("fu ");
                    number = -number;
                }
                int temp = number;
                while (temp > 0)
                {
                    temp = temp/10;
                    digit++;
                }
                do
                {
                    switch (number/(int)(Math.pow(10, digit-1)))
                    {
                    case 0: System.out.print("ling");
                            break;
                    case 1: System.out.print("yi");
                            break;
                    case 2: System.out.print("er");
                            break;
                    case 3: System.out.print("san");
                            break;
                    case 4: System.out.print("si");
                            break;
                    case 5: System.out.print("wu");
                            break;
                    case 6: System.out.print("liu");
                            break;
                    case 7: System.out.print("qi");
                            break;
                    case 8: System.out.print("ba");
                            break;
                    case 9: System.out.print("jiu");
                    }
                    if (digit > 1)
                        System.out.print(" ");
                    number -= number/(int)(Math.pow(10, digit-1))*(int)(Math.pow(10, digit-1));
                    digit--;
                } while (digit > 0);
            }
        }
    }
}

Java Program: Sum of Primes

We think that 2 is the first prime, 3 is the second prime, 5 is the third prime, and so on.

Now, two integers n and m are given, 0<n<=m<=200. The program is to calculate the sum of n-th to m-th primes, including the n-th and the m-th prime.

Pay attention that it is to calculate the sum of n-th to m-th primes, but not the primes between n and m.

The program is following.

//Sum of Primes
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), m = in.nextInt(), count = 0, number = 2, sum = 0;
        while (count < m)
        {
            boolean IsPrime = true;
            for (int i=2;i<number;i++)
            {
                if (number%i==0)
                {
                    IsPrime = false;
                    break;
                }
            }
            if (IsPrime)
            {
                count++;
                if (count>=n)
                    sum += number;
            }
            number++;
        }
        System.out.println(sum);
    }
}