三周刷题记录，和同学们讨论，欢迎大家指正我的代码需要优化的地方

love1point

注册一亩三分地论坛，查看更多干货！

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

我三周后在职跳槽onsite，刚收的通知，好久没刷了，目标是一百题。

love1point

8) 409. Longest Palindrome

I tried to use HashMap, but cannot work for all test cases.
Any one can debug it?

import java.util.*;
public class Solution {
public int longestPalindrome(String s) {
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
int result = 0;
for(int i= 0; i < s.length(); i++)
{
if(map.get(s.charAt(i)) == null)
{
map.put(s.charAt(i), 1);
}
else
{
map.put(s.charAt(i), map.get(s.charAt(i)) + 1);
}
}
Collection<Integer> valuesSet = map.values();
Iterator<Integer> iter = valuesSet.iterator();
HashSet<Integer> hs = new HashSet<Integer>();
ArrayList<Integer> array = new ArrayList<Integer>();
while(iter.hasNext())
{
array.add(iter.next());
}
for(int i = 0; i < array.size(); i++)
{
if(array.get(i) % 2 == 0)
{
result += array.get(i);
}
}
for(int i = 0; i < array.size(); i++)
{
if(array.get(i) % 2 != 0)
{
return result + array.get(i);
}
}
return result;
}
}

复制代码

I refer others solution only use HashSet.
Working version:

public class Solution {
public int longestPalindrome(String s) {
HashSet<Character> hs = new HashSet<Character>();
int counter = 0;
for(int i = 0; i < s.length(); i++)
{
if(!hs.contains(s.charAt(i)))
{
hs.add(s.charAt(i));
}
else
{
hs.remove(s.charAt(i));
counter++;
}
}
if(hs.size() != 0)
{
return 2 * counter + 1;
}
else
{
return 2 * counter;
}
}
}

复制代码

love1point

13) 515. Find Largest Element in Each Row

BFS

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int[] findValueMostElement(TreeNode root) {
if(root == null)
{
return new int[0];
}
ArrayList<Integer> list = new ArrayList<Integer>();
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while(queue.size() > 0)
{
int max = Integer.MIN_VALUE;
int size = queue.size();
for(int i = 0; i < size; i++)
{
TreeNode node = queue.poll();
max = Math.max(node.val, max);
if(node.left != null)
{
queue.offer(node.left);
}
if(node.right != null)
{
queue.offer(node.right);
}
}
list.add(max);
}
int[] result = new int[list.size()];
for(int i = 0; i < list.size(); i++)
{
result[i] = list.get(i);
}
return result;
}
}

复制代码

love1point

14) Boomerangs

I did not think of using HashMap. Refer others solution. I think this one is tricky.

This one should not be easy level.

public class Solution {
public int numberOfBoomerangs(int[][] points) {
int result = 0;
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i = 0; i < points.length; i++)
{
for(int j = 0; j < points.length; j++)
{
if( i == j)
{
continue;
}
int d = getDistance(points[i], points[j]);
if(map.get(d) != null)
{
map.put(d, map.get(d) + 1);
}
else
{
map.put(d, 1);
}
}
for(Integer value : map.values())
{
result += value * (value-1);
}
map.clear();
}
return result;
}
private int getDistance(int[] a, int[] b)
{
int dx = a[0] - b[0];
int dy = a[1] - b[1];
return dx*dx + dy*dy;
}
}

复制代码

love1point

1 ) 461. Hamming Distance

This problem I stuck is how to transfer int to bits string. I do not think this question will test us any algorithm. Just use build-in method, not very fun. I referred other's solution.

How to transfer into same lengths of bit strings using Integer.toBinaryString()????????

public class Solution {
public int hammingDistance(int x, int y) {
return Integer.bitCount( x ^ y);
}
}

复制代码

love1point

2) 476. Number Complement

Mistake: I try to change string in-place. But string is immutable in java !!!!!
Get bit string of int first, then flip string. Then change to int using build-in method.
No fun again, MAKE AMERICA GREAT AGAIN!!!

public class Solution {
public int findComplement(int num) {
String s = Integer.toBinaryString(num);
String result = "";
for(int i = 0; i < s.length(); i++)
{
if(s.charAt(i) == '1')
{
result += '0';
}
else
{
result += '1';
}
}
return Integer.parseInt(result, 2);
}
}

复制代码

love1point

3) 412. Fizz Buzz

Easy enough.
just remember that how to transfer int to string

public class Solution {
public List<String> fizzBuzz(int n) {
List<String> result = new ArrayList<String>();
for(int i = 1; i <= n; i++)
{
if(i % 3 == 0 && i % 5 == 0)
{
result.add("FizzBuzz");
}
else if (i % 3 == 0)
{
result.add("Fizz");
}
else if(i % 5 == 0)
{
result.add("Buzz");
}
else
{
result.add(Integer.toString(i));
}
}
return result;
}
}

复制代码

love1point

4) 448. Find All Numbers Disappeared in an Array

I cannot figure out how to solve it without using extra space.

public class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> result = new ArrayList<Integer>();
HashSet<Integer> hs = new HashSet<Integer>();
for(Integer i : nums)
{
hs.add(i);
}
for(int i = 1; i <= nums.length; i++)
{
if(!hs.contains(i))
{
result.add(i);
}
}
return result;
}
}

复制代码

love1point

5） 455. Assign Cookies

Cannot find out how to do.
Refer other's solution. Using greedy algorithm.

public class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int result = 0;
for(int i = 0 ; i < s.length && result < g.length; i++)
{
if(s[i] >= g[result])
{
result++;
}
}
return result;
}
}

复制代码

love1point

6 ） 383. Ransom Note
Feb. 11, 2017

Just use hashmap to count how many char we have in magazine string, then traverse ransomNote to check if its char is in hashmap, if does, minus one. If we find its value is null or value is 0, just return false.

public class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
if(ransomNote == null && magazine == null)
{
return true;
}
if(magazine == null)
{
return false;
}
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
for(int i = 0; i < magazine.length(); i++)
{
if(map.get(magazine.charAt(i)) != null)
{
map.put(magazine.charAt(i), map.get(magazine.charAt(i)) + 1);
}
else
{
map.put(magazine.charAt(i), 1);
}
}
for(int j = 0; j < ransomNote.length(); j++)
{
if(map.get(ransomNote.charAt(j)) == Integer.valueOf(0) || map.get(ransomNote.charAt(j)) == null)
{
return false;
}
else
{
map.put(ransomNote.charAt(j), map.get(ransomNote.charAt(j)) - 1);
}
}
return true;
}
}

复制代码

love1point

7) 387. First Unique Character in a String

similar to 6.

public class Solution {
public int firstUniqChar(String s) {
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
for(int i = 0; i < s.length(); i++)
{
if(map.get(s.charAt(i)) == null)
{
map.put(s.charAt(i), 1);
}
else
{
map.put(s.charAt(i), map.get(s.charAt(i)) + 1);
}
}
for(int j = 0 ; j < s.length(); j++)
{
if(map.get(s.charAt(j)) == Integer.valueOf(1))
{
return j;
}
}
return -1;
}
}

复制代码

love1point

9） 401. Binary Watch

I just do not why this question is easy level. I do not know how to do it.
Refer others solution.

Why h * 64 + m?????????

public class Solution {
public List<String> readBinaryWatch(int num) {
List<String> result = new ArrayList<String>();
for(int h = 0; h < 12; h++)
{
for(int m = 0; m < 60; m++)
{
if(Integer.bitCount(h * 64 + m) == num)
{
result.add(String.format("%d:%02d", h, m));
}
}
}
return result;
}
}

复制代码

三周刷题记录，和同学们讨论，欢迎大家指正我的代码需要优化的地方

注册一亩三分地论坛，查看更多干货！

相关帖子