📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
楼主: tall_cool_13
跳转到指定楼层
上一主题 下一主题
收起左侧

开一贴刷题打卡

🔗
 楼主| tall_cool_13 2018-9-24 03:25:32 | 只看该作者
全局:
刚在leetcode上面计时写了一道题目, 40分钟,终于在最后一分钟写完代码提交成功, https://leetcode.com/mockinterview/session/result/n6q6goc/
总体来说问题:读题时间太长,花了10分钟才读完题目,又花了10几分钟理清思路
  1. import copy
  2. class Solution(object):
  3.     def calcEquation(self, equations, values, queries):
  4.         """
  5.         :type equations: List[List[str]]
  6.         :type values: List[float]
  7.         :type queries: List[List[str]]
  8.         :rtype: List[float]
  9.         """
  10.         pairs = {}
  11.         for index, v in enumerate(equations):
  12.             if v[0] in pairs:
  13.                 pairs[v[0]].append([v[1], values[index], 0])
  14.             else:
  15.                 pairs[v[0]] = [[v[1], values[index], 0]]

  16.             if v[1] in pairs:
  17.                 pairs[v[1]].append([v[0], 1/values[index], 0])
  18.             else:
  19.                 pairs[v[1]] = [[v[0], 1/values[index], 0]]

  20.         res = []
  21.         for q in queries:
  22.             x = copy.deepcopy(pairs)
  23.             res.append(self.get_result(q[0], q[1], x))
  24.         return res

  25.     def get_result(self, a, b, pairs):
  26.         # special cases
  27.         if a not in pairs or b not in pairs:
  28.             return -1.0

  29.         if a == b and a in pairs:
  30.             return 1.0

  31.         for nodes in pairs[a]:
  32.             cur = -1.0
  33.             if nodes[2] == 0:
  34.                 nodes[2] = 1
  35.                 if nodes[0] == b:
  36.                     cur = nodes[1]
  37.                 else:
  38.                     m = self.get_result(nodes[0], b, pairs)
  39.                     if m == -1.0:
  40.                         cur = -1.0
  41.                     else:
  42.                         cur = nodes[1] * m
  43.             if cur != -1.0:
  44.                 return cur
  45.         return -1.0


  46. if __name__ == "__main__":
  47.     equations = [["a", "b"], ["b", "c"]]
  48.     values = [2.0, 3.0]
  49.     queries = [["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"]]
  50.     obj = Solution()
  51.     print obj.calcEquation(equations, values, queries)
复制代码
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-9-24 06:16:06 | 只看该作者
全局:
做了一题Regular Expression Match

Basic Regex Parser
Implement a regular expression function isMatch that supports the '.' and '*' symbols. The function receives two strings - text and pattern - and should return true if the text matches the pattern as a regular expression. For simplicity, assume that the actual symbols '.' and '*' do not appear in the text string and are used as special symbols only in the pattern string.

In case you aren’t familiar with regular expressions, the function determines if the text and pattern are the equal, where the '.' is treated as a single a character wildcard (see third example), and '*' is matched for a zero or more sequence of the previous letter (see fourth and fifth examples). For more information on regular expression matching, see the Regular Expression Wikipedia page.

Explain your algorithm, and analyze its time and space complexities.

Examples:

input:  text = "aa", pattern = "a"
output: false

input:  text = "aa", pattern = "aa"
output: true

input:  text = "abc", pattern = "a.c"
output: true

input:  text = "abbb", pattern = "ab*"
output: true

input:  text = "acd", pattern = "ab*c."
output: true

  1. import java.util.*;

  2. public class Regex {

  3.     private boolean isMatch(String text, String pattern) {
  4.         // your code goes here
  5.         // special cases
  6.         if (pattern.length() <= 1) {
  7.             // . or a-z or empty string
  8.             if (pattern == ".") {
  9.                 return text.length() >= 1 ;
  10.             }
  11.             return text.contains(pattern) ;
  12.         }
  13.         if (text == "") {
  14.             return false ;
  15.         }

  16.         // step 1: extract the char-star
  17.         int maxSize = text.length() ;
  18.         // the size of char-stars == arrSplit.length() -1
  19.         String []arrSplit = pattern.split("\\*") ;
  20.         // get all the possible strings
  21.         ArrayList<String> outStars = getPossibleOutStarStrings(arrSplit, maxSize, 0) ;

  22.         // step 2: check the string is vaild
  23.         for(String subPattern: outStars) {
  24.             for (int i = 0; i < text.length(); i++) {
  25.                 if (checkVaildFromStart(text.substring(i), subPattern)) {
  26.                     return true ;
  27.                 }
  28.             }
  29.         }
  30.         return false ;
  31.     }

  32.     private ArrayList<String> getPossibleOutStarStrings(String []arrSplit, int maxSize, int startIndex) {
  33.         ArrayList<String> res = new ArrayList<>() ;
  34.         if(arrSplit.length - startIndex == 1) {
  35.             res.add(arrSplit[startIndex]) ;
  36.             return res ;
  37.         }
  38.         for (String rest: getPossibleOutStarStrings(arrSplit, maxSize, startIndex + 1)) {
  39.             // 0 - maxSize
  40.             String currentStr = arrSplit[startIndex] ;
  41.             String first, second ;
  42.             if (currentStr.length() == 1) {
  43.                 first = "" ;
  44.                 second = currentStr ;
  45.             }else {
  46.                 first = currentStr.substring(0, currentStr.length()-2) ;
  47.                 second = currentStr.charAt(currentStr.length() - 1) + "" ;
  48.             }
  49.             for (int i =0; i<=maxSize; i++) {
  50.                 String repeatSecond = "" ;
  51.                 for (int j = 1; j <= i; j ++) {
  52.                     repeatSecond += second ;
  53.                 }
  54.                 res.add(first + repeatSecond + rest);
  55.             }
  56.         }

  57.         return res;
  58.     }

  59.     private boolean checkVaildFromStart(String subText, String pattern) {
  60.         // pattern could contains the char wailcard, and check from the first character
  61.         // abaedaeda ab.e
  62.         if (subText.length() < pattern.length()) {
  63.             return false ;
  64.         }
  65.         for (int i = 0; i < pattern.length(); i ++) {
  66.             if (pattern.charAt(i) != '.' && pattern.charAt(i) != subText.charAt(i)) {
  67.                 return false ;
  68.             }
  69.         }
  70.         return true ;
  71.     }

  72.     public static void main(String[] args) {
  73.         Regex obj = new Regex() ;
  74.         System.out.println(obj.isMatch("aabccccd", ".*")) ;
  75.     }
  76. }
复制代码



补充内容 (2018-10-23 08:20):
代码也太长了,需要改进一下,而且时间复杂度太高这题
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-9-24 06:17:59 | 只看该作者
全局:
tall_cool_13 发表于 2018-9-24 06:16
做了一题Regular Expression Match

Basic Regex Parser

如果单纯的整体匹配相对而言还好做,但是如果是partial 匹配的就比较麻烦了,想一遍写对也不容易,我这题写了一个小时,然后来回思考了几遍才提交
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-9-24 14:40:50 | 只看该作者
全局:
又做了一个一下entire的题目,发现思路容易但是也容易写错,花了将近80分钟也提交成功,马蛋

  1. public class Regex2 {

  2.     private boolean isMatch(String text, String pattern) {
  3.         // special cases
  4.         if (pattern.isEmpty()) {
  5.             return text.isEmpty() ;
  6.         }

  7.         // pattern is not empty
  8.         if (text.isEmpty()) {
  9.             // special cases, "" => c*b*d* 这个特殊情况也没有考虑
  10.             if (pattern.length() % 2 == 1) {
  11.                 return false ;
  12.             }
  13.             for (int i = 0; i < pattern.length(); i ++) {
  14.                if (i % 2 == 1) {
  15.                    if (pattern.charAt(i) != '*') {
  16.                        return false ;
  17.                    }
  18.                }
  19.             }
  20.             return true ;
  21.         }

  22.         if (pattern.equals(".*")) {
  23.             return true ;
  24.         }

  25.         if (pattern.length() == 1) {  // text == 1的情况还是比较复杂
  26.             if (text.length() == 1) {
  27.                 if (text.equals(pattern) || pattern.equals(".")) {
  28.                     return true ;
  29.                 }
  30.             }
  31.             return false ;
  32.         }

  33.         if (pattern.charAt(1) != '*') {
  34.             if (text.charAt(0) == pattern.charAt(0) || pattern.charAt(0) == '.') {
  35.                 return isMatch(text.substring(1), pattern.substring(1)) ;
  36.             } else {
  37.                 return false ;
  38.             }
  39.         } else {
  40.             if (pattern.charAt(0) == '.') {
  41.                 return isMatch(text.substring(1), pattern) || isMatch(text, pattern.substring(2)) ;
  42.             }
  43.             if (pattern.charAt(0) != text.charAt(0)) {
  44.                 return isMatch(text, pattern.substring(2)) ;
  45.             } else {
  46.                 return isMatch(text.substring(1), pattern) || isMatch(text, pattern.substring(2)) ;
  47.             }
  48.         }
  49.     }


  50.     public static void main(String[] args) {
  51.         Regex2 obj = new Regex2() ;
  52.         //System.out.println(obj.isMatch("aa", "a")) ;
  53.         //System.out.println(obj.isMatch("aa", "a*")) ;
  54.         //System.out.println(obj.isMatch("ab", ".*")) ;
  55.         //System.out.println(obj.isMatch("aab", "c*a*b")) ;
  56.         //System.out.println(obj.isMatch("mississippi", "mis*is*p*.")) ;
  57.         System.out.println(obj.isMatch("", "e*")) ;
  58.     }
  59. }
复制代码
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-9-24 14:42:20 | 只看该作者
全局:
发现代码写完以后可以再优化一把代码,让代码更加简洁
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-9-25 06:23:17 | 只看该作者
全局:
气煞我也,花了一个小时写好了,居然超时了
https://leetcode.com/problems/online-election/description/
  1. import copy
  2. class TopVotedCandidate(object):
  3.     def __init__(self, persons, times):
  4.         """
  5.         :type persons: List[int]
  6.         :type times: List[int]
  7.         """
  8.         self.persons = persons
  9.         self.times = times

  10.         diffs = []
  11.         cur_diff = {}  # person_id => [cnt, last_idx]
  12.         for idx, time in enumerate(self.times):
  13.             if self.persons[idx] in cur_diff:
  14.                 cur_diff[self.persons[idx]] = [cur_diff[self.persons[idx]][0] + 1, idx]
  15.             else:
  16.                 cur_diff[self.persons[idx]] = [1, idx]
  17.             diffs.append(copy.deepcopy(cur_diff))
  18.         self.diffs = diffs

  19.     def q(self, t):
  20.         """
  21.         :type t: int
  22.         :rtype: int
  23.         """
  24.         # get the leading vote
  25.         # find the nearest time idx
  26.         idx = self.getNearTimeIdx(0, len(self.times) - 1, t)
  27.         cur_diff = self.diffs[idx]

  28.         max_cnt = -1
  29.         max_idx = -1
  30.         res_id = -1
  31.         for person_id, v in cur_diff.items():
  32.             cnt = v[0]
  33.             last_idx = v[1]
  34.             if cnt > max_cnt:
  35.                 res_id = person_id
  36.                 max_cnt = cnt
  37.                 max_idx = last_idx
  38.             elif cnt == max_cnt:
  39.                 if last_idx > max_idx:
  40.                     res_id = person_id
  41.                     max_cnt = cnt
  42.                     max_idx = last_idx
  43.         return res_id

  44.     def getNearTimeIdx(self, low, high, time):
  45.         if low >= high:
  46.             return low

  47.         if high - low == 1:
  48.             if self.times[high] == time:
  49.                 return high
  50.             elif self.times[high] > time:
  51.                 return low
  52.             else:
  53.                 return high

  54.         mid = int((low + high) / 2)
  55.         if self.times[mid] == time:
  56.             return mid
  57.         elif self.times[mid] > time:
  58.             return self.getNearTimeIdx(low, mid - 1, time)
  59.         else:
  60.             return self.getNearTimeIdx(mid, high, time)


  61. if __name__ == "__main__":
  62.     obj = TopVotedCandidate([0, 1, 0, 1, 1], [24, 29, 31, 76, 81])
  63.     for t in [28, 24, 29, 77, 30, 25, 76, 75, 81, 80]:
  64.         print obj.q(t)
复制代码

补充内容 (2018-10-23 08:21):
Leetcode 911
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-9-25 06:27:22 | 只看该作者
全局:
优化了一个版本, 终于通过了
  1. import copy
  2. class TopVotedCandidate(object):
  3.     def __init__(self, persons, times):
  4.         """
  5.         :type persons: List[int]
  6.         :type times: List[int]
  7.         """
  8.         self.persons = persons
  9.         self.times = times

  10.         diffs = []
  11.         cur_diff = {}  # person_id => [cnt, last_idx]
  12.         for idx, time in enumerate(self.times):
  13.             if self.persons[idx] in cur_diff:
  14.                 cur_diff[self.persons[idx]] = [cur_diff[self.persons[idx]][0] + 1, idx]
  15.             else:
  16.                 cur_diff[self.persons[idx]] = [1, idx]
  17.             max_cnt = -1
  18.             max_idx = -1
  19.             res_id = -1
  20.             for person_id, v in cur_diff.items():
  21.                 cnt = v[0]
  22.                 last_idx = v[1]
  23.                 if cnt > max_cnt:
  24.                     res_id = person_id
  25.                     max_cnt = cnt
  26.                     max_idx = last_idx
  27.                 elif cnt == max_cnt:
  28.                     if last_idx > max_idx:
  29.                         res_id = person_id
  30.                         max_cnt = cnt
  31.                         max_idx = last_idx
  32.             diffs.append(res_id)
  33.         self.diffs = diffs

  34.     def q(self, t):
  35.         """
  36.         :type t: int
  37.         :rtype: int
  38.         """
  39.         # get the leading vote
  40.         # find the nearest time idx
  41.         idx = self.getNearTimeIdx(0, len(self.times) - 1, t)
  42.         return self.diffs[idx]

  43.     def getNearTimeIdx(self, low, high, time):
  44.         if low >= high:
  45.             return low

  46.         if high - low == 1:
  47.             if self.times[high] == time:
  48.                 return high
  49.             elif self.times[high] > time:
  50.                 return low
  51.             else:
  52.                 return high

  53.         mid = int((low + high) / 2)
  54.         if self.times[mid] == time:
  55.             return mid
  56.         elif self.times[mid] > time:
  57.             return self.getNearTimeIdx(low, mid - 1, time)
  58.         else:
  59.             return self.getNearTimeIdx(mid, high, time)
复制代码
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-9-25 06:44:07 | 只看该作者
全局:
刷了一道medium题,https://leetcode.com/problems/top-k-frequent-elements/description/,比较简单,采用计数排序的方式
  1. class Solution(object):   
  2.     def topKFrequent(self, arr, k):
  3.         h = {}
  4.         for i in arr:
  5.             h[i] = h[i] + 1 if i in h else 1

  6.         # sort by values
  7.         tag = []
  8.         for _ in range(0, len(arr)):
  9.             tag.append([])
  10.         for kk, vv in h.items():
  11.             tag[len(arr) - vv].append(kk)

  12.         res = []
  13.         for keys in tag:
  14.             for key in keys:
  15.                 res.append(key)
  16.                 k = k - 1
  17.                 if k == 0:
  18.                     return res
  19.         return res

  20.         
复制代码
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-9-25 06:54:23 | 只看该作者
全局:
写了一个LIS,刚学动态规划的时候的入门题目
  1. class Solution(object):
  2.     def lengthOfLIS(self, nums):
  3.         """
  4.         :type nums: List[int]
  5.         :rtype: int
  6.         """
  7.         res = []
  8.         for num in nums:
  9.             m_length = 1
  10.             for idx, mx in enumerate(res):
  11.                 if nums[idx] < num:
  12.                     m_length = mx + 1 if mx + 1 > m_length else m_length
  13.                     
  14.             res.append(m_length)
  15.         
  16.         mmax_length = 0
  17.         for m_length in res:
  18.             mmax_length = m_length if m_length > mmax_length else mmax_length
  19.         
  20.         return mmax_length
复制代码
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-9-25 07:00:58 | 只看该作者
全局:
写了个一个easy 刷刷信心,还是easy好写,每次都10分钟写完还一点错都没有
  1. class Solution(object):
  2.     def longestPalindrome(self, s):
  3.         """
  4.         :type s: str
  5.         :rtype: int
  6.         """
  7.         h = {}
  8.         for i in s:
  9.             h[i] = h[i] + 1 if i in h else 1
  10.         
  11.         res = 0
  12.         is_plus = False
  13.         for _, cnt in h.items():
  14.             if cnt > 1:
  15.                 res += (cnt / 2) * 2
  16.                
  17.             if cnt % 2 == 1:
  18.                 is_plus = True
  19.         
  20.         return res + (1 if is_plus else 0)
  21.         
  22.         
复制代码
回复

使用道具 举报

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

本版积分规则

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