Leetcode write up for 1-30 problems

1, two sum:

从一个list中找到两个数的和达到target。如7+2=9. 
尝试：
  • 为了降低时间复杂度，使用target减当前的数，再去里面找有没有差值。
一个循环搞定，但是要记得我们取的是index，所以要key是值，value是index。
class Solution(object):
    def twoSum(self, nums, target):
        L = len(nums)
        tmp = {}
        for i in range(L):
            mid = target  - nums[i]
            if mid in tmp:
                return [i,tmp[mid]]
            if mid not in tmp:
                tmp[nums[i]] = i


2. Add Two Numbers

先让root， curr都为一个空指针，curr会移动并且更新，root也会更新，
但是始终还在第一个点。
curr.next = curr = ListNode(sumval % 10), curry.next 先赋值为ListNode(sumval % 10)，
然后curr再赋值ListNode(sumval % 10)。
已存在的listnode，要用 L=L.next往下延续，但是新的node不能，因为next本来就为none.
class Solution:
    def addTwoNumbers(self, l1, l2):
        S = 0
        root = curr = ListNode(0)
        while l1 or l2 or S:
            if l1: S+=l1.val; l1=l1.next
            if l2: S+=l2.val; l2=l2.next
            curr.next = ListNode(S % 10)
            curr =  curr.next
            S //= 10
        return root.next

3, Longest Substring Without Repeating Characters
如果遇到相连的，start（index）的位置就从当前这个开始
如果第一个和最后一个重复了，index就往后移一个，并把最后一个加进来。
class Solution(object):
    def lengthOfLongestSubstring(self, s):
        sub = ""
        max_len = cur_len = 0
        
        for ch in s:
            if ch in sub:
                index = sub.index(ch)
                sub = sub[index+1:]
                cur_len = len(sub)
            sub += ch
            cur_len += 1
            max_len=max(max_len,cur_len)
        return max_len

4，Roman to Integer
先把所有的可能都写进去。
 res += dic_map[s[i:i+2]]. while循环判断 i 到 i+1这个组合在不在我们的字典里，所以这个判断只能是i<len-1,因为一旦i 直接取了 最后一个，i+1 的时候就会out of range。
然后其他情况都可以直接加当前值
class Solution(object):
    def romanToInt(self, s):
        res= 0
        i=0
        dict_map = {'M': 1000, 'D': 500, 'C': 100, 'CM': 900, 'CD': 400, 'L': 50, 'X': 10, 'XC': 90, 'XL': 40, 'V': 5,
                    'I': 1, 'IX': 9, 'IV': 4}
        while i < len(s):
            if i < len(s)-1 and s[i:i+2] in dict_map:
                res+= dict_map[s[i:i+2]]
                i = i+2
            else:
                res += dict_map[s[i]]
                i= i+1
        return res



5. Longest Palindromic Substring
我们要用dp算法，所有可能都要考虑到，所以是一个二维数组，所有的先赋值为False。
自己到自己是一个palindromic，先赋值为True。
从后往前，比如我们一个ababa五个数字的，先判断最后两个是不是相等。
先判断所有的最近的两个，再往外扩散。
(3, 4)
(2, 3)
(2, 4)
(1, 2)
(1, 3)
(1, 4)
(0, 1)
(0, 2)
(0, 3)
(0, 4)
class Solution(object):
    def longestPalindrome(self, s):
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        ans = ''
        for i in range(n):
            dp[i][i] = True
            ans = s[i]
        for start in range(n-2, -1,-1):
            for end in range(start+1,n):
                if s[start] == s[end]:
                    if end - start ==1 or dp[start+1][end-1]:
                        dp[start][end] = True
                        if len(ans) < end -start+1:
                            ans = s[start:end+1]
        return ans

6. ZigZag Conversion
只用一维数组就能搞定。每一行作为一个字符串，step是向上走或者向下走。
如果到底了，就向上走，不然就继续向下。

class Solution(object):
    def convert(self, s, numRows):
        if numRows == 1 or numRows >= len(s):
            return s
        L = [''] * numRows
        index, step = 0, 1 #step1 means go down, step-1 means go up
        for x in s:
            L[index] += x #the first number
            if index == 0:
                step = 1
            elif index == numRows -1: #if the index to the last row
                step = -1 #it will go up
            index += step #move like Z
        return ''.join(L)



7，reverse integer
直接使用s[::-1]， python的slice来reverse，注意正负数，和32位的判断，
被反的数和反的结果都要判断。注意这个要先转换为str才能reverse，
转完再转换为int。

class Solution(object):
    def reverse(self, x):

        if x > 2** 31 -1 or x< -(2**31):
            return 0
        flag =1
        if x < 0:
            flag = -1      
        x = str(abs(x))
        x  =  x[::-1]
        ans = abs(int(x)) * flag
        if ans > 2** 31 -1 or ans < -(2**31):
            return 0
        else:
            return ans


8. String to Integer (atoi)
hasSpace and string[_].isdigit() == False,先计算 string[_].isdigit() == False 再计算and。
所以默认刚开始的时候是不会break。如w5，就会把w5都收入。 如w5w，只会收到w5，
然后break掉。
try except遇到字母就会捕捉到因为字符在int转换的时候被捕捉，然后返回0.
class Solution(object):
    def myAtoi(self, string):
        list1 = []
        hasSpace = False
        
        for _ in range (0, len(string)):
            
            if hasSpace and string[_].isdigit() == False:
                break
            elif string[_] != ' ' or string[_] == '-' or string[_] == '+' or string[_].isdigit():
                hasSpace = True
                list1.append(string[_])    
        try:
            if int(''.join(list1)) > (2 ** 31) - 1 or int(''.join(list1)) < (2 ** 31) * -1:
                if list1[0] == '-':
                    return (2 ** 31) * -1
                else:
                    return (2 ** 31) - 1
        except ValueError:
            return 0
        return int(''.join(list1))

9, Palindrome Number
直接reverse。注意负数直接return False。
class Solution(object):
    def isPalindrome(self, x):
        if x <0:
            return False
        else:
            re = int(str(x)[::-1])
            if re == x:
                return True
            else:
                return False

11, Container With Most Water
Two pointer approach. 两边往里来算最大面积,每种情况都遍历。

class Solution(object):
    def maxArea(self, height):
        S = 0
        i = 0
        j = len(height) - 1
        while(i< j):
            S =  max (S, min(height[i],height[j])*(j-i))
            if height[i] < height[j]:
                i += 1
            else:
                j -= 1
        return S

12. Integer to Roman
self的使用，会无限迭代并覆盖。
class Solution(object):
    dic = {
        0:'',1:'I',2:'II',3:'III',4:'IV',5:'V',6:'VI',7:'VII',8:'VIII',9:'IX',
    10:'X',20:'XX',30:'XXX',40:'XL',50:'L',60:'LX',70:'LXX',80:'LXXX',90:'XC',
    100:'C',200:'CC',300:'CCC',400:'CD',500:'D',600:'DC',700:'DCC',800:'DCCC',900:'CM',
    1000:'M',2000:'MM',3000:'MMM'
    }
    def intToRoman(self, num):
        return self.dic[num//1000*1000] + self.dic[num%1000//100*100] +self.dic[num%100//10*10] + self.dic[num%10]
       

14,Longest Common Prefix

初始第一个为被比较的，while循环来更新最短pref,每次缩小一个。
class Solution(object):
    def longestCommonPrefix(self, strs):
        if not strs:
            return ""
        pref = strs[0]
        for c in strs[1:]:
            while c[: len(pref)] != pref and pref:
                
                pref = pref[:len(pref)-1]
                if not pref:
                    break
        return pref

15. 3Sum
nums不能set()，因为（-1,-1,2）这种情况会被筛选掉。
set()加入要用add，而不是append。
sort先排序，一旦取的第一个数大于0 了，后面就不用看了。
tmp的set应该在i取了之后再初始化，不然会对应不上，别对i取了其他的b和c。
class Solution(object):
    def threeSum(self, nums):
        n = len(nums)
        nums.sort()
        res = set()
        if n< 3:
            return []
        for i in range(n-2):
            if nums[i] >0:
                break
            tmp = set()
            for j in range(i+1,n):
                b = nums[j]
                c = -nums[i]-b
                if b not in tmp:
                    tmp.add(c)
                else:
                    res.add((nums[i],b,c))
        return res

16. 3Sum Closest
为什么要返回target - diff，而不直接返回sum，因为我们要取的是最小的，不是当前的。
class Solution(object):
    def threeSumClosest(self, nums, target):
        diff = 10**4
        nums.sort()
        for i, num in enumerate(nums):
            lo = i +1
            hi = len(nums) -1
            while(lo < hi):
                sum = num + nums[lo]+ nums[hi]
                if abs(target -sum ) < abs(diff):
                    diff = target -sum
                if sum < target :
                    lo +=1
                if sum > target:
                    hi -=1
                if diff == 0:
                    break
        return target - diff

17. Letter Combinations of a Phone Number
Itertools.product 显示需要带list才能显示，如果是多维数组，则需要带*才能组合。
[phonepad[int(d)] for d in digits] 相当于取了（’abc’,’def’）并放在了同一个数组。
>>> A = [[1,2,3],[3,4,5]]
>>> print list(product(*A))
[(1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 3), (3, 4), (3, 5)]
class Solution:
    def letterCombinations(self, digits):
        if not len(digits): return ""
        phonepad = {2 : "abc", 3 : "def", 4 : "ghi", 5 : "jkl", 6 : "mno", 7 : "pqrs", 8 : "tuv", 9 : "wxyz"}
        d_list = []
        
        d_list = list(itertools.product(*[phonepad[int(d)] for d in digits], repeat=1))
        res = []
        for d in d_list:
            res.append(''.join(d))
        return res

18. 4Sum
比较有意思的一道题，把第四个数当成了target。
为了不重复计算，if i == 0 or nums[i]!= nums[i-1]:，
当取的第一个数和前一个数相等时就不算了。
while l < r and nums[l] == nums[l+1]: l+=1
 while l < r and nums[r] == nums[r-1]: r-=1
取第二个和第三个数时，和前一个计算过的相等也不算了。
class Solution(object):
    def threeSum(self,nums, target):
        res = []
        nums.sort()
        for i in range(len(nums)-2):
            l = i+1
            r = len(nums) -1
            t = target - nums[i]
            if i == 0 or nums[i]!= nums[i-1]:
                while(l<r):
                    s = nums[l] + nums[r]
                    if s == t:
                        res.append([nums[i],nums[l],nums[r]])
                        while l < r and nums[l] == nums[l+1]: l+=1
                        while l < r and nums[r] == nums[r-1]: r-=1
                        l+=1; r-=1;
                    elif s < t:
                        l +=1
                    else:
                        r -=1
        return res                         
        
    def fourSum(self, nums, target):
        res = []
        nums.sort()
        for i in range(len(nums)-3):
            if i == 0 or nums[i] != nums[i-1]:
                threeres = self.threeSum(nums[i+1:],target- nums[i])
                for item in threeres:
                    res.append([nums[i]]+item)
        return res

19. Remove Nth Node From End of List
List 相等的话是会互相影响的，修改其中一个，其他的也会被改变。
while fast.next的意思是fast始终比slow多走n步，所以最后fast走完的时候，
slow还剩两步，然后把slow的node指向隔一个的。
class Solution:
    def removeNthFromEnd(self, head, n):
        fast = slow = head
        
        for _ in range(n):
            fast = fast.next # remove the n nodes from the first
        if not fast: # that means the last one we remove is the head
            return head.next # then return the list without the header
        while fast.next:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return head

20，Valid Parentheses
使用消消乐的方式来消除，一旦找到两个一对，就替换为空。判断语句和return的连用方式。
class Solution(object):
    def isValid(self, s):
        while "()" in s or "{}" in s or '[]' in s:
            s = s.replace("()", "").replace('{}', "").replace('[]', "")
        return s == ''

22. Generate Parentheses
递归，把所有可能都考虑进去，一旦右边比左边大了就停止，防止先右边再左边。
一旦都等于0了，就把结果append进去。如果left比0小了，也不符合要求return
(类似于break,但是不能用break，会把所有的情况都终止掉)单独一个return不反回值，
只是终止当前这个函数。
每种情况都带current，不用公用current。
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        if not n:
            return []
        output=[]
        def generate(left,right,current=''):
            if right<left:
                return
            if not right and not left:
                output.append(current)
            if left < 0:
                return
            generate(left-1,right, current+'(')
            generate(left,right-1, current+')')
        generate(left=n,right=n)
        return output


23. Merge k Sorted Lists
最重要的是如何转换列表为链表。
class Solution(object):
    def mergeKLists(self, lists):
        root = ListNode(0)
        tmp = []
        for i in lists:
            while i:
                tmp.append(i.val)
                i =  i.next
        tmp.sort()
        p = root
        for i in range(len(tmp)):
            p.next = ListNode(tmp[i])
            p = p.next
        return root.next

24. Swap Nodes in Pairs
第一个为0 ，不是nodelist里面的成员，如果0是里面的成员会断连接。
0—>1—>2—>3会变成
0—>2—>1—>3
然后再以1为原来的0元素来修改后面的两个数组位置。
p0, p1, p2 = p1, p1.next, p1.next.next 不能修改为：
                p0 = p1
                p1 = p1.next
                p2 = p1.next.next
class Solution:
    # @param a ListNode
    # @return a ListNode
    def swapPairs(self, head):
        p1 = guard = ListNode(0)
        guard.next = head
        
        try:
            while True:
                p0, p1, p2 = p1, p1.next, p1.next.next
                p0.next, p1.next, p2.next = p2, p2.next, p1
        except:
            return guard.next

25. Reverse Nodes in k-Group
注意多变量同时赋值，相当于同时改变，没有先后关系。
listnode有点继承的感觉，继承的修改，被继承的也会被修改，但是被继承的head不变，
只是后面的指向可能会改变。
比如case：1->2->3->4->5->6 and k = 3

dummy = jump = ListNode(0) 
the head of jump and dummy are both 0
dummy.next = l = r = head   
dummy turns to 0->1->2->3->4->5->6, l is 1->2->3->4->5->6, r is 1->2->3->4->5->6
while r and count < k:   r = r.next
r turns to 4->5->6
pre, cur = r, l.  
pre is 4->5->6, cur = 1->2->3->4->5->6.
for _ in range(k): 
    cur.next, cur, pre = pre, cur.next, cur  
pre turns to 3->2->1->4->5->6, cur turns to 4->5->6. At this time, the head of ‘l’ is still 1,
 but cur has been changed, so l turns to be 1->4->5->6, r’s head is still 4,
 so r is 4->5->6 which is part of pre.
jump.next, jump, l = pre, l, r  
jump.next = pre so that jump turns to 0->3->2->1->4->5->6, then jump = l ：
 jump turns to 1->4->5->6.  l = r then l turns to 4->5->6
class Solution(object):
    def reverseKGroup(self, head, k):
        dummy = jump = ListNode(0)
        dummy.next = l = r = head
        while True:
            count = 0
            while r and count < k:   # use r to locate the range
                r = r.next
                count += 1
            if count == k:  # if size k satisfied, reverse the inner linked list
                pre, cur = r, l
                for _ in range(k):
                    cur.next, cur, pre = pre, cur.next, cur  # standard reversing
                jump.next, jump, l = pre, l, r  # connect two k-groups
            else:
                return dummy.next


29. Divide Two Integers
class Solution(object):
        def divide(self, a, b):
            sig = (a < 0) == (b < 0)
            a, b, res = abs(a), abs(b), 0
            res = a // b
            return min(res if sig else -res, 2147483647)




Popular posts from this blog

Phonebook - Hack the box Write up -- Web LDAP injection

Image
 0x00 Problem  0x01 Check the vulnerability When we see the login form on the website, it might be command injection, SQL injection, LDAP injection.  We can see that this need us to login with workstation username, it might be LDAP injection. 0x02 LDAP injection payload Here is the basic LDAP injection payload. We can check the vulnerability. user=*)(& password=*)(& --> (&(user=*)(&)(password=*)(&))  After we type it, we found the response shows successful, and return a page has search box. Then we type a character in the search box, and it returns some user phonebook information. I tried 'flag', 'HTB', it doesn't find any results. Then we try to find user 'Reese', but the information doesn't look like flag.   0x03 Locate the flag  Then we change our payload to check if the password is the flag. user=Reese password=HTB*)(& --> (&(user=Reese)(password=HTB*)(&  It can also return to the search page which means it...
Read more

wafwaf -- Hack The Box -- Web SQL injection

Image
0x00 Problem 0x01 Check the Source Code We open the website and only see the source code on the website. As we can see, there is a WAF will filter some characters and words, that means the normal injection will not work. However, we can see, there is a json_decode() function will decode JSON data, that means the data can be accepted should be JSON format.  The example JSON format data is like: /u0074, /u0075. In addition, there is a "php://input",  accesses the read-only stream of the requested raw data, executing the data in the post request as PHP code. 0x02 Local Test We can launch an Apache server to test it. I copy the source code and make a little change to test this. This file is in /var/www/html. We will construct the data first. This time I use 'select' as an example. The word transfer to ASCII, then to hex, then replace the '\0x' as '\u00'. This can be test in the browser console. At the end, we can test it with curl . As we can see, the SQL...
Read more

Cheat sheet for security+

Image
Malware virus: need people action to execute and spread. Hoax: trick the victim to infect, like game. worms: spread and execute without humman  trojans: can get remote control. RAT(remote access Trojan) ransomware: take control of your computer system, pay for unlock, most time will not unlock if you pay spyware: audit the callender, website history and other actions. rootkit: a type of backdoor, software design to administrative level control or root priviledge without detection. use DLL injection. malicious code inserted into a running process or kernel-mode device drvier. intercept calls and redirect to the malicous code. spam: CAN-Spam Act law to stop relaying send out email through other's mail server. Spim(instant message) like chat, text message.
Read more