Leetcode 题型总结 - Stone's Blog

总结

[toc]

https://img-blog.csdnimg.cn/2020121721064966.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pzdG9uZTE=,size_16,color_FFFFFF,t_70

Leetcode3 无重复的最长子串

这几天也写了好多遍了。发现用typora写题还行。一本质上抑制了看题解的冲动。二还可以这碎碎念..

就是python缩进太蛋疼了

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

大体思路:滑动窗口双指针,当然还可以用哈希表优化优化，有点懒得搞。还是搞搞吧。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s: return 0
        if len(s)==1: return 1
        left=right=0
        ans = float(-inf)
        while right !=len(s)-1:
            # 
            right+=1
            # 收缩
            while s[right] in s[left:right]:
                left+=1
            ans =max(ans,right-left+1)
        return ans

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:return 0 
        if len(s)==1:return 1 
        left=right =0
        ret = 0
        window={}
        while right!=len(s):
            c=s[right]
            right+=1
            window[c]=window.get(c,0)+1
            
            while window[c]>1:
                d = s[left]
                left+=1
                window[d]-=1

            ret= max(ret,right-left)
        return ret

好像也没优化到哪去，反而代码还复杂了…

LEETCODE25.K个一组翻转链表

有时间再写吧…

重写已经忘的差不多了。

class Solution:
    def threeSum(self, nums: [int]) -> [[int]]:
        nums.sort()
        res, k = [], 0
        # 操作都在循环里面
        for i in range(0, len(nums) - 2):
            if nums[i] > 0: break
            if i > 0 and nums[i] == nums[i - 1]: continue
            j, k = i + 1, len(nums) - 1
            while j < k:
                s = nums[i] + nums[j] + nums[k]
                if s < 0:
                    j += 1
                    while j < k and nums[j] == nums[j - 1]: j += 1
                elif s > 0:
                    k -= 1
                    while j < k and nums[k] == nums[k + 1]: k -= 1
                else:
                    res.append([nums[k], nums[i], nums[j]])
                    j += 1
                    k -= 1
                    while j < k and nums[j] == nums[j - 1]: j += 1
                    while j < k and nums[k] == nums[k + 1]: k -= 1
        return res

LEETCODE15.三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

大体思路就是先排个序然后一个for循环接双指针麻烦点在于不重复还有可以跳过的情况

去重的问题忘了咋解决了.. 去重的代码有四处，太逆天了…

后面的代码倒也能够理解。看一看与下面一个值是否相同，相同直接跳

class Solution:
    def threeSum(self, nums: [int]) -> [[int]]:
        nums.sort()
        res, k = [], 0
        # 操作都在循环里面
        for i in range(0, len(nums) - 2):
            if nums[i] > 0: break
            if i > 0 and nums[i] == nums[i - 1]: continue
            j, k = i + 1, len(nums) - 1
            while j < k:
                s = nums[i] + nums[j] + nums[k]
                if s < 0:
                    j += 1
                    while j < k and nums[j] == nums[j - 1]: j += 1
                elif s > 0:
                    k -= 1
                    while j < k and nums[k] == nums[k + 1]: k -= 1
                else:
                    res.append([nums[k], nums[i], nums[j]])
                    j += 1
                    k -= 1
                    while j < k and nums[j] == nums[j - 1]: j += 1
                    while j < k and nums[k] == nums[k + 1]: k -= 1
        return res

果然还是要自己写一遍自己写一遍就发现错误百出

LEETCODE42.接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

经典题目。思路就是按列遍历左边找最高的，左边找最高的如果低于当前高度。那么这一格就集不到水。然后又根据木桶效应。

class Solution:
    def trap(self, height: List[int]) -> int:
      ans=0
      for i in range(1,len(height)-1):
          left_max=max(height[:i])
          right_max=max(height[i+1:])
          if left_max<height[i] or right_max<height[i]:continue
          ans += min(left_max,right_max)
      return ans

这么看这代码满打满算才10行

LEETCODE415.字符串相加

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。

你不能使用任何內建 BigInteger 库，也不能直接将输入的字符串转换为整数形式

但是可以int()其中的字符..

class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        i=len(num1)-1
        j=len(num2)-1
        carry=0
        ans=''
        while i>=0 or j>=0:
            n1 = int(num1[i]) if i>=0 else 0
            n2 = int(num2[j]) if j>=0 else 0
            tmp = n1+n2+carry
            carry = tmp//10
            ans = str(tmp%10)+ans
            i-=1
            j-=1
      
        return "1"+ ans if carry else ans

这题还挺有意思的

LEETCODE103.二叉树的锯齿层次遍历

给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

大体思路:

先完成层次遍历再加一个flag?

flag只控制加入temp_list的顺序…跟我理解的题意不太一样。其实这样感觉可以逆转一下也一样的。

class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        ans = []
        if not root:return []
        flag=1
        temp = collections.deque()
        temp.append(root)
        while len(temp)!=0:
            n = len(temp)
            temp_list=collections.deque()
            for i in range(n):
                node = temp.popleft()
                //就记住这个flag就行
                //
                if flag==1:
                    temp_list.append(node.val)
                else:
                    temp_list.appendleft(node.val)

                if node.left!=None:temp.append(node.left)
                if node.right!=None:temp.append(node.right)            

            flag=(-1)*flag
            ans.append(list(temp_list))
        return ans

LEETCODE.121 买卖股票的最佳时机

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。

注意：你不能在买入股票前卖出股票。

这题是真的经典覃超这个讲的真的挺明白的。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        
        if n==0:return 0
        
        dp=[[0 for _ in range(3)] for i in range(n)]
        
        # 0代表手上没有股票 1代码手上有股票 2代码卖出股票
        dp[0][0]=0
        dp[0][1]=-price[0]
        dp[0][2]=0
       	ans =0 
        for i in range(1,n):
        	dp[i][0]=dp[i-1][0]
          dp[i][1]=max(dp[i-1][1],dp[i-1][0]-price[i])
          dp[i][2]=dp[i-1][1]+price[i]
          ans = max(ans,dp[i][0],dp[i][1],dp[i][2])
        return ans

Leetcode124.二叉树的最大路径和

给定一个非空二叉树，返回其最大路径和。本题中，路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

不是很能理解

好像大概又能理解了。

class Solution:
    def __init__(self):
        self.maxSum = float("-inf")
    def maxPathSum(self, root: TreeNode) -> int:
   			def maxGain(node)->int:
      		if not node:return 0
          
          left=max(0,maxGain(root.left))
          right=max(0,maxGain(root.right))
          
					priceNew = root.val +left + right
          self.maxSum=max(self.maxSum,spriceNew
       	
        return node.val+max(left,right)
        
        maxGain(root)
        return self.maxSum

LEECODE31.下一个排列

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须原地修改，只允许使用额外常数空间。

今天想办法搞定。

先试着理解题意吧。举几个例子看看。

1->2->4->5,这一段是升序的，也就是5421已经是最大数，不存在比它大的组合，

递增这样的就是字典序最大。因为啥呢。反正就是和真实大小相反。

这个题目本身不难，关键是理解题意，我们以一个例子来分析，给定325421，求其下一个比它大的数，怎么办呢？我们应该从最低位开始，1->2->4->5,这一段是升序的，也就是5421已经是最大数，不存在比它大的组合，我们继续找，1->2->4->5->2，出现降序这个位置就是我们要找的关键点，只需要将2与其后的数字中的（1,2,4,5）比它大的最小数，也就4替换，然后再将后面的数（1,2,2,5）升序排列便可得到下一个数，过程为：325421->345221->345122

找反向遍历第一个降序点 2 之后的数字

从后往前找到比一个数字大的数

找到后和后面比它大的最小数交换

换完后排序

这样就清晰多了


class Solution {
public:
    void nextPermutation(vector<int>& nums)
	{
		int keyIndex=nums.size()-1;//指向最后一个数
      
    //比前一个数字大
		while(keyIndex>0&&nums.at(keyIndex)<=nums.at(keyIndex-1))
			keyIndex--;//寻找降序关键点
 
 
		if(keyIndex==0)//如果关键点下标为0，则原数据排列为全降序，不存在比它更大的数，将原排列升序重排
		{
			sort(nums.begin(),nums.end())
		}
		else
		{
			int minNum=nums[keyIndex-1];//关键点下标对应的待替换数字
      //因为是升序所以直接找
      //找到比它最大最小那个 对那的确就是反向找
			for(int i=nums.size()-1;i>keyIndex-1;i--)//寻找关键点后最小的且大于待替换数字的数据对应的下标
			{
				if(nums[i]>minNum)//找到，则替换
				{
					int temp;
					temp=nums[i];
					nums[i]=nums[keyIndex-1];
					nums[keyIndex-1]=temp;
					break;
				}
			}
			sort(nums.begin()+keyIndex,nums.end());//将替换后，关键点后的数据进行升序重排
		}
	}
};

1 2	看题解都看的不是很明白

LEETCODE143.重排链表

给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

这题挺有意思的。

两个思路一个是像这样的用数组存

第二个是找中点 + 反转后半部分 + merge

显然前一个比后一个简单太多了。

class Solution:
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        if not head:return head
        vec=[]
        cur =head
        while cur:
            vec.append(cur)
            cur=cur.next
        
        i=0
        j=len(vec)-1
        while i<j:
            vec[i].next=vec[j]
            i+=1
            if i==j:
                break
            vec[j].next=vec[i]
            j-=1
        
        vec[j].next=None
        return head

第一次面试的题现在才解出来。那时候的确没法写出回溯来。

给定一个int数组A，给定一个数x，求所有求和能得到x的数字组合，组合中的元素来自A

解回溯的题感觉最重要的是遍历只要我能遍历到所有的tmp 那么就一定能找到答案。

然后再加上一些剪枝。

from typing import List
class Solution:
	def __init__(self):
		self.res=[]
		self.tmp=[]
	def getSetOfSum(self,nums:List[int],target) -> List[int]:
		if not nums:return self.res

		def recur(nums:List[int],target:int,index:int):
			if target<0:
				return

			if target==0:
				self.res.append(self.tmp[:])
				return

			for i in range(index,len(nums)-1):
				self.tmp.append(nums[i])
				recur(nums,target-nums[i],i)
				self.tmp.pop()

		recur(nums,target,0)
		return self.res

if __name__=='__main__':
	a = Solution()
	result = a.getSetOfSum([1,2,3,4,5],6)
	print(result)

LEETCODE105.重建二叉树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return Create(0,preorder.size()-1,0,inorder.size()-1,preorder,inorder);
    }

    // 先序 根左右
    // 中序 左根右
    TreeNode* Create(int preL,int preR,int inL,int inR,vector<int>& preorder, vector<int>& inorder){
        if (preL>preR){
            return NULL;
        }
        
        TreeNode * root =new TreeNode;
        root->val=preorder[preL];
        
        //先序的第一个就是根节点 保留根节点
        //想一想后序怎么写好吧
        //左右根
        //左根右
        int k=0;//保存根节点在中序里的下标
        for (int i =inL;i<=inR;i++){
            if (root->val==inorder[i]){
                k=i;
                break;
            }
        }

        //左子树长度
        int left_tree_length = k-inL;

        //思路还是很清晰的 之前一直没绕过这个弯
        root->left = Create(preL+1,preL+left_tree_length,inL,k-1,preorder,inorder);
        root->right = Create(preL+left_tree_length+1,preR,k+1,inR,preorder,inorder);

        return root;
    }
};

果然代码要自己写一遍才是自己的。

边界问题还是挺多问题的。

1.preL+k–inL 2.还有size()-1 3.还有Treenode *root = new TreeNode

踩了三个坑。

move on move on

LEETCODE206.反转链表

直接条件反射

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
     		if not head:return None
        prev=None
        while head:
          next_p=head.next
          # 条件反射还是能写出bug
          
          head.next=prev
          
          prev=head
          head=next_p
       return prev

LEETCODE1.两数之和

写了这么多遍还是容易忘

class Solution:
  # key 是num value 是index
    def twoSum(self, nums: List[int], target: int) -> List[int]:
    		hashtable={}
        for index,value in emumerate(nums):
            if target-value in hashtable:
              	return [index,hashtable[target-num]]
            hashtable[value]=index
       return []

LEETCODE199.二叉树的右视图

最近才写的应该


class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
      #懒得写了...
      	if not root:return []
        ans=[]
        #ans.append(root.val)
        queue=[root]
        
        while queue:
          n = len(queue)
          ans.append(queue[-1].val)
          for i in range(0,n):
             node = queue.pop()
             if root.left:queue.append(root.left)
             if root.right:queue.append(root.right)
        
        return ans

LEETCODE160.相交链表

编写一个程序，找到两个单链表相交的起始节点。

这题挺有意思的。题解太好玩了。

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        l1 =headA
        L2 =headB
        while l1!=l2:
          # 相当于第一条路走到头了.
           if l1==None:
                l1=headB
            else:
                l1=l1.next
            
            if l2==None:
                l2=headA
            else:
                l2=l2.next     
        return l1

LEETCODE215.数组中第K个最大元素原来这就是topK

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

大体思路:直接奔着题解去了~方法一：基于快速排序的选择方法方法二：基于堆排序的选择方法

所以这个题目排个序就完了

堆排然后调用K次？建堆然后调用K次

今天下午尽量就是解决堆排和快排的问题

堆的话就是大顶堆

我有点不太清楚大顶堆和二叉树搜索树区别

大顶堆只能保证根是最大的？但是不保证左右。

void swap(int arr[],int i,int j){
	int temp= arr[i];
	arr[i]=arr[j];
	arr[j]=temp;
}

void heapify(int tree[],int n,int i){
	if (i>=n){
		return;
	}
	int c1 = 2*i +1;
	int c2 = 2*i +2;
	int maxIndex=i;
	if (c1< n && tree[c1]>tree[maxIndex]){
		maxIndex =c1;
	}
	if (c2< n && tree[c2]>tree[maxIndex]){
		maxIndex =c2;
	}
	if (maxIndex!=i){
		swap(tree,maxIndex,i);
		heapify(tree,n,maxIndex);
	}
}
void build_heap(int tree[],int n){
	int last_node=n-1;
	int parent=(last_node-1)/2;
	int i;
	for (i=parent;i>=0;i--){
		heapify(tree,n,i);
	}
}

void heap_sort(int tree[],int n){
	build_heap(tree,n);
	int i;
	for(i=n-1;i>=0;i--){
		swap(tree,i,0);
		heapify(tree,i,0);
        //大的被交换到尾巴去了 太有意思了堆排
	}
}
int findKthLargest(int* nums, int numsSize, int k){
    heap_sort(nums,numsSize);
    return nums[numsSize-k];
}

然后就是快排

先回忆一下快排两个哨兵找然后交换一直到相遇相遇了就可以再交换。找到temp的位置了说明

public static void sort(int[] arr, int left, int right) { 
        if (left > right) {
            return ;
        }
        int i = left, j = right, temp = arr[left], t;
        while (i != j) {
          	// 右边找到一个比base小的
            while (arr[j] >= temp && i < j) {
                j--;
            }
          	// 左边找到一个比base大的
            while (arr[i] <= temp && i<j) {
                i++;
            }
          	//交换
            if (i < j) {
                t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
            }
        }
  			//base交换
  			//然后递归下去
        arr[left] = arr[i];
        arr[i] = temp;
        sort(arr, left, i - 1);
        sort(arr, i+1, right);
    }

太骚了这个快排

def quicksort(list):
    if len(list)<2:
        return list
    else:
        midpivot = list[0]
        lessbeforemidpivot = [i for i in list[1:] if i<=midpivot]
        biggerafterpivot = [i for i in list[1:] if i > midpivot]
        finallylist = quicksort(lessbeforemidpivot)+[midpivot]+quicksort(biggerafterpivot)
        return finallylist

print quicksort([2,4,6,7,1,2,5])

LEETCODE232.用栈实现队列

old friend 思路清晰就行

class CQueue {
public:
    stack<int> s1;
    stack<int> s2;
    CQueue() {

    }
    
    void appendTail(int value) {
        s1.push(value);
    }
    //# 思路没问题的
    int deleteHead() 
    {
      //# s2非空
      if(s2.size()!=0){
        int temp= s2.top();
      	s2.pop();
      	return temp;
      }
      //# s2 s1 为空
      if (s1.size()==0 and s2.size()==0) return -1;
      //# # s1非空 s2为空
      while (!s1.empty()){
        s2.push(s1.top());
        s1.pop();
      }
      int ans =s2.top();
      s2.pop();
      return ans;
    }
};

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue* obj = new CQueue();
 * obj->appendTail(value);
 * int param_2 = obj->deleteHead();
 */

LEETCODE 146.LRU

class DLinkListNode:
    def __init__(self,key=0,value=0):
        self.key=key
        self.value=value
        self.prev=None
        self.next=None


class LRUCache:

    def __init__(self, capacity: int):
        self.cache=dict()
        # 伪头伪尾
        self.tail=DLinkListNode()
        self.head=DLinkListNode()
        self.head.next=self.tail
        self.tail.prev=self.head
        self.capacity=capacity
        self.size=0


    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self.moveToHead(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if key not in self.cache:
            # 初始化
            node = DLinkListNode(key,value)
            self.cache[key]=node
            self.addToHead(node)
            self.size+=1

            if self.size>self.capacity:
                removed = self.removeTail()
                #pop
                self.cache.pop(removed.key)
                self.size-=1
        else:
            node=self.cache[key]
            node.value=value
            self.moveToHead(node)

    def addToHead(self,node):
        # o->o o->N->o
        head_next = self.head.next
        node.prev=self.head
        node.next=head_next
        head_next.prev=node
        self.head.next=node

    def removeNode(self,node):
        node.prev.next=node.next
        node.next.prev=node.prev
    

    def moveToHead(self,node):
        self.removeNode(node)
        self.addToHead(node)

    def removeTail(self):
        node = self.tail.prev
        self.removeNode(node)
        return node

LEETCODE53.最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

别说这道题要是冷不丁一来我还真接不住

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        maxSum = nums[0]
        curSum =nums[0]
        for i in range(1,len(nums)):
            curSum = max(curSum+nums[i],nums[i])
            maxSum=max(maxSum,curSum)
        
        return maxSum

LEETCODE155.最小栈

这个解法也挺巧妙的。

大体思路:之前一直扣细节。其实只要每次push 的时候栈顶和当前push一个最小的进去就行。

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = [math.inf]

    def push(self, x: int) -> None:
        self.stack.append(x)
        # 就这一句
        self.min_stack.append(min(x, self.min_stack[-1]))

    def pop(self) -> None:
        self.stack.pop()
        self.min_stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min_stack[-1]

LEETCODE20.有效的扩号

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) % 2 == 1:
            return False
        
        pairs = {
            ")": "(",
            "]": "[",
            "}": "{",
        }
        stack = list()
        for ch in s:
            if ch in pairs:
                if not stack or stack[-1] != pairs[ch]:
                    return False
                stack.pop()
            else:
                stack.append(ch)
        return not stack

LEETCODE141.环形链表

大体思路:快慢指针就行

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if not head or not head.next:
            return False
        slow = fast =head
        while slow and fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                return True
        return False

LEETCODE105.前序与中序重建二叉树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* Rebuild(vector<int>& preorder, vector<int>& inorder,int preL,int preR,int inL,int inR)
    {
        if(preL>preR)
        {
            return NULL;
        }

        TreeNode * root = new TreeNode;
        root->val = preorder[preL];

        int k=0;

        for(int i=inL;i<=inR;i++){
            if(root->val ==inorder[i]){
                k=i;
                break;
            }
        }

        int leftLen= k-inL;

        root->left=Rebuild(preorder,inorder,preL+1,preL+leftLen,inL,k-1);
        root->right=Rebuild(preorder,inorder,preL+leftLen+1,preR,k+1,inR);   

        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return Rebuild(preorder,inorder,0,preorder.size()-1,0,inorder.size()-1);
    }
};

LEETCODE300.最长上升子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

dp题你要我写我不一定写的出来。就到这吧。留给明天写一写。

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        
    }

Contents