力扣 | 高性能架构探索

不能因为每次做一道算法题就开个随笔，故开个记录贴。坚持就是胜利！

IT：https://blog.csdn.net/hackbuteer1/category_9261019.html

初期我不知道该怎么讲解，所以先以代码显示为主。。。。

2021/2/28

单调数列：如果数组是单调递增或单调递减的，那么它是单调的。当给定的数组 A 是单调数组时返回 true，否则返回 false。

代码：（自己编写）

class Solution {
public:
    bool isMonotonic(vector<int>& A) {
        int size = A.size();
        if(A[size-1]>A[0])
        {
            for(int i = 0; i<size-1;i++)
            {
                if(A[i+1]<A[i])
                {
                    return false;
                }              

            }
        }
        else
        {
            for(int j = 0; j<size-1;j++)
            {
                if(A[j+1]>A[j])
                {
                    return false;
                }              

            }
        }
        return true;
    }
};

2021/3/1

给定整数1,2,4,1,7,8,3 ，求第n个之前加起来的最大值(被加的整数必须是间隔的)

使用动态规划，

//递归
int opt(std::vector<int>& nums,int i)
{
    if (i == 0)
    {
        return 1;
    }
    else if(i == 1)
    {
        return 2;
    }
    else
    {
        int A = opt(nums, i - 2) + nums[i];
        int B = opt(nums, i - 1);
        return max(A, B);
    }

}

//非递归
int dp_opt(std::vector<int>& nums)
{
    int* arr = new int[nums.size()];
    memset(arr, 0, nums.size());
    arr[0] = 1;
    arr[1] = max(arr[0], nums[1]);
    for (int i = 2; i < nums.size(); i++)
    {
        int A = arr[i - 2] + nums[i];
        int B = arr[i - 1];
        arr[i] = max(A, B);
    }
    return arr[nums.size() - 1];

}

opt(n, 6);
dp_opt(n);

拓展：给定一串数字{ 3,34,4,12,5,2 }，给出第n个数字之前加起来的和(只要有数字相加等于S即可)是否等于S，如果可以，返回true, 否则false

递归方法，也是动态规划

bool subset(std::vector< int >& nums,  int i,  int s)
{
    if (s == 0)
    {
        return true ;
    }
    else if (i == 0)
    {
        return nums[0] == s;
    }
    else if (nums[i] > s)
    {
        return subset(nums,i-1,s);
    }
    else
    {
        int A = subset(nums, i - 1, s-nums[i]);
        int B = subset(nums, i - 1, s);
        return A || B;
    }
}

bool l = subset(nums, 5, 13);

2021/3/3

给定某范围数组[m,n]，求解m到n之间所有数 '与' 之后的结果，包括m,n

一共有两种方法，都写在代码里了

#include <stdio.h>
#include <stdlib.h>

int smb(int m)
{
    int result = m;
    int count = 0;
    while (result > 0)
    {
        result = (result >> 1);
        count++;
    }
    return count - 1;
}

int set_bit(int m, int i)
{
    return (m | (1 << i));
}

int get_bit(int m, int i)
{
    return ((m >> i) & 1);
}

int rangeresult(int m, int n)
{
    int smb1 = smb(m);
    int smb2 = smb(n);
    if (smb1 != smb2)
    {
        return 0;
    }
    int msb = smb1;
    int result = 0;
    while (msb >= 0)
    {
        int x = get_bit(m, msb);
        int y = get_bit(n, msb);
        if (x != y)
        {
            return result;
        }
        else if (x == 1)
        {
            result = set_bit(result, msb);           
        }      
         msb--;      
    }

    return result;
}
int set_bit0(int m, int i) 
{
    return m &= ~(0x1 << i);
}
int rangeresult2(int m, int n)
{
    int smb1 = smb(m);
    int smb2 = smb(n);
    if (smb1 != smb2)
    {
        return 0;
    }
    int result = n;
    int x = 0;
    int temp = 0;
    while (result >= m)
    {
        if (result == 1)
        {
            return 1;
        }
        result = set_bit0(result, x);      
        x++;
        temp = result;
    }
    return temp;
}
int main()
{
    printf("%dn",smb(4));
    printf("%xn", rangeresult(23, 27));
    printf("%x", rangeresult2(23, 27));
    return 0;
}

2021/3/4

汉诺塔。。。。看完视频发现很简单：推荐这个大佬的教程

代码：

#include <stdio.h>

void hannuota(int n, char A, char B, char C)
{
    if (n == 1)
    {
        printf("%c -> %cn", A, C);
    }
    else
    {
        hannuota(n - 1, A, C, B);
        printf("%c -> %cn", A, C);
        hannuota(n - 1, B, A, C);

    }
}

int main()
{
    hannuota(4, 'A', 'B', 'C');

    return 0;
}

2021/3/5

给定两个交叉链表m,n，求它们的交叉点的值

除了暴力求解，时间复杂度m*n，使用下面的方法，可以使复杂度降低到m+n

B站视频链接：交叉链表练习题讲解

#include <stdio.h>
#include <stdlib.h>

typedef struct NodeList {
    int val;
    struct  NodeList* next;
};

int getlen_list(NodeList* node)
{
    if (!node)
    {
        return 0;
    }
    int count = 0;
    while (node != NULL)
    {
        count++;
        node = node->next;
    }
    return count;
}

NodeList* relocate_node(NodeList* node,int n)
{
    NodeList* p = node;
    for (int i = 0; i < n; i++)
    {
        p = p->next;
    }
    return p;
}

NodeList* common_list(NodeList* l1, NodeList* l2)
{
    NodeList* long_list = l1;
    NodeList* short_list = l2;
    int len_1 = getlen_list(l1);
    int len_2 = getlen_list(l2);
    if (len_1 < len_2)
    {
        long_list = l2;
        short_list = l1;
    }
    int ret = abs(len_1 - len_2);
    NodeList* p1 = relocate_node(l1, ret);
    while (p1 != NULL)
    {
        if (p1 == short_list)
        {
            return p1;
        }
        p1 = p1->next;
        short_list = short_list->next;
    }
    return NULL;

}
int main()
{
    NodeList n1, n2, n3, n4, n5, n6, n7;
    n1.val = 1;
    n2.val = 2;
    n3.val = 3;
    n4.val = 4;
    n5.val = 5;
    n6.val = 6;
    n7.val = 7;

    n1.next = &n2;
    n2.next = &n3;
    n3.next = &n4;
    n4.next = &n5;
    n5.next = &n6;
    n6.next = NULL;
    n7.next = &n4;

    printf("%dn", getlen_list(&n1));
    printf("%dn", getlen_list(&n7));
    NodeList *common_node = common_list(&n1, &n7);
    printf("%dn", common_node->val);

    return 0;

}

2021/3/6

递归：给定1，1，2，3，5，8，13....规律的数字，求出它们的和

注意：求第n个数的值与求n个数之前(包含n)所有数的和的方法是有所不同的。

#include <stdio.h>

int num(int i)    //第i位数是多少
{
    if (i == 1)
        return 1;
    else if (i == 2)
        return 1;
    else
        return num(i - 1) + num(i - 2);
}

int sum(int i)   //所有数的和
{
    if (i == 1)
        return 1;
    else if (i == 2)
        return 2;
    else
        return sum(i - 1) + num(i);
}

int main()
{
    printf("%dn", sum(8));
    return 0;
}

2021/3/7

创建平衡二叉树，并求出树的高度和最大结点的值， p.s: 中序遍历可以将数从小到大列出来

#include <stdio.h>

typedef struct NodeList {
    int val;
    struct NodeList* left;
    struct NodeList* right;
}Node;

typedef struct Tree {
    Node* root;
};

void insert(Tree* tree, int data)
{
    Node* node = new Node();
    node->val = data;
    node->left = NULL;
    node->right = NULL;

    if (tree->root == NULL)
    {
        tree->root = node;
    }
    else
    {
        Node* temp = tree->root;
        while (temp != NULL)
        {
            if (data < temp->val)
            {
                if (temp->left == NULL)
                {
                    temp->left = node;
                    return;
                }
                else
                {
                    temp = temp->left;
                }
            }
            else
            {
                if (temp->right == NULL)
                {
                    temp->right = node;
                    return;
                }
                else
                {
                    temp = temp->right;
                }
            }
        }
    }

}

void prelist(Node* node) //先序遍历
{
    if (node != NULL)
    {
        printf("%d ", node->val);
        prelist(node->left);
        prelist(node->right);
    }
}

void midlist(Node* node) //中序遍历
{
    if (node != NULL)
    {
        midlist(node->left);
        printf("%d ", node->val);
        midlist(node->right);
    }
}

void lastlist(Node* node) //后序遍历
{
    if (node != NULL)
    {
        lastlist(node->left);
        lastlist(node->right);
        printf("%d ", node->val);
    }
}

int get_hightree(Node* node)
{
    if (node == NULL)
    {
        return -1;
    }
    int left = get_hightree(node->left);
    int right = get_hightree(node->right);
    int max = left;
    if (right > max)
    {
        max = right;
    }
    return max + 1;
}

int get_maxvalue(Node* node)
{
    int max;
    if (node == NULL)
    {
        return -1;
    }
    else
    {
        int m = get_maxvalue(node->left);
        int n = get_maxvalue(node->right);
        max = node->val;
        if (m > max)
        {
            max = m;
        }
        if (n > max)
        {
            max = n;
        }
    }
    return max;
}

int main()
{
    int arr[9] = { 2,5,1,8,6,7,9,3,4 };
    Tree tree;
    tree.root = NULL;
    for (int i = 0; i < 9; i++)
    {
        insert(&tree, arr[i]);
    }

    midlist(tree.root); //中序遍历
    printf("n");
    int height = get_hightree(tree.root);
    printf("树高: %dn", height);
    int max_value = get_maxvalue(tree.root);
    printf("最大值: %dn", max_value);
    return 0;
}

2021/3/8

已知一串数字，其中一个数字占所有数字的二分之一以上，比如{1，1，1，1，2，4，3}， 1是个数是最多的。

我们的任务是写个算法来算出是哪个数字出现的频率最高。这里我们使用栈来实现。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int valuemax(int* arr,int len)
{    
    int* stack = (int *)malloc(sizeof(int)*len);
    int top = -1;

    for (int i = 0; i < len; i++)
    {
        if (top == -1)
        {
            stack[++top] = arr[i];
        }
        else if (stack[top] == arr[i])
        {
            stack[++top] = arr[i];
        }
        else
        {
            top--;
        }
    }
    return stack[0];
}

int main()
{
    int arr[] = { 2,8,3,2,1,1,1,1,1,7,1 };
    int len = sizeof(arr) / sizeof(int);
    int result = valuemax(arr, len);
    printf("%dn", result);
    return 0;
}

2021/3/9

给出一串数字，求出其中出现频率为1的数字。比如 [1,2,3,5,4,2,1,4,3]，只有'5'出现一次

这里用异或的方法，异或：如果a、b两个值不相同,则异或结果为1。如果a、b两个值相同,异或结果为0。

#include <stdio.h>

int singleNumer(int* nums, int numsize)
{
    int result = nums[0];
    for (int i = 1; i < numsize; i++)
    {
        result = result ^ nums[i];
    }
    return result;
}

int main()
{
    int nums[9] = { 1,2,3,5,4,2,1,4,3 };
    int res = singleNumer(nums, 9);
    printf("%dn", res);

    return 0;
}

2021/3/10

镜像二叉树，递归写法

void mirror_tree(Node* tree)
{
    Node* node = tree;
    if ((node == NULL) || ((node->left == NULL) && (node->right == NULL)))
    {
        return;
    }
    Node* temp = node->left;
    node->left = node->right;
    node->right = temp;

    if (node->left)
    {
        mirror_tree(node->left);
    }
    if (node->right)
    {
        mirror_tree(node->right);
    }
}

非递归写法参考：二叉树的镜像(递归&非递归)

2021/3/11

给出两个数组，将它们按从小到大重新排序，并且将新数组放到第一个数组里，假设第一个数组空间足够大。

比如：{ 9,10,11,12,13 }; { 1,2,3,4 }; 重新排序后：{ 1,2,3,4,9,10,11,12,13 } 这里我们使用归并排序

#include <stdio.h>
#include <stdlib.h>

int* guibing(int* arr1, int* arr2,int m,int n)
{
    int* arr = (int*)malloc(sizeof(int) * (m + n));
    int i = 0;
    int j = 0;
    int k = 0;

    while (i < m && j < n)
    {
        if (arr1[i] > arr2[j])
        {
            arr[k] = arr2[j];
            j++;
        }
        else
        {
            arr[k] = arr1[i];
            i++;
        }
        k++;
    }
    while (i < m)
    {
        arr[k] = arr1[i];
        i++;
        k++;
    }
    while (j < n)
    {
        arr[k] = arr2[j];
        j++;
        k++;
    }
    arr1 = arr;

    return arr1;
}

int main()
{
    int arr1[100] = { 9,10,11,12,13 };
    int arr2[4] = { 1,2,3,4 };

    int* arr = guibing(arr1, arr2, 5, 4);

    for (int i = 0; i < 9; i++)
    {
        printf("%d ", arr[i]);
    }
    return 0;
}

2021/3/

开始投入QT的怀抱，回见

2021/12/29

找出 1~n 之间的重复的数字

#include 

bool FindDuplicateValue_1( int Nums[],  int lens,  int * dup_value) {
  if (Nums == nullptr || lens <= 0) {
    return false ;
  }

  for ( int i = 0; i < lens; i++) {
    if (Nums[i] < 0 || Nums[i] > lens) {
      return false ;
    }
  }

  // Nums[4] => 2
  // Nums[2] => 2
  for ( int i = 0; i < lens; i++) {
    while (Nums[i] != i) {
      if (Nums[Nums[i]] == Nums[i]) {
        *dup_value = Nums[i];
        return true ;
      }

      int temp = Nums[i];
      Nums[i] = Nums[temp];
      Nums[temp] = temp;

      for ( int i = 0; i < lens; i++) {
        std::cout << Nums[i] <<  " " ;
      }
      std::cout << std::endl;
    }
  }

  return false ;
}

int DupCount( int Nums[],  int lens,  int start,  int end) {
  int dupcount = 0;
  for ( int i = 0; i < lens; i++) {
    if (Nums[i] >= start && Nums[i] <= end) {
      dupcount++;
    }
  }
  return dupcount;
}

bool FindDuplicateValue_2( int Nums[],  int lens,  int * dup_value) {
  if (Nums == nullptr || lens <= 0) {
    return false ;
  }

  for ( int i = 0; i < lens; i++) {
    if (Nums[i] < 0 || Nums[i] > lens) {
      return false ;
    }
  }

  int start = 1;
  int end = lens;

  int count = 0;
  while (start <= end) {
    int middle = (end - start) / 2  + start;
    count = DupCount(Nums, lens, start, middle);
    if (count >= 2) {
      if (start == end) {
        return true ;
      }
    }

    if (count > ((middle - start) + 1)) {
      end = middle;
    }  else {
      start = middle + 1;
    }
  }

  return false ;
}

int main() {
  int Nums[] = {3, 5, 6, 7, 4, 2, 2, 1};
  int lens =  sizeof (Nums) /  sizeof ( int );
  int dup_value = 0;
  if (FindDuplicateValue_1(Nums, lens, &dup_value)) {
    std::cout <<  "Find!"
              <<  " " << dup_value;
  }

  // 只能确定有重复数字
  if (FindDuplicateValue_2(Nums, lens, &dup_value)) {
    std::cout <<  "Find!" ;
  }

  return 0;
}

原文链接: https://www.cnblogs.com/strive-sun/p/14460731.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/404673

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

力扣

相关推荐