preface

Recently, I reviewed the data structure and algorithm written by C, and found that my algorithm and data structure are really weak. Now I am rewriting it with Java to review it.

Can only say slowly accumulate ~ the following topic difficulty is simple, the algorithm of the big guy can directly ignore this article ~ entry or weak algorithm of the students can refer to ~

A lot of the little sorting algorithms (merging arrays, getting the sum of each digit) I didn’t write down, because once you know merge sort (merging arrays), bucket sort (getting the value of each digit), they’re not a problem. If you are not familiar with the eight basic ranking students can see :【 eight basic ranking summary 】

Because of the length problem, each article write 10 ~

If there is something wrong, or there is a better implementation, a more appropriate way to understand, I hope you don’t hesitate to leave a message in the comment section

Ten simple arithmetic problems

An overview of the subject

1. 1-nThe sum of factorial
2. Gets the smallest value for each column of a two-dimensional array
3. O 1!” + 4! 2 squared plus 9 factorial. (3 squared)+… The value of + n
4. The sum of the diagonal elements of an array
5. Print the Yang Hui triangle
6. Monkeys eat peaches
7. Count the words
8. Determine if the letters are exactly the same
9. Determine whether a number is raised to a power of 2
10. Determine if a number is an ugly number

1. Sum of 1-n factorial

What is the sum of 1 minus n factorial?

• The factorial of 1 is 11
• The factorial of 2 is 21 * 2
• The factorial of 3 is 31 * 2 * 3
• The factorial of 4 is 11 * 2 * 3 * 4
• .

Now we want to take the sum of these factorials. Ideas:

• The sum of 3 factorial is actually the sum of 2 factorial plus 3 factorial
• The sum of 4 factorial is actually the sum of 3 factorial plus 4 factorial
• .

    /** * 1-n factorial */
    public static void Factorial(int n) {

        / / the sum
        double sum = 0;

        // The factorial value is initialized to 1
        double factorial = 1;

        for (int i = 1; i <= n; i++) {

            factorial = factorial * i;


            sum = (int) (sum + factorial);

        }

        System.out.println("Public account: Java3y" + "" + sum);

    }
Copy the code

Get the minimum value for each column of the two-dimensional array

Gets the smallest value for each column of a two-dimensional array

Iterate over the column, then iterate over the row in the column

We typically operate on arrays from row to column. This time the minimum value for each column is required, so the rows need to be iterated through in the internal for loop

    /** * Find the minimum value of each column of the two-dimensional array */
    public static void minArray(a) {


        // A two-dimensional array
        int[][] arrays = {
            {23.106.8.234},
            {25.9.73.19},
            {56.25.67.137}};// Get the number of columns
        int maxColLength = arrays[0].length;



        // Use an array to load the smallest value for each column
        int[] minArray = new int[maxColLength];


        // Control column number
        for (int i = 0; i < maxColLength; i++) {

            // Assume that the first element of each column is the smallest
            int min = arrays[0][i];

            // Control the number of rows
            for (int j = 1; j < arrays.length; j++) {


                // Find the minimum value
                if(arrays[j][i] < min) { min = arrays[j][i]; }}// Assign to the array carrying the smallest value for each column
            minArray[i] = min;
        }


        System.out.println("Public account: Java3y" + "" + minArray);

    }


Copy the code

Three, seek “1! + 4! 2 squared plus 9 factorial. (3 squared)+… The value of + n

O 1!” + 4! 2 squared plus 9 factorial. The value of 3 squared

First square, then factorial, finally add can be ~

    /** * = 1; + 4! 2 squared plus 9 factorial. (3 squared)+... + n value * /
    public static void calculate(a) {

        double sum = 0;

        for (int i = 1; i <= 3; i++) {

            // Get the square number
            int square = i * i;

            // The factorial value starts at 1
            double factorial = 1;

            / / factorial
            for (int j = 1; j <= square; j++) {
                factorial = factorial * j;
            }

            sum = sum + factorial;

        }

        System.out.println("Public account: Java3y" + "" + sum);
        
    }
Copy the code

Sum of array diagonal elements

The sum of the diagonal elements of an array

Ideas:

• As long as the rows and columns are equal, they’re diagonal elements

    /** * array diagonal sum */
    public static void arraySum(a) {

        int[][] arrays = {
                {23.106.8.234},
                {25.9.73.19},
                {56.25.67.137},
                {33.22.11.44}};/ / and
        int sum = 0;

        for (int i = 0; i < arrays.length; i++) {

            for (int j = 0; j < arrays[i].length; j++) {

                if (i == j) {

                    sum = sum + arrays[i][j];

                }
            }
        }


        System.out.println("Public account: Java3y" + sum);
        
    }
Copy the code

Five, print Yang Hui triangle

Yang Hui triangle

Yang Hui triangle looks like this:

Ps: The pictures are from the Internet

Rule:

• The first and last of each row are all 1’s
  • Further calculation: the first column is all 1, the first row is all 1, when the number of columns equals the number of rows is 1
• The current value is equal to the value on the head plus the value on the left of the head
• The first row has one column, the second row has two columns, and the third row has three columns…….

Code implementation:

    /** * Print the yanghui triangle */
    public static void PascalTriangle(a) {


        // Print ten lines of Yang Hui triangles
        int[][] arrays = new int[10] [];/ / the number of rows
        for (int i = 0; i < arrays.length; i++) {


            // Initialize the size of the second layer
            arrays[i] = new int[i + 1];

            / / the number of columns
            for (int j = 0; j <= i; j++) {

                // is the first column, the first row, the number of rows is equal to the number of columns, so all of them are 1
                if (i == 0 || j == 0 || j == i) {
                    arrays[i][j] = 1;
                } else {

                    // The current value is equal to the value on the head + the value on the left of the head
                    arrays[i][j] = arrays[i - 1][j] + arrays[i - 1][j - 1];
                }

            }
        }

        System.out.println("Public account: Java3y" + "-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -");

        for (int[] array : arrays) {
            for (int value : array) {
                System.out.print(value + "\t");
            }
            System.out.println();

        }


        System.out.println("Public account: Java3y" + "-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -");


    }
Copy the code

Results:

Six, monkeys eat peaches

The monkey picked n peaches and ate more than one half that day. The next day, he also ate more than one half of the remaining peaches. On the tenth day, there were only one peach left. Q: How many peaches did the monkey pick on the first day

Ideas:

• Let’s say there are n peaches that day, and it’s one less than half of the peaches that there were the day before,f(n - 1) = f(n)/2 - 1.
• We can deduce the number of peaches on that day:f(n) = 2 * f(n - 1) + 2

Both recursion and loop can be used to solve:

Recursive mode:

    /** * Monkey eat peach problem *@paramX number of days * /
    public static int monkeyQue(int x) {

        if (x <= 0) {
            return 0;

        } else if (x == 1) {
            return 1;

        } else {
            return 2 * monkeyQue(x - 1) + 2; }}Copy the code

Circulation mode:

        int x = 1;
        for (int i = 1; i <= 9; i++) {
            x = (x + 1) * 2;
		}
Copy the code

Results:

Count the words

Enter a paragraph of characters and count the number of words in it. Separate the words with Spaces. A space represents a word

Ideas:

• The number of times a character is iterated from a space string to a non-space string is the number of words
• Define a flag variable, where 0 represents the space state and 1 represents the non-space state

    /** * enter a character and count the number of words **@paramSTR a text */
    public static int countWord(String str) {


        // 0 indicates the space state and 1 indicates the non-space state
        int flag = 0;

        // Number of words
        int num = 0;


        for (int i = 0; i < str.length(); i++) {

            if (String.valueOf(str.charAt(i)).equals("") ) {
                flag = 0;
            } else if (flag == 0) {
                num++;
                flag = 1; }}return num ;

    }

Copy the code

Results:

Eight, determine whether the letters are exactly the same

Given two strings s and t, determine whether the letters in the two strings are exactly the same.

Ideas:

• Iterate over the two strings, subtracting each character'a'Store them in an array and see if the two arrays are equal

Key points:

• 'c'-'a'=2To calculate the location of the storage, if there are more than one, +1.Let’s compare the array sizes later

Code implementation:

    /** * Given two strings s and t, determine whether the letters in the two strings are exactly the same */
    public static void isAnagram(a) {

        // Store the characters of the string separately
        char[] array1 = new char[26];
        char[] array2 = new char[26];


        String s1 = "pleasefollowthewechatpublicnumber";
        String s2 = "pleowcnumberthewechatpubliasefoll";


        for (int i = 0; i < s1.length(); i++) {
            char value = s1.charAt(i);

            // Figure out where to store it
            int index = value - 'a';

            array1[index]++;
        }

        for (int i = 0; i < s2.length(); i++) {
            char value = s2.charAt(i);

            // Figure out where to store it
            int index = value - 'a';

            array2[index]++;
        }

        for (int i = 0; i < 26; i++) {
            if(array1[i] ! = array2[i]) { System.out.println("Different");
                return;
            }
        }

        System.out.println("The same");

    }

Copy the code

Results:

9. Determine whether a number is raised to a power of 2

Determine whether a number is raised to a power of 2

Ideas:

• Divide 2 by the remainder until the remainder is not 0, and see if it equals 1 to determine whether it is 2 to some power

    /** * check if it is 2 to some power */
    public static void isPowerOfTwo(a) {

        int num = 3;

        if (num == 0) {
            System.out.println("Not");
        }

        while (num % 2= =0) {
            num = num / 2;
        }

        if (num == 1) {
            System.out.println("Yes");
        } else {
            System.out.println("Not"); }}Copy the code

Results:

There’s another way to solve this problem, which is bitwise operations:

• Two to the NTH power all have one feature, binary is one million
• If **2 to the NTH power of binary -1 and 2 to the NTH power of binary do the bitwise sum, then the result is definitely 0 **

	if(num <= 0){
        System.out.println("Not");
    }
    else if(num == 1){
        System.out.println("Yes");
    }
    else{
        if( (num & (num-1) ) == 0){
            System.out.println("Yes");
        }
        else{
            System.out.println("Not"); }}Copy the code

A number is ugly number

Determine if a number is an ugly number (2, 3, 5)

Ideas:

• If it’s made up of 2,3,5, then you keep dividing it by 2,3,5, and you get 1, so it’s made up purely of 2,3,5
  • It’s the same idea that we used to figure out if this number is 2 to the power of something ~

Code:

    /** * Determine if a number is a ugly number@param num
     */
    public static void isUgly(int num) {
        if (num <= 0) {
            System.out.println("Not");
        } else {
            while (num % 2= =0) {
                num = num / 2;
            }
            while (num % 3= =0) {
                num = num / 3;
            }
            while (num % 5= =0) {
                num = num / 5;
            }
            if (num == 1) {
                System.out.println("Yes");

            } else {
                System.out.println("Yes"); }}}Copy the code

Results:

conclusion

Yes, you read that right, simple small algorithm also want to sum up!

In fact, I think these simple algorithms have a “pattern”, if you know the pattern, you can easily figure it out, if you don’t know the pattern, you probably won’t do it.

After accumulating certain “routines”, we can infer from experience, figure out how to do the algorithm.

Here’s a very simple example:

• Multiplication is based on addition, so how do we learn multiplication? ** back (accumulated)** out of,9 * 9Who hasn’t memorized the multiplication table? Like to see2 + 2 + 2 + 2 + 2, will multiply (routine) later, who will slowly add. You see five twos, you get straight out2 * 5the

---

1. 1-nThe sum of factorial
   • We can take n factorial1 * 2 * 3 * 4 *... nIn fact, it is a circular process, the sum of the variable “sum” can be!
2. Get a two-dimensional arrayEach columnThe value of the minimum
   • The outer loop controls the number of columns and the inner loop controls the number of rows, which is how each column is iterated
3. O 1!” + 4! 2 squared plus 9 factorial. (3 squared)+… The value of + n
   • Square it, factorial it, and then sum
4. The sum of the diagonal elements of an array
   • Row and column positions are equal, that is, elements on the diagonal
5. Print the Yang Hui triangle
   • Find the rule of the Yang Hui triangle: the first row, the first column, and the column value equal to the row value of the above elements are 1, the rest are the value of the head plus the value of the left of the head
6. Monkeys eat peaches
   • According to the condition, we can calculate the peach of the previous day, and then deduce the peach of the day (rule). The monkeys were all in the same condition (one more half of the peach left), so you should think of a loop or recursion
7. Count the words
   • Take advantage of the rule that there will be a space between each word, use variables to remember this state (letter and space) transition, you can calculate the number of words!
8. Determine if the letters are exactly the same
   • Load each letter individually into an array,'c-a'isThe lettercinLocation of arrayThat is, 2. Since the number of occurrences of letters is not unique, weCompare the values of arrays(2 if it occurs twice, 3 if it occurs three times). As long as the values used to load both arrays match, the letters are the same!
9. Determine whether a number is raised to a power of 2
   • Best solution: a power of 2 in binary has a characteristic: the 10000 (0 n) — – > ps: programmers integer ~… So the binary less than this number has to be 01111, so let’s do both of them&Operation, then it must be 0. This property makes it very easy to tell if the number is raised to a power of 2
   • Subscheme: 2 to the power of a number that keeps shrinking (as long asnumber % 2 == 0I can zoom out, every timenumber / 2(Last of allThe quotient has to be 1.
10. Determine if a number is an ugly number
    • The prime factors are only 2, 3, and 5, so this is just an upgraded version of whether or not the number is 2 to some power. Keep narrowing this number (as long asnumber%2||%3||%5==0Every time,number / 2 | / 3 /5(Last of allThe quotient has to be 1.

If the article has the wrong place welcome to correct, everybody exchanges with each other. Students who are used to reading technical articles on wechat and want to get more Java resources can follow the wechat public account :Java3y