131. Palindrome Partitioning (Medium)

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.
A palindrome string is a string that reads the same backward as forward.

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        if len(s)==1:
            return [[s]]
        res = []
        for i in range(1,len(s)):
            head = s[:i]
            tail = s[i:]
          
            if [e for e in head]==[e for e in head][::-1]:
                for rest in self.partition(tail):
                    res.append([head]+rest)
        #check total
        if [e for e in s ]==[e for e in s][::-1]:
            res.append([s])
        
        return res

132. Palindrome Partitioning II （Hard）

Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.

class Solution:
    def minCut(self, s: str) -> int:
        # find all possible palindrome then return 
        mem = dict()
        def palindrom(s):
            if s in mem: return mem[s]
            if len(s)==1:
                return [[s]]
            res = []
            for i in range(1,len(s)):
                head=s[:i]
                tail=s[i:]
                if [e for e in head]==[e for e in head][::-1]:
                    for rest in palindrom(tail):
                        res.append([head]+rest)
            #final test on whole string
            if [e for e in s]==[e for e in s][::-1]:
                res.append([s])
            mem[s]=res
            return res
        
        res = palindrom(s)
        mincut=float('inf')
        for row in res:
            mincut=min(mincut,len(row)-1)
        return mincut
               
#answer way of DP
class Solution:
    def minCut(self, s: str) -> int:
        
        if not s or len(s)==1: return 0
        
        dp=[i for i in range(len(s))]
        
        # 0...ith char cut 
        for mid in range(1,len(s)):
            #case 1 odd len center is at index mid
            start=mid
            end=mid
            while start>=0 and end<len(s) and s[start]==s[end]:
                newcutatend=0 if start==0 else dp[start-1]+1
                dp[end]=min(dp[end],newcutatend)
                start-=1
                end+=1
             
            #case 2  even len center is between mid-1,mid
            start=mid-1
            end=mid
            while start>=0 and end<len(s) and s[start]==s[end]:
                newcutatend=0 if start==0 else dp[start-1]+1
                dp[end]=min(dp[end],newcutatend)
                start-=1
                end+=1
               
            
        return dp[len(s)-1]

class Solution:
    @lru_cache(None)
    def minCut(self, s: str) -> int:

        res = len(s)-1
        for i in range(1,len(s)):
            head = s[:i]
            tail = s[i:]
            if head==head[::-1]:
                res = min(res, 1+self.minCut(tail))
        if s==s[::-1]:res = 0
        return res
                    

直接产生出full list 来计算time limit exceeded。即使加了mem都不行。所以得调整思路。BT无法解决，感觉像DP问题。但没思路。
思路：string expansion+DP , OR RECURSION
string可以从mid的位置做expansion，但odd/even长度expansion初始情况不同， odd时候 start=mid end=mid， enven时候 start=mid-1 end=mid, 定义dp【i】为在0~i包含i位置的string minCut。 则 dp【end】=min（dp【end】，dp【start-1】+1），注意边界情况，如果start==0， dp【end】=dp【end】。

133. Clone Graph （Medium）

Given a reference of a node in a connected undirected graph.
Return a deep copy (clone) of the graph.

"""
# Definition for a Node.
class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []
"""

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node: return node
        
        visited=set()
        map_old2new = dict()
        
        #clone node only
        def walk(node):
            visited.add(node)
            #clone node without neighbors
            new_node = Node(node.val)
            map_old2new[node]=new_node
            for nei in node.neighbors:
                if nei not in visited:
                    walk(nei)
        
        walk(node)
        
        #clone neighbors
        visited=set()
        def walk_nei(node):
            visited.add(node)
            #clone new_node neighbors
            map_old2new[node].neighbors = [map_old2new[nei] for nei in node.neighbors]
            for nei in node.neighbors:
                if nei not in visited:
                    walk_nei(nei)
        
        walk_nei(node)
        
        return map_old2new[node]

134. Gas Station (Medium)

There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations.
Given two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique
Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.

#TLE 用了for break else ...
class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:

    
        for start in range(len(gas)):
            cur = 0
            for i in range(start,start+len(gas)):
                i=i%len(gas)
                cur+=gas[i]
                cur-=cost[i]
                if cur<0:
                    break
            else:
                return start
        
        return -1
            

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        
        #gas = [1,2,3,4,5], cost = [3,4,5,1,2]
        #Start at station 2 (index 2) and fill up with 3 unit of gas. Your tank = 0 + 3 = 3
        #Travel to station 3. Your tank = 3 - 5 + 4 = 2
        #Travel to station 4. Your tank = 2 - 1 + 5 = 6
        #Travel to station 0. Your tank = 6 - 2 + 1 = 5
        #Travel to station 1. Your tank = 5 - 3 + 2 = 4
        #Travel to station 2. Your tank = 4 - 4 + 3 = 3
        
 
     
        length=len(gas)
       
        for start_pos in range(length):
            my_tank=gas[start_pos]
            cur_pos = start_pos
            i=0
            #print('start_pos{} mytank {}'.format(start_pos,my_tank))
            while i<=length:
                i+=1
                travel_to = (cur_pos+1)%length
                my_tank=my_tank-cost[cur_pos]
                if my_tank<=0:
                    if my_tank==0 and i>0 and travel_to==start_pos: return start_pos
                    break
                my_tank+=gas[travel_to]
                #print('travel to {} mytank {}'.format(travel_to,my_tank))
              
                cur_pos=travel_to
                if cur_pos==start_pos:
                    return start_pos
                         
  
        return -1

#answer way of writting
class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        
        n=len(gas)
        total_tank=cur_tank=0
        starting_station=0
        for i in range(n):
            total_tank += gas[i]-cost[i]
            cur_tank+=gas[i]-cost[i]
            if cur_tank<0:
                starting_station=i+1
                cur_tank=0
        
        if total_tank>=0:
            return starting_station
        return -1
            

细心，做判断时候， my_tank - cost[cur_pos] 如果小于0要break的， 只有确认可以到 travel_to时候才能my_tank += gas[traval_to] 但是显然是O（n*n）时间复杂度。 答案是O（N）。思路： 记录total_tank 和 cur_tank, 如果total_tank 小于0 或者cur_tank 小于0都不能成环路。 如果cur_tank 小于0，说明起始点有问题， start_station=i+1 cur_tank=0.

135. Candy (Hard)

There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.

You are giving candies to these children subjected to the following requirements:
Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.
Return the minimum number of candies you need to have to distribute the candies to the children.
Input: ratings = [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

class Solution:
    def candy(self, ratings: List[int]) -> int:
        #[1,0,2]
        # 1 1 1
        # 2 1 2
        
        #[1,2,2]
        # 1 1 1
        # 1 2 1
        
        res = [1]*len(ratings)
        
        hasChanged = True
        while hasChanged:
            hasChanged = False
            for i in range(len(ratings)):
                neigh_left_rating = ratings[i-1] if i-1>=0 else None
                neigh_right_rating = ratings[i+1] if i+1<len(ratings) else None
                if neigh_left_rating is not None and ratings[i]>neigh_left_rating and res[i]<=res[i-1]:
                    hasChanged=True
                    res[i] = res[i-1]+1

                if  neigh_right_rating is not None and ratings[i]>neigh_right_rating and res[i+1] >= res[i]:
                    hasChanged=True
                    res[i] = res[i+1]+1
       
        print(res)
        return sum(res)

#answer way of writting 1）Using two arrays 
class Solution:
    def candy(self, ratings: List[int]) -> int:
        
        left2right = [1]*len(ratings)
        right2left = [1]*len(ratings)
        for i in range(1,len(ratings)):
            if ratings[i] > ratings[i - 1]:
                left2right[i] = left2right[i - 1] + 1
            
        for i in range(len(ratings)-2,-1,-1):
            if ratings[i] > ratings[i + 1]:
                right2left[i] = right2left[i + 1] + 1;
        
        res = 0
        for i in range(len(ratings)):
            res+=max( left2right[i], right2left[i]) 
        
        return res

# answer way of writting： Using one array
class Solution:
    def candy(self, ratings: List[int]) -> int:
        
        candies = [1]*len(ratings)
        for i in range(1,len(ratings)):
            if ratings[i] > ratings[i - 1]:  
                candies[i] = candies[i - 1] + 1
          
        sum = candies[-1]
        
        for i in range(len(ratings)-2,-1,-1):
            if  ratings[i] > ratings[i + 1]:
                candies[i] = max(candies[i], candies[i + 1] + 1)
            
            sum += candies[i];
        
        return sum 
    

hard题目果然有坑，直接做会遇到更新candy数目之后发现之前的res违反了rules 还需要回溯更新。而且即使是brutal force也只写对了一半，没想到用hasChanged Flag，以为过一次就已经得到解了。 O（n）方法 感觉是用stack。但感觉不正确。应该用拆分方法。 答案思路： 1）Using two arrays ：把一个复杂问题分割成2个小问题，单从左向右扫， 做更新使其满足左侧限制，让后从右向左扫。 使其满足右侧条件。最后结果必须满足左右条件，所以取max即可。2）Using one array： 思路和法1相同。

136. Single Number （Easy）

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.
You must implement a solution with a linear runtime complexity and use only constant extra space.
Input: nums = [2,2,1]
Output: 1

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        res = 0
        for n in nums:
            res = res^n
        return res

137. Single Number II (Medium)

Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it.
You must implement a solution with a linear runtime complexity and use only constant extra space.
Input: nums = [2,2,3,2]
Output: 3

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        seen_once = seen_twice = 0
        
        for num in nums:
            # first appearance: 
            # add num to seen_once 
            # don't add to seen_twice because of presence in seen_once
            
            # second appearance: 
            # remove num from seen_once 
            # add num to seen_twice
            
            # third appearance: 
            # don't add to seen_once because of presence in seen_twice
            # remove num from seen_twice
            seen_once = ~seen_twice & (seen_once ^ num)
            seen_twice = ~seen_once & (seen_twice ^ num)

        return seen_once

O1 mem On time 木有思路,要是用set 会violate use only constant extra space. 答案是bit manipulation。

138. Copy List with Random Pointer （Medium）

"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head: return head
        map_old2new = dict()
        # just copy node without random 
        cur=head
        while cur:
            map_old2new[cur] = Node(x=cur.val)
            cur=cur.next
        
        # copy random and next pointers
        cur=head
        while cur:
            map_old2new[cur].next = map_old2new.get(cur.next,None)
            map_old2new[cur].random = map_old2new.get(cur.random,None)
            cur=cur.next
        
        return map_old2new[head]

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':

        #copy node

        cur = head
        while cur:
            curnext = cur.next
            cur.next = Node(cur.val)
            cur.next.next=curnext
            cur=curnext
        
    
        #assign random
        cur = head
        while cur:
            curnextnext = cur.next.next
            cur.next.random = cur.random.next if cur.random else None
            cur=curnextnext

        #delink
        cur=head
        res= head.next if head else None
        #1-1'-2-2'-3-3'...
        while cur:
            curnext = cur.next
            cur.next = cur.next.next if cur.next else None
            cur = curnext
        
        return res

139. Word Break (Medium)

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

class Solution:

    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
       
        mem=dict()
        def helper(s,wordDict):
            if not s: return True
            if s in mem: return mem[s]
            res = False
            for word in wordDict:
                l=len(word)
                if s[:l] == word:
                    res = res or helper(s[l:],wordDict)

            mem[s]=res
            return res
        
        return helper(s,wordDict)
#answer way of writting
class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        
        
        dp[i]= dp[j] and s[j:i] in dic    j<i
        
        """
        dp=[False]*(len(s)+1)
        se=set(wordDict)
        
        for i in range(1,len(s)+1):
            dp[i]=(s[:i] in se)
            for j in range(i):
                if dp[j]:
                    dp[i]=dp[i] or (s[j:i] in se)
        #print(dp)
        return dp[-1]

用了recursion+mem ，答案dp，异曲同工。

140. Word Break II （Hard）

Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.
Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
Output: ["cats and dog","cat sand dog"]

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        
        
        def helper(s,wordDict):
            res = []
            for word in set(wordDict):
                l=len(word)
                if s[:l] in set(wordDict):
                    head = s[:l]
                    tail = s[l:]
                    if not tail:
                        res.append([head])
                    else:
                        for rest in helper(tail,wordDict):
                            res.append([head]+rest)
            return res
        
        res = set()
        for row in  helper(s,wordDict):
            res.add(' '.join(row))
        return list(res)

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        
        result = []
     
        def helper(s,tmp):
            if not s: result.append(tmp[:])
            

            for word in wordDict:
                temp = tmp[:]
                l=len(word)
                if s[:l]==word:
                    temp.append(s[:l])
                    ss=s[l:]
                    helper(ss,temp)
             
        helper(s,[])
        return [' '.join(li) for li in result]

just backtracking.