Leetcode之旅

作者: VincentJianshu | 来源:发表于2018-05-30 23:19 被阅读0次

20180530 又开始刷Leetcode，但愿能够坚持

两数之和
两数之和，典型用空间换时间的问题，用HashMap可以有效减少时间复杂度。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] re = new int[2];
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++)
            if (!map.containsKey(nums[i]))
                map.put(target - nums[i], i);
            else {
                re[0] = map.get(nums[i]);
                re[1] = i;
                break;
            }
        return re;
    }
}

两数相加
链表练习题，最后忘了判断是否有进位，wa了一次。

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode p1 = l1;
        ListNode p2 = l2;
        ListNode re = new ListNode(0), head = re;
        int flag = 0, temp = 0;
        while (p1 != null && p2 != null) {
            temp = p1.val + p2.val + flag;
            flag = temp / 10;
            re.next = new ListNode(temp - flag * 10);
            p1 = p1.next;
            p2 = p2.next;
            re = re.next;
        }
        while (p1 != null) {
            temp = p1.val + flag;
            flag = temp / 10;
            re.next = new ListNode(temp - flag * 10);
            p1 = p1.next;
            re = re.next;
        }
        while (p2 != null) {
            temp = p2.val + flag;
            flag = temp / 10;
            re.next = new ListNode(temp - flag * 10);
            p2 = p2.next;
            re = re.next;
        }
        if (flag == 1)
            re.next = new ListNode(1);
        return head.next;
    }
}

无重复字符的最长子串 [推荐]
一开始想用HashMap节省时间，坑了自己好久，应该先在脑子里想清楚思路和细节，再决定用什么数据结构。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int max = 0, count = 0, mark = 0;
        for (int i = 0; i < s.length(); i++) {
            count++;
            for (int j = mark; j < i; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    count--;
                    mark = j + 1;
                    max = count > max ? count : max;
                    count = i - j;
                    break;
                }
            }
        }
        max = count > max ? count : max;
        return max;
    }
}

最长回文
字符串操作题，要加加减减的逻辑，以免出界

class Solution {
    public String longestPalindrome(String s) {
        int max = 0, start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int offset = 0;
            // mode 1
            while (i - offset >= 0) {
                if ((i + offset < s.length()) && (s.charAt(i - offset) == s.charAt(i + offset)))
                    offset++;
                else
                    break;
            }
            // max = max > offset * 2 + 1 ? max : offset * 2 + 1;
            if (max < offset * 2 - 1) {
                max = offset * 2 - 1;
                start = i + 1 - offset;
                end = i - 1 + offset;
            }
            // mode 2
            offset = 0;
            while (i - offset >= 0)
                if ((i + 1 + offset < s.length()) && (s.charAt(i - offset) == s.charAt(i + 1 + offset)))
                    offset++;
                else
                    break;
            if (max < offset * 2) {
                max = offset * 2;
                start = i + 1 - offset;
                end = i + offset;
            }
        }
        return s.substring(start, end + 1);
    }
}

6.Z字形变换
基本字符串操作题，注意循环次数和防御性条件即可

class Solution {
    public String convert(String s, int numRows) {
        if (s.length() == 0 || numRows == 1) 
            return s;
        StringBuffer sb = new StringBuffer();
        int circleLength = (numRows - 1) * 2;
        for (int j = 0; j * circleLength < s.length(); j++)
            sb.append(s.charAt(j * circleLength));
        for (int i = 1; i < numRows - 1; i++) {
            for (int j = 0; j * circleLength < s.length(); j++) {
                int mark = j * circleLength + i;
                if (mark < s.length())
                    sb.append(s.charAt(mark));
                mark = (j + 1) * circleLength - i;
                if (mark < s.length())
                    sb.append(s.charAt(mark));
            }
        }
        for (int j = 0; j * circleLength < s.length(); j++) {
            int mark = j * circleLength + numRows - 1;
            if (mark < s.length())
                sb.append(s.charAt(mark));
        }
        return sb.toString();
    }
}

7.翻转整数
题目里说假设环境只能存32位int，想了半天只能用try catch处理溢出了，一搜发现大家都用long……

后来想出了以下溢出判断方法

(c * 10) + t <= Integer.MAX_VALUE ==> c <= (Integer.MAX_VALUE - t) / 10
-(c * 10) - t >= Integer.MIN_VALUE ==> c <= - (Integer.MIN_VALUE + t) / 10

class Solution {
    public int reverse(int x) {
        boolean isPositive = true;
        if (x < 0)
            isPositive = false;
        StringBuilder sb = new StringBuilder(String.valueOf(Math.abs(x)));
        String re = (isPositive ? "" : "-") + sb.reverse().toString();
        int i;
        try {
            i = Integer.valueOf(re).intValue();
        } catch (NumberFormatException e) {
            i = 0;
        }
        return i;
    }
}

class Solution {
    public int reverse(int x) {
        boolean isNeg = x < 0;
        if (isNeg) x = -x;
        long l = 0;
        while (x > 0) {
            l = l * 10 + x % 10;
            x = x / 10;
        }
        if (isNeg) l = -l;
        if (l < Integer.MIN_VALUE || l > Integer.MAX_VALUE)
            l = 0;
        return (int) l;
    }
}

字符串转整数 [推荐]
注意溢出处理

class Solution {
    public int myAtoi(String str) {
        int index = 0;
        long l = 0;
        char x = 0;
        boolean isNeg = false;
        for (; index < str.length(); index++) {
            x = str.charAt(index);
            if (x != ' ')
                break;
        }
        if (x == '+' || x == '-') {
            isNeg = x == '-';
            ++index;
            if (index >= str.length())
                return 0;
            x = str.charAt(index);
        }
        while (index < str.length()) {
            x = str.charAt(index);
            if (x < '0' || x > '9')
                break;
            l = l * 10 + (x - '0');
            if (isNeg && -l < Integer.MIN_VALUE)
                return Integer.MIN_VALUE;
            if (!isNeg && l > Integer.MAX_VALUE)
                return Integer.MAX_VALUE;
            index++;
        }
        if (isNeg) l = -l;
        return (int) l;
    }
}

9.回文数
送的

class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0) return false;
        String t = String.valueOf(x);
        int len = t.length();
        for (int i = 0; i < len / 2; i++)
            if (t.charAt(i) != t.charAt(len - i - 1))
                return false;
        return true;
    }
}

11.盛最多数的容器 [推荐]
注意到只有运动较短侧，才可能提升容量，那么这题就解决了

class Solution {
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1, max = 0;
        while (left < right) {
            int lh = height[left], rh = height[right];
            int temp = (lh < rh ? lh : rh) * (right - left);
            max = max > temp ? max : temp;
            if (lh > rh)
                right--;
            else 
                left++;
        }
        return max;
    }
}

整数转罗马数
纯考验细心

class Solution {
    public String intToRoman(int num) {
        int rep = num / 1000;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < rep; i++)
            sb.append('M');
        num -= rep * 1000;
        rep = num / 100;
        if (rep == 9)
            sb.append("CM");
        else if (rep > 4) {
            sb.append('D');
            for (int i = 0; i < rep - 5; i++)
                sb.append('C');
        } else if (rep == 4) 
            sb.append("CD");
        else 
            for (int i = 0; i < rep; i++)
                sb.append('C');
        num -= rep * 100;
        rep = num / 10;
         if (rep == 9)
            sb.append("XC");
        else if (rep > 4) {
            sb.append('L');
            for (int i = 0; i < rep - 5; i++)
                sb.append('X');
        } else if (rep == 4) 
            sb.append("XL");
        else 
            for (int i = 0; i < rep; i++)
                sb.append('X');
        num -= rep * 10;
        rep = num;
         if (rep == 9)
            sb.append("IX");
        else if (rep > 4) {
            sb.append('V');
            for (int i = 0; i < rep - 5; i++)
                sb.append('I');
        } else if (rep == 4) 
            sb.append("IV");
        else 
            for (int i = 0; i < rep; i++)
                sb.append('I');
        return sb.toString();
    }
}

罗马转整数
网上看了别人的代码，还是比if-else省力不少的，多多观察规律总有好处

class Solution {
    public int romanToInt(String s) {
        HashMap<Character, Integer> map = new HashMap<Character, Integer>() {{
            put('I', 1); put('V', 5); put('X', 10); put('L', 50);
            put('C', 100); put('D', 500); put('M', 1000);
        }};
        int re = 0;
        for (int i = 0; i < s.length(); i++) {
            if (i + 1 < s.length() && map.get(s.charAt(i)) < map.get(s.charAt(i + 1)))
                re -= map.get(s.charAt(i));
            else
                re += map.get(s.charAt(i));
        }
        return re;
    }
}

最长公共前缀
最长子串的无限弱化版，注意array.length, string.length(), list.size()

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0 || strs[0].length() == 0) 
            return "";
        int mark = 0;
        while (mark < strs[0].length()) {
            char t = strs[0].charAt(mark);
            for (int j = 1; j < strs.length; j++) {
                if (mark >= strs[j].length() || t != strs[j].charAt(mark))
                    return strs[0].substring(0, mark);
            }
            mark++;
         }
         return strs[0].substring(0, mark);        
    }
}

三数之和
题很简单，坑很多，比如重复值处理

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> re = new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            int m1 = i + 1, m2 = nums.length - 1;
            while (m1 < m2) 
                if (nums[m1] + nums[m2] > -nums[i])
                    m2--;
                else if (nums[m1] + nums[m2] < -nums[i])
                    m1++;
                else {
                    List<Integer> list = Arrays.asList(nums[i],nums[m1],nums[m2]);
                    if (!re.contains(list))
                        re.add(list); 
                    m1++;
                    m2--;
                }
            while (i < nums.length - 3 && nums[i] == nums[i + 1])
                i++;
        }
        return re;
    }
}

最接近的三数之和
与三数之和类似，通过排序减低时间复杂度

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        List<Integer> re = new ArrayList<Integer>();
        int diff = Integer.MAX_VALUE, sum = 0;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            int m1 = i + 1, m2 = nums.length - 1;
            while (m1 < m2) {
                int tsum = nums[i]+nums[m1]+nums[m2];
                int tdiff = Math.abs(tsum - target);
                if (tdiff < diff) {
                    diff = tdiff;
                    sum = tsum;
                }
                if ( tsum > target ) 
                    m2--;
                else 
                    m1++;
            } 
        }
        return sum;
    }
}

电话号码字母
又是无聊题

class Solution {
    public List<String> letterCombinations(String digits) {
        ArrayList<String> res = new ArrayList<String>();
        if (digits.equals("")) return res;
        res.add("");
        HashMap<String, String> map = new HashMap<String, String>(){{
            put("0", " ");put("1", "");put("2", "abc");put("3", "def");put("4", "ghi");
            put("5", "jkl");put("6", "mno");put("7", "pqrs");put("8", "tuv");put("9", "wxyz");
        }};
        String[] ins = digits.split("");
        for(String in: ins) {
            ArrayList<String> tempList = new ArrayList<String>();
            String str = map.get(in);
            String[] chs = str.split(""); 
            for (String re: res)
                for (String ch: chs)
                    tempList.add(re+ch);
            res = tempList;
        }
        return res;
    }
}

删除链表的倒数第N个数
链表操作题，自己加一个链表头会极大减少复杂度

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head.next == null)
            return null;
        ListNode start = new ListNode(0), p1 = start, p2 = start;
        start.next = head;
        int cnt = 0;
        while (p1.next != null) {
            p1 = p1.next;
            p2 = p2.next;
            cnt++;
            if (cnt <= n)
                p2 = start;
        }
        p2.next = p2.next.next;
        return start.next;
    }
}

有效的括号 [推荐]
感觉自己写得太复杂，难过

class Solution {
    public boolean isValid(String s) {
        int m = 0, len = s.length();
        if (len % 2 != 0)
            return false;
        Map<Character, Character> map = new HashMap<Character, Character>(){{
            put('(', ')');put('[', ']');put('{', '}');
        }};
        Stack<Character> stack = new Stack<Character>();
        while (m < len) {
            Character c = s.charAt(m);
            if (map.containsKey(c))
                stack.push(c);
            else if (stack.isEmpty() || c != map.get(stack.pop()))
                return false;
            m++;
        }
        if (stack.isEmpty())
            return true;
        else
            return false;
    }
}

Generate Parentheses
先放右边，再放左边

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> re = new ArrayList<String>();
        genPar(re, "", n, 0);
        return re;
    }
    
    private void genPar(List<String> re, String str, int le, int ri) {
        if (le == 0 && ri == 0) {
            re.add(str);
            return;
        }
        
        if (ri > 0)
            genPar(re, str + ")", le, ri - 1);
        if (le > 0)
            genPar(re, str + "(", le - 1, ri + 1);
    }
}

21.23. 合并n个有序列表
21是23的特例，而23是最简单的困难题吧……

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        int size = lists.length, cnt = 0;
        ListNode h = new ListNode(0), p = h;
        for (int i = 0; i < size; i++)
            if (lists[i] == null)
                cnt++;
        while (cnt < size) {
            int min = Integer.MAX_VALUE, mark = 0;
            for (int i = 0; i < size; i++)
                if (lists[i] != null && lists[i].val < min) {
                    min = lists[i].val;
                    mark = i;
                } 
            p.next = lists[mark];
            lists[mark] = lists[mark].next;
            p = p.next;
            if (lists[mark] == null)
                cnt++;
        }
        return h.next;
    }
}

24.25. Reverse List in k-Group
24是25的特例，就不分开写了，连标题真的要特别注意初始化和终止条件，注意是否越界、是否符合要求

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (k <= 1 || head == null)
            return head;
        ListNode start = new ListNode(0), p1 = head, p2 = head, pt = head, ph = head, ptail = start;
        start.next = head;
        int cnt = 1;
        while (p2 != null) {
            if (cnt >= k) {
                ph = p2.next;
                while (p1 != p2) {
                    pt = p1.next;
                    p1.next = ph;
                    ph = p1;
                    p1 = pt; 
                }
                p2.next = ph;
                ptail.next = p2;
                while (cnt-- > 0)
                    ptail = ptail.next;
                cnt = 1;
                p1 = p2 = ptail.next;
            } else {
                p2 = p2.next;
                cnt++;
            }
        }
        return start.next;
    }
}

Remove Duplicates from Sorted Array
太水了

class Solution {
    public int removeDuplicates(int[] nums) {
        int i = 1, len = nums.length, cnt = 1;
        if (len == 0)
            return 0;
        for (; i < len; i++)
            if (nums[i - 1] != nums[i])
                nums[cnt++] = nums[i];
        return cnt;
    }
}

27-28 太水，就不贴了

Divide Two Integers [推荐]
用位运算计算触发，也许会用到

class Solution {
    public int divide(int dividend, int divisor) {
        if (divisor == Integer.MIN_VALUE)
            if (dividend == divisor) return 1;
            else return 0;
        else if (divisor == -1 && dividend == Integer.MIN_VALUE)
            return Integer.MAX_VALUE;
        
        int a = Math.abs(dividend), b = Math.abs(divisor), res = 0;
        for (int x = 31; x >= 0; x--)
            if ((a >>> x) - b >= 0) {
                res += 1 << x;
                a -= b << x;
            }
        return (dividend > 0) == (divisor > 0) ? res : -res;
    }
}

Next Permutation [推荐]
这题比较有意思，找到规律后居然cover所有测试，而不需要 if 处理一些特例，数学真奇妙

class Solution {
    public void nextPermutation(int[] nums) {
        int len = nums.length, i = len - 2;
        while (i >= 0 && nums[i] >= nums[i + 1])
            i--;
        if (i >= 0) {
            int j = len - 1;             
            while(nums[j] <= nums[i]) j--;      
            swap(nums, i, j);                    
        }
        reserve(nums, i + 1, len - 1);
    }
    
    private void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
    
    private void reserve(int[] nums, int i, int j) {
        while (i < j)
            swap(nums,i++,j--);
    }
}

Search for a Range [推荐]
二分查找的变形，我觉得这种经典算法的变形题比较有趣，考验基础掌握和灵活变通，且有一定的工程意义，而不是智力游戏。

class Solution {
    public static int[] searchRange(int[] nums, int target) {
        int[] re = new int[] {-1, -1};
        if (nums.length == 0)
            return re;
        int t = searchLo(nums, target, 0, nums.length - 1);
        if (t != -1) {
            re[0] = t;
            re[1] = searchHi(nums, target, 0, nums.length - 1);
        }
        return re;
    }
    
    private static int searchLo(int[] nums, int target, int lo, int hi) {
        if (nums[lo] == target)
            return lo;
        if (lo + 1 >= hi)
            if (nums[hi] == target)
                return hi;
            else
                return -1;
        int mi = (lo + hi) / 2;
        if (nums[mi] >= target)
            return searchLo(nums, target, lo, mi);
        else
            return searchLo(nums, target, mi, hi);
    }
    
    private static int searchHi(int[] nums, int target, int lo, int hi) {
        if (nums[hi] == target)
            return hi;
        if (lo + 1 >= hi)
            return lo;
        int mi = (lo + hi) / 2;
        if (nums[mi] <= target)
            return searchHi(nums, target, mi, hi);
        else
            return searchHi(nums, target, lo, mi);
    }
}

简化一点：

class Solution {
    public static int[] searchRange(int[] nums, int target) {
        int[] re = new int[] {-1, -1};
        if (nums.length == 0)
            return re;
        int t, tail = nums.length - 1;
        if (nums[0] == target)
            t = 0;
        else
            t = search(nums, target, 0, tail, true);
        if (t != -1) {
            re[0] = t;
            if (nums[tail] == target)
                re[1] = tail;
            else
                re[1] = search(nums, target, 0, tail, false);
        }
        return re;
    }
    
    private static int search(int[] nums, int target, int lo, int hi, boolean searchLow) {
        if (lo + 1 >= hi)
            if (searchLow)
                if (nums[hi] == target) return hi;
                else return -1;
            else
                if (nums[lo] == target) return lo;
                else return -1;
        
        int mi = (lo + hi) / 2;
        if ((searchLow && nums[mi] >= target) || (!searchLow && nums[mi] > target))
            return search(nums, target, lo, mi, searchLow);
        else
            return search(nums, target, mi, hi, searchLow);
    }
}

Search Insert Position
做完刚才那题，再写这题就很随意。

class Solution {
    public int searchInsert(int[] nums, int target) {
        int lo = 0, hi = nums.length - 1;
        if (hi == -1 || nums[lo] >= target)
            return 0;
        if (nums[hi] < target)
            return hi + 1;
        return bsInsert(nums, target, lo, hi);
    }
    
    private int bsInsert(int[] nums, int target, int lo, int hi) {
        int mi = (lo + hi) / 2;
        if (nums[mi] < target && nums[mi + 1] >= target)
            return mi + 1;
        
        if (nums[mi] >= target)
            return bsInsert(nums, target, lo, mi);
        else
            return bsInsert(nums, target, mi, hi);
    }
}

1. CombinationSum
  就是个dfs，注意到排序去重即可

class Solution {
    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (candidates.length == 0)
            return res;
        List<Integer> re = new ArrayList<Integer>();
        boolean[] flags = new boolean[candidates.length];
        dfs(res,re,candidates,flags, target);
        return res;
    }
    
    private static void dfs(List<List<Integer>> res, List<Integer> re, int[] candidates, boolean[] flags, int target) {
        int sum = 0;
        for (Integer t: re)
            sum += t;
        if (sum == target && !res.contains(re)) {
            res.add(new ArrayList<Integer>(re));
            return;
        } else if (sum > target)
            return;
        for (int i = 0, len = candidates.length; i < len; i++) 
            if (flags[i] == false && (re.size() == 0 || candidates[i] >= re.get(re.size() - 1))) {
                re.add(candidates[i]);
                flags[i] = true;
                dfs(res, re, candidates, flags, target);
                re.remove(re.size() - 1);
                flags[i] = false;
            }
    }
}

41 First Missing Positive [推荐]
将下标作为容器，是算法题里一种重要思路

class Solution {
    public int firstMissingPositive(int[] nums) {
        int i = 0;
        int len = nums.length;
        while (i<len) {
            if (nums[i] > 0 && nums[i] < len // careful with both barriers
                && nums[ nums[i] - 1 ] != nums[i])
                swap(nums, i, nums[i] - 1);
            else // brilliant 'else'
                i++;
        }
        
        i = 0;
        while (i<len) {
            if (nums[i] != i + 1)
                return i + 1;
            i++;
        }
        return len + 1;
    }
    
    private void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

45 Jump Game II
这么水的DP居然是hard……看来最简单hard可以更新了

class Solution {
    public int jump(int[] nums) {
        int len = nums.length;
        if (len == 0)
            return 0;
        int[] min = new int[len];
        min[0] = 0;
        for (int i = 1; i < len; i++)
            min[i] = Integer.MAX_VALUE;
        for (int i = 0; i < len - 1; i++) {
            int steps = min[i] + 1;
            for (int j = 1; j <= nums[i]; j++) {
                int index = i + j;
                if (index < len && min[index] > steps)
                    min[index] = steps;
            }
        }
        return min[len - 1];
    }
}

Permutation [推荐]
两个亮点：直接把nums转成list传进去remove,add，会导致排列错序，以后还是用flag标记是否访问吧；居然要手动import!

import java.util.Map.Entry;

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        List<Integer> re = new ArrayList<Integer>();
        if (nums.length > 0) {
            Map<Integer, Boolean> map = new HashMap<Integer, Boolean>();
            for (int num: nums) {
                map.put(num, false);
            }
            dfs(res, re, map);
        }
        return res;
    }
    
    private void dfs(List<List<Integer>> res, List<Integer> re, Map<Integer, Boolean> map) {
        if (!map.values().contains(false)) {
            res.add(new ArrayList<Integer>(re));
            return;
        }
            
        for (Entry<Integer, Boolean> entry: map.entrySet())
            if (!entry.getValue()) {
                entry.setValue(true);
                re.add(entry.getKey());
                dfs(res,re,map);
                entry.setValue(false);
                re.remove(entry.getKey());
            }
    }
}

Permutation II
为什么呢？

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        LinkedList<List<Integer>> res = new LinkedList<List<Integer>>();
        Arrays.sort(nums);
        dfs(nums, new LinkedList<Integer>(), res, new boolean[nums.length]);
        return res;
    }
    
    private void dfs(int[] nums, LinkedList<Integer> re, LinkedList<List<Integer>> res, boolean[] visited) {
        int len = nums.length;
        if (re.size() == len) {
            res.add(new LinkedList<Integer>(re));
            return;
        }
        
        for (int i = 0; i < len; i++) {
            if (visited[i] || (i-1 >= 0 && visited[i-1] && nums[i] == nums[i-1]))
                continue;
            
            visited[i] = true;
        re.add(nums[i]);
        dfs(nums, re, res, visited);
        re.remove(re.size()-1);
        visited[i] = false; 
        }
    }
}

48 Rotate Image
用笔推演旋转过程，不难发现坐标转换规律，但是写代码时不小心写错了两个地方，细心真是一件很难的事情。

class Solution {
    public void rotate(int[][] matrix) {
        int len = matrix.length;
        if (len <= 1)
            return;
        for (int i = 0, endi = len / 2; i < endi; i++)
            for (int j = 0, endj = len - 1 - i * 2; j < endj; j++) // forget to multiply 2 and i
                swap4(matrix, len, i + j, i); // forget to use i + j, i instead of i, j
    }

    private void swap4(int[][] m, int l, int i, int j) {
        int tempValue, lastValue = m[i][j], tempi, tempj;
        for (int k = 0; k < 4; k++) {
            tempi = i;
            tempj = j;
            i = tempj;
            j = l - 1 - tempi;
            tempValue = m[i][j];
            m[i][j] = lastValue;
            lastValue = tempValue;
        }
    }
}

Group Anagram [推荐]
没什么难度，看了discuss习得质数分桶法，牛b！

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        int[] prime = {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}; // careful with potential overflow
        List<List<String>> res = new LinkedList<>();
        Map<Integer, List<String>> map = new HashMap<>();
        for (String str: strs) {
            int key = 1;
            for (char c: str.toCharArray()) {
                key *= prime[c - 'a'];
            }
            List<String> list;
            if (map.containsKey(key)) {
                list = map.get(key);
            } else {
                list = new LinkedList<>();
                map.put(key, list);
                res.add(list);
            }
            list.add(str);
        }
        return res;
    }
}

Pow [推荐]
位操作

class Solution {
    public double myPow(double x, int n) {
        if (n == Integer.MIN_VALUE)
            return 1/(myPow(x,Integer.MAX_VALUE)*x);
        boolean reverse = false;
        if (n < 0) {
            n = -n;
            reverse = true;
        }
        double res = 1;
        //for (int i = 0; i < 32; i++) {
        while (n>0) {
            if ((n&1) == 1) 
                res *= x;
            n = n >> 1;
            x *= x;
        }
        return reverse? 1/res:res;
    }
}

Leetcode之旅

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读