Welcome to LeaCoder's Blog!

• 关于Python-的“多元”赋值

  2019-03-17

  leacoder

  python

  python
  • 引入：
  • 变量赋值
    • 多重赋值
  • 列表和元组

  引入：

  实现链表翻转

  class Solution:
      def reverseList(self, head: ListNode) -> ListNode:
          cur = head
          prev = None
          while cur:
              cur.next,prev,cur = prev,cur,cur.next
          return prev
  

  初入Python时，常按着C++的思维去想，然后被如下赋值给搞懵逼了。

   cur.next,prev,cur = prev,cur,cur.next
  

  那为什么这样赋值能产生我们需要的效果？我们来简单了解下Python的变量赋值

  变量赋值

  ###赋值运算符 Python 语言中， 等号(=)是主要的赋值运算符。

  anInt = 11

  aString = ‘leacoder’

  aFloat = -3.1415

  aList = [“a”, “b”, “c”, “d”];

  当然还有其他基本数据类型 可以参见 Python3 基本数据类型

  注意，赋值并不是直接将一个值赋给一个变量，尽管可能根据其它语言编程经验认为应

  该如此(比如我T_T)。在 Python 语言中，对象是通过引用传递的。在赋值时，不管这个对象是新创建的，还是一个已经存在的，都是将该对象的引用（并不是值）赋值给变量。

  多重赋值

  x=y=z=0
  

  一个值为 0 的整数对象被创建，该对象的同一个引用被赋值给 x、y 和z 。也就是将一个对象赋给了多个变量。当然，在 Python 当中，将多个对象赋给多个变量也是可以的。

  ###“多元”赋值 另一种将多个变量同时赋值的方法我们称为多元赋值（multuple)。将 “mul-tuple”连在一起自造的。因为采用这种方式赋值时， 等号两边的对象都是元组。

  x, y, z = 1, 2, 'a string'
  等同于 (x, y, z) = (1, 2, 'a string')
  

  两个整数对象（值分别为 1 和 2）及一个字符串对象， 被分别赋值给x, y 和 z。通常元组需要用圆括号（小括号）括起来，尽管它们是可选的。但是加上圆括号以使得代码有更高的可读性，当然误解也就更少了。

  在其他语言中（如C++），要交换两个值， 会想到使用一个临时变量比如 tmp 来临时保存其中一个值：

  tmp = x;
  x = y;
  y = tmp;
  

  在上面的 代码片段中，变量 x 和变量 y 的值被互相交换.临时变量 tmp 用于在将 y 赋值给 x 前先保存 x 的值。将 y 的值赋给 x 之后， 才可以将保存在 tmp 变量中的 x 的值赋给 y。

  Python 的多元赋值方式可以实现无需中间变量交换两个变量的值。

  x, y = 123, 'a string'
  print(x,y)
  x, y = y, x
  print(x,y)
  

  输出：

  Python 在赋值之前已经事先对 x 和 y 的新值做了计算。

  列表和元组

  可以将列表和元组当成普通的“数组”，它能保存任意数量任意类型的 Python 对象。和数组一样，通过从 0 开始的数字索引访问元素，但是列表和元组可以存储不同类型的对象。

  列表和元组有几处重要的区别：

  列表：元素用中括号( [ ])包裹，元素的个数及元素的值可以改变

  元组：元素用小括号(( ))包裹，不可以更改（尽管他们的内容可以）。元组可以看成是只读的列表。

  ---

  GitHub链接： https://github.com/lichangke/LeetCode

  知乎个人首页： https://www.zhihu.com/people/lichangke/

  简书个人首页： https://www.jianshu.com/u/3e95c7555dc7

  个人Blog: https://lichangke.github.io/

  欢迎大家来一起交流学习

  Read All

  ---

• LeetCode-25-k个一组翻转链表(Reverse-Nodes-in-k-Group)

  2019-03-17

  leacoder

  Algorithm

  Algorithm  Leetcode
  • k个一组翻转链表
  • C++实现
    • 存储法
  • Python3实现
    • 借助单链表翻转

  

  k个一组翻转链表

  给出一个链表，每 k 个节点一组进行翻转，并返回翻转后的链表。
  
  k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么将最后剩余节点保持原有顺序。
  
  示例 :
  
  给定这个链表：1->2->3->4->5
  
  当 k = 2 时，应当返回: 2->1->4->3->5
  
  当 k = 3 时，应当返回: 3->2->1->4->5
  
  说明 :
  
  你的算法只能使用常数的额外空间。
  你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
  

  C++实现

  存储法

  用数组存储k个元素，虽然能通过但是执行用时有点长，不过逻辑简单

  /**
   * Definition for singly-linked list.
   * struct ListNode {
   *     int val;
   *     ListNode *next;
   *     ListNode(int x) : val(x), next(NULL) {}
   * };
   * @author:leacoder
   * @des: 存储法 k个一组翻转链表
   */
  class Solution {
  public:
      ListNode* reverseKGroup(ListNode* head, int k) {
          ListNode *nodearray[k];//存储 需翻转的 k个节点
          ListNode* result = new ListNode(0); //翻转后链表 用于结果返回
          ListNode* ret = result;//由于存储翻转后链表
          int count = 0;
          while( NULL != head){
              ListNode* next = head->next; //记录下移节点
              nodearray[count] = head; //记录到数组
              count++;//数组 下标自加 
              if(k == count){ //已存 k个值  需要翻转了
                 for(int i = k;i>0;i--){ //循环读取 数组中数据
                     ret->next = nodearray[i-1]; //从后往前去数组中数据 添加到ret链表中
                     ret = ret->next;//移位
                     nodearray[i-1] = NULL;//置空
                     count--;//数组中数据个数--
                 }
              }
              head = next;
          }
          
          for(int i = 0;i<count;i++){//处理不需要翻转的数据
             ret->next = nodearray[i];
             ret = ret->next;
             nodearray[i] = NULL;
          }
          ret->next = NULL;
          return result->next;
      }
  };
  

  k作为函数参数传入后就确定了可以当做常数，但是k作为参数可以为合理范围内任意值不确定，这点和题目描述说明貌似有点出入

  说明 : 你的算法只能使用常数的额外空间。

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

  我这种方法处理也只是提供一种思路，待后续其他实现方法

  Python3实现

  借助单链表翻转

  # @author:leacoder
  # @des: 借助单链表翻转  k个一组翻转链表
  
  class Solution:
      def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
          cur = head #由于遍历
          dim = ListNode(0) #新建一节点 
          dim.next = head #next指向head
          pre = dim #pre 赋值为 dim  1、记录和获取 k个一组的头 2、方便统一处理
          i = 1
          while cur: #遍历链表
              if i%k == 0: #k个一组 对这里面的数据翻转
                  temp = cur.next #记录 后一个 k个一组的 头节点
                  cur.next = None #赋值为None 前面 k个一组数据 为新的链表 以 None结束  
                  end, start = self.reverse(pre.next)  #翻转新链表 返回头尾  注pre.next 为新链表翻转前的头
                  pre.next = start  # 将翻转后的 链表头节点 赋值给 pre.next 链入按需要处理过的链表中
                  end.next = temp #将翻转后的尾节点的next  end.next赋值为temp(后一个 k个一组的 头节点)  链入按需要处理过的链表中
                  pre = end #pre 赋值为end 由于下一次循环 其 next为下一个 k个一组的头节点
                  cur = temp #将之前 存下来的 后一个 k个一组的 头节点 赋值给 cur ，while循环下移
              else:
                  cur = cur.next #我们关心k个一组的首尾
              i += 1
          return dim.next
      
      def reverse(self, head): #翻转链表
          dim1 = ListNode(0)
          dim1.next = head
          cur = head
          pre = None
          while cur: #遍历
              tmp = cur.next #存储 cur.next
              cur.next = pre #翻转 将 cur.next 赋值为pre
              pre = cur #pre移动
              cur = tmp #cur移动
          return dim1.next,pre    #翻转后end 和 start
  

  ---

  GitHub链接： https://github.com/lichangke/LeetCode

  知乎个人首页： https://www.zhihu.com/people/lichangke/

  简书个人首页： https://www.jianshu.com/u/3e95c7555dc7

  个人Blog: https://lichangke.github.io/

  欢迎大家来一起交流学习

  Read All

  ---

• LeetCode-232--用栈实现队列(Implement-Queue-using-Stacks)

  2019-03-17

  leacoder

  Algorithm

  Algorithm  Leetcode
  • 用栈实现队列
  • Python3 实现
    • 出入双栈 Py3
  • Java 实现
    • 出入双栈 Java
  • C++实现
    • 出入双栈 C++

  

  用栈实现队列

  用栈实现队列(Implement Queue using Stacks)

  使用栈实现队列的下列操作：
  
  push(x) -- 将一个元素放入队列的尾部。
  pop() -- 从队列首部移除元素。
  peek() -- 返回队列首部的元素。
  empty() -- 返回队列是否为空。
  示例:
  
  MyQueue queue = new MyQueue();
  
  queue.push(1);
  queue.push(2);  
  queue.peek();  // 返回 1
  queue.pop();   // 返回 1
  queue.empty(); // 返回 false
  说明:
  
  你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
  你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
  假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。
  

  Python3 实现

  出入双栈 Py3

  用栈实现队列(Implement Queue using Stacks) Py3 出入双栈实现

  #@author:leacoder
  #@des: 用栈实现队列
  class MyQueue:
  
      def __init__(self):
          self.inputstack = []
          self.outputstack = []
          
  
      def push(self, x: int) -> None:
          self.inputstack.append(x)
          
  
      def pop(self) -> int:
          if 0!=len(self.outputstack):
              return self.outputstack.pop()
          else:
              while 0!=len(self.inputstack):     
                  self.outputstack.append(self.inputstack.pop())      
              return self.outputstack.pop()        
  
      def peek(self) -> int:
          if 0!=len(self.outputstack):
              return self.outputstack[-1]
          else:
              while 0!=len(self.inputstack):
                  self.outputstack.append(self.inputstack.pop())
              return self.outputstack[-1]
  
      def empty(self) -> bool:
          return 0==len(self.inputstack) and 0==len(self.outputstack)
          
  
  # Your MyQueue object will be instantiated and called as such:
  # obj = MyQueue()
  # obj.push(x)
  # param_2 = obj.pop()
  # param_3 = obj.peek()
  # param_4 = obj.empty()
  

  1.push(x) – 将x放入 入栈（inputstack ）

  2.pop() – 判断 出栈（outputstack）是否为空，不为空从出栈（outputstack）直接取元素；为空则先将入栈（inputstack）所有元素依次取出放入出栈（outputstack）中，再从出栈（outputstack）取元素

  3.peek() – 同pop()

  4.empty() – 判断出入栈是否都为空（inputstack 、outputstack）

  Java 实现

  出入双栈 Java

  实现逻辑不变 用栈实现队列(Implement Queue using Stacks) Java 出入双栈实现

  C++实现

  出入双栈 C++

  用栈实现队列(Implement Queue using Stacks) C++ 出入双栈实现

  ---

  GitHub链接： https://github.com/lichangke/LeetCode

  知乎个人首页： https://www.zhihu.com/people/lichangke/

  简书个人首页： https://www.jianshu.com/u/3e95c7555dc7

  个人Blog: https://lichangke.github.io/

  欢迎大家来一起交流学习

  Read All

  ---

• LeetCode-20-有效的括号(Valid-Parentheses)

  2019-03-17

  leacoder

  Algorithm

  Algorithm  Leetcode
  • 有效的括号
  • Python3 实现
    • 堆栈 + 字典
  • Java实现
    • 堆栈 + map
  • C++实现
    • 堆栈 + map

  

  有效的括号

  有效的括号（Valid Parentheses）

  给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
  
  有效字符串需满足：
  
  左括号必须用相同类型的右括号闭合。
  左括号必须以正确的顺序闭合。
  注意空字符串可被认为是有效字符串。
  
  示例 1:
  
  输入: "()"
  输出: true
  示例 2:
  
  输入: "()[]{}"
  输出: true
  示例 3:
  
  输入: "(]"
  输出: false
  示例 4:
  
  输入: "([)]"
  输出: false
  示例 5:
  
  输入: "{[]}"
  输出: true
  

  Python3 实现

  堆栈 + 字典

  有效的括号(Valid Parentheses) Py3 堆栈 + 字典实现

  class Solution:
      def isValid(self, s: str) -> bool:
          stack = []
          paren_dict = {')':'(',']':'[','}':'{'}  #有配对情况 可以使用dict存储其键值对
          for c in s:
              if c not in paren_dict: #右括号类型 入栈
                  stack.append(c)
              elif not stack: #如果这时栈已经空了 无效 注这个判断需要在下一个判断之前
                  return False
              elif stack.pop()!= paren_dict[c]: #左括号类型 其paren_dict对应值需要与栈顶元素匹配 
                  return False
          return not stack #s遍历完了  如果为空栈 有效 否则为无效
  

  Java实现

  堆栈 + map

  其解题思路同Python3一样 有效的括号(Valid Parentheses) Java堆栈 + map实现

  C++实现

  堆栈 + map

  有效的括号(Valid Parentheses) C++堆栈 + map实现

  ---

  GitHub链接： https://github.com/lichangke/LeetCode

  知乎个人首页： https://www.zhihu.com/people/lichangke/

  简书个人首页： https://www.jianshu.com/u/3e95c7555dc7

  个人Blog: https://lichangke.github.io/

  欢迎大家来一起交流学习

  Read All

  ---

• LeetCode-24--两两交换链表中的节点(Swap-Nodes-in-Pairs)

  2019-03-16

  leacoder

  Algorithm

  Algorithm  Leetcode
  Read All

  ---

• LeetCode-236-二叉树的最近公共祖先(Lowest-Common-Ancestor-of-a-Binary-Tree)

  2019-03-16

  leacoder

  Algorithm

  Algorithm  Leetcode
  Read All

  ---