The single line solution using just substring, length and integer arithmetic is definitely more awesome, though.
If you can understand what I wrote, it's exactly the same, except he's representing the 1 with something that becomes 0 if the string's length is 0.
This is genuinely a clever way of solving the problem. I really want to know what your thought process is when solving problems like this.This is it. x * 2 / (x + 1) evaluates to 0 when x is 0, and 1 when x is any positive integer. This allows us to single out x == 0 as a special case without using a conditional. In this case I used it to add 1 to the indexes if x is 0 and then simplified the expression slightly. Which sometimes has the side effect of making it look more confusing.
This is genuinely a clever way of solving the problem. I really want to know what your thought process is when solving problems like this.
In this case, it might be an artificial constraint, but being able to avoid conditional statements is a very good skill to have in general. When you can do it without doing anything silly, your code is likely to be better for it in several ways: more robust, easier to analyze and test, etc. In some environments conditionals are poison for performance - GPU programming in particular.
public void rationaliseArray(Object[] array) {
for (int i = 0; array != null && i < (array.length - 1); i++) {
if (array[i] == null) {
array[i] = array[i + 1];
}
}
}Do you have to use an array? Using something from the Collections API - an ArrayList or similar - would make this trivial.
Here's a quick method to rationalise an array (ie. push all nulls to the end of the array)
Code:public void rationaliseArray(Object[] array) { for (int i = 0; array != null && i < (array.length - 1); i++) { if (array[i] == null) { array[i] = array[i + 1]; } } }
Scratch that - doesn't work.
private static void sortArray() {
PhoneRecord[] temp = new PhoneRecord[50];
for(int i = 0, j = 0; i < records.length; i++) {
if (records[i] != null) {
temp[j] = records[i];
j++;
}
}
for (int i = 0; i < records.length; i++) {
temp[i] = records[i];
}
}You are doing the right thing, but don't make a temp array because it's unnecessary.
Thank you. I'm starting to understand it much better. I'll start participate in this thread as much as I can.It just so happens I remember the thought process I went through.
1. First state the problem: the problem is that we need to treat 0 as a special case, but can't do so because we aren't allowed to use if (and I'm not going to use ternary if as a way round that).
2. First approach: if 0 is problematic, ensure that we never have a length 0 string - by adding a dummy character front and end, and removing them after the operation. Unfortunately this leaves us with the same problem in a different way - if we do this for a zero-length string we end up with a zero-length string which we then want to remove the first and last characters from - no good.
3. Right, so for any solution we need to be able to distinguish between zero and non-zero. The easiest way to do this using the constraints we have is to come up with an expression that evaluates to 0 for an input of 0 and 1 for any positive integer input.
4. x / x + 1 looks positive - 0 divided by anything will always be 0, and we divide by x + 1 to avoid the risk of dividing by zero. Unfortunately it doesn't work, because we always round down.
5. x / x + 1 gives us 1/2, 2/3 and other numbers tending towards (but never reaching) 1, which all get rounded down to 0. We want to round to 1. Doubling this value will always give us a range from 1 to not-quite-2, which is exactly what we want.
6. Looking at the errors we were getting before, we need to add 1 if text.length() is zero in one case and subtract it in the other case. So whip up a formula that maps 0 to +1 and 1 to 0, and add or subtract it accordingly.
7. Simplify the expression.
//pseudo-polynomial algorithm
public static bool balancePatition(int[] S)
{
var n = S.Length;
var N = S.Sum();
bool[,] P = new bool[N / 2 + 1, n + 1];
for (int i = 0; i < n + 1; i++)
P[0, i] = true;
for (int i = 1; i < N / 2 + 1; i++)
P[i, 0] = false;
for (int i = 1; i <= N / 2; i++)
for (int j = 1; j <= n; j++)
P[i, j] = S[j - 1] <= i ? P[i, j - 1] || P[i - S[j - 1], j - 1] : P[i, j - 1];
return P[N / 2, n];
}
int _tmain(int argc, _TCHAR* argv[])
{
int line, col;
for (line = 1; line < 11; line++)
{
for (col = 1; col <= line; col++)
printf_s( "*");
printf_s("\n");
}
printf_s(" ");
return 0;
}int size;
for(){ //repeat for the number of lines
for() //repeat for the number of spaces (Hint: the number of spaces is related to the number of the line)
for() //repeat for the '*'
//new line
}Just write code that prints the first line correctly.
**********
**********
**********
**********
**********
**********
**********
**********
**********
**********Some people here definitely are. If it's something simple, I might be able to help too. Just post the actual question.
int firstNull = -1;
for (int i = 0; i < array.length; i++) {
if (array[i] == null) {
if (firstNull == -1) {
firstNull = i;
}
} else if (firstNull != -1) {
array[firstNull++] = array[i];
array[i] = null;
}
}You are right, it can be folded into the same loop. I didn't stop to actually think about the code, just gave some drive-by advice.
for (int in=0, out=0; out < a.length; ++out) {
while (in < a.length && a[in] != null) ++in; // find next value to read
a[out] = in < a.length ? a[in] : null; // write it or null if no more values
}int out=0;
for (int in = 0; in < a.length; ++in)
if (a[in] != null) a[out++] = a[in];
while (out < a.length) a[out++] = null;Oh, I don't think we're arguing as such, and Water's doing better optimisation than me on this one.
I think my version is more clearly divided into meaningful parts, and makes it more explicit what the state is supposed to be at any point in the execution. In your code the execution jumps around; it took me a while before I was convinced that the code was correct.<shrug> I find your version a lot harder to understand - albeit somewhat more elegant. Suspect it's actually using more conditionals than mine, although they're better concealed.
I don't think I'm condensing the code in a way that reduces readability. (What I'd do differently in actual code would be to stick the comments on their own rows above the code they refer to, and to give the statement inside the while its own row and indent.) For instance, I rarely embed an increment operator inside an expression like you do; I think that's a recipe for trouble.I understand what you're getting at with your other approach now, by the way. To borrow your somewhat condensed style (which I don't like - give me whitespace and explicitly marked out blocks any day of the week):
...
Fewer conditionals, yes. Given how minor any difference in performance is likely to be between the three solutions, I'd go with whichever is clearest.
, and none of them's doing anything hideous performance-wise. A few assigns here, a few comparisons there, with the advantage going different ways for different arrays; you picks your algorithm and you takes your choice...I pointed towards the individual assignments/mutations in the code because having few of them, and those few ones being in a simple pattern, are what I generally strive for to make my code readable. Actual runtime counts of those operations were not the point.
void doublyLinkedList::addTail(Node *n)
{
if ((head == NULL) && (tail == NULL))
{
head = n;
tail = n;
n->prev = head;
n->next = tail;
}
else
{
tail->next = n;
n->prev = tail;
tail = n;
}
}void doublyLinkedList::addHead(Node *n)
{
if ((head == NULL) && (tail == NULL))
{
head = n;
tail = n;
n->prev = head;
n->next = tail;
}
else
{
head->prev = n;
n->next = head;
head = n;
}
}doublyLinkedList *dl = new doublyLinkedList();
Node *n1 = new Node(10);
dl->addTail(n1);
Node *n2 = new Node(20);
dl->addTail(n2);
dl->displayTail();
Node *n3 = new Node(30);
dl->addHead(n3);Node *n3 = new Node(30);
dl->addHead(n3);20
10
0
*popup screen
program.exe has stopped working*