PHP按特定key进行多维数组排序
这个排序在网上直接搜索的结果有这样一个:
array_multisort(array_column($array,'sort'),SORT_ASC,$array);
这个是错误的。 切忌不要以讹传讹了。
分析排查
实际上array_multisort 是PHP内置的方法,官方有说明: PHP - array_multisort
这个排序在网上直接搜索的结果有这样一个:
array_multisort(array_column($array,'sort'),SORT_ASC,$array);
这个是错误的。 切忌不要以讹传讹了。
实际上array_multisort 是PHP内置的方法,官方有说明: PHP - array_multisort
隐约记得之前做过一个c++的题目是判断一个数是否素数(质数) 我当时给的算法是判断 2 - x/2, 因为被除数大于 x/2 那商一定小于2,所以被除数必须大于x/2
最近看书的时候发现通用的算法是计算 2- sqrt(x) 即 根号x 这就让我产生疑问了,毋庸置疑,这个算法的效率更高,时间复杂度是logn。 那为什么到sqrt(x)就够了呢?
我反复思考总算得出了结论,这里用反证法即可:
已知 n 不是素数,且a,b是 n的两个根, a*b = n
假设 b>sqrt(n),且a>=sqrt(n)
则a*b > sqrt(n) * sqrt(n) 即 a*b > n 与条件相悖
得出若存在一个根大于sqrt(n),
那必定存在另一个小于sqrt(n)的根
与此对应的逆否命题是
若不存在小于sqrt(n)的根,则不存在大于sqrt(n)的根
根据这个证明的结论,判断是否是素数,最多只需要判断到 n 的平方根即可。
在开发一款中国文化的app时,需要以竖排文字的方式展示诗文。 在CSS中,有一个文字方向的属性可以用来直接显示竖排文字,但是在iOS中并没有直接提供,所以扩展一下String类,可以返回一个竖排多行文字
先看一下效果:
简单做一下说明:
convertVerticalText 是将多行文字转变为多列文字的处理过程,类似于矩阵的对角。
首先获取待转换的文字一共有多少行,那么也就对应着转换后每一行有几个字。
由于每一行的文字个数未必相同,在转换为列的时候,就意味着会有空白,所以要获取最长一行有多少个字符。 每次在取完有效字符后,如果没有达到最长字符时,就要自动填入空白字符了。
数据结构、算法与应用 习题6.1 69题 p143
这里应该能支持两种表示法,1链表,2数组。
使用链表比较符合我们直观上对于数字的印象,其中将 rear链接到最后一位数,那么使用prev就可以陆续的取出每一个数字。 并且在进行数学运算时,我们无需关注最终的位数,只需要将结果insert进入结果链表中即可。
由于没有规定一定是正整数,所以需要给一个符号。 (在网上也搜索了一些大数运算的参考,没有提供有符号运算的版本) 带符号的时候,逻辑会变复杂不少。
这里我给出一个带符号的方式 其中isNegative true为负数,false为正数
为了表示符号对于运算的影响,我会写两个版本的 加法
class BigInt: public Chain<int>{
public:
bool isNegative = false;
BigInt( int* a, int size ){ // 基于数组构造
for( int i=0; i<size; i++ ){
insert( a[i] );
}
}
// 最基本的 正正 相加
BigInt& operator+( BigInt& bigInt ){
int plus = 0; // 进位
int res = 0; // 单次计算结果
BigInt result = new BigInt; // 结果
ChainNode<int>* cursor = last();
ChainNode<int>* targetCursor = bigInt.last();
// 使用倒序的方式取出元素并计算
while( cursor->prev() && targetCursor->prev() ){
res = cursor->element + targetCursor->element + plus;
plus = res > 9 ? 1 : 0;
result->prepend( res ); // prepend即为 addAfter( head )
cursor = cursor->prev();
targetCursor = targetCursor->prev();
}
while( cursor->prev() ){
result->prepend( cursor->element );
cursor = cursor->prev();
}
while( targetCursor->prev() ){
result->prepend( targetCursor->element );
targetCursor = targetCursor->prev();
}
return result;
}
// 完整版 带符号运算的加法 (不是重载!!!)
BigInt& operator+( BigInt& bigInt ){
BigInt result = new BigInt; // 结果
result.isNegative = size() >= bigInt.size() ? isNegative : bigInt.isNegative; // 暂定为较大位数。 如果位数相同,根据最后一次计算结果修正。
int plus = 0; // 进位或借位
int res; // 单次计算结果
ChainNode<int>* cursor = last(); // 当前游标
ChainNode<int>* targetCursor = bigInt.last(); // 目标游标
while( cursor->prev() && targetCursor->prev() ){
res = isNegative ? -cursor->element : cursor->element
+ bigInt.isNegative ? -targetCursor->element : targetCursor->element
+ plus; // 我们把大数中的每一个数 都当成 a[i] * 10i来看。
// 绝对值超过>9的都需要向上进一位(一定是同符号)
// 不同符号 结果小于0的 需要借位
// 同符号小于0,不同符号大于0小于10的都可以忽略
// 小于0的时候 res需要取绝对值,保持元素的非负
if( res >9 || res<-9 ){
plus = 1;
}else if( res < 0 ){
plus = isNegative == bigInt.isNegative ? 0 : -1;
res = -res;
}
result.prepend(res);
}
if( size() == bigInt.size() ){ // 修复位数相同的问题
if( plus>0 ){
result.prepend(1); // 一定是同符号的,直接+1
}else if( plus<0 ){
result.isNegative = true; // 此时已经无法借位了,确认最终结果为负数
}
}
// 任意链表仍有元素未计算,继续补齐
while( cursor->prev() ){
result->prepend( cursor->element + plus );
plus = 0;
cursor = cursor->prev();
}
while( targetCursor->prev() ){
result->prepend( targetCursor->element + plus );
plus = 0;
targetCursor = targetCursor->prev();
}
// 修复首位为0的情况 // 全部删除则为空 即0
while( result.first().element == 0 ){
result.remove( result.first() );
}
return result;
}
// 在有符号加法的前提下,减法运算就简单多了
BigInt& operator-( BigInt& bigInt ){
bigInt.isNegative = !bigInt.isNegative; // 符号位颠倒
BigInt result = *this + bigInt;
bigInt.isNegative = !bigInt.isNegative; // 恢复
return result;
}
}
复杂度O(n)
template <class T>
void chain<T>::theSize( int n ){
chainNode<T> current = firstNode();
int i=0, max = _size < n ? _size : n;
// 由于不是双向链表,所以需要先到达n的极点
while( i < max ){
current = current->next();
i++;
}
chainNode<T> tmp;
// 如果有多余的
while( _size > n ){
tmp = current->next();
delete current; // 系统会执行element析构
current = tmp;
}
_size = n;
}
复杂度O(n) 在实际使用的时候,链表一般不用index表示法来获取或设置元素。因为每次都相当于O(n)的复杂度。
template <class T>
void chain<T>::checkIndex( int theIndex ){
if( theIndex <0 || theIndex >= _size ){
throw illegalIndex("Out of range");
}
}
template <class T>
void chain<T>::set( int theIndex, T& theElement ){
checkIndex(theIndex);
chainNode<T>* current = firstNode();
int i = 0;
while( i < _size ){
current = current->next();
}
current->element.~T(); // 析构
current->element = theElement;
}
复杂度O(n) 和上面的setSize类似,做一次遍历,之后将切割掉的部分接起来即可。
template <class T>
void chain<T>::setSize( int fromIndex, int toIndex ){
checkIndex(fromIndex);
checkIndex(toIndex);
chainNode<T>* current = firstNode();
int i=0;
// fromIndex的极点
while( i < fromIndex ){
current = current->next();
i++;
}
chainNode<T>* tmp;
while( i < toIndex ){
tmp = current->next();
delete current; // 系统会执行element析构
current = tmp;
}
_size -= toIndex-fromIndex +1; // 考虑左右闭区间
}
复杂度O(n) 遍历元素并比对,不即时返回。
template <class T>
int chain<T>::lastIndex( T& theElement ) const{
if( empty() ) return -1;
chainNode<T>* current = firstNode();
int i = 0, lastIndex = -1;
while( i< _size ){
if( current->element == theElement ){
lastIndex = i;
}
current = current->next();
i++;
}
return lastIndex;
}
复杂度O(n) 实际上重载应该包含两种,分别是提供左值,右值返回。
template <class T>
const T& chain<T>::operator[](int n) const{ } // 右值
T& chain<T>::operator[]( int n) const{ // 左值
int i = 0;
chainNode<T>* current = firstNode();
while( i < n ){
current = current->next();
}
return current->element;
}
复杂度O(n) 同步遍历两个链表元素,一旦发现不同元素返回false。
template <class T>
bool chain<T>::operator==( chain<T>& c) const{
if( size() != c.size() ) return false;
chainNode<T>* current = firstNode();
chainNode<T>* target = c.firstNode();
int i = 0;
while( i < size() ){
if( current->element !== target->element ) return false;
current = current->next();
target = target->next();
}
return true;
}
复杂度O(n)
template <class T>
bool chain<T>::operator!=( chain<T>& c) const{
return !*this == c;
}
复杂度O(n) 略微需要注意的是,除了最后一项的值完全相等以外,其他的相等 都不能判断非<。 所以在遍历的靠前阶段,== 都应该算成功,只有最后一项相等判断非小于。
template <class T>
bool chain<T>::operator<( chain<T>& c) const{
if( size() > c.size() ) return false;
chainNode<T>* current = firstNode();
chainNode<T>* target = c.firstNode();
int i = 0;
while( i < size() ){
if( current->element > target->element ){
return false;
}else{
current = current->next();
target = target->next();
}
}
if( current->element == target->element ) return false;
return true;
}
最近回复