Skip to content

Latest commit

 

History

History
201 lines (167 loc) · 5.91 KB

算法.md

File metadata and controls

201 lines (167 loc) · 5.91 KB
Raw

判断矩阵相交

首先求出P1与P3点在X方向较大值与Y方向较大值的交点，在下图中就是P3，用红点(记为M点)表示。然后求出P2与P4点在X方向较小值与Y方向较小值的交点，在下图中就是P2，用橙色点(记为N点)表示。如果M点的X坐标和Y坐标值均比N点相应的X坐标和Y坐标值小，亦即M和N可以分别构成一个矩形的左上角点和右上角点，则两矩形相交；其余情况则不相交。

ef33c3939742d780a9eef2569a11436a.png

class Solution {
public:
    int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
        int s1 = (C - A) * (D - B), s2 = (G - E) * (H - F);
        int mix = max(A, E), miy = max(B, F), maxx = min(C, G), maxy = min(D, H);
        if(mix <= maxx && miy <= maxy){
        int s3 = (maxx - mix) * (maxy - miy);
        return s1 + s2 - s3;
        }
        else return s1 + s2;
    }
};

快速排序

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace QuickSort    //***对相同元素, 不稳定的排序算法***
{
    //相对来说，快速排序数值越大速度越快 。  快速排序是所有排序里面最快的

    class Program
    {
        static void Main(string[] args)
        {
            int[] arr = { 15, 22, 35, 9, 16, 33, 15, 23, 68, 1, 33, 25, 14 }; //待排序数组
            QuickSort(arr, 0, arr.Length - 1);  //调用快速排序函数。传值(要排序数组，基准值位置，数组长度)

            //控制台遍历输出
            Console.WriteLine("排序后的数列：");
            foreach (int item in arr)
                Console.WriteLine(item);
        }

        private static void QuickSort(int[] arr, int begin, int end)
        {
            if (begin >= end) return;   //两个指针重合就返回，结束调用
            int pivotIndex = QuickSort_Once(arr, begin, end);  //会得到一个基准值下标

            QuickSort(arr, begin, pivotIndex - 1);  //对基准的左端进行排序  递归
            QuickSort(arr, pivotIndex + 1, end);   //对基准的右端进行排序  递归
        }

        private static int QuickSort_Once(int[] arr, int begin, int end)
        {
            int pivot = arr[begin];   //将首元素作为基准
            int i = begin;
            int j = end;
            while (i < j)
            {
                //从右到左，寻找第一个小于基准pivot的元素
                while (arr[j] >= pivot && i < j) j--; //指针向前移
                arr[i] = arr[j];  //执行到此，j已指向从右端起第一个小于基准pivot的元素，执行替换

                //从左到右，寻找首个大于基准pivot的元素
                while (arr[i] <= pivot && i < j) i++; //指针向后移
                arr[j] = arr[i];  //执行到此,i已指向从左端起首个大于基准pivot的元素，执行替换
            }

            //退出while循环,执行至此，必定是 i= j的情况（最后两个指针会碰头）
            //i(或j)所指向的既是基准位置，定位该趟的基准并将该基准位置返回
            arr[i] = pivot;
            return i;
        }

    }
}

约瑟夫环

0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。 例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

常规解法:

  • 将[0,n]依次存储在链表中
  • 只要链表的长度不为1，就一直循环，如果到了第m个就remove；否则将其添加到链表尾部
  • 时间复杂度为O(nm)
public int lastRemaining(int n, int m) {
     List<Integer> list=new ArrayList<>();
     for(int i=0;i<n;i++)
         list.add(i);
     while(list.size()>1){
         for(int j=0;j<m;j++){
             if(j!=m-1)
                 list.add(list.get(0));
             list.remove(0);
         }
     }
     return list.get(0);
 }

公式解法

  • f(people,num) 表示在有people个人时，报数为num，胜利的人的位置
  • people = 1 时， pos = 0
  • pos=f(people,num)=(f(people−1,num)+num)%peoplepos = f(people,num) = (f(people-1,- num)+num)% peoplepos=f(people,num)=(f(people−1,num)+num)%people
class Solution {
public:
    int lastRemaining(int n, int m) {
        int pos = 0;//1个人时
        for(int i = 2; i <= n; i++)
        {	//i表示人数
        	pos = (pos+m)%i;
        }
        return pos;
    }
};

100层的楼，2个鸡蛋，如何最快测出哪层楼扔鸡蛋不会碎？时间复杂度是多少？平均时间复杂度？

https://blog.csdn.net/qq_38316721/article/details/81351297

字符串翻转

#include <stdio.h>
#include <string.h>
#include <assert.h>
void reverse_string(char *left, char *right)    //连续的字符串逆序
{	
	char temp;
	printf("\n");printf("\n");printf("\n");
	printf("left:%s,right:%s",left,right);
	printf("\n");
	while (right > left)
	{
		temp = *left;
		*left = *right;
		*right = temp;
		left++;
		right--;
		
	}
	printf("left:%s,right:%s",left,right);
	printf("\n");
}

char *reserve(char *str)
{
	assert(str);
	char *first = str;
	char *last = str + strlen(str) - 1;
	while (*str)
	{
		char *part = str;
		while (*str != ' '&&*str != '\0')
		{
			str++;
		}
		reverse_string(part, str - 1);
		if (*str != '\0')
		{
			str++;
		}
		else
			break;
	}
	reverse_string(first, last);
	return first;
}

int main()
{
	char p[] = "student a am i";
	printf("%s\n", reserve(p));
	return 0;
}

LeetCode 236 二叉树最近公共祖先: https://blog.csdn.net/jiangziya1713/article/details/105478334

AStar

https://www.cnblogs.com/LiveForGame/p/10528393.html

动态规划

LeetCode 62：不同路径: https://blog.csdn.net/weixin_44547562/article/details/114236870