常用算法题

如有笔误，欢迎留言指正或讨论！

快排算法

---

冒泡算法

package main

import "fmt"

func mpPx(arr []int) []int {
	tmp := 0
	arrLen := len(arr) - 1

	//如 arr = [1,2,3,4,5]  len = 5
	//外循环：4次  内循环：4 - i		  前后两个值比较、替换值
	// i = 0	 j 循环次数：4-0次 4	  j > j+1 : 12 23 34 45
	// i = 1	 j 循环次数：4-1次 3	  j > j+1 : 12 23 34
	// i = 2	 j 循环次数：4-2次 2	  j > j+1 : 12 23
	// i = 3	 j 循环次数：4-3次 1	  j > j+1 : 12
	
	for i := 0; i < arrLen; i++ {
		for j := 0; j < arrLen-i; j++ {
			if arr[j] > arr[j+1] {
				tmp = arr[j+1]
				arr[j+1] = arr[j]
				arr[j] = tmp
			}
		}
	}

	return arr
}

func main() {
	arr := []int{24, 69, 80, 57, 13}
	newArr := mpPx(arr)
	fmt.Println(newArr)
}

---

二分查找

注意：一定必须是有序的数组

 package main

import "fmt"

func binarySearch(n int, arr []int) int {

	leftKey := 0
	rightKey := len(arr) - 1

	for leftKey <= rightKey {
		// 中间值键 = 左右键相加除以2 （!!! 重点 !!!）
		middleKey := (leftKey + rightKey) / 2
		if arr[middleKey] == n {
			return middleKey // key
		} else if arr[middleKey] > n {
			// 说明在右边，rightKey坐移到中间值的上一个键
			rightKey = middleKey - 1
		} else {
			// 说明在左边，leftKey右移到中间值的下一个键
			leftKey = middleKey + 1
		}
	}

	return -1
}

func main() {
	n := 77
	arr := []int{1, 3, 5, 7, 8, 33, 66, 77, 99}
	newArr := binarySearch(n, arr)
	fmt.Println(newArr)
}

---

链表反转

class Node
{
    public $data;

    public $next;
}

//头插法创建一个链表
$linkList = new Node();
$linkList->next = null;//头结点

for ($i = 1; $i <= 10; $i++) {
    $node = new Node();

    $node->data = "aaa{$i}";//创建新结点$node

    $node->next = $linkList->next;//$node->next指向头结点->next

    $linkList->next = $node;//头结点->next指向$node
}

function ReverseList($pHead)
{
    $old = $pHead->next;//跳过头结点

    $new = null;

    //反转过程
    while ($old != null) {
        $tmp = $old->next;

        $old->next = $new;

        $new = $old;

        $old = $tmp;
    }

    //给新链表加个头结点
    $newHead = new Node();
    $newHead->next = $new;
    var_dump($newHead);
}

ReverseList($linkList);

斐波那契数

斐波那契数，亦称之为 斐波那契数列（意大利语： Successione di Fibonacci)

又称 黄金分割数列、费波那西数列、费波拿契数、费氏数列

指的是这样一个数列：0、1、1、2、3、5、8、13、21、……

在数学上，斐波纳契数列以如下被以递归的方法定义：

F0=0，F1=1，Fn=Fn-1+Fn-2（n>=2，n∈N*）

用文字来说就是 斐波那契数列 列由 0 和 1 开始，之后的 斐波那契数列 系数 就由之前的 两数相加。

//请使用递归的方式，求出 斐波那契数 0、1、1、2、3、5、8、13、21、……
//给你一个整数n, 求出它的值是多少 ？
package main

import (
	"fmt"
)

//斐波那契数列 给定前两个值，输入n返回对应的值
func test1(n int) int {
	if n == 1 {
		return 0 //第一个值 固定
	} else if n == 2 {
		return 1 //第二个值 固定
	} else {
		return test1(n-1) + test1(n-2)
	}
}

//斐波那契数列 给定前两个值【1,1】，输入n返回数列切片数组
//6 [1 1 2 3 5 8]
func fbn(n int) []int {

	fbnSlice := make([]int, n)
	fbnSlice[0] = 1
	fbnSlice[1] = 1

	for i := 2; i < n; i++ {
		fbnSlice[i] = fbnSlice[i-1] + fbnSlice[i-2]
	}

	return fbnSlice
}

func main() {

	var n int

	_, _ = fmt.Scanf("%d", &n)

	j := test1(n)
	fmt.Println(j)
  
  nSlice := fbn(n)
	fmt.Println(n, nSlice)

}

---

算法：数组去重

package main

import "fmt"

func main() {
	arr := []int{1, 2, 3, 4, 5, 5, 6, 7, 8, 9}

	var result []int
	newArr := make(map[int]bool)

	for _, v := range arr {
		if _, ok := newArr[v]; !ok {
			newArr[v] = true
			result = append(result, v)
		}
	}

	fmt.Println(result)
}

---

算法：寻找最长不含有重复的字符的字串

//案例
//1、abcbbccaaa		3
//2、bbbbbbbb		  3
//3、jabad		  		3
//4、我爱你中国我		5

 func lengthOfNonRepeatingSubStr(s string) int {
	lastOccurred := make(map[rune]int)
	start := 0 //最长不含有重复的字符字串开始
	maxLength := 0

   //[]rune(s) 字符串转字符编码
	for i, ch := range []rune(s) {
    //记录开始位置 1是否存在 2当前i位置值加1：新开始的位置赋值给start
		lastI, ok := lastOccurred[ch]
		if ok && lastI >= start {
			start = lastI + 1 //新开始的位置赋值给 start
		}
		//判断从开始位置个数 > maxLength：主要就是为了看下重复值之前的范围有没有大于现在的个数
		//i-start：上个重复的位置
		//i-start +1： 上个重复的位置开始（不包括） ~ 到现在这个重复的位置（+1）的个数
		//如：123451  5-1:(2,3,4,5) +1:(1) = 5(23451)
		if i-start+1 > maxLength {
			maxLength = i - start + 1
		}
		lastOccurred[ch] = i
	}

	return maxLength
 }

---

/*
 * 题目：n只兔子放到y个笼子，要求每个笼子重量一样，成功返回：true  失败返回：false
 *
 * 要求：兔子重量为正整数，且不许杀兔子，数组长度不超过15
 *
 * 题目分析：
 * 1、兔子都是为正整数，每个笼子承载的重量（n个兔子体重 / y个笼子）如果出现小数点有余数可直接返回 false;
 * 2、基于第一点分析，每只兔子的重量 >= 每个笼子承载的重量;
 *
 */

$y = 3; //总笼子数

$n_arr = [2, 2, 3, 3, 5, 1]; //每只兔子的体重

$n_total = array_sum($n_arr); //兔子总重量

$y_weight = $n_total / $y; //每个笼子承载的重量

if (!is_int($y_weight)) {
    var_dump(false);
    die();
}

for ($i = 0; $i < count($n_arr); $i++) {
    if ($n_arr[$i] == $y_weight) {
        $y--;  
    } else {
        $surplus = $y_weight - $n_arr[$i]; //这个笼子剩余承载的重量
        if (!in_array($surplus, $n_arr)) {
            break;
        }
        $y--;
        unset($n_arr[$surplus]); //取出一个笼子的兔子
    }
}

// 判断笼子是否刚好用完
if (empty($y)) {
    var_dump(true);
    die();
}

var_dump(false);
die();

---

//给定一个正整数n。确定n是否为素数

func IsPrime(number int) bool {
  for i := 2; i <= number; i ++ {
    if number % i == 0 {
      return false
    }
  }
 
  return true
}

---

//给出一个非负整数列表，将它们排列成最大数
func LargestNumber(arr []int) string {
	arrLen := len(arr)
	for i := 0; i < arrLen-1; i++ {
		for j := i + 1; j < arrLen; j++ {
			x, _ := strconv.Atoi(strconv.Itoa(arr[i]) + strconv.Itoa(arr[j]))
			y, _ := strconv.Atoi(strconv.Itoa(arr[j]) + strconv.Itoa(arr[i]))
			if x < y {
				temp := arr[i]
				arr[i] = arr[j]
				arr[j] = temp
			}
		}
	}

	var res string
	for k := 0; k < arrLen; k++ {
		res += strconv.Itoa(arr[k])
	}

	return res
}