重开博客

Featured

博客断断续续,不知道重开多少次了。

以前申学校,找工作的时候,无比焦虑,忙起来连饭都不想吃,也顾不上更新。

现在工作渐渐稳定下来,似乎进入了一段“和平”时期,于是打算收拾一下之前的烂摊子。

这次换了主机,换了主题,换了很多插件,连博客名也换了。改的连妈都不认识了。

删了很多比较水的文章和评论,尽量保证公开发布的文章都是原创。

现在大部分文章都是LeetCode题解,也算是找工作时期的一段回忆吧。水平有限,不一定是最优解,而且好多解法现在都忘了,不过也欢迎探讨。

简单暴力翻墙法:搭建自己的VPN

网上各种免费、收费VPN良莠不齐,时好时坏。如果VPN在你最需要的时候掉链子,着实令人沮丧。为什么不自己搭建一个呢?

关键点在于要有一个不被墙的境外服务器,确保你和该服务器正常通信,该服务器和你想访问的网站或服务可以正常通信。这里以AWS EC2为例。

Continue reading 简单暴力翻墙法:搭建自己的VPN

LeetCode #33 Search in Rotated Sorted Array

题目:

Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.

 

分析:

在一个旋转过的有序数组中查找一个数,如果该数不存在,返回-1。

方法一:

首先通过二分查找找出数组中最小值的位置。这样我们可以将数组分成2段,使得每一段都是有序的。之后看要查找的数(target)的值落在哪一段,然后再在这一段里进行一次二分查找即可。

方法二:(推荐)

对于每一轮二分查找,中点的左侧和右侧必然有有一边是有序的。我们看看target是不是在有序的这个范围内,是的话就查这一边,不是的话就查另一边。

Continue reading LeetCode #33 Search in Rotated Sorted Array

已知前序遍历、中序遍历、后序遍历结果其中之二,生成二叉树

一、已知前序遍历和中序遍历

假设我们用2个数组preorder和inorder来表示前序和中序遍历的结果。

要生成的二叉树的任意子树都对应于preorder和inorder的某个子数组。该子树的根节点对应于preorder子数组的第一个元素,然后在inorder中查找该该元素。对于inorder中的的子数组,根节点元素左侧的子数组对应左子树,右侧的子数组对应右子树。之后使用递归重复该过程。

下面给出一段Java示例代码:

Continue reading 已知前序遍历、中序遍历、后序遍历结果其中之二,生成二叉树

LeetCode #133 Clone Graph (拷贝图)

题目:

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors

 

分析:

拷贝一个图。每个节点中用List存储它的邻居节点。

基本思路就是遍历原图,使用一个map来记录已经访问过的节点以及它和新节点的对应关系。

遍历可以考虑DFS或者BFS。下面的代码是使用BSF实现的。

Continue reading LeetCode #133 Clone Graph (拷贝图)

LeetCode #148 Sort List (链表合并排序)

题目:

Sort a linked list in O(n log n) time using constant space complexity.

 

分析:

排序一个链表。要求O(nlogn)时间,O(1)空间。

说到O(nlogn)时间,首先想到的是合并排序。虽然合并排序对于数组是O(n)空间,但是对于链表却可以做到O(1)空间。

Continue reading LeetCode #148 Sort List (链表合并排序)

LeetCode #71 Simplify Path (路径化简)

题目:

Given an absolute path for a file (Unix-style), simplify it.
For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

 

分析:

路径化简。

基本思路就是使用栈来模拟进入某一路径或者返回上一级。

注意以下边界情况:

  • "/../" 应化简为 "/"
  • "/home//foo/" 应化简为 "/home/foo"

Continue reading LeetCode #71 Simplify Path (路径化简)

LeetCode #260 Single Number III (查找数组中2个不成对的数)

题目:

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.
For example:
Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:

  1. The order of the result is not important. So in the above example, [5, 3] is also correct.
  2. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

 

分析:

数组中除了2个数以外,其他所有的数都是成对的。要求把这2个数找出来。

本题也用到了异或运算的性质:A^A = 0, A^B^A = B

首先遍历数组,将数组中所有的数进行异或之后,得到值就等于不成对的两个数的异或值。例如,对于[1,2,1,3,2,5],异或所有的数得到6,这也正是其中不成对的两个数3和5的异或结果。

得到这两个数的异或结果有什么用的?怎样把他们分开?

我们知道,既然两个数不成对,那么他们之间至少存在一个二进制位是不同的。我们可以通过这个不同的位来区分这两个数。对于异或运算的结果,1表示原来的两个数在这一位上不同。现在找到异或结果的任何一个置为1的位即可。还是看刚才的例子,3和5的异或运算如下:

      3 (0011)
xor   5 (0101)
=     6 (0110)

Continue reading LeetCode #260 Single Number III (查找数组中2个不成对的数)

LeetCode #222 Count Complete Tree Nodes (完全二叉树节点个数)

题目:

Given a complete binary tree, count the number of nodes.

 

分析:

给定一个完全二叉树的根节点,求该完全二叉树节点的个数。

完全二叉树就是:除最后一层外,每一层上的节点数均达到最大值;在最后一层上只缺少右边的若干结点。

本题的关键就是求二叉树最后一层的节点个数。对此我们可以使用二分查找。

使用一个整数来表示从根节点到叶子节点的路径,每一位代表方向(0向左,1向右)。例如,1个4层的二叉树,如果路径为5,写成二进制是101,就代表从根节点出发,右,左,右。

通过二分查找,我们可以得到最后一层第一个空节点的位置,也就知道了最后一层有几个几点。然后加上上面几层的节点数就是答案。

Continue reading LeetCode #222 Count Complete Tree Nodes (完全二叉树节点个数)