算法题

01 September 2014

算法题

一个数n只能+1、-1、/2，如何最少的步骤到达1。
1-n个数，你设计围成一个环，使得任意相邻两数和为质数。
一个数组中，除了两个数字只出现一次之外，每个数字都出现两次，找出这两个数字。
n个骰子扔在地上，所有骰子朝上一面的点数之和是s。输入n，打印出s的所有可能的值出现的概率。

1-n循环，维护两个大小为6n的数组。a[i]表示点数之和为i出现的次数。

约瑟环、O(n)解法。映射分析。

 last=0；//最后一个编号肯定为0；
 for(int i=2;i<=n;i++)
     last=(last+k)%i;//从队伍中有两个人开始递推last在上一层的中编号。

不用+-*/做加法。

二叉树最近公共祖先问题（无父节点）。

TreeNode *getLCA(TreeNode *root, TreeNode *p, TreeNode *q) { if (!root) return nullptr; else if (root == p || root == q) return root;

 //如果在root的左右子树中都未找到p，q的公共祖先，那么root就是其公共祖先。
 TreeNode *L = getLCA(root->left, p, q);
 TreeNOde *R = getLCA(root->right, p, q);
 if (L && R) return root;
 else return L ? L : R;  }

数值之差的最大值。
调整数组使奇数位于偶数前面/使能被3整除的再不能被3整除的前面/…

两个指针，每次都是判断head指针。如果head指针指的是奇数，head指针前移。如果指的是偶数，则与尾部指针交换数字，尾部指针移动。

给出一个入栈序列，判断一个出栈序列是否合法。如入栈为1，2，3，4。出栈为3，4，1，2。

思路1:对于任意位置的数a, 其右方的比a小的数，都是从大到小排列的。则是合法的。思路2:用一个栈模拟这个过程，若出栈为a，判断栈顶是否为a，若是则弹，若不是则按入栈顺序压入，直到找到a。若入栈的压光了也没找到说明不合法。

两个栈实现队列。
O(lgn)斐波拉契序列。
字符串中第一个只出现一次的字符。

bitmap[256]。
表达式的计算。(逆波兰式===>逆波兰式求值)
写出 YYYY-MM-dd 的正则表达式

/^[1-9]{4}(-)([0][1-9] [1][1-2])(-)([0-2][1-9] [3][0-1])$/g
判断电话号码的正则表达式

/^1[3 4 5 8][0-9]{4,8}$/
2N个人买票，N个有5元，N个人有10元，景点不用找零的概率。

[C(2n,n)/(n+1)]/[(2n)!/(n!*n!)] = 1/(n+1)
一堆硬币，一个机器人，如果是反的就翻正，如果是正的就抛掷一次，无穷多次后，求正反的比例。

a[n+1]=0.5a[n-1]+(1-a[n-1]) ans: a[n+1]=2/3
小孩不被拐走有个千年的规矩，那就是吃饭的时候小孩左右只能是其他小孩或者自己的父母。那么5对父子在圆桌上共有______种坐法。（旋转一下，每个人面对的方向变更后算是一种新的坐法）

ans：9600
数组的全组合、全排列（有重复）

LeetCode 47

算法题 算法题汇总笔记

算法题

算法题算法题汇总笔记