算法拾遗01 2021-10-20

本文主要是介绍算法拾遗01 2021-10-20，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

链表反转

public class Solution {
    public ListNode ReverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode second = head.next;
        head.next = null;
        ListNode three = null;
        while (second != null) {
            three = second.next;
            second.next = head;
            head = second;
            second = three;
        }
        return head;
    }
}

scanf and printf

scanf("%d", &n);  int  
scanf("%lld", &n);  long long
scanf("%f", &fl); float
scanf("%lf", &db);  double
scanf("%c", &c);  char
scanf("%s", str);  字符串(char数组)
    
    
printf("%d", n);  int
printf("%lld", n);  long long
printf("%f", fl);  float
printf("%f", db);  double
printf("%c", c);  char
printf("%s", str);  字符串(char 数组)

字符数组的输入输出

#include<stdio.h>
int main() {
    char str[10];
    scanf("%s", str);
    printf("%s", str);
    return 0;
}

getchar 和 putchar分别用来输入和输出单个字符

#include<stdio.h>
int main() {
    char str[5][5];
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
        	str[i][j] = getchar();            
        }
        getchar(); // 把输入中的每行末尾的换行符吸收掉
    }
    
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            putchar(str[i][j]);
        }
        putchar('\n');
    }
    return 0;
}

// gets用来输入一行字符串
// puts用来输出一行字符串

当题目没有说明有多少数据需要读入时，可以利用scanf的返回值是否为EOF来判断输入是否结束

while (scanf("%d", &n) != EOF) {
    
}

题目要求输入的数据满足某个条件时停止输入(当输入的两个a b都为0是结束输入)

#include<stdio.h>
int main() {
    int a, b;
    while (scanf("%d%d", &a, &b), a || b) {
        printf("%d\n", a + b);
    }
    return 0;
}

// 当a和b中有一个不为0时就结束循环(循环条件a||b的全写为a!=0||b!=0)

指针与数组

#include<stdio.h>
int main() {
    int a[10] = {1};
    int* p = a;
    printf("%d\n", *p);
    return 0;
}

只有在获取地址的情况下对元素进行操作，才能真正地修改变量

#include<stdio.h>

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int main() {
    int a = 1, b = 2;
    int* p1 = &a, * p2 = &b;
    swap(p1, p2);
    printf("a = %d, b = %d\n", *p1, *p2);
    return 0;
}

指针的引用

#include<stdio.h>

void swap(int* &p1, int* &p2) {
    int* temp = p1;
    p1 = p2;
    p2 = temp;
}

int main() {
    int a = 1, b = 2;
    int* p1 = &a, * p2 = &b;
    swap(p1, p2);
    printf("a = %d, b = %d\n", *p1, *p2);
    return 0;
}

结构体

struct studentInfo {
    int id;
    char gender;
    
    // 用以不初始化就定义结构体变量
    studentInfo(){}
    
    // 只初始化gender
    studentInfo(char _gender) {
        gender = _gender;
    }
    
    // 同时初始化id和gender
    studentInfo(int _id, char _gender) {
        id = _id;
        gender = _gender;
    }
};

#include<stdio.h>

struct Point {
    int x, y;
    Point(){}
    Point(int _x, int _y): x(_x), y(_y) {} // x和y的初始化
}pt[10];

int main() {
    int num = 0;
    for (int i = 1; i <= 3; i++) {
        for (int j = 1; j <= 3; j++) {
            pt[num++] = Point(i, j); // 使用构造函数
        }
    }
    for (int i = 0; i < num; i++) {
        printf("%d, %d\n", pt[i].x, pt[i].y);
    }
    return 0;
}

全排列

// 设定一个数组P，用来存放当前的排列
// 再设定一个散列数组hashTable，其中hashTable[x]当整数x已经在数组P中时为true

#include<cstdio>
const int maxn = 11;

// P为当前排列，hashTable记录整数x是否已经在P中
int n, P[maxn], hashTable[maxn] = {false};

// 当前处理排列的第index号位
void generateP(int index) {
    if (index == n + 1) { // 递归边界，已经处理完排列的1~n位
        for (int i = 1; i <= n; i++) {
            printf("%d", P[i]); // 输出当前排列
        }
        printf("\n");
        return;
    }
    for (int x = 1; x <= n; x++) {
        if (hashTable[x] == false) {
            P[index] = x;
            hashTable[x] = true;
            generateP(index + 1);
            hashTable[x] = false;
        }
    }
}


int main() {
    n = 3; // 欲输出1~3的全排列
    generateP(1); // 从P[1]开始填
    return 0;
}

皇后问题

int count = 0;

void generateP(int index) {
    if (index == n + 1) {
        bool flag = true; // 递归边界，生成一个排列
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                if (abs(i - j) == abs(P[i] - P[j])) {
                    flag = false;
                }
            }
        }
        if (flag) {
            count++;
        }
        return;
    }
    
    for (int x = 1; x <= n; x++) {
        if (hashTable[x] == false) {
            P[index] = x;
            hashTable[x] = true;
            generateP(index + 1);
            hashTable[x] = false;
        }
    }
}

枚举与回溯

枚举所有情况，然后判断每一种情况时候合法的做法是非常朴素的
一般把不使用优化算法、直接用朴素算法来解决问题的做法称为暴力法

如果在到达递归边界前的某层，由于一些事实导致已经不需要往任何一个子问题递归，就可以直接返回上一层。一般把这种做法称为回溯法

皇后问题改进

void generateP(int index) {
    if (index == n + 1) { // 递归边界，生成一个合法方案
        count++; // 能到达这里的一定是合法的
        return;
    }
    
    for (int x = 1; x <= n; x++) {
        if (hashTable[x] == false) {
            bool flag = true;
            for (int pre = 1; pre < index; pre++) {
                if (abs(index - pre) == abs(x - P[pre])) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                P[index] = x;
                hashTable[x] = true;
                generateP(index + 1);
                hashTable[x] = false;
            }
        }
    }
}

java大数加法

import java.util.*;

public class Solution {
    public String solve (String s, String t) {
        Stack<Integer> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();
        int i = s.length() - 1;
        int j = t.length() - 1;
        int carry = 0;
        
        while (i >= 0 || j >= 0 || carry != 0) {
            carry += i >= 0 ? s.charAt(i--) - '0' : 0;
            carry += j >= 0 ? t.charAt(j--) - '0' : 0;
            stack.push(carry % 10);
            carry = carry / 10;
        }
        
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        
        return sb.toString();
    }
}

1到10的阶乘之和

int ans = 0;

for (int i = 1; i <= 10; i++) {
    int t = 1;
    for (int j = 1; j <= i; j++) {
        t *= j;
    }
    ans += t;
}

跳出两层或者多层循环

当t>1000时结束双层循环，使用break语句显然是不行的，break语句只能跳出单层循环。
当需要跳出两层或者多层循环时，最常用的方法是引入另一个通常为bool类型的标志量，将该标志量加入到多层循环的条件中，并在循环体内部根据具体条件去修改这个标志量

bool flag = true;
int ans = 0;
for (int i = 1; i <= 10 && flag; i++) {
    int t = 1;
    for (int j = 1; j <= i; && flag; j++) {
        t *= j;
        if (t > 1000) {
            flag = false;
        }
    }
    ans += t;
}

c++ 优化cin/cout的方法

#include<bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    // 要执行的代码
    
    return 0;
}

c++模板

#include<bits/stdc++.h>
using namespace std;
using gg = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // 要执行的代码
    return 0;
}

精度

#include<bits/stdc++.h>
using namespace std;
int main() {
    for (double i = 0.1; 1.0 - i > 1e-6; i += 0.1) {
        cout<<i<<" ";
    }
    return 0;
}

3n+1猜想

#include<bits/stdc++.h>
using namespace std;
using gg = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    gg ni, ans = 0;
    cin>>ni;
    for (; ni != 1; ans++) {
        if (ni % 2 == 1) {
            ni = 3 * ni + 1;
        }
        ni /= 2;
    }
    cout<<ans;
    return 0;
}

(const String &s1, const String &s2)

使用传引用调用修改实参，是引用最典型的作用

引用的另一个重要左右是避免拷贝。拷贝大的类型对象或容器对象比较低效
准备编写一个函数比较两个string对象的长度。因为string对象可能会非常长，如果使用传值调用，拷贝过程可能会非常低效。所以应该尽量避免直接拷贝它们，这时使用引用形参是比较明智的选择

bool f(string& s1, string& s2) {
    return s1.size() < s2.size();
}

由于传引用调用可能会改变实参，又不希望在比较两个string对象的长度的函数中改变实参的值，那么可以在函数f的参数上加上const限定符，这时形参类型称为常量引用或常引用，在函数f中参数值的任何修改都会被视为一种语法错误

bool f(const string& s1, const string& s2) {
    return s1.size() < s2.size();
}

// 两组输入数据之间有一个空行，最后一组数据后面没有空行

#include<stdio.h>

int main() {
    int T, n, a;
    scanf("%d", &T);
    while (T--) {
        int sum = 0;
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%d", &a);
            sum = sum + a;
        }
        printf("%d\n", sum);
        if (T > 0) {
            printf("\n");
        }
    }
    return 0;
}

数据流中的中位数

import java.util.ArrayList;
import java.util.Collections;

public class Solution {
   	public ArrayList<Integer> list = new ArrayList<Integer>();
    
    public void Insert(Integer num) {
        list.add(num);
        Collections.sort(list);
    }
    
    public Double GetMedian() {
        int mid = list.size() / 2;
        if (list.size() % 2 == 0) {
            return (list.get(mid) + list.get(mid - 1) / 2.0);
        } else {
            return (double)list.get(mid);
        }
    }
}

c大数加法

char* solve(char* s, char* t) {
    int lens = strlen(s);
    int lent = strlen(t);
    
    int lenresult = (lens > lent : lens : lent) + 2;
    int curresult = lenresult - 1;
    
    int temp, flag = 0;
    char* result = (char*)malloc(sizeof(char)* (lenresult));
    
    result[curresult] = 0;
    
    while (lens || lent) {
        temp = flag;
        if (lent) {
            temp += t[lent--] - '0';
        }
        if (lens) {
            temp += s[lens--] - '0';
        }
        flag = temp / 10;
        temp %= 10;
        result[--curresult] = temp + '0';
    }
    result[0] = flag + '0';
    return flag ? result : result + 1;
}

这篇关于算法拾遗01 2021-10-20的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程

算法拾遗01 2021-10-20

链表反转

scanf and printf

字符数组的输入输出

getchar 和 putchar分别用来输入和输出单个字符

当题目没有说明有多少数据需要读入时，可以利用scanf的返回值是否为EOF来判断输入是否结束

题目要求输入的数据满足某个条件时停止输入(当输入的两个a b都为0是结束输入)

指针与数组

只有在获取地址的情况下对元素进行操作，才能真正地修改变量

指针的引用

结构体

全排列

皇后问题

枚举与回溯

皇后问题改进

java大数加法

1到10的阶乘之和

跳出两层或者多层循环

c++ 优化cin/cout的方法

c++模板

精度

3n+1猜想

(const String &s1, const String &s2)

数据流中的中位数

c大数加法

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯