Skip to content

Latest commit

 

History

History
590 lines (451 loc) · 11.4 KB

算法题.md

File metadata and controls

590 lines (451 loc) · 11.4 KB

[toc]

1.查询最长子串

<?php

function getString($s) {
	$len = strlen($s);
	$res = array();
	$r = array();
	for ($i = 0; $i < $len; $i++) {
		if (in_array($s[$i], $r)) {
			$r = array_slice($r, array_search($s[$i], $r) + 1);
		}
		$r[] = $s[$i];
		if (count($r) > count($res)) {
			$res = $r;
		}
	}
	return implode('', $res);
}

$str = 'abcab';

print_r(getString($str));

2. 母牛问题。有一母牛，到4岁可生育，每年一头，所生均是一样的母牛，到15岁绝育，不再能生，20岁死亡，问n年后有多少头牛?

<?php

function getCows($years)
{
//    看第一只牛算1岁还是0岁
    $cowMap[1] = 1;
    $count = 0;
    for ($i = 1; $i < $years; $i++) {
        for ($j = 19; $j > 0; $j--) {
            $cowMap[$j] = $cowMap[$j - 1] ?? 0;
        }
        $cowMap[0] = 0;
        for ($j = 4; $j < 15; $j++) {
            $cowMap[0] += $cowMap[$j] ?? 0;
        }
    }
    array_walk($cowMap, function ($value) use (&$count) {
        $count += $value;
    });
    return $count;
}

给定String类型的数组strArr，再给定整数k，请严格按照出现顺序打印出现出现次数前k名的字符串。strArr=["1","3","3","4","1","5","1"], k=3 No.1:1,times:3 No.2:3,times:2 No.3:4,times:1 要求：如果strArr长度为N，时间复杂度请达到O(Nlogk)【2月16 头条】

function getSort($str, $k = 1) {
	$arr = array();

	foreach ($str as $val) {
		if (!isset($arr[$val])) {
			$arr[$val] = 1;
		} else {
			$arr[$val]++;
		}
	}
	arsort($arr);
	return array_slice($arr, 0, $k);
}

$strArr = ["1", "3", "3", "3", "3", "4", "1", "5", "1"];

var_dump(getSort($strArr, 3));

求中位数。（【1，2】， 【3，4】）

<?php

class Solution {
	/**
	 * @param Integer[] $nums1
	 * @param Integer[] $nums2
	 * @return Float
	 */
	function findMedianSortedArrays($nums1, $nums2) {
		$nums = array();
		while (!empty($nums1) && !empty($nums2)) {
			if ($nums1[0] < $nums2[0]) {
				$nums[] = array_shift($nums1);
			} else {
				$nums[] = array_shift($nums2);
			}
		}

		while (!empty($nums1)) {
			$nums[] = array_shift($nums1);
		}

		while (!empty($nums2)) {
			$nums[] = array_shift($nums2);
		}

		$count = count($nums);
		if ($count % 2 == 1) {
			return $nums[$count / 2];
		} else {
			$mid = $count / 2;
			return ($nums[$mid] + $nums[$mid - 1]) / 2;
		}
		return -1;
	}
}

$result = new Solution();

$nums1 = [1, 2];
$nums2 = [3, 4];

print_r($result->findMedianSortedArrays($nums1, $nums2));

算法题，100元红包，分给10个人，没人金额在8-12元之间

先分给没人8元，然后再随机跟每个用户分钱。这种方式还是比较简单和粗暴的。

<?php
$cash = 20;
$user_arr = array(8,8,8,8,8,8,8,8,8,8);
while($cash>0){
    $user_id = rand(0, 9);
    if($user_arr[$user_id]<12){
        $user_arr[$user_id]++;
        $cash--;
    }
}
var_dump($user_arr,array_sum($user_arr));die;

翻转链表

/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val) { $this->val = $val; }
 * }
 */
class Solution {

    /**
     * @param ListNode $head
     * @return ListNode
     */
    function reverseList($head) {
        if (empty($head) || empty($head->next)) return $head;
        $p = $this->reverseList($head->next);
        $head->next->next = $head;
        $head->next = null;
        return $p;
    }
}

已知一随机发生器，产生0的概率是P，产生1的概率是1-P。现在需要构造一个发生器，使得它构造0和1的概率均为1/2，请写出思路或伪代码

由于需要产生1/2，而用1位0，或1位1无法产生等概率，因此，考虑将随机数扩展成2位：

00   p*p

01  p*(1-p)

10  (1-p)*p

11 (1-p)*(1-p)

有上述分析知道，01和10是等概率的，因此我们只需要产生01和10就行了。于是可以，遇到00和11就丢弃，只记录01和10。可以令，01表示0,10表示1，则等概率1/2产生0和1了。

求解最大的k个数。

求解两个有序数据里面，是否有相同的元素，不允许用php函数。

求解1的个数

<?php
function getbit($nums) {
    $bits = 0;
    $mask = 1;
    for ($i = 0; $i < 32; $i++) {
        if (($nums & $mask) != 0) {
            $bits++;
        }
        $mask <<= 1;
    }
    return $bits;
}

function getBit2($nums) {
    $sum = 0;
    while ($n != 0) {
        sum++;
        $n &= ($n - 1);
    }
    return $sum;
}

var_dump(getbit(12));

有1999个球，甲乙两人轮流取，每人每次可取1---4个，去到最后一个球者为输，如果甲先取，怎样才能获胜？

1999÷（1+4）
=1999÷5
=399…4

答：甲先拿4个，然后看乙拿几个，甲拿的球数与乙拿的和是5，甲一定胜利．

二叉树的最小深度

<?php

// 二叉树的最小深度
function getDeep($root) {
    if (empty($root)) {
        return 0;
    }
    
    return $this->deep($root);
}

function deep($root) {
    if (empty($root->left) && empty($root->right)) {
        return 1;
    }

    if ($root->left) {
       $leftDeep = $this->deep($root->left) + 1;
    }
    
    if ($root->right) {
        $rightDeep = $this->deep($root->right) + 1;
    }
    
    return min($leftDeep, $rightDeep);
}

什么是hash

hash就是对数组的一种延伸吧。

以数组为例，key从1-89.但是假如用户的key是0105111111这种形式呢？就得需要hash计算去进行对应到响应的key，比如说对应的key值是1.

快速排序

<?php

function quickSort($arr) {
    if (empty($arr)) {
        return [];
    }
    

    
    $provit = $arr[0];
    $count = count($arr);
    if ($count == 1) {
        return $arr;
    }
    
    $left = array();
    $right = array();
    for ($i = 1; $i < $count; $i++) {
        if ($arr[$i] < $provit) {
            $left[] = $arr[$i];
        } else {
            $right[] = $arr[$i];
        }
    }
    
    $left = $this->quickSort($left);
    $right = $this->quickSort($right);
    
    return array_merge($left, [$provit], $right);
}

一个索引表 a => 2000W，数据有2000w，然后索引字段为

{ b, c, d }

b+c index 索引为bc 下面这个语句能命中索引么？

select * from a where c = 1 and b = 2 order by d asc limit 10;

能命中bc索引，但是这个语句效率不高，因为d上面没有索引，导致按d排序会很慢。

只考虑数据库的情况，A => 500个�库存，2000个人同时过来抢。如何避免超卖的问题。

商品的库存表
{
 sku_no,
 num,
}

// 比如用户抢购商品数量为5 // 如果抢购数量表比库存大， 直接返回

----
begin;
select num from goods where sku_no = xxxxx for update;
update goods set num = num - 5 where sku_no = xxxxx;
commit
------

用户订单表

{
 user_id,
 sku_no,
 num
}

insert into order values(xxxx, xxxx, 5);

有64只兔子，8条跑道，每次跑8只兔子，可以决出1~8名次，最少跑几次可以算出前3名

  1. 首先64只兔子，分成8组，然后都跑一遍。跑8次
  2. 然后每组里面的第一名都跑一次。然后 分出名次。第8名，以及他所在的组，就不用考虑了。
  3. 然后让第一组的 23 和第二组的第12 第三组的1，再去跑一下。 第一二三组的第一名，都取取出来。

求每个渠道的转换率

select channel,sum(register)/sum(activate) as per from t where activate_time = '2020-03-10' group by channel;

是很大的文件，每一行都是一个数。最大的一个数值。

1，2，3，2，3，4，5

二叉树的反转

<?php

function get($root) {
    if (empty($root)) {
        return null;
    }
    
    $left = '';
    $right = '';
    
    if ($root->left) {
        $left = get($root->left);
    }
    
    if ($root->right) {
        $right = get($root->right);
    }
    
    $root->left = $right;
    $root->right = $left;
    return $root;
}

如果不用递归，该怎么实现呢？面试问道了。用队列就可以。

ip to int 将一个ip地址（182.92.31.125）转成整数？

<?php

function ip2Int($str) {
    $data = 0;
 $str = explode('.', $str);
 for ($i = 0; $i < count($str); $i++) {
         $data &= ($str[$i] << (8 * $i));
 }
 return $data;
}

最长回文吧？


func longestPalindrome(s string) string {
    var maxLen int = 1
    var minIndex int
    var maxIndex int = 1

    if s == "" {
        return s
    }

    if len(s) == 1 {
        return s
    }
    
    for i := 0; i < len(s); i++ {
       k := i
       j := i
        for j < len(s) - 1 && s[k] == s[j+1]  {
            j = j + 1
        } 
        for k > 0 && j < len(s) - 1 && s[k - 1] == s[j + 1] {
            k = k - 1
            j = j + 1
        } 
       
       tmpLen := j - k + 1
       if tmpLen > maxLen {
           minIndex = k
           maxIndex = j + 1
       }
    }

    return s[minIndex:maxIndex]
}

 function filterIP($ip){
   $ip_low = ip2Int($ip_low);
   $ip_top = ip2Int($ip_top);
   $black_low = ip2Int($black_low);
   $black_top = ip2Int($black_top);
   $ip = ip2Int($ip);
   if ($ip >= $black_low && $ip <= $black_top) {
     return false;
   }
   if ($p < $ip_low || $ip > $ip_top) {
     return false;
   }
   
   return true;
 }

function ip2Int($ip) {
  $data = 0;
  $str = explode('.', $p);
  for ($i = 0; $i < count($str); $i++) {
    $data &= ($str[$i] << (8 * $i));
  }
  return $data;
}

目标路径和。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
     bool hasPathSum(TreeNode* root, int sum) {
        if(!root)return false;
        if((!root->left)&&(!root->right)&&sum==root->val){
            return true;
        }
        return hasPathSum(root->left,sum-root->val)||hasPathSum(root->right,sum-root->val);
    }
};

非递归形式怎么实现？

下面会输出什么？


$items = ['a', 'b', 'c', 'd'];
 

foreach($items as &$item) {
}

foreach($items as $item) {
}

echo json_encode($items);

-----------------------------

$items = ['a', 'b', 'c', 'd'];


foreach($items as $item) {
}

foreach($items as &$item) {
}

echo json_encode($items);

输出一个合法的ip

题目

全部名单 [127.0.0.1] [195.0.0.1]

黑名单 [185.0.0.1] [187.0.0.1]


  <?php
 
  function getValidIp($ip) {
  // 127.0.0.1] [195.0.0.1]
 
  // 黑名单
  // [185.0.0.1] [187.0.0.1]
     if (ip2long($ip) < ip2long('127.0.0.1') || ip2long($ip) > ip2long('195.0.0.1')) {
         return false;
     }
     if (ip2long($ip) > ip2long('185.0.0.1') && ip2long($ip) < ip2long('187.0.0.1')) {
         return false;
     }
     return $ip;
  }
 
  var_dump(getValidIp('184.0.0.1'));
  var_dump(getValidIp('18666666.0.0.1'));

每隔k个节点，进行翻转

动态最短路径之和，面试官说是入门级

最近公共父节点

去掉几个数字，剩下的数字最大？

例如数字9784596 比如去掉4个数字，剩下的数字最大，应该是剩 456.

应该考虑的是一个增进的关系吧。

零钱兑换 头条

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

示例 1:

输入: coins = [1, 2, 5], amount = 11 输出: 3 解释: 11 = 5 + 5 + 1