📣 4th of July限时特惠: VIP通行证立减$68
搜索
体验新版
<
一亩三分地»论坛 › 专业技术 › 转码 › 学习圈 › 刷题skill+编程cultivation+记录
12345678下一页
返回列表 发新帖
楼主: AChris
跳转到指定楼层
上一主题 下一主题
收起左侧

刷题skill+编程cultivation+记录

刷题 leetcode
🔗
 楼主| AChris 2019-4-6 09:03:47 | 只看该作者
全局：


04/6/2019 Day37
LeetCode 572. Subtree of Another Tree
Importantce【4】

解题思路：
这题的关键是将 找是否是subtree的问题转化为是否是same tree的问题，然后，在通过递归来解决是否是 same tree的问题。

  1. /**
  2. * Definition for a binary tree node.
  3. * public class TreeNode {
  4. *     int val;
  5. *     TreeNode left;
  6. *     TreeNode right;
  7. *     TreeNode(int x) { val = x; }
  8. * }
  9. */
  10. class Solution {
  11.     public boolean isSubtree(TreeNode s, TreeNode t) {
  12.         // time: O(n) 99.64%
  13.         // space: O(logn) 90.11%
  14.         if (s == null && t!= null) return false;
  15.         if (sameTree(s, t)) return true;
  16.         return isSubtree(s.left, t) || isSubtree(s.right, t);
  17.     }
  18.    
  19.     private boolean sameTree(TreeNode s, TreeNode t) {
  20.         if (s == null && t == null) return true;
  21.         if (s == null || t == null) return false;
  22.         return s.val == t.val && sameTree(s.left, t.left) && sameTree(s.right, t.right);
  23.     }
  24. }
复制代码
回复

使用道具 举报

🔗
 楼主| AChris 2019-4-9 01:17:49 | 只看该作者
全局：



04/6/2019 Day37
LeetCode 309. Best Time to Buy and Sell Stock with Cooldown
Importantce【4】

解题思路：
使用dynamic programming。
解决这种问题的时候，主要分为几步。
1. define state variable
2. set objective
3. base case
4. state change rule




  1. class Solution {
  2.     public int maxProfit(int[] prices) {
  3.         // time: O(n) 96.33%
  4.         // space: O(n) 93.64%
  5.         if (prices == null || prices.length <= 1) return 0;
  6.         if (prices.length == 2) return Math.max(0, prices[1] - prices[0]);
  7.         
  8.         // variables
  9.         int[] hold = new int[prices.length];
  10.         int[] unhold = new int[prices.length];
  11.         
  12.         // base case
  13.         hold[0] = -prices[0];
  14.         hold[1] = Math.max(-prices[0], -prices[1]);
  15.         unhold[0] = 0;
  16.         unhold[1] = Math.max(hold[0] + prices[1], unhold[0]);
  17.         
  18.         // state change
  19.         for (int i = 2; i < prices.length; i++) {
  20.             hold[i] = Math.max(unhold[i-2] - prices[i], hold[i-1]);
  21.             unhold[i] = Math.max(hold[i-1] + prices[i], unhold[i-1]);
  22.         }
  23.         
  24.         return unhold[prices.length - 1];
  25.         
  26.     }
  27. }
复制代码
回复

使用道具 举报

🔗
 楼主| AChris 2019-4-12 01:27:15 | 只看该作者
全局：
04/11/2019 Day38
LeetCode 12. Integer to Roman
Importantce【4】

解题思路：
用两个arrays存储可能的组合。然后用greedy algo



  1. class Solution {
  2.     public String intToRoman(int num) {
  3.         // time: O(n)
  4.         // space: O(n)
  5.         int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
  6.         String[] strs = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
  7.         
  8.         StringBuilder sb = new StringBuilder();
  9.         for (int i = 0; i < values.length; i++) {
  10.             while (num - values[i] >= 0) {
  11.                 num -= values[i];
  12.                 sb.append(strs[i]);
  13.             }
  14.         }
  15.         return sb.toString();
  16.     }
  17. }
复制代码
回复

使用道具 举报

🔗
 楼主| AChris 2019-4-12 02:44:21 | 只看该作者
全局：
04/11/2019 Day38
LeetCode 8. String to Integer (atoi)
Importantce【4】

解题思路：
关键在于用long 来代替int 存result，方便处理超出 int 范围的边界情况



  1. class Solution {
  2.     public int myAtoi(String str) {
  3.         // time: O(n) 91.17%
  4.         // space: O(1) 23.47%
  5.         str = str.trim();
  6.         if (str == null || str.length() == 0) return 0;
  7.         
  8.         long res = 0;
  9.         int sign = 1;
  10.         int start = 0;
  11.         if (str.charAt(0) == '-') {
  12.             sign = -1;
  13.             start++;
  14.         } else if (str.charAt(0) == '+') {
  15.             start++;
  16.         }
  17.         
  18.         while (start < str.length()) {
  19.             if (!Character.isDigit(str.charAt(start))) {
  20.                 return (int) res * sign;
  21.             }
  22.             res = res * 10 + str.charAt(start) - '0';
  23.             if (sign == 1 && res > Integer.MAX_VALUE) return Integer.MAX_VALUE;
  24.             if (sign == -1 && res > Integer.MAX_VALUE) return Integer.MIN_VALUE;
  25.             start++;
  26.         }
  27.         return (int) res * sign;
  28.     }
  29. }
复制代码
回复

使用道具 举报

🔗
 楼主| AChris 2019-4-13 01:35:53 | 只看该作者
全局：

04/12/2019 Day39
LeetCode 24. Swap Nodes in Pairs
Importantce【4】

解题思路：
首先，在head之前加一个dummy node
然后，用cur和cur.next是需要交换的两个点。用prev和nextStart分别指出交换部分之外的连接处的node。


  1. /**
  2. * Definition for singly-linked list.
  3. * public class ListNode {
  4. *     int val;
  5. *     ListNode next;
  6. *     ListNode(int x) { val = x; }
  7. * }
  8. */
  9. class Solution {
  10.     public ListNode swapPairs(ListNode head) {
  11.         // time: O(n) 100%
  12.         // space: O(1) 91.13%
  13.         ListNode dummy = new ListNode(1);
  14.         dummy.next = head;
  15.         
  16.         ListNode prev = dummy;
  17.         ListNode cur = head;
  18.         while (cur != null && cur.next != null) {
  19.             ListNode nextStart = cur.next.next;
  20.             prev.next = cur.next;
  21.             cur.next.next = cur;
  22.             cur.next = nextStart;
  23.             prev = cur;
  24.             cur = cur.next;
  25.         }
  26.         return dummy.next;
  27.     }
  28. }
复制代码
回复

使用道具 举报

🔗
 楼主| AChris 2019-4-13 03:23:03 | 只看该作者
全局：
04/12/2019 Day39
LeetCode 6. ZigZag Conversion
Importantce【3】

解题思路：
首先要看懂题目。
然后把字母分成 2*numRows-2 一组一组append到相应的行上去。


  1. class Solution {
  2.     public String convert(String s, int numRows) {
  3.         // time: O(n) 92.62%
  4.         // space: O(n) 91.15%
  5.         if (s == null || s.length() == 0 || numRows == 1) return s;
  6.         
  7.         StringBuilder[] sbs = new StringBuilder[numRows];
  8.         StringBuilder res = new StringBuilder("");
  9.         for (int i = 0; i < numRows; i++) {
  10.             sbs[i] = new StringBuilder("");
  11.         }
  12.         
  13.         for (int i = 0; i < s.length(); i++) {
  14.             int index = i % (numRows * 2 - 2);
  15.             index = index < numRows? index : (numRows * 2 - 2) - index;
  16.             sbs[index].append(s.charAt(i));
  17.         }
  18.         
  19.         for (int i = 0; i < numRows; i++) {
  20.             res.append(sbs[i]);
  21.         }
  22.         return res.toString();
  23.     }
  24. }
复制代码
回复

使用道具 举报

🔗
 楼主| AChris 2019-4-13 04:29:08 | 只看该作者
全局：

04/12/2019 Day39
LeetCode 14. Longest Common Prefix
Importantce【3】

解题思路：
主要是方法1。利用string里面的indexOf来降低算法复杂度。
首先，假设 strs[0] 就是我们想要的result。
让后一个一个看strs里面的元素是否包含result，并且起始位置是0，这一步用indexOf实现。
如果是的，就检查下一个strs[] 里的元素。
如果不是，就讲result从后面减少一位。

如果要写proof的话。可以用induction来证明他的feasibility。然后用反证法来证他的maximality。


  1. class Solution {
  2.    
  3.     // method 1:
  4.     public String longestCommonPrefix(String[] strs) {
  5.         // time: O(n) 100%
  6.         // space: O(m) 26.07%
  7.         if (strs == null || strs.length == 0) return "";
  8.         
  9.         String res = strs[0];
  10.         for (int i = 1; i < strs.length; i++) {
  11.             while (strs[i].indexOf(res) != 0) res = res.substring(0, res.length() - 1);
  12.         }
  13.         return res;
  14.     }
  15.    
  16. //     // method 2:
  17. //     public String longestCommonPrefix(String[] strs) {
  18. //         // n = strs.length, m = max length of string in strs
  19. //         // time: O(n*m) 94.28%
  20. //         // space: O(m) 15.91%
  21. //         // corner case
  22. //         if (strs == null || strs.length == 0) return "";
  23. //         if (strs.length == 1) return strs[0];
  24.         
  25. //         // general case
  26. //         StringBuilder sb = new StringBuilder("");
  27. //         for (int i = 0; i < strs[0].length(); i++) {
  28. //             char c = strs[0].charAt(i);
  29. //             for (String str : strs) {
  30. //                 if (str.length() == i || str.charAt(i) != c) return sb.toString();
  31. //             }
  32. //             sb.append(c);
  33. //         }
  34. //         return sb.toString();
  35. //     }
  36. }
复制代码
回复

使用道具 举报

🔗
 楼主| AChris 2019-4-15 03:43:49 | 只看该作者
全局：
04/12/2019 Day39
LeetCode 14. Longest Common Prefix
Importantce【3】

解题思路：
两种写法。
第一种是用dummy node，然后依次判断。
第二种递归，空间复杂度大一些，



  1. /**
  2. * Definition for singly-linked list.
  3. * public class ListNode {
  4. *     int val;
  5. *     ListNode next;
  6. *     ListNode(int x) { val = x; }
  7. * }
  8. */
  9. class Solution {
  10.     // // method 1(1): similar to method1(2) but easy to understand
  11.     // public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
  12.     //     // time: O(n) 90.23%
  13.     //     // space: O(1) 97.95%
  14.     //     ListNode dummy = new ListNode(0);
  15.     //     ListNode cur = dummy;
  16.     //     while (l1 != null && l2 != null) {
  17.     //         if (l1.val <= l2.val) {
  18.     //             cur.next = l1;
  19.     //             l1 = l1.next;
  20.     //         } else {
  21.     //             cur.next = l2;
  22.     //             l2 = l2.next;
  23.     //         }
  24.     //         cur = cur.next;
  25.     //     }
  26.     //     if (l1 != null) {
  27.     //         cur.next = l1;
  28.     //     } else {
  29.     //         cur.next = l2;
  30.     //     }
  31.     //     return dummy.next;
  32.     // }
  33.    
  34. //     // method 1(2):
  35. //     public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
  36. //         // time: O(n) 90.23%
  37. //         // space: O(1) 97.90%
  38. //         ListNode dummy = new ListNode(0);
  39. //         ListNode cur = dummy;
  40. //         while (l1 != null || l2 != null) {
  41. //             // in the requisite of loop, l1 and l2 cannot be null simutaneouly,
  42. //             // so if l2 is null, then l1 is not null
  43. //             if (l2 == null || (l1 != null && l1.val <= l2.val)) {
  44. //                 cur.next = l1;
  45. //                 l1 = l1.next;
  46. //             } else if (l1 == null || (l2 != null && l1.val > l2.val)) {
  47. //                 cur.next = l2;
  48. //                 l2 = l2.next;
  49. //             }
  50. //             cur = cur.next;
  51. //         }
  52.         
  53. //         return dummy.next;
  54. //     }
  55.    
  56.    
  57.     // method 2: recursive
  58.     public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
  59.         // time: O(n) 100%
  60.         // space: O(n) 97.90%
  61.         if (l1 == null) return l2;
  62.         if (l2 == null) return l1;
  63.         if (l1.val <= l2.val) {
  64.             l1.next = mergeTwoLists(l1.next, l2);
  65.             return l1;
  66.         } else {
  67.             l2.next = mergeTwoLists(l1, l2.next);
  68.             return l2;
  69.         }
  70.     }
  71. }
复制代码
回复

使用道具 举报

🔗
 楼主| AChris 2019-4-15 03:52:46 | 只看该作者
全局：

04/14/2019 Day40
LeetCode 28. Implement strStr()
Importantce【3】

解题思路：
两种写法。
用substring并依次比较。
注意substring的时间复杂度是线性的。



  1. class Solution {
  2.     public int strStr(String haystack, String needle) {
  3.         // time: O(n^2) 93.03% substring is of the linear time complexity
  4.         // space: O(1) 78.33%
  5.         if (needle.length() == 0) return 0;
  6.         for (int i = 0; i <= haystack.length() - needle.length(); i++) {
  7.             if (haystack.substring(i, i + needle.length()).equals(needle)) return i;
  8.         }
  9.         return -1;
  10.     }
  11. }
复制代码
回复

使用道具 举报

🔗
 楼主| AChris 2019-4-16 12:11:50 | 只看该作者
全局：
04/15/2019 Day40
LeetCode 28. Implement strStr()
Importantce【4】

这一题的方法2.利用KMP算法。
解题思路：
主要是考虑到string = aaaaab 和pattern = aaab这种情况下，要利用已经得到的信息
1. 计算lps表，longest proper prefix is also suffix
2.分情况便利整个string，在char不同的时候，根据lps决定从pattern的哪里开始比较，不需要从头比较

【奇怪的是，这个算法理论上复杂度更低，但是leetcode的评测time只有20%多】

  1. class Solution {
  2.    
  3.     // method1: KMP Algorithm (Knuth Morris Pratt)
  4.     public int strStr(String haystack, String needle) {
  5.         // m: length of haystack, n: length of needle
  6.         // time: O(m + n) 28.40%
  7.         // space: O(n) 6.44%
  8.         if (needle.length() == 0) return 0;
  9.         
  10.         int res = -1;
  11.         int[] lps = getPrefixTable(needle);
  12.         // System.out.println(Arrays.toString(lps));
  13.         int i = 0;
  14.         int len = 0;
  15.         while (i < haystack.length()) {
  16.             // System.out.println("****");
  17.             // System.out.println(i);
  18.             // System.out.println(len);
  19.             if (haystack.charAt(i) == needle.charAt(len)) {
  20.                 i++;
  21.                 len++;
  22.             }
  23.             
  24.             if (len == needle.length()) {
  25.                 res = i - len;
  26.                 len = lps[len - 1];
  27.                 // we only need the first occurrence
  28.                 break;
  29.             }
  30.             
  31.             else if (i < haystack.length() && haystack.charAt(i) != needle.charAt(len)) {
  32.                 if (len == 0) {
  33.                     i++;
  34.                 } else {
  35.                     len = lps[len - 1];
  36.                 }
  37.             }
  38.         }
  39.         
  40.         return res;
  41.     }
  42.    
  43.     private int[] getPrefixTable(String needle) {
  44.         int[] lps = new int[needle.length()];
  45.         lps[0] = 0;
  46.         // i is the index for prefix, j going through the needle
  47.         int i = 0, j = 1;
  48.         while (j < needle.length()) {
  49.             if (needle.charAt(j) == needle.charAt(i)) {
  50.                 i++;
  51.                 lps[j] = i;
  52.                 j++;
  53.             } else {
  54.                 if (i == 0) {
  55.                     j++;
  56.                 } else {
  57.                     i = lps[i - 1];
  58.                 }
  59.             }
  60.         }
  61.         return lps;
  62.     }
  63.    
  64. //     // method2: using substring and equals
  65. //     public int strStr(String haystack, String needle) {
  66. //         // time: O(m*n) 93.03% substring is of the linear time complexity
  67. //         // space: O(1) 78.33%
  68. //         if (needle.length() == 0) return 0;
  69. //         for (int i = 0; i <= haystack.length() - needle.length(); i++) {
  70. //             if (haystack.substring(i, i + needle.length()).equals(needle)) return i;
  71. //         }
  72. //         return -1;
  73. //     }
  74. }
复制代码
回复

使用道具 举报

下一页 »
12345678下一页
返回列表 发新帖
B Color Link Quote Code
您需要登录后才可以回帖 登录 | 注册账号
隐私提醒：
  • ☑ 禁止发布广告，拉群，贴个人联系方式：找人请去🔗同学同事飞友，拉群请去🔗拉群结伴，广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑，过后则不能删帖。为防止被骚扰甚至人肉，不要公开留微信等联系方式，如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名：面经（美国面经、中国面经、数科面经、PM面经），抖包袱（美国、中国）和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表