preface
Friends who want to contact algorithms often ask, is algorithm difficult? I pinched the finger to calculate, answer generally have three kinds of result, difficult, not difficult, have a try. In fact, this problem is not good, we often come into contact with a course called mathematics, from primary school to university, and even work, we still do not let go, and this is familiar to you, do you think it is difficult? Many people always say that their IQ is not enough, but you don’t want to face it seriously. Let me put it this way. There is definitely a talent gap, but I can say that 80% of the people around you have the same IQ as you. Is there any reason not to finish this article and challenge yourself? Maybe you can find a better solution? Maybe you ran into one at your job interview? Isn’t it beautiful?
Some of the topics in this article are quite brain-burning, so save them to challenge or memorize them in your spare time. Your subconscious mind may have already completed them. Good Luck!
Algorithm problem
Now let’s play a few interesting algorithms together!
1 to n Number of occurrences of 1 in the integer
The title
Enter an integer n and find the number of occurrences of 1 in the decimal representation of n integers. For example, if you enter 12, 1, and 12, the digits that contain 1 are 1, 10, 11, and 12. 1 appears five times.
Analysis of the
Whenever you encounter a problem, you should calmly analyze it, rather than write code in a rush, even if the problem is simple. So somebody said, does one plus one need to think? Any fool knows that equals 2. I don’t want to break it to you, but sometimes it’s 3, good luck might be 4, bad luck might be 1, maybe even 0.
Many so-called truths are conditional, so we should analyze these conditions and get an optimal solution. The regression thesis, when we first see this topic, the first idea is to add a statistical variable, and then iterate through 1~n. We increase our statistical variable according to whether the mod of each number (greater than 10, we need to divide by 10) is equal to 1, and finally return our statistical variable. The idea is very clear, the code is very simple, as follows:
public static int numberOf1Between1AndN(int num) {
if (num < 1) {
return 0;
}
int count = 0;
for (int i = 1; i <= num; i++) {
count += numberOf1(i);
}
return count;
}
private static int numberOf1(int num) {
int count = 0;
while(num ! = 0) {if (num % 10 == 1) {
count++;
}
num /= 10;
}
return count;
}
Copy the codeIn the calculation of time complexity, there are two steps: first, there is an O(n) traversal, and then there is an O(LGN) division mod calculation for each integer, so its time complexity is O(N LGN). One thing to add here is that LGN (base 10) and log base 2n(base 2) can be considered indistinguishable when we analyze time complexity, because their ratio is a constant, so we call time complexity O(logn), ignore the base, and do the same thing in the following analysis. Can we think of a better way? At that time, I came up with a way to concatenate integers into a string, and then iterate over the string to determine the number of 1. I happily finished writing the code. When I looked at it carefully, I regretted that, it was too low to look at. But I posted the code anyway.
public static int numberOf1Between1AndN(int num) {
if (num < 1) {
return 0;
}
StringBuilder sb = new StringBuilder();
for (int i = 1; i <= num; i++) {
sb.append(i);
}
int count = 0;
for (int i = 0, n = sb.length(); i < n; i++) {
if (sb.charAt(i) == '1') { count++; }}return count;
}
Copy the codeA quick analysis of why low is, first of all, we don’t even need to mention it because we use StringBuilder for auxiliary space, and second of all, in the loop of num, StringBuilder appends an integer, and if you know anything about StringBuilder, The underlying array is nothing more than a char array. When initialized, a fixed size array is created. Copy is nothing more than an array traversal, its capacity growth is exponential, will inevitably waste memory. Ah, that’s a lesson in how not to do it. Shame.
On second thought, is there a better way? Can’t seem to figure it out. Take a look? Just read the book a few lines of analysis, I know how to solve, at least I was praised by the goddess is a mathematical prodigy, or very sensitive to numbers. The general idea is as follows: The core idea is to analyze the rule of occurrence of 1, for example, 1~520, let’s analyze, can be divided into 1~20 and 21~520, where 20 is exactly the result of removing the highest digit of 520, let’s analyze 21~520 first, among these numbers, which digit will appear 1? One’s place, ten’s place, hundred’s place? Civilization, civilization, civilization (manual funny). First of all, analyze the highest digit, the number with 1 is no more than 100~199, a total of 100, so here is a case where the highest digit is 1, such as 120, the number with 1 is 100~120, a total of 20+1. This is a little bit easier to understand, but now it’s a little bit harder, because we just analyzed the highest place, which is the hundreds place. So then we have the tens place, and we can divide it into these segments, 21 to 120,121 to 220,221 to 320,321 to 420,421 to 520. Do you see any patterns? No? Dude, did you get cheated by your teammates? Calm down. If the tens place of each segment is fixed at 1, can the ones place have 0 to 9? Similarly, if the ones place is fixed at 1, the tens place can also have 0 to 9 situations. So the answer is pretty obvious, 5 times 2 times 10, that’s 5 pieces (5), we can fix the tens place and the ones place (2), fix the one place, we only have one place left and there are 10 possibilities from 0 to 9 (10). We come to the simple deduction, 5 is the highest number, 2 can be understood as out after the highest remaining digits, here we go out to a one hundred – bit, then only ten bits, and 10 is under the condition of fixed one is 1, the remaining few is 10 times the power go out (highest), 10 ^ 1 is here, if is 1314, one thousand to 1, So is there between 0 and 9 cases of the tens place and the ones place, which is 10 squared. So that gives us our formula, which is the highest digit times the number of digits left after we subtract the highest digit times the number of digits left of 10 given that one digit is 1. What’s the problem with formulas? Pull out the code every minute.
public static int numberOf1Between1AndN(int num) {
if (num < 1) {
return0; } int len = numberOfLen(num); // Get the digitsif (len == 1) {
return1; } int pow = (int) math.pow (10, len-1); Int maxDigit = num/pow; Int maxDigitCount = maxDigit == 1? num % pow + 1 : pow; Int otherDigitCount = maxDigit * (len-1) * (pow / 10); int otherDigitCount = maxDigit * (len-1) * (pow / 10); // Count the remaining bits as 1return maxDigitCount + otherDigitCount + numberOf1Between1AndN(num % pow);
}
private static int numberOfLen(int num) {
int len = 0;
while(num ! = 0) { len++; num /= 10; }return len;
}
Copy the codeCareful friends found that we used recursion, more careful friends found that we only analyze 21~520, the rest is 520%100? That’s not the point, the point is why it’s more efficient, first of all, we’re recursing, but the number of recursions is the number of bits we have in n, which we know from numberOfLen is O logn, and then every time we recurse, numberOfLen is another O logn, If someone who knows a lot about low-level Math points out a problem to Math.pow, don’t you think this is a multiplication of several identical numbers? Because computers aren’t that smart. The implementation of POW in Java is based on the recursion of even and odd judgment. If you are interested, you can go to see it. The time complexity is O(logn), where n is the highest bit -1, and in our analysis, it can be understood as seeking digits, so it is O(logn). Obviously this thing is less than order logn, so the time in the method is order logn, and the total time in the algorithm is order logn times logn, which is order logn. If you can’t read the math, go back to the math.
The number of n dice
The title
If you throw n dice on the ground, the sum of all the dice that face up is s. Enter n and print out the probabilities for all possible values of S.
Analysis of the
First of all, we need to define a few fixed points, n dice are rolled, so the sum has at least n (for all 1s), and at most 6n (for all sixes), and the total number of permutations is 6 to the n (for those of you who don’t know, check probability). So these are all deterministic, and what we’re trying to figure out is the probability of the sum of each of these heads, and one way to do that is we’re going to create an array of 6n minus n plus 1, which is exactly how many times that happens, and then we’re going to go through the array and we’re going to get 6 to the n. So how do you store it? N might be too abstract, but try a concrete constant, like 2 dice and print the probability of all the values. What do you do? Would you write code like this?
private static final int MAX_VALUE = 6;
public static void printProbabilityOf2() { int number = 2; int maxSum = number * MAX_VALUE; int[] pProbabilities = new int[maxSum - number + 1]; // initialize, 0 times before statistics startfor (int i = number; i <= maxSum; i++) {
pProbabilities[i - number] = 0;
}
int total = (int) Math.pow(MAX_VALUE, number);
for (int i = 1; i <= MAX_VALUE; i++) {
for(int j = 1; j <= MAX_VALUE; j++) { pProbabilities[i + j - number]++; }}for (int i = number; i <= maxSum; i++) {
System.out.println(String.format(Locale.getDefault(), "The value of s is %d and the probability is %d/%d=%.4f", I, pProbabilities[i-number], total, pProbabilities[i-number] * 1.0f/total)); }}Copy the codeIf you can write code like this, you’re on the right track, but you don’t have the recursion idea, and I don’t have the recursion idea myself, so I have to hand over my knees, and the recursion method didn’t occur to me at first, so I had to come up with the second method, which is a loop.
Getting back to the subject, if you had 2 dice, you had 2 cycles. If you had 3 dice, would you have 3 cycles? Four fours? Five five floors? I don’t know if n is n. You should think about recursion when you have an indeterminate number of loops like this and it’s nested. There are two common solutions, either circular or recursive (easy to say, but damn hard to imagine). The implementation of recursion requires a decision statement to continue recursion or to terminate recursion. How about this? I’m going to start with the first die, and I’m going to say that the current die is the last one, so we’re going to write down the data, otherwise I’m going to throw one die until it’s the last one. Just do it. Give me the code.
private static final int MAX_VALUE = 6;
public static void printProbability(int number) {
if (number < 1) {
return; } int maxSum = number * MAX_VALUE; 6n int[] pProbabilities = new int[maxsum-number + 1]; // Stores every possible array // initializes 0 times before starting countingfor(int i = number; i <= maxSum; i++) { pProbabilities[i - number] = 0; } int total = (int) Math.pow(MAX_VALUE, number); // 6^n probability(number, pProbabilities); // Count the number of occurrences of each case from n to 6n and store it in pProbabilitiesfor (int i = number; i <= maxSum; i++) {
System.out.println(String.format(Locale.getDefault(), "The value of s is %d and the probability is %d/%d=%.4f", I, pProbabilities[i-number], total, pProbabilities[i-number] * 1.0f/total)); } } public static void probability(int number, int[] pProbabilities) {for(int i = 1; i <= MAX_VALUE; I ++) {// From the first die, probability(number, 1, I, pProbabilities); }} /** * recurse each path continuously until all dice are thrown ** @param Original Total number of dice * @param current Current number of dice thrown * @param sum each path calculation and * @param pProbabilities array */ public static void probability(int original, int current, int sum, int[] pProbabilities) {if (current == original) {
pProbabilities[sum - original]++;
} else {
for(int i = 1; i <= MAX_VALUE; i++) { probability(original, current + 1, sum + i, pProbabilities); }}}Copy the codeWe found that we only changed the nesting part of the loop in the middle of the two dice, using recursion. Let’s review the statistical code for 2 dice:
pProbabilities[i + j - number]++;
Copy the codeI +j is just the sum of each of these cases, and we’re going to use sum for each of these routes, so it’s pretty easy to understand that. However, recursion has significant disadvantages. Recursion consumes time and space because it is called by the method itself: Each method call allocates space in the stack to hold parameters, return addresses, and temporary variables, takes time to push and pop data onto the stack, and many calculations in recursion can be repeated, which can have a significant negative impact on performance. In fact, MY heart is broken, you write out (personally think recursion itself is a great idea, but the computer does not help). Anyway, the first time I did this problem, I didn’t think of recursion, I thought of a loop, and without further ado, LET’s just analyze how a loop works.
Now, before WE do this, let’s just say that my current die is my KTH roll and I have a sum of n, and I’ll call it f of k,n. So the question is, how many times can I roll a 1 on the k-1 die, if I roll a 1 on the K-1 die, then I get f(k-1,n-1) on the K-1 die, f(k-1,n-2), F (k-1,n-3), F (k-1,n-4), F (k-1,n-5), F (n – k – 1, 6). So each of these are the paths from the K minus 1 flip to the k flip, so is that going to add up to f of k,n? Let’s simple validation (known f (1, 1) = f (1, 2) = f (1, 3) = f (1, 4) = f (1, 5) = f (1, 6) = 1, this needless to say), for example, we want to f (2, 4), According to the formula for f (2, 4) = f (1, 3) + f (1, 2) + f (1, 1) + f (1, 0) + f (1, 1) + f (1, 2), not ah, zha might f (1, 0), or at least have to o f (1, 1). Nothing wrong. You can throw zeros? We get a constraint that n-z must be greater than or equal to k-1, where 1<=z<=6 and k>=2. So the final result is f(2,4)=f(1,3)+f(1,2)+f(1,1)=1+1+1=3. The sum of two numbers is four, so there are three possibilities ((2,2), (1,3), (3,1)), which seems to be true, but what about a longer one? F (2, 7) = f (1, 6) + f (1, 5) + f (1, 4) + f (1, 3) + f (1, 2) + f (1, 1) = 6, 6 it? (1,6), (6,1), (2,5), (5,2), (3,4), (4,3)). It doesn’t have to be verified at all, it’s the famous idea of dynamic programming. Interested can learn, because of recent contact more, I suddenly want to come out, if put in peacetime, may want to a few minutes (manual funny).
So with that in mind, how do we program? The problem here is that we need the result of the previous calculation to calculate this result. The first thing that comes to mind about storage is arrays, where the size of an array is simply points and a maximum of +1. Because its subscript is the current count and its value is how many times it happened. So how do you switch? From the perspective of analysis, we need at least two arrays, each time after calculation to swap, there is an elegant way to implement, using a two-dimensional array, one dimension is the flag bit, take flag=0, use 1-flag to achieve elegant switching. The difficulty is also about the analysis, here the code, the code is adapted from the book, MY own implementation is not so, but the idea is the same.
private static final int MAX_VALUE = 6;
public static void printProbability(int number) {
if (number < 1) {
return;
}
int[][] pProbabilities = new int[2][MAX_VALUE * number + 1];
for(int i = 0; i < MAX_VALUE * number + 1; I ++) {// Initialize the array pProbabilities[0][I] = 0; pProbabilities[1][i] = 0; } int flag = 0;for(int i = 1; i <= MAX_VALUE; I ++) {// When the die is rolled for the first time, there are 6 possibilities, each of which occurs once pProbabilities[flag][I] = 1; } // Roll the dice from the second timefor (int k = 2; k <= number; k++) {
for(int i = 0; i < k; I ++) {pProbabilities[1-flag][I] = 0; }for(int i = k; i <= MAX_VALUE * k; I ++) {// roll the dice for the KTH time, and the minimum is k and the maximum is MAX_VALUE*k pProbabilities[1-flag][I] = 0; / / resetfor(int j = 1; j <= i && j <= MAX_VALUE; J++) {/ / execution f (k, n) = f (k - 1, n - 1) + f (n - k - 1, 2) + f (n - k - 1, 3) + f (n - k - 1, 4) + f (n - k - 1, 5) + f (n - k - 1, 6) pProbabilities [1 - flag] [I] + = pProbabilities[flag][i - j]; } } flag = 1 - flag; } int total = (int) math.pow (MAX_VALUE, number);for (int i = number; i <= MAX_VALUE * number; i++) {
System.out.println(String.format(Locale.getDefault(), "The value of s is %d and the probability is %d/%d=%.4f", I, pProbabilities[flag][I], total, pProbabilities[flag][I] * 1.0f/total)); }}Copy the codeQuestion almost to this end, in fact, there is a small detail in the code ha, that is the accuracy of the problem, careful partners must see it, but also scolded me! I want to say, this print result, I looked at it myself, want to be concise, you can change the accuracy as needed.
The last remaining number in the circle
The title
0, 1, ···, n-1 The n digits are arranged in a circle, starting with the number 0, and each time the MTH digit is deleted from the circle. Find the last number left in the circle.
Yes, it’s the famous Joseph question and it’s accompanied by a romantic story, which I won’t say in case it’s deemed too much…
Analysis of the
This problem is actually very simple ha, the title has said very detailed, keep turning around, report m is out, some students may go to tangle ring things ha, there is no need ha, as long as the order of out is right, let a person look like a ring on the line, god, I can not say too much… On the code:
/** * @param totalNum */ public static void yueSeFu(int totalNum) List<Integer> start = new ArrayList<Integer>();for(int i = 0; i < totalNum; i++) { start.add(i); } int k = 0; int size;while((size = start.size()) > 0) { k = k + m; // index position k = k % size-1;ifSystem.out.println(start.get(size-1)); start.remove(size - 1); k = 0; // Delete the last one and start again}else{ System.out.println(start.get(k)); start.remove(k); }}}Copy the codeIf it was so simple, would it be necessary to post it? But isn’t the above code O(n) time? At first glance, it looks real. Is it? You also need to read more books. Not to mention that, it also uses an auxiliary set of length N. Of course, you could not say that, but is there a better way? Excelsior.
Let’s calm down and analyze, if the original sequence is 0,1, k minus 1, k plus 1, n minus 1, where k is the first person to go out, obviously k=(m minus 1)%n. Let’s look at this mapping again:
k+1 -> 0
k+2 -> 1
...
n-1 -> n-k-2
0 -> n-k-1
1 -> n-k
...
k-1 -> n-2
Copy the codeIs there a math guru who can figure out this relationship? Well, does that need a math guru? Obviously f of x is equal to x minus k minus 1 percent n. I checked a few in my heart, and it seems to be true. What about the inverse mapping? G (x) = (x + k + 1) % n. Good for you, my brother. Those who disagree can use authoritative mathematical verification. Now let’s assume that a function f(n) is the last number left over from the sequence 0 to n-1, so clearly f(n-1) is the last number left over from the sequence 0 to n-2. So according to the mapping relation we obtained above, the numbers left by F (n-1) must be equal to the numbers left by F (n), but they belong to different functions exactly, one is for 0~n-1, the other is for 0~n-2, but according to the above inverse mapping, we can deduce the original numbers for 0~n-1.
Let’s take a look at the top mapping again, is the right-hand side a sequence from 0 to n minus 2? Student: Is the left-hand side for the sequence from 0 to n minus 1, minus k? So does f of n have to be in the left-hand sequence? So f of n minus 1, if I plug in g of x is equal to x plus k plus 1 percent n, is equal to f of n? Well, finally conclude formula f (n) = [f (n – 1) + k + 1) % n, we have known k = (m – 1) % n, continue to plug in, the final solution to f (n) = [f (n – 1) + m] % n. Where n minus 1 has to be greater than 0, so n is greater than 1, so can a person play the game? Who said no? What do you say? So isn’t n equal to 1 going to be 0? With the formula, the code is simple:
Public static void yueSeFu(int totalNum, int m) {public static void yueSeFu(int totalNum, int m) {if (totalNum < 1 || m < 1) {
throw new RuntimeException("At least one person can play this game!");
}
int last = 0;
for (int i = 2; i <= totalNum; i++) {
last = (last + m) % i;
}
System.out.println("The last one out is:" + last);
}
Copy the codeThe topic after SaoHua
What do you think about these three problems? Do you find algorithms particularly interesting? But I feel like most of you are already in the upper right corner. Adhere to the small partner here, I admire you very much, very appreciate you, I see your skeleton fine and strange, is a martial arts wizard, oh, no, is a rare logical algorithm genius, here leave you two questions (in Java language).
- 1+2+··· ·+n, do not use multiplication and division, for, while, if, else, switch, case and other keywords and conditional statement (A? B, C).
- Write a method to find the sum of two integers. Do not use +, -, *, / inside the method.
The topic is very boring but very interesting, the first question, I will come up with a kind, is recursive + abnormal, the second way said that do not look at the answer really can not come out, IQ has overdue, ah, we can consider and, or, not, different or. Of course, those who have read The “Sword Finger Offer” must be familiar with these questions, including the top three questions, because they are all from this book, but a lot of analysis mixed with my own ideas, I use my own ideas to express this idea, if there is something wrong, you must point out.
Finally, thanks to those who have supported me all the time!
portal
Github：github.com/crazysunj/
Blog: crazysunj.com/