Categories
不学无术

C++ STL容器能力一览表

摘自《C++标准程序库 (The Standard C++ Library)》pp.227
未摘齐,需要详细可参考6.9节:各种容器的运用时机
STL_container_compare

Categories
不学无术

LeetCode 328. Odd Even Linked List

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.
You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.
Example:
Given 1->2->3->4->5->NULL,
return 1->3->5->2->4->NULL.
Note:
The relative order inside both the even and odd groups should remain as it was in the input.
The first node is considered odd, the second node even and so on …

思路

既然是要O(n)时间复杂度,并且O(1)空间复杂度,基本就能想到要用俩指针了。其中一个指针指向当前的奇数位元素,另一个指向偶数位的。
LeetCode328
大概就是这个意思啦,然后指针不断往前挪动。注意要保存偶数指针的头,因为奇数结束之后要串上偶数的~

代码

里面的oddTail是为了防止链表长度为奇数的时候,里面currOdd指针走到NULL的情况。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if(head == NULL || head->next == NULL)
            return head;
        ListNode* currOdd = head;
        ListNode* currEven = head->next;
        ListNode* evenHead = currEven;
        ListNode* oddTail = currOdd;
        while(currOdd != NULL && currEven != NULL){
            currOdd->next =currEven->next;
            if(currOdd->next != NULL)
                currEven->next = currOdd->next->next;
            oddTail = currOdd;
            currOdd = currOdd->next;
            currEven = currEven->next;
        }
        if(currOdd != NULL)
            currOdd->next = evenHead;
        else
            oddTail->next = evenHead;
        return head;
    }
};

 

Categories
不学无术

C++类型转换符 static_cast, dynamic_cast, const_cast

“cast”一词在英文里有“浇铸”的意思,还是挺形象的。

1.static_cast

可以看做是利用一个原始值构建一个临时对象,并再设定初始值的时候使用类型转换。
例如:

float x;
...
cout << static_cast<int>(x); //float to int
...
cout << static_cast<string>("hello")); //char* to string

2.dynamic_cast

将多态类型(polymorphic type)成员向下转换为其对应的静态类型成员。这个cast是在运行时实时检验的,因此可以用来检测某个指针指向的对象到底是不是XXX类的。

class Car; //abstract class
class Cabriolet : public Car {...};
class Limousine : public Car {...};
void f(Car* cp){
    Cabriolet* p = dynamic_cast<Cabriolet*>(cp);
    if(p == NULL) {
        //cp is not referred to an object of Cabriolet
    }
}

当参数是个引用,并且类别转换失败的时候,会抛出bad_cast异常哦。

3.const_cast

去除某个对象的const修饰作用,也可以拿来去除volatile修饰作用。
 

Categories
不学无术

C++异常处理,stack unwinding

这篇文章的内容摘自《C++标准程序库》2.2.3节
C++标准程序库可以在不污染函数接口的情况下处理异常。如果你遇到一个意外情况,可以跑出异常来停止后续流程,例如:

class Error;
void f()
{
    ...
    if(exception-condition)
        throw Error();
    }
    ...
}

其中throw开始了stack unwinding过程,也就是说,他将使得退离任何函数区段时的行为像以return语句返回一样,然而程序却不会跳转到任何地点。对于所有被声明与某区段——而该区段却因程序异常而退离——的局部对象而言,会调用它的析构函数stack unwinding的动作会持续到退出main()或被某个catch子句捕捉并处理了异常为止。
异常对象(exception objects)其实就是一般类或基本类的对象,可以是int,string类型的对象,也可以是某个模板类对象。
 

Categories
不学无术

M$ 2016 题目3 : Demo Day

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

You work as an intern at a robotics startup. Today is your company’s demo day. During the demo your company’s robot will be put in a maze and without any information about the maze, it should be able to find a way out.
The maze consists of N * M grids. Each grid is either empty(represented by ‘.’) or blocked by an obstacle(represented by ‘b’). The robot will be release at the top left corner and the exit is at the bottom right corner.
Unfortunately some sensors on the robot go crazy just before the demo starts. As a result, the robot can only repeats two operations alternatively: keep moving to the right until it can’t and keep moving to the bottom until it can’t. At the beginning, the robot keeps moving to the right.

rrrrbb..
...r....     ====> The robot route with broken sensors is marked by 'r'.
...rrb..
...bb...

While the FTEs(full-time employees) are busy working on the sensors, you try to save the demo day by rearranging the maze in such a way that even with the broken sensors the robot can reach the exit successfully. You can change a grid from empty to blocked and vice versa. So as not to arouse suspision, you want to change as few grids as possible. What is the mininum number?

输入

Line 1: N, M.
Line 2-N+1: the N * M maze.
For 20% of the data, N * M <= 16.
For 50% of the data, 1 <= N, M <= 8.
For 100% of the data, 1<= N, M <= 100.

输出

The minimum number of grids to be changed.

注记:

动态规划的一道题,后悔当时没有看通过率先做了第二道,第二题没有熟练掌握Trie结果处理超时了!
这题就是状态麻烦点,我的处理方式是在当前位置就判断右侧及下侧的通行情况,必要时做出改变,然后继续。因此注意点是一开始就被[0][0]位置blocked的情况。
以(x位置,y位置,当前方向)为一个三元组,可以保存唯一的状态结果,避免重复递归。

代码:

未经详细测试,待测试!感觉自己的编码能力还是有限,欢迎过客提出意见。

#include <iostream>
#include <vector>
#include <string>
using namespace std;
const int FAIL = -32767;
struct St {
	bool hasRight;
	bool hasDown;
	int rightBest;
	int downBest;
	St(){
		hasRight = false;
		hasDown = false;
	}
	void setVal(bool movR, int val) {
		if (movR) {
			hasRight = true;
			rightBest = val;
		}
		else {
			hasDown = true;
			downBest = val;
		}
	}
	bool hasVal(bool movR) {
		if (movR)
			return hasRight;
		else
			return hasDown;
	}
	int getVal(bool movR) {
		if (movR)
			return rightBest;
		else
			return downBest;
	}
};
int legalMin(int x, int y) {
	if (x < 0) return y;
	else if (y < 0) return x;
	else return x<y ? x : y;
}
int moveMaze(const vector<string>& maze, int i, int j, bool movR, vector<vector<St>>& storedMap) {
	//cout << '.';
	if ((i == maze.size() - 1) && (j == maze[0].size() - 1)) {
		//Out of maze and finished
		return 0;
	}
	else if ((i == maze.size()) || (j == maze[0].size())) {
		//Reach boundary
		return FAIL;
	}
	if (storedMap[i][j].hasVal(movR)) {
		//cout << "HIT!" << i << ", " << j << ", "<< movR << endl;
		return storedMap[i][j].getVal(movR);
	}
	int right = FAIL;
	int down = FAIL;
	if (movR) {
		//Moving towards right side
		if (j == maze[0].size() - 1 || maze[i][j + 1] == '.') {
			right = moveMaze(maze, i, j + 1, movR, storedMap);
			if (j == maze[0].size() - 1)
				down = moveMaze(maze, i + 1, j, false, storedMap);
			else
				down = 1 + moveMaze(maze, i + 1, j, false, storedMap);
		}
		else {
			//blocked
			right = 1 + moveMaze(maze, i, j + 1, movR, storedMap);
			if (i == maze.size() - 1 || maze[i + 1][j] == '.')
				down = moveMaze(maze, i + 1, j, false, storedMap);
			else
				down = 1 + moveMaze(maze, i + 1, j, false, storedMap);
		}
	}
	else {
		if (i == maze.size() - 1 || maze[i + 1][j] == '.') {
			//Move down safely
			down = moveMaze(maze, i + 1, j, movR, storedMap);
			if (i == maze.size() - 1)
				right = moveMaze(maze, i, j + 1, true, storedMap);
			else
				right = 1 + moveMaze(maze, i, j + 1, true, storedMap);
		}
		else {
			//blocked
			down = 1 + moveMaze(maze, i + 1, j, movR, storedMap);
			if (j == maze[0].size() - 1 || maze[i][j + 1] == '.')
				right = moveMaze(maze, i, j + 1, true, storedMap);
			else
				right = 1 + moveMaze(maze, i, j + 1, true, storedMap);
		}
	}
	int result = legalMin(down, right);
	storedMap[i][j].setVal(movR, result);
	return result;
}
int main() {
	int N, M;
	cin >> N >> M;
	vector<string> maze;
	for (int i = 0; i<N; i++) {
		string str;
		cin >> str;
		maze.push_back(str);
	}
	vector<vector<St>> storedMap;
	for (int i = 0; i < N; i++) {
		vector<St> line;
		for (int j = 0; j < M; j++) {
			line.push_back(St());
		}
		storedMap.push_back(line);
	}
	int result;
	if(maze[0][0] == '.')
		result = moveMaze(maze, 0, 0, true, storedMap);
	else //[0][0]就是'b'
		result = 1 + moveMaze(maze, 0, 0, true, storedMap);
	cout << result << endl;
	return 0;
}

 

Categories
不学无术

Longest Common Subsequence 最长公共子序列

这是个很老的问题了,最近总是碰到,大三时候学的算法好多都忘记了,不如重新学一遍。
比起XXblog上的教程,我最喜欢的还是这个版本:http://www.ics.uci.edu/~eppstein/161/960229.html
里面的代码干净利落,解释也非常的清晰,一步一步怎么来的都很好。
这个问题是个动态规划的问题,最基本的样子是这样的:

假设当前搜索到字符串A,B中的字符a[i],b[j].
LCS[i,j]表示字串A,B分别在位置[i][j]及以后的最大子序列数量
IF A[i] == B[j]:
    LCS[i,j] = 1 + LCS[i+1][j+1] # 当前的算入,然后A,B再往后挪一格
ELSE
    LCS[i,j] = max(LCS[i][j+1], LCS[i+1][j]) # 分别挪动A,B后一格看看哪个好
ENDIF

由于这样递归能弄出的子问题里面,好多是重复的,因此我们可以像计算斐波那契数列那样,采用自底向上的方法,用非递归的方式实现。即从字符的末尾往前推导LCS[i][j],这样当计算LCS[i][j]的时候, LCS[i+1][j]或LCS[i][j+1]已经计算好了。
具体还是看英文教程吧,这里给出C++实现的代码。因为下午例会还得讲PPT,下面的代码用了全局变量传递计算好的序列,有点丑。

#include <iostream>
using namespace std;
/**
 * Longest Common Subsequence
 */
int** storeMat;
int max(int x, int y){
    return x>y? x:y;
}
int getLCSLength(char* A, char* B){
    int sz_A = strlen(A);
    int sz_B = strlen(B);
    storeMat = new int*[sz_A+1];
    for(int i=0; i<=sz_A; i++){
        storeMat[i] = new int[sz_B+1];  // Allocate memory
    }
    for(int i=sz_A; i>=0; i--){
        for(int j=sz_B; j>=0; j--){
            if(A[i] == '\0' || B[j] == '\0'){
                storeMat[i][j] = 0;
            } else if (A[i] == B[j]) {
                storeMat[i][j] = 1 + storeMat[1+i][1+j];
            } else {
                storeMat[i][j] = max(storeMat[1+i][j], storeMat[i][1+j]);
            }
        }
    }
    return storeMat[0][0];
}
string getLCS(char* A, char* B){
    if(NULL == storeMat){
        getLCSLength(A, B);
    }
    int i=0, j=0;
    string result;
    int sz_A = strlen(A); int sz_B = strlen(B);
    while(i < sz_A && j<sz_B){
        if(A[i] == B[j]){
            result += A[i];
            i++;
            j++;
        } else if (storeMat[i+1][j] > storeMat[i][j+1]){
            i++;
        } else {
            j++;
        }
    }
    return result;
}
int main() {
    char a[50], b[50];
    scanf("%s %s", a, b);
    cout << getLCS(a, b);
    return 0;
}

 

Categories
不学无术

LeetCode 239. Sliding Window Maximum

题目

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Therefore, return the max sliding window as [3,3,5,5,6,7].

思路

又是《剑指Offer》的原题(#65),大致讲一下思路吧。
思路来源于之前做过的一道题,是要求设计一个栈,可以用O(1)时间找到栈中最大(最小)元素的。当时的方法是,另辟一个栈,记录可能会改变最大值的那些值(可以称他们为关键值),当这弹出的栈顶元素恰好是这些值的时候,把关键值栈顶的元素也弹出。这就相当于做了“撤销”操作,这时关键值栈顶的新元素也就是目前的最大值了。
假设我们用一个容器存放那些可能成为最大值的元素,那维护它过程就发生在向后移动窗口读入一个新元素a[i]时,主要的想法有两步:

  • 如果a[i]比容器中那些排在它前面的(先前读入的)元素大,由于a[i]的存活时间肯定比老一辈们来的长,因此前面那些比它的值还小的元素就可以删去了;
  • 删去那些“过气”的元素,也就是目前已经不在窗口中的那些元素;

每挪动一下,可以得知当前窗口最大的元素肯定就是在容器最前头的(可能是还没“过气”老大),后面排着一串老大挂掉后想当老大的元素
由于按照时间顺序,“过气”元素在容器的开头,而我们又要从容器的末尾开始找那些比a[i]小的元素,因此有这么两个重要决定:

  1. 使用双端队列存放候选元素:因为我们要方便地操作数组的首末项;
  2. 队列中存放元素的序号而不是值:这是因为我们要判断哪些元素已经滑出窗口了,如果存储值的话,每次还得重新到原序列里找位置;

整个方法的时间复杂度是O(n),空间复杂度应该也是O(n)

代码

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int numSz = nums.size();
        vector<int> results;
        if(numSz <= 0 || k > numSz){
            return results;
        }
        deque<int> working;
        //Init deque
        for(int i=0; i<k; i++){
            while(!working.empty() && nums[i]>=nums[working.back()]){
                working.pop_back();
            }
            working.push_back(i);
        }
        results.push_back(nums[working.front()]);
        //Interate through remaining nums
        for(int i=k; i<numSz; i++){
            while(!working.empty() && working.front() <= (i-k)){
                working.pop_front(); //Remove the out-of-window elements
            }
            while(!working.empty() && (nums[i]>=nums[working.back()])){
                working.pop_back();  //Remove the smaller elements
            }
            working.push_back(i);
            results.push_back(nums[working.front()]);
        }
        return results;
    }
};

 

Categories
不学无术

LeetCode 335. Self Crossing

题目:

You are given an array x of n positive numbers. You start at point (0,0) and moves x[0] metres to the north, then x[1] metres to the west, x[2] metres to the south,x[3] metres to the east and so on. In other words, after each move your direction changes counter-clockwise.
Write a one-pass algorithm with O(1) extra space to determine, if your path crosses itself, or not.
Example 1:

Given x = [2, 1, 1, 2],
┌───┐
│   │
└───┼──>
    │
Return true (self crossing)

Example 2:

Given x = [1, 2, 3, 4],
┌──────┐
│      │
│
│
└────────────>
Return false (not self crossing)

Example 3:

Given x = [1, 1, 1, 1],
┌───┐
│   │
└───┼>
Return true (self crossing)

思路:

https://leetcode.com/discuss/88054/java-oms-with-explanation
本人愚钝,想不到O(1)空间复杂度的方法,只能看Discussion啦,看完以后发现,遇到问题能够分析出各种情况真是不容易。
把大神的代码总结一下,可以变成下面这张图,图中给出了可能发生self-crossing的所有情况(其他情况都是这些情况的”旋转”版本):
LeetCode_Self_Crossing
所以就是遍历所有移动步x[i],判断之前的情况是否在这三种情况之内,如果有的话,那肯定就有crossing了。其中情况2的意思是,当前的步进x[i]覆盖到了x[i-4]了,其他情况看图应该都好理解的。

代码:

class Solution {
public:
    bool isSelfCrossing(vector<int>& x) {
        int numSz = x.size();
        if(numSz <= 3)
            return false;
        for(int i=3; i<numSz; i++){
            if(x[i]>=x[i-2] && x[i-1]<=x[i-3]) //Cond 1
                return true;
            else if(i>=4 && x[i-1]==x[i-3] && x[i]+x[i-4]>=x[i-2])//Cond 2
                return true;
            else if(i>=5 && x[i-1]<=x[i-3] && x[i-4]<=x[i-2] && x[i]+x[i-4]>=x[i-2] && x[i-1]+x[i-5]>=x[i-3]) //Cond 3
                return true;
        }
        return false;
    }
};

 

Categories
不学无术 木有技术

百度前端技术学院 任务四:定位和居中问题

任务:

http://ife.baidu.com/task/detail?taskId=4

效果图:

屏幕快照 2016-04-03 下午5.54.13

有用的参考资料:

思路:

灰色矩形使用relative定位,然后设定left与top为50%,由于已经知道框的大小,用margin把长款的一半距离补回来就行了。
两个扇形在矩形的div内部,使用绝对定位,用border-radius做圆角,clip:rect剪切。

代码:

CodePen: http://codepen.io/idailylife/full/QNqJXe/

<div class="rectangle">
  <div id="left_top" class="qcircle">
  </div>
  <div id="right_bottom" class="qcircle">
  </div>
</div>

 

.rectangle{
  position: absolute;
  width: 400px;
  height: 200px;
  top: 50%;
  left: 50%;
  margin-left: -200px;
  margin-top:-100px;
  background-color: #ccc;
}
.qcircle{
  position:absolute;
  width:100px;
  height:100px;
  border-radius:50px;
  background-color:#fc0;
}
#left_top{
  top: -50px;
  left: -50px;
  clip:rect(50px, 100px, 100px, 50px);
}
#right_bottom{
  right: -50px;
  bottom: -50px;
  clip:rect(0, 50px, 50px, 0);
}

 

Categories
不学无术 木有技术

百度前端技术学院 任务三 HTML、CSS布局入门,三栏式布局的实践

恩,很遗憾没有赶上报名,因为是事后好几天才知道的。好在他们公开了练习题已经微信通知,所以还是可以跟着练一练哒!就是得不到别人的评论了,很忧伤,但是可以看每一队提交的作业,挺好。
给出我自己的实现吧,作为“对于有过页面实践,但没做过太复杂页面的同学”,我先选了第三题
效果图:
屏幕快照 2016-04-02 下午6.42.20
实现:
三栏布局使用的是float,没有用到相对定位。文字在框里的垂直居中,找到的是这里的方法。
前端团队提供的有关清除浮动的信息很给力:http://zh.learnlayout.com/clearfix.html,里面还有些很实用的技巧。
目前的缺陷是,强制设置了min-width,移动界面不适配,我还要慢慢学习啊!
代码:
CodePen: https://codepen.io/idailylife/pen/pyWLvq
HTML

<div class="container">
  <div id="group" class="nav sub container">
    <div id="group_logo" class="smallbox container">
      团队LOGO</br>80x80
    </div>
    <div id="group_name">
      团队名称
    </div>
  </div>
  <div id="right" class="right sub container">
    <div class="plogo smallbox container withvmargin">
      <p>个人LOGO</p>
    </div>
    <div class="plogo smallbox container withvmargin">
      <p>个人LOGO</p>
    </div>
    <div class="plogo smallbox container withvmargin">
      <p>个人LOGO</p>
    </div>
    <div class="plogo smallbox container">
      <p>个人LOGO</p>
    </div>
  </div>
  <div id="middle" class="sub container">
    <p>团队介绍</p>
    <p>《金刚般若波罗蜜经》来自印度的初期大乘佛教。因其包含根本般若的重要思想,在般若系大乘经中被视为一个略本;本经说“无相”而不说“空”,保持了原始般若的古风。本经六种译本中,通常流通的是鸠摩罗什的初译。如印顺法师所说,此后的五译是同一唯识系的诵本,比如菩提流支、达摩笈多等,都是依无著、世亲的释本译出;只有罗什所译为中观家(般若系)的诵本。又如吕澂说,罗什传龙树的般若学,所以能“心知其意”;到玄奘新译般若经,《金刚经》其实已“面目全非”了。
《金刚经》在印度有唯识家(无著、世亲)的论释。传入中国,三论、天台、贤首、唯识各宗都有注疏;然而中国佛教深受真常系大乘的影响,各宗表面上阐扬《金刚经》,实际上阐扬常住佛性和如来藏。又在三教合流环境下,明清以来,三教九流都来注解《金刚经》,杂合浓厚的真常理论和儒道信仰。又受到密教影响,《金刚经》被附上密咒形成读诵仪轨。此外,民间还出现各种离奇的灵验记和感应录。般若经典《金刚经》被真常化、儒道化、迷信化之中,在中国特别的盛行起来。
本经文义次第的艰深为古印度学者所公认,如无著说:“金刚难坏句义聚,一切圣人不能入”。依龙树所示《般若经》的“两番嘱累”,《金刚经》的“初问初答”即宣说“般若道”,“再问再答”宣说“方便道”。本经侧重广观万法(《心经》则侧重观身心五蕴),阐扬发菩提心,行无我的大乘菩萨道;彻始彻终归宗於般若无住的离相法门,以此明示阿耨多罗三藐三菩提。</p>
  </div>
</div>

CSS

body{
  min-width:540px;
}
.container{
    padding: 20px;
    background-color: #eee;
    border: 1px solid #999;
    overflow: auto;
    zoom: 1;
    -webkit-box-sizing: border-box;
    -moz-box-sizing: border-box;
    box-sizing: border-box;
}
.sub{
  background-color: #fff;
}
.nav{
  float:left;
  width:200px;
}
.right{
  width:120px;
  float:right;
}
.smallbox{
  width:80px;
  height:80px;
  float:left;
  overflow:hidden;
}
.withvmargin{
  margin-bottom:20px;
}
.plogo{
  padding:20px 0;
  font-size: 12px;
  text-align:center;
}
#group_name{
  margin: 0px auto;
  width: 78px;
  font-size: 16px;
  float: left;
  text-align:right;
}
#group_logo{
  font-size: 12px;
  padding: 0 auto;
}
#middle{
  margin-left: 220px;
  margin-right: 140px;
}