Floor表示向下取整 Ceiling表示向上取整

/* 1、假设变量x和n是两个正整数，我们知道x/n这个表达式的结果要取Floor，
 * 例如x是17，n是4，则结果是4。如果希望结果取Ceiling应该怎么写表达式呢？
 * 例如x是17，n是4，则结果是5；x是16，n是4，则结果是4。
 */

向上取整算法：(x+n-1)/n

解析：（1）当x/n正好除尽时，(x+n-1)/n=x/n+(n-1)/n=x/n

      （2）当x/n除不尽时，余数肯定大于1，所以（x+n-1）/n<=x/n+(1+n-1)=x/n+1;

摘自《Linux C一站式编程》书中问题

     向下取整的运算称为Floor，用数学符号⌊⌋表示，与之相对的，向上取整的运算称为Ceiling，用数学符号⌈⌉表示。
C语言定义的取整运算既不是Floor也不是Ceiling，无论操作数是正是负总是把小数部分截断（Truncate），所以当操作数为正的时候相当于Floor，当操作符为负的时候相当于Ceiling。
 
网页分页常用到的一个分页算法
 
      假设变量x和n是两个正整数，我们知道x/n这个表达式的结果是取Floor，例如x是17，n是4，则结果是4。如果希望结果取Ceiling应该怎么写表达式呢？例如x是17，n是4，则结果是5，而x是16，n是4，则结果是4。
 
#include <stdio.h>

int main()
{
    int x,n;

    printf("请输入数字：x n/n");
    scanf("%d %d",&x,&n);
    printf("x/n 向上取整的结果：%d/n",(x+n-1)/n);
    printf("x/n 向上取整方法二：%d/n",(int)(((float)x/(float)n)+0.9));
    return 0;
}

1: 判断一个字符串是否回文
回文是指类似于“上海自来水来自海上”或者“madam”，从前往后和从后往前读，字符串的内容是一样的，称为回文。判断一个字符串是否是回文有很多种思路：
1: 创建一个与原字符串前后倒过来的新字符串，比较二者是否相等，如果相等则是回文
1.1 利用中介Array.reverse()的反转数组的特性
function isPalindRome(str) {
return str.split('').reverse().join('') === str;
}
console.log(isPalindRome('madam')); //true
console.log(isPalindRome('mada')); //false
1.2 不利用任何方法，手动创建新字符串
function isPalindRome(str) {
let newStr = '';
for(let i = str.length - 1; i >= 0; i --){
newStr = newStr + str[i];
}
return newStr === str;
}
console.log(isPalindRome('madam'));
console.log(isPalindRome('mada'));
2: 从字符串的头和尾开始，依次比较字符串组是否相等，逐渐往中间收，如果全部相等，则是回文
function isPalindRome(str) {
let length = str.length;
for(let i = 0; i <= Math.floor(str.length / 2); i ++){
if(str[i] !== str[length - 1 - i]){
return false;
}
}
return true;
}
console.log(isPalindRome('aabbaa')); //true
console.log(isPalindRome('aabaa')); //true
console.log(isPalindRome('abb')); //false
2: 数组去重
2.1 利用ES6新增的Set，因为Set的元素是非重复的
function deduplicate(arr) {
return Array.from(new Set(arr));
}
deduplicate([1,1,2,2,3]);//[1,2,3]
2.1 创建一个新数组，只包含源数组非重复的元素
function deduplicate(arr) {
let newArray = [];
for(let i of arr){
if(newArray.indexOf(i) === -1){
newArray.push(i);
}
}
return newArray;
}
deduplicate([1, 1, 2, 2, 3]);//[1,2,3]
3: 统计字符串中出现最多次数的字符及其次数
function getMaxCount(str) {
let resultMap = new Map();
for (let letter of str) {
if (resultMap.has(letter)) {
resultMap.set(letter, resultMap.get(letter) + 1);
} else {
resultMap.set(letter, 1);
}
}
let maxCount = Math.max(...resultMap.values()); //利用ES6解构，从而可以使用Math.max()
let maxCountLetters = []; //可能几个字符同时都是出现次数最多的，所以用一个Array去装这些字符
resultMap.forEach((value, key, mapSelf) => {
if (value === maxCount) {
maxCountLetters.push(key);
}
});
return {maxCountLetters: maxCountLetters, maxCount: maxCount};
}
getMaxCount('aabbc'); //{maxCountLetters: ['a', 'b'], maxCount: 2}
4: 生成某个整数范围内的随机数
生成随机数，我们需要用到Math.random()这个方法。Math.random()生成0(包含) ～ 1(不包含)之间的小数。
4.1 利用Math.round()进行四舍五入
function randomInt(min, max){
return Math.round(Math.random() * (max - min) + min);
}
randomInt(3, 6)，就是 Math.round(Math.random() * 3 + 3);
4.2 利用Math.ceil()向上取整
Math.ceil(num)返回比num大的最小的整数，如果num已经是整数，就返回自己
console.log(Math.ceil(0.95)); //1
console.log(Math.ceil(4)); //4
console.log(Math.ceil(7.0009)); //8
所以，如果我们是要得到3 ～ 6之间的整数，利用ceil()方法就是：
Math.ceil(Math.random()* (6 - 3) + 3)
所以代码实现就是：
function randomRang(min, max) {
return Math.ceil(Math.random()* (max - min) + min);;
}
4.3 利用Math.floor()向下取整
Math.floor()和 Math.ceil()正好相反，Math.floor(num)返回小于num的最大的整数，如果num已经是整数，则返回自己
console.log(Math.floor(0.05)); //0
console.log(Math.floor(4)); //4
console.log(Math.floor(7.95)); //7
如果要得到3 ～ 6之间的整数，利用floor()就是：
Math.floor(Math.random()* (4) + 3);
代码的实现就是：
function randomRang(min, max) {
return Math.floor(Math.random()* (max - min + 1) + min);
}
5: 二分查找
二分查找的前提是有序数组，算法的思想是：
1: 比较需要查找的元素和数组的中间元素做比较，如果相等则返回对应的坐标，否则
2: 如果需要查找的元素比中间元素小，则在数组的前半部分继续采用步骤1的方法查找
3: 如果需要查找的元素比中间元素大，则在数组的后半部分继续采用步骤1的方法查找
4: 递归以上步骤
5: 特别要注意的一点是，如果数组不包含需要查找的元素，则返回-1
function binarySearch(target, arr, startIndex, endIndex) {
let length = arr.length;
if (target < arr[0] || target > arr[length - 1]) {
return -1;
}
let pivotIndex = startIndex + Math.floor((endIndex - startIndex) / 2);
let pivot = arr[pivotIndex];
if (pivot === target) {
return pivotIndex;
} else if (target < pivot) {
return binarySearch(target, arr, startIndex, pivotIndex - 1);
} else {
return binarySearch(target, arr, pivotIndex + 1, endIndex)
}
}
binarySearch(8, [0, 1, 2, 4, 5, 6, 7], 0, 7); //-1
binarySearch(0, [0, 1, 2, 4, 5, 6, 7], 0, 7); //0
6: 使用闭包获取每个li的index
在ES6之前，因为没有块级作用域，在循环体内创建的函数，常常得不到我们想要的结果。例如很经典的依次输出0～9，最后输出9个9；或者如我们这里的获取每个li元素的index:
//fun这种写法，点击每一个li，输出的结果都是5
let fun = function () {
let lists = document.getElementsByTagName('li');
for (var index = 0; index < lists.length; index++) {
lists[index].onclick = function () {
console.log(`index: ${index}`)
}
}
};
window.onload = fun;
a
b
c
d
e
以上的fun的这种写法之所以不对是因为：循环里的每次迭代都共享一个变量index，循环内部创建的函数都保留了对同一个变量的引用，当循环结束的时候，index的值已经变为5，所以点击每一个li都会输出5.
以下的三个函数的实现方式都是对的：
let fun1 = function () {
let lists = document.getElementsByTagName('li');
for (let index in lists) {
lists[index].onclick = function () {
console.log(`index: ${index}`)
}
}
};
let fun2 = function () {
let lists = document.getElementsByTagName('li');
for (let index = 0; index < lists.length; index++) {
lists[index].onclick = function () {
console.log(`index: ${index}`)
}
}
};
let fun3 = function () {
let lists = document.getElementsByTagName('li');
for (var index = 0; index < lists.length; index++) {
(function (index) {
lists[index].onclick = function () {
console.log(`index: ${index}`)
}
})(index)
}
};
f1和f2是利用let定义的块级作用域特性，f3是利用闭包的特性。
7: 随机生成指定长度字符串

之前谈的都是查找某个特定值，这里主要是谈论最小化最大值和最大化最小值问题。二分问题最容易搞错的就是终止条件，区间形式，返回lb还是ub或者需不需要再加减一。这里列出了模板
一：整型数二分
1.最小化最大值问题
形式一：(ub - lb) > 1 　　区间为 (lb, ub]　　结果为 ub
while (ub - lb > 1) {
int mid = lb + (ub - lb) / 2;
if (C(mid))
ub = mid;
else
lb = mid;
}
// 终止循环时 ub == lb + 1
形式二: (ub - lb) > 0　　区间为 [lb, ub]　　结果为 ub
while (ub - lb > 0) {
int mid = lb + (ub - lb) / 2;
if (C(mid))
ub = mid;
else
lb = mid + 1;
}
// 终止循环时 ub == lb
2.最大化最小值问题
形式一：(ub - lb) > 1 　　区间为 [lb, ub)　　结果为 lb
while (ub - lb > 1) {
int mid = lb + (ub - lb) / 2;
if (C(mid))
ub = mid;
else
lb = mid;
}
// 终止循环时 ub == lb + 1
形式二: (ub - lb) > 0　　区间为 [lb, ub]　　结果为 lb
while (ub - lb > 0) {
int mid = lb + (ub - lb + 1) / 2;
if (C(mid))
lb = mid;
else
ub = mid - 1;
}
// 终止循环时 ub == lb
最小化最大值通过维护ub的位置，最大化最小值通过维护lb的位置。
死循环的核心点在于mid的取值方式：mid = lb + (ub - lb) /2，如果某一时刻 ub == lb + 1，那么由于mid的向下取整，会导致 mid = lb; 假如 if 语句导致 lb = mid 发生，那么就会进入死循环，mid = lb，接着 lb = mid。同样的 mid = lb + (ub - lb + 1) / 2； 如果有 ub = mid操作，也有可能进入死循环。但是ub - lb > 1的终止条件会使得此情况不再发生，原因在于当ub == lb + 1时，由于不满足循环条件循环退出，也就不存在mid = lb或者 mid = ub的操作了。
当区间为闭区间，防止进入死循环的方法就是不能使mid == lb && mid == ub成立
1)最小化最大值 mid 向下取整(维护ub)
如果 if 条件成立，需要维护ub，令ub = mid; 如果不成立则令lb = mid + 1；因为mid向下取整只可能取到lb，为避免死循环就必须使lb = mid + 1；且因为我们要求的是最小化满足条件的值，既然mid不满足循环条件，也就无需考虑此值了。
2)最大化最小值 mid 向上取整(维护lb)
如果 if 条件成立，需要维护b，令lb = mid; 如果不成立则令ub = mid - 1；因为mid向上取整只可能取到ub，为避免死循环就必须使ub = mid - 1；且因为我们要求的是最大化满足条件的值，既然mid不满足循环条件，也就无需考虑此值了。
二：浮点数二分
浮点数二分就通常没有所谓的边界问题了
形式一：
for (int i = 0; i < 100; i++) {
double mid = lb + (ub - lb) / 2;
if (C(mid))
ub = m; // lb = m;  according to problem
else
lb = m; // ub = m;  according to problem
}
100次的循环精度可达10e-30
形式二：
while (ub - lb > eps) {
double mid = lb + (ub - lb) / 2;
if (C(mid))
ub = m; // lb = m;  according to problem
else
lb = m; // lb = m;  according to problem
}
eps可根据实际情况来设定，需要注意的是eps如果太小，因为浮点数机器实现的原因，可能会导致死循环。