6.6号刷题

第一题 149. Max Points on a Line

题目描述

平面上有n个点，找出共线的点的最大个数

算法

很容易想到O(n^3)的解法，通过起点i，终点j枚举直线，然后枚举中间点k，依次判断k与i,j是否共线，统计最大值。

代码还有问题，有一种test case过不了

public class Solution {
    public int maxPoints(Point[] points) {
        if (points.length <= 1) return points.length;

        HashMap<String, String> newmap = new HashMap<>();
        int max = 0;

        for (int i = 0; i < points.length; i++) {
            long ax = points[i].x, ay = points[i].y;
            String point = Integer.toString( (int) ax) + ":" + Integer.toString( (int) ay);
            for (int j = i + 1; j < points.length; j++) {
                long bx = points[j].x, by = points[j].y;
                int tempsum = 2;
                if (ax == bx && ay == by) {

                    if (newmap.containsKey(point)) {
                        String[] all = newmap.get(point).split(",");
                        String newindexes = "";
                        for (int z = 0; z < all.length - 1; z++) {
                            newindexes = newindexes + all[z] + ",";
                        }
                        
                        int num = Integer.parseInt(all[all.length - 1]);

                        if (newindexes.contains(Integer.toString(j))) {
                            max = Math.max(tempsum + num - 1, max);
                        } else {
                            max = Math.max(tempsum + num - 1, max);
                            newindexes = j + "," + newindexes;
                            num += 1;
                            newindexes += (num);
                            System.out.println(newindexes + " " + num);
                            newmap.put(point, newindexes);
                        }

                        continue;
                    } else {
                        max = Math.max(tempsum, max);
                        String indexes = i + "," + j + "," + 1;
                        newmap.put(point, indexes);
                        continue;
                    }
                }
                for (int k = j + 1; k < points.length; k++) {
                    long cx = points[k].x, cy = points[k].y;
                    long area = (ax - cx) * (by - cy) - (bx - cx) * (ay - cy);
                    if (area == 0) {
                        tempsum++;
                    }
                }

                if (newmap.containsKey(point)) {
                    String[] all = newmap.get(point).split(",");
                    int num = Integer.parseInt(all[all.length - 1]);
                    max =  Math.max(tempsum + num, max);
                }
                else max = Math.max(tempsum, max);
            }
        }
        return max;
    }
}

第二题 500. Keyboard Row

题目描述

给定一组单词，返回可以用美式键盘中的某一行字母键入的所有单词。

算法

利用String数组对每一行的字母进行存储，然后使用一个tag作为标示是否为连续的一行元素。

public class Solution {
    public String[] findWords(String[] words) {
        if (words.length <= 0) return new String[0];

        String first = "qwertyuiop";
        String second = "asdfghjkl";
        String third = "zxcvbnm";

        List<String> store = new ArrayList<>();

        for (String word : words) {
            int tag = 0;
            String lower = word.toLowerCase();

            for (int i = 0; i < word.length(); i++) {
                char al = lower.charAt(i);
                if (first.indexOf(al) >= 0 && (tag == 0 || tag == 1)) {
                    tag = 1;
                } else if (second.indexOf(al) >= 0 && (tag == 0 || tag == 2)) {
                    tag = 2;
                } else if (third.indexOf(al) >= 0 && (tag == 0 || tag == 3)) {
                    tag = 3;
                } else {
                    break;
                }
                if (i == word.length() - 1) store.add(word);
            }
        }
        String[] result = store.toArray(new String[store.size()]);
        return result;   
    }
}

学到的东西

List转Array可以用String[] result = store.toArray(new String[store.size()]);
然后Set用Array初始化，new HashSet(Arrays.asList(someArray));

第三题 575. Distribute Candies

题目描述

给定一组长度为偶数的整数，其中每个数字代表一个糖果的种类标号。

将糖果均分给哥哥和妹妹，返回妹妹可以得到的最大糖果种类数。

算法

public class Solution {
    public int distributeCandies(int[] candies) {
        if (candies.length < 2 || candies.length % 2 == 1) return 0;
        Set<Long> dif = new HashSet<>();
        for (int i = 0; i < candies.length; i++) {
            if (dif.size() >= candies.length / 2) return candies.length / 2;
            if (!dif.contains((long) candies[i])) dif.add((long) candies[i]);
        }
        
        return dif.size();
        
    }
}

第四题 359. Logger Rate Limiter

算法

用hashmap存数据

public class Logger359 {

    Map<String, Integer> store;
    public Logger359() {
        this.store = new HashMap<String, Integer>();
    }
    public boolean shouldPrintMessage(int timestamp, String message) {
        if (store.containsKey(message)) {
            int temp = store.get(message);
            if (timestamp - temp >= 10) {
                store.put(message, timestamp);
                return true;
            } else {
                return false;
            }

        } else {
            store.put(message, timestamp);
            return true;
        }

    }
}

第五题 463. Island Perimeter

题目描述

给定一个二维地图，1表示陆地，0表示水域。单元格水平或者竖直相连（不含对角线）。地图完全被水域环绕，只包含一个岛屿（也就是说，一个或者多个相连的陆地单元格）。岛屿没有湖泊（岛屿内部环绕的水域）。单元格是边长为1的正方形。地图是矩形，长宽不超过100。计算岛屿的周长。

算法

遍历一遍整个矩阵，查看有多少个岛。每个岛有4条边，如果存在相邻的陆地，那么需要减去2条边。最后计算出结果

public class Solution {
    public int islandPerimeter(int[][] grid) {
        int row = grid.length;
        if (row <= 0) return 0;
        int col = grid[0].length;

        int island = 0, neighbor = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == 1) {
                    island ++;
                    if (i < row - 1 && grid[i + 1][j] == 1) neighbor++;
                    if (j < col - 1 && grid[i][j + 1] == 1) neighbor++;
                    
                }
            }
        }
        return island * 4 - neighbor * 2;        
    }
}

第六题 266. Palindrome Permutation

算法

HashMap

利用hashmap存储出现过的数，并检查最后是奇数还是偶数

package Hash606;
import java.util.*;

/**
 * Created by xiaochen on 6/6/17.
 */
public class canPermutePalindrome266 {
    public boolean canPermutePalindrome(String s) {
        if (s.length() < 0) return false;

        int sumOdd = 0;
        Map<Character, Integer> store = new HashMap<>();

        for (char c : s.toCharArray()) {
            if (store.containsKey(c)) {
                int num = store.get(c);
                if (num % 2 == 0) sumOdd++;
                else sumOdd--;
                store.put(c, ++num);
            } else {
                sumOdd++;
                store.put(c, 1);
            }
        }
        return sumOdd <= 1;
    }
}

HashSet

方法相似

public class canPermutePalindrome266 {

    public boolean canPermutePalindrome2(String s) {
        Set<Character> store = new HashSet<>();

        for (char c : s.toCharArray()) {
            if (store.contains(c)) store.remove(c);
            else store.add(c);
        }
        return store.size() <= 1;
    }
}

第七题 609. Find Duplicate File in System

题目描述

给定一组文件信息，包含目录路径，以及目录下包含的文件。将所有内容重复的文件分组输出。

算法

算法比较简单，存储下所有相同的内容，最后查看，如果大于2的话就进行输出。

public class Solution {
    public List<List<String>> findDuplicate(String[] paths) {
        if (paths == null || paths.length <= 0) return new ArrayList<>();
        // Map <Content, List<path>>
        Map <String, List<String>> store = new HashMap<>();
        for (int i = 0; i < paths.length; i++) {
            String[] mixContent = paths[i].split("\\s+");
            String path = mixContent[0];
            for (int j = 1; j < mixContent.length; j++) {
                String[] file = mixContent[j].split("\\(");
                String fileName = file[0];
                String content = file[1].split("\\)")[0];
                List<String> tempList = store.getOrDefault(content, new ArrayList<>());
                StringBuilder wholePath = new StringBuilder(path);
                wholePath.append("/" + fileName);
                tempList.add(wholePath.toString());
                store.put(content, tempList);
            }
        }

        //Get all the path
        List<List<String>> result = new ArrayList<>();
        for (String key : store.keySet()) {
            List<String> temp = store.get(key);
            if (temp.size() >= 2) result.add(temp);
        }

        return result;       
    }
}