New answers tagged algorithm
0
If you tried logging what happens you would probably be able to figure it out :D
The good part is that it has nothing to do with your program, but it has to do with JS.
if (!myDict[target - ele]) {
total+= memoCombinationSum4(nums, target - ele, myDict)
}
If myDict = { 1: 0 }, then !myDict[1] is true. Welcome to the world of pain that is JS.
...
2
Length is a property of the array
static int KthElementInTwoArrays(int[] arr1,int arr1_length, int[] arr2, int arr2_length,int k){
It is unnecessary to pass the array lengths separately. In Java, the length is a property of the array. So arr1.length is the length of that array. You would only need a separate variable if you wanted to work with only ...
0
So C. Nivs gave a great review of your code, despite some minor flaws in the improvements. Take his advice at heart and you will be a great coder in no time. This review focuses more on how to properly implement Luhn's algorithm.
Reeinventing the wheel
While reinventing the wheel can be good sometimes, it is also important to look for existing resources ...
1
Style
Wrap your code in one or more clearly named functions. For example, print(primes_up_to(1000)), or is_prime(38)
Remove the print statements
Don't call your variables i, j, and k. Use descriptive names like possible_prime and test_divisor
Start your divisor test list at 2, instead of checking whether the divisor is 1 each loop.
Similarly, start your ...
3
You should not bake hand literal strings in your logic; instead refer to your constants or better yet an Enum
You should try to reduce the amount of class state floating around. index and current_hand for instance are not good class members; instead they should just be local variables.
Consider refactoring your Player class to be an iterator over its hands, ...
3
Your mainloop and Ai functions take a BOARD object by value, which will make a copy. You can pass those as const BOARD &board to avoid this. And since the board object already has the Cells data, you shouldn't need to pass that in as a separate parameter.
From your comment near the end, you're already aware you should use the random number facilities ...
3
It's good to see the improvements you've made to your code! There's still more that can be done better though, some of which I'll list below.
Use a consistent code style
The style of your code has lots of inconsistencies. Some of them are related to the use of spaces (especially around commas) and empty lines. A code formatting tool, like Artistic Style or ...
2
PEP 8
Is the code easy to read?
No, it violates the Style Guide for Python Code in a few areas.
Commas should be followed by a space. Eg, range(0,len(lst)) should be range(0, len(lst)), and range(i,0,-1) should be range(i, 0, -1).
For throw-away varables, you should use _. Since k is not used in the loop for k in range(len(lst)):, you should write for _ ...
0
Here's the realization with Z-function. It can be solved with prefix function as well.
https://pastebin.com/Uu07Ni5b
2
I am not a professional Python developer, so I will address only the performance issue: judging from you for loops structure, it seems that the running time of your implementation is \$\Theta(n^2)\$, where \$n\$ is the prime limit. However, you can do the same in \$O(n \log n)\$, or even, \$O(n \log \log n)\$ time. (See below.)
import math
import time
def ...
0
I just wanted to give my two cents about a very small optimization that everybody oversees.
You're developing a FastErathostenes, but you have the following code:
checkLimit(limit);
if (limit < 2) {
return new BitSet(limit);
}
if (limit == 2) {
BitSet bitSet = new BitSet(3);
...
0
One can split hairs over naming until the cows come home. And at the end of the day, someone will always disagree anyway. As long as it's not horrid, you're good. Your code will work and do the thing.
What's more important is the API that you present to your users.
In this case you have chosen to create an extensible class hierarchy. This is OK, but your ...
1
Remove print statements
Printing to the console takes a significant amount of time, and you are printing for every iteration and every element in the list. Run it once with the statements, and once without. It's a substantial time save.
Removing elements
For every iteration in the second loop, you check if 1 is there. When in reality, you just need to remove ...
4
Getting the First 2 Digits of a Number
A solution for this in constant space and time is already documented in this answer:
from math import log10
# go from this
num = int(str(nums)[:2])
# to this
def leading_digits(num):
return num // 10 ** (int(math.log10(num)) - 1)
And checking for a type of card lends itself to using a dictionary
Credit Card Types
...
2
This probably isn't a significant portion of the total time including sieving, but converting a bitset to an array / ArrayList of integers can be done more efficiently by searching for the next set bit with i = bitset.nextSetBit(i);, rather than querying every bit separately. (It returns -1 for not found.)
It may avoid branch mispredicts when the next set ...
2
Class naming
The names you used are fine IMO. You could prefix PrimeFinder with Abstract, but that's personal preference. Even Java's builtin classes aren't consistent with it (see Reader vs. AbstractSet<E>, both are abstract).
I've also seen the Base suffix (e.g. PrimeFinderBase), but not very often.
Method naming
findPrimesUpTo() could be shortened ...
5
Just a few stabs:
Why an abstract class? You could even have static method members in interfaces.
/* Finds all the primes no larger than {@code limit} and returns them in a * sorted list. I read BitSet findPrimesUpTo(int limit)
PrimeFinder.primeBitSetToList() - what is the relation to primes?
Why convert in the first place?
Why not to Set<>?
While ...
3
Avoid numeric inaccuracies
You can use the vector along the x axis calculated as ct, st to deduce the quadrant rather than use Math.PI / 2 or the approximation 1.5708
ct >= 0 for quads 1 & 4 and st >= 0 for quads 2 & 3
Reduce complexity
Rather than calculate the width {wct: w * ct, wst: w * st} and height {hct: h * ct, hst: h * st}vectors in ...
1
I think the way you're folding it to create newS is \$\mathcal{O}(n^2)\$. Try instead:
val newS = buildString {
append('#')
s.forEach { append(it).append('#') }
}
Also consider that most respondents are probably inputting \$\mathcal{O}(n)\$ solutions, so smaller optimizations that don't affect big O might make a big difference in your percentile. For ...
0
At least in the worst case you can get \$\mathcal{O}(n^2)\$. For some strings (like 'aaaaaaaaa') any substring is going to be symmetric. That's why symRadius function may take \$\mathcal{O}(n)\$. So in worst case symRadius is called with \$\mathcal{O}(n)\$ complexity for all \$n\$ chars (which should lead to \$\mathcal{O}(n^2)\$ in total).
2
print(check_loop([(0,0), (5,0), (5, 5)])) # False
print(check_loop([(0,0), (5,0), (5, 5), (0, 5), (0, 0)])) # True
print(check_loop([(0,0), (5,0), (5, 5), (4, 5)])) # False
print(check_loop([(0,0), (5,0), (5, 5), (4, 5), (4, 2)])) # False
print(check_loop([(0,0), (5,0), (5, 5), (4, 5), (4, -1)])) # True
print(check_loop([(0,0), (5,0), (5, 5), (4, 5), (4, 0)])...
0
There is a problem with the algorithm described - if the first and last segment are both horizontal or both vertical, they could overlap without meeting a line of opposite direction:
+---O <--+
| |
+---------+
You might be able to catch this by simply adding a zero-length segment to the end if the input has an odd number of segments.
0
One possible solution to handle duplicates without a big performance degrade is to randomly shuffle the input list before doing the sort. A specific algorithm to do so is a Fisher Yates Suffle.
1
There aren't many best practices on how to package classes, a rule of thumb is to package classes of a module/feature together in a way so that they aren't strongly coupled together. If you were to make a ...disjointset.impl and a ...disjointset.abstr pack for example, you'd couple them together strongly since you can't use the implementations without the ...
1
I'm not going to really talk much about the algorithm for the first part, and more about Python usage.
line_segment needs to be LineSegment by PEP8
__start_point should not be double-underscored, and should not be declared at the static level, so delete __start_point = (0, 0)
Add PEP484 type hints
Don't index [0] and [1] when you actually just mean .x and ....
1
Just a few quick shots...
Instead of having DateTime check15 which leads to the assumption there may be some more DateTime structs laying around like check1...check15 you could just juse currDate which by the way should be renamed to currentDate because abbreviations will make the code harder to read. By using currentDate you could replace (j * ...
1
Couldn't this class just have static methods and members? You wouldn't need to create an instance every time you want to DFS and you reset the internal sets/maps after each search anyways. I'm not sure about how you plan on using this class later on or if it still works if everything is static, so it might be fine as-is.
Also, consider renaming the class to ...
2
Your DCT computation can be made significantly more efficient, though for these small array sizes it doesn't matter a whole lot. I'll tackle this in the 2nd part of this answer. First I'll discuss some MATLAB syntax and style improvements.
OutputCollection{x, y, z} = {Output};
This puts Output into a 1x1 cell array, and assigns this cell array into the ...
2
serialize_tree is fine. deserialize_tree is \$O(n^2)\$ . In the case of balanced tree, it's still \$O(n\log{n})\$. To prove that to yourself, just add a counter inside deserialize_tree, or measure the runtime, vs input size.
But here's why:
First, you scan the serialized result to find the split between the left and the right tree. This takes linear time \$...
1
This approach will work, but be slow. You will be comparing something like N**2.5 lines in the worst case, which is quite bad. You should be running in something more like linear time.
The biggest problem I see here is that your problem is not well-defined, so first clarify your problem to yourself. What do you want to count as "duplicate text"? Do ...
-1
Some guess
The code you provide is missing important information that we must guess.
Being a programmer means being able to present the problem and the solution without ambiguity. Here is one important and some pedantic ambiguities listed.
What type are the items referenced by array?
We can assume they are int but depending on the compiler settings your ...
1
Unless we're told the array is a square array, we have a bug. I'm guessing that should be j < column_count (or whatever the appropriate global is called, since you haven't shown the declarations).
We have another bug where we update the largest_row before we have finished adding values from the row. It's possible that the rest of the elements are ...
0
Took me some time - but it had to do with how large the Integers were being handled. I refactored the code to instead count consecutive non-railway cells, rather count the number of cells which had a track in them (using the interval merge method). I further had to break it down row by row to handle the big intergers:
function gridlandMetro(n, m, k, track) {
...
Top 50 recent answers are included