Array and Strings easy系列题

  1. Remove Duplicates from Sorted Array(首先想到放到set里面;然后想到自己写的需要判断是否重复,重复了几个;后面想到由于是有序的,判断发生了几次前后不同即可->解决)
  2. Best Time to Buy and Sell Stock II(首先想到了贪心的方法,即累加所有差值->解决)
  3. Rotate Array(首先想到循环K次,每次循环一个,把尾巴暂存,其他书集体后移一位;答案的方法用了三次数组逆排序,数组逆排序的代码要会背->解决)
  4. Contains Duplicate(首先想到排序后判断前后是否相同,但是这就没啥意义了;然后想到用map或者set的性质,不过这也是偷懒;看到一种解决方法是用桶,求出最大最小值后建立桶数组,然后再遍历数组,要是重复了,桶的false会变成true,虽然时间控制在常数内,但是空间复杂度太高->解决)
  5. Single Number(首先想到了上一题,只是个不同的问法;但是考虑到只有一个出现了1次,其他都是两次,感觉会有简单方法;问题是那句不用任何的额外空间,我想不到什么点子;答案的一个方法非常有意思,由于无法用额外的空间,所以让数组前后不断的异或,由于出现两次的数异或之后会被消除,所以只剩下了那个出现了一次的数->解决)
  6. Intersection of Two Arrays II(取两个数组的交集,无序的版本自己没有任何想法;参考答案的解法是先把数组进行排序,然后用两个指针while循环进行比较->解决;另外一种答案的解法是用hashmap存储比较,感觉不舒服的解法)
  7. Plus One(关于进位的基本题;考验进位标志位和边界9的处理;虽然基本但是值得注意)
  8. Move Zeroes(把0移到最后,同时保持非0部分有序;想到的第一种自然的解法是,遇到0暂存,后面全部前移一位,0放到最后;偷懒一点先排序,然后把0移到最后;答案的方法是建立一个新的索引,不等于0的时候才向前进,然后直接在原数组上覆盖,由于原数组有0的存在,指针移动位置总是大于等于新的索引指针的->解决)
  9. Two Sum(老朋友了;首先想到的就是hashmap存储,存数找target-nums[i]->解决)
  10. Valid Sudoku(9*9数独,行列9宫格都不能重复;自己一开始想到这题要干嘛;答案其实就是两个for循环内,用除法取余等方式一起把三个判断调节一起解决了,基本的数据类型是set->解决)
  11. Rotate Image(旋转矩阵,看上去挺可怕的;首先想到的是按行变列,但是题目要求in-order,不能新增一个矩阵来操作;然后我想到swap()函数,但是没有多想;答案的解决方法也是建立在swap之上的,先将对角线进行互换,然后将每一行进行reverse,可见swap,reverse这些都是基本的数组字符串操作)
  12. Reverse String(反转数组真的是好基本啊;由于string的不可变性质,所以得先换成char数组,改完后强行改回来->解决)
  13. Reverse Integer(首先想到的是需要考虑负数和0的特殊情况;答案用除法和取余的方式巧妙的解决了,但还是要注意int的上下限问题->解决)
  14. First Unique Character in a String(返回第一个非重复字符的index,首先想到了数组里面XOR的骚操作;然后想到了用map来记录出现的次数,然后遍历map找到第一个值为1的键即可;答案的方式思想和map一样,只不过实现更加的高效,使用char[26]的小型字典来统计出现次数然后遍历找到值为1的,其时间复杂度为O(n)
  15. Valid Anagram(首先想到的利用上一题的小型字典,第一次加,第二次减,第三次找0)
  16. Valid Palindrome(判断字符串对称,首先想到去掉干扰因素比如空格和标点符号,然后首尾指针移动判断,同时考虑奇偶数;实际解决思想一样,不过是用半个fori循环,直接比较首尾,还剩去了奇偶数的考虑->解决)
  17. String to Integer (atoi)(TODO)
  18. Implement strStr()(字符串匹配,相当的经典了;TODO;再多考虑一下当needle为空的时候如何)
  19. Count and Say(首先会让人觉得有点难,然后想一下就是判断最大连续字符个数同时还要指出是哪一个字符的问题;TODO)
  20. Longest Common Prefix(最长公共序列,又是一道经典题;TODO)

    Array and Strings middle系列题

    3Sum

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    
    public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < nums.length - 2; i++) {
            if (i == 0 || (i >= 1 && nums[i] != nums[i - 1])) {
                int lo = i + 1, hi = nums.length - 1, sum = 0 - nums[i];
                while (lo < hi) {
                    if (nums[lo] + nums[hi] == sum) {
                        res.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
                        while (lo < hi && nums[lo] == nums[lo + 1]) {
                            lo++;
                        }
                        while (lo < hi && nums[hi] == nums[hi - 1]) {
                            hi--;
                        }
                        lo++;
                        hi--;
                    } else if (nums[lo] + nums[hi] < sum) {
                        lo++;
                    } else {
                        hi--;
                    }
                }
            }
        }
        return res;
    }
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {-1,0,1,2,-1,-4};
        System.out.println(solution.threeSum(nums));
    }
    }

    首先看到3sum,的确想到了2sum。也想到了挨个把0-nums[i]当做target套用2sum的做法,但是总是没有具体成型的思路,大概看了下答案其实就懂了,关键是先做了排序,然后之后的2sum找值就是简化版的了(双指针移动),同时在一些地方做一下剪枝就大功告成了。

    Set Matrix Zeroes

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    
    public class Solution {
    public void setZeroes(int[][] matrix) {
        if (matrix.length == 0) {
            return;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        boolean fcol = false;
        boolean frow = false;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    if (i == 0) frow = true;
                    if (j == 0) fcol = true;
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        if (frow) {
            for (int i = 0; i < n; i++) {
                matrix[0][i] = 0;
            }
        }
    
        if (fcol) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
    }
    }

    基本的矩阵操作到是熟练的,但是这道题为了效率还是做了不少改进的,比如我在第一次做的时候感觉需要额外的数组来记录哪些行或列需要变零,但是解法巧妙的使用了第一行和第一列作为记录,然后在第二次循环中,以此为判断进行第二次变零,同时考虑到第一行或第一列自己本身也要变零的可能性,还特意设置了标志位进行补充(这边的标志位自己做的时候搞错了)。

    Group Anagrams

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    
    class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        int[] dict = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103};
        List<List<String>> res = new ArrayList<>();
        Map<Integer, Integer> map = new HashMap<>();
        for (String str : strs) {
            int k = 1;
            for (char c : str.toCharArray()) {
                k *= dict[c - 'a'];
            }
            List<String> t;
            /*
             * 判断指纹是不是第一次出现以及出现的层数,用map来记录
             * */
            if (map.containsKey(k)) {
                t = res.get(map.get(k));//获取层数
            } else {
                t = new ArrayList<>();//新建新的template
                res.add(t);//添加进res里
                map.put(k, res.size() - 1);//在map中加入指纹
            }
            t.add(str);//在确定的层数插入字符
        }
        return res;
    }
    }

    这题思路还比较清晰的,首先是要确定字符的指纹(即字母出现过即值相同,首先想到了微型字典的想法,但是数组之间比较效率不高,后面用了素数法,其实可以再深入考虑下hash的原理),确定了指纹之后需要判断是不是第一次出现,如果不是的话需要在第几层插入该数字。这就需要用一个map来记录指纹和指纹所在的层数了,接下去的代码就好写了,这道题告诉我需要在编程钱确定好该考虑的问题和思路。

    Longest Substring Without Repeating Characters

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    
    class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length() == 0) {
            return 0;
        }
        int max = 0;
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0, j = 0; i < s.length(); i++) {
            if (map.containsKey(s.charAt(i))) {
                j = Math.max(j, map.get(s.charAt(i)) + 1);
            }
            map.put(s.charAt(i), i);
            max = Math.max(max, i - j + 1);
        }
        return max;
    }
    }

    虽然题目不难,但还是没有自己一口气写出来,自己本来是想用微型字典代替map来记录字符状态的,也不是不行,可以再尝试一次,map的方法的话还是好理解的,i,j两个指针进行滑动,i总是滑动,j的话遇到已经出现过的,就向后滑动。

    Longest Palindromic Substring

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    
    public class Solution {
    public boolean increasingTriplet(int[] nums) {
        int min = Integer.MAX_VALUE;
        int secondMin = Integer.MAX_VALUE;
        for (int num : nums) {
            if (num <= min) {
                min = num;
            } else if (num <= secondMin) {
                secondMin = num;
            } else {
                return true;
            }
        }
        return false;
    }
    }

    这道题我以为是最长上升子序列的特殊情况题(当然,最长上升子序列太经典了),但是由于其指定了只要三个(往往三个就可以大大简化问题,想起之前那个0,1,2的移位排序了嘛),所以换种角度想,只要找到一个数比两个数大就行了,原理就是不断的维护已遍历的最小值和第二小值,然后找到一个数比他们大即可。

    Array and Strings hard系列题(不做了,反正到时候也不一定做出来)

    Product of Array Except Self Spiral Matrix 4Sum II Container With Most Water Game of Life First Missing Positive Longest Consecutive Sequence Find the Duplicate Number Longest Substring with At Most K Distinct Characters Basic Calculator II Sliding Window Maximum Minimum Window Substring