Find Minimum 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). Find the minimum element. You may assume no duplicate exists in the array. Hide […]
Maximum Product Subarray Find the contiguous subarray within an array (containing at least one number) which has the largest product. For example, given the array [2,3,-2,4], the contiguous subarray [2,3] has the largest product = 6. Show Tags Show Similar Problems Attention: product means the result of multiplication, not the […]
行程： 第一天：梅河口-省道303中朝边境-长白县 第二天：长白县-十五道沟望天鹅景区-松江河 第三天：松江河-长白山西坡-梅河口 中朝边境 省道303比想象中好走得多，只是一路上的隧道大部分都在维修，半幅开放，需小心驾驶。 路上的风景很美，我们走走停停。公路沿着长白山脉起伏绵延，左边是一人多高的玉米地，右边是茂盛树林，笔直的公路延伸到大山深处。 经过临江县后，道路一转，鸭绿江映入眼帘。省道303与鸭绿江并行，依长白山脉，傍鸭绿江水。江对岸就是朝鲜境内，江面最窄处不足百米，隔江而望，能看到日常生活的朝鲜人民，或散步，或嬉闹，或在江边洗衣、洗澡。他们的衣着并非都是死气沉沉的蓝灰，也不乏衣着光鲜的女子和孩童。 长白县对面似乎是朝鲜的一个集镇。集镇用一人多高的围墙围着，看不清里面的情况。围墙只有几个窄窄的供人进出的小门，门旁有持枪的士兵把守，进门需要出示证件。墙外五百米便是一个岗哨，监视着江面与对岸的一举一动。 同行的人拿起相机欲拍照，对岸的士兵发现后，端起枪瞄准我们。吓得我们连忙四散而逃。同行的人说，百十来米的距离，我们就是活靶子。后来才看到路旁拉的横幅，“禁止对朝鲜境内拍照 – 长白县边防部队宣”。 我当时在想，若是带个无人机过来，飞到对岸去，估计就是侵犯领土的外交事件了吧。 鸭绿江让我想起了深圳河，同样都是界河，一水之隔，左边繁华，右边贫困。上世纪七十年代，大逃港的人们游过深圳河，奔向香港；四十多年后的今天，脱北者同样冒着生命危险游过鸭绿江，进入中国，历史惊人地相似。 天上飞来几只不知名的小鸟，时而落在此岸嬉戏，时而落在彼岸栖息，物犹如此。 夜宿长白县，特色是狗肉。不过很贵要90一盘，米饭1两1块。听镇上人说，对面朝鲜人过去经常游过来偷东西，偷完再游回去，只是近几年少了些。 可能是靠近朝鲜的缘故，长白县晚上的星星很多很美，银河肉眼可辨。只是因为白天被瞄准的关系，并没敢拿出相机来拍照。上一次见到如此多的星星还是在垦丁，可以拉着喜欢的人一起来看。 十五道沟望天鹅风景区 从长白驱车五十余公里，来到望天鹅景区。 望天鹅也属于长白山脉，是火山喷发形成的景观。景区内的岩石很有特色，笔直而细长的玄武岩，像铅笔一样整齐地排列着。 自然景观还是不错，青山绿水小溪，呼吸呼吸氧气。游玩全程大概三个小时。 正好看到一位画家给小溪作画。 长白山西坡 长白山有东南西北四个坡可以登山，除了东坡位于朝鲜境内，南坡只做高端旅游（1000元每人）外，西坡和北坡都适合大众登山。 北坡开发较早，设施完善，但游人很多，人工痕迹比较重。我们选择了稍微自然一点的西坡登山。 游人到松江镇游客集散中心集合，停车场上看到全国各地的拍照，辽宁，山东，北京……还看到浙A杭州的拍照，倍感亲切。买好门票后有大巴车直接拉到山腰，下车后登上1400多级台阶，运气好的话，就会看到湛蓝的天池水。运气不好的话，就是云雾缭绕的景象。 登山要穿长袖长裤，带好雨衣，不可打伞，因为会引雷。山脚下有大衣出租，但不太划算，建议自带。 去年来过一次长白山，今年再次看到天池水，还是激动不已。借了旁边人的脚架，拍了张全景。北坡已经被云雾缭绕，北坡的人们恐怕连自己的鞋都见不到了。 返程 返程走省道302，都是山路+急转弯，并且有很长一部分正在修路，车辆也比省道303多得多，建议慢行，安全第一。 2015.8.15 于梅河口
Reverse Words in a String Given an input string, reverse the string word by word. For example, Given s = “the sky is blue“, return “blue is sky the“. Update (2015-02-12): For C programmers: Try to solve it in-place in O(1) space. Clarification: What constitutes a word? A sequence of […]
Power of Two Given an integer, write a function to determine if it is a power of two. //can n be negative? //negative number is definitely not a power of two //1 is power of 2 //0 is not //1 2 4 8 16 32 64 .. class Solution { […]
Max Points on a Line Given n points on a 2D plane, find the maximum number of points that lie on the same straight line. First, I thinked out an o(n^3) force solution. It’s workable at last. However, an o(n^2) solution exists which uses a hash table to store the slope […]
Insertion Sort List Sort a linked list using insertion sort. Basic question. //Should I solve this problem in place? //Contains duplicates values? /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution […]
Binary Tree Postorder Traversal Given a binary tree, return the postorder traversal of its nodes’ values. For example: Given binary tree {1,#,2,3}, 1 \ 2 / 3 return [3,2,1]. Note: Recursive solution is trivial, could you do it iteratively? Use two stacks to simulate recursion. stack st stores visiting nodes, […]
Reorder List Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→… You must do this in-place without altering the nodes’ values. For example, Given {1,2,3,4}, reorder it to {1,4,2,3}. The algorithm is straightforward. First, divide the linked list into two parts equally. (left part may be longer than […]
Word Break II Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences. For example, given s = “catsanddog”, dict = [“cat”, “cats”, “and”, “sand”, “dog”]. A solution is […]
