few things to not in the 3DS version:
1) Skulltula's will show up at a 1000 kills on ALL maps unless they have a prequisite (check warrior info on the battle start screen)
2) They only show up in the webbed area
3) Turn the sound up not music the sound they make noises you can use to home in on them
4) Yes every time you miss one you must replay
5) Drop everything and go for the skulltula they are there for a limited time.
ON heart pieces
Mostly they are keep rewards for specific characters this you can see on level select, sometimes they'll be under rocks it's kinda dependent on Legend Mode or Adventure Mode
On Battle advice
Work on one thing at a time don't try for both heart pieces and skulltula at the same time only one or the other, if you've a rough idea of where the skulltula will be clear the keeps nearby (if having difficulty some characters have built in keep clearers, such as link with his strong attack, or buy the keep badges in the market)
General advice in battle:
Try and obtain ALL the keeps and keep an eye on the captains or higher foes as they show up on the map as either larger red markers or red markers with a dark red dot on them, kill those first otherwise you'll find your keeps being taken from underneath you.
Faster you take keeps the more efficient at skulltula hunting you become, always try and take the keeps.
Make use of the ability of your character swapping or the ocarina, if in the map you've two enemy keeps on opposite side of the map send your second character over to one you go take the other, if they haven't taken the keep yet just swap to them and you can take that one just as easily, same principle applies to the ocarina, i generally leave keeps near the owl statues til last as they are easier to get to and take and plus if they spawn enemies you can get more kills ^^.
That does it for me
