算法练习

假期闲着没事干刷刷算法题，为以后找工作面试做一下准备工作

1.数组中的重复数字

1.1题目描述

在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的，也不知道每个数字重复几次。请找出数组中任意一个重复的数字。要求时间复杂度 O(N)，空间复杂度 O(1)。

1.2思路分析

为了使时间复杂度和空间复杂度满足要求，不能使用排序或者再创建一个数组记录。对于数组元素在0到n-1范围内的数组我们可以采用将值为 i 的元素调整到第 i 个位置上进行求解。本题要求找出重复的数字，因此在调整过程中，如果第 i 位置上已经有一个值为 i 的元素，就可以知道 i 值重复。

1.3代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<stdio.h>

void swap(int *nums,int i,int j){//将nums数组中i位置和j位置交换 
	int temp;
	temp = nums[i];
	nums[i] = nums[j];
	nums[j] = temp;
}

int main(){
	int nums[]={2, 3, 2, 1, 1, 5},i,j;
	for(i=0;i<6;i++){
		if(nums[i]!=i){//保证当前位置数字没有交换过 
			if(nums[i]==nums[nums[i]])
			{
				printf("%d\n",nums[i]);
				return 0;
			}
			swap(nums,i,nums[i]);
		}
		
	}
	printf("no repeat num\n");
	return 1;
}

2.跳台阶问题

2.1 题目描述

一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

2.2 思路分析

假设到第 n 阶总共有 f(n) 种跳法，而且想跳到第 n 阶只有两种可能，要么从第 n-1 阶跳一阶到达，要么从第 n-2 阶跳两阶到达，所以递推式为f(n) = f(n-1) + f(n-2)。特殊情况为，n=0 的时候跳法为 0；n=1时，跳法为1；n=2时，跳法为2。

2.3 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<stdio.h>

int jump(int num){
	if(num < 1){
		return 0;
	}
	if(num == 1){
		return 1;
	}
	if(num == 2){
		return 2;
	}
	return jump(num-1)+jump(num-2);//使用递归算法 
}
int main(){
	int num,result;
	scanf("%d",&num);
	result = jump(num);
	printf("%d\n",result);
	return 0;
}

3.链表中倒数第k个节点

3.1题目描述

难度简单8输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。

3.2思路分析

最开始想到的思路也是最容易想到的就是先计算链表长度，然后减k，从head遍历这个长度后返回即是倒数第k个节点。

3.3代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* getKthFromEnd(struct ListNode* head, int k){
    struct ListNode* p1;
    p1 = head;
    int num = 0;
    for(;p1->next!=NULL;p1=p1->next){
        num++;
    }
    num = num - k;
    for(;num>=0;num--){
        head = head->next;
    }
    return head;

}

3.4参考最优解法

设置两个指针，快指针比慢指针深入k个节点， 当快指针为空时，慢指针也就到了size(head)-k个节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* getKthFromEnd(struct ListNode* head, int k){
    struct ListNode* p1;
    p1 = head;
    for(;k>0;k--){
        p1 = p1->next;
    }
    while(p1!=NULL){
        p1 = p1->next;
        head = head->next;
    }
    return head;
}

4.左叶子之和

4.1题目描述

计算给定二叉树的所有左叶子之和。

4.2思路分析

用递归算法比较容易，采用广度优先递归遍历算法，递归时判断该节点是不是叶节点以及是不是左叶节点。

4.3代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

int sumOfLeftLeaves(struct TreeNode* root){
    if(root == NULL){
        return 0;
    }
    int ret = 0;
    if(root->left != NULL && root->left->left == NULL && root->left->right == NULL){
        ret += root->left->val;
    }
    return sumOfLeftLeaves(root->left)+sumOfLeftLeaves(root->right)+ret;
}

5.拼写单词

5.1题目描述

给你一份『词汇表』（字符串数组） words 和一张『字母表』（字符串） chars。

假如你可以用 chars 中的『字母』（字符）拼写出 words 中的某个『单词』（字符串），那么我们就认为你掌握了这个单词。

注意：每次拼写时，chars 中的每个字母都只能用一次。

返回词汇表 words 中你掌握的所有单词的 长度之和。

示例：

输入：words = [“cat”,”bt”,”hat”,”tree”], chars = “atach”
输出：6
解释：可以形成字符串 “cat” 和 “hat”，所以答案是 3 + 3 = 6。

5.2思路分析

本题使用python解答很简单，只需要判定单词列表中的每个字母数量是否小于等于给定的字符串中的即可，使用字符串的count()方法即可

5.3代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def countCharacters(self, words: List[str], chars: str) -> int:
        result = 0
        for w in words:
            for i in w:
                if w.count(i) <= chars.count(i):
                    flag = 1
                else:
                    flag = 0
                    break
            if flag == 1:
                result += len(w)
        return result

6.优美的排列

6.1题目描述

给定两个整数 n 和 k，你需要实现一个数组，这个数组包含从 1 到 n 的 n 个不同整数，同时满足以下条件：

① 如果这个数组是 [a1, a2, a3, … , an] ，那么数组 [|a1 - a2|, |a2 - a3|, |a3 - a4|, … , |an-1 - an|] 中应该有且仅有 k 个不同整数；.

② 如果存在多种答案，你只需实现并返回其中任意一种.
题目链接：https://leetcode-cn.com/problems/beautiful-arrangement-ii

6.2思路分析

找规律即可，下标段[0, k]中，偶数下标填充[1,2,3..]，下标段[0, k]中，奇数下标填充[k + 1, k, k - 1…]，下标段[k + 1, n - 1]都是顺序填充。

6.3代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<stdio.h>
#include<stdlib.h>
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* constructArray(int n, int k, int* returnSize){
    int i = 0;
    returnSize = (int* )malloc(n*sizeof(int));
    int numK = k + 1, numTemp = 1;
	//下标段[0, k]中，偶数下标填充[1,2,3..]
    for (i = 0; i <= k; i += 2){
        returnSize[i] = numTemp++;
    }
    //下标段[0, k]中，奇数下标填充[k + 1, k, k - 1...]
    for (i = 1; i <= k; i += 2){
        returnSize[i] = numK--;
    }
    //下标段[k + 1, n - 1]都是顺序填充
	for (i = k + 1; i < n; ++i) {
		returnSize[i] = i + 1;
	}
    return returnSize;
}
int main(){
	int* returnSize;
	int n,k,i;
	scanf("%d%d",&n,&k);
	returnSize=constructArray(n,k,returnSize);
	for(i = 0;i < n;i++){
		printf("%d ",returnSize[i]);
	}
	free(returnSize);
	return 0;
}

自己运行的结果是对的，但是oj平台一直显示溢出，不知道啥原因，内存分配和访问都没问题啊，蜜汁操作。

7.旋转数字

7.1题目描述

我们称一个数 X 为好数, 如果它的每位数字逐个地被旋转 180 度后，我们仍可以得到一个有效的，且和 X 不同的数。要求每位数字都要被旋转。

如果一个数的每位数字被旋转以后仍然还是一个数字， 则这个数是有效的。0, 1, 和 8 被旋转后仍然是它们自己；2 和 5 可以互相旋转成对方；6 和 9 同理，除了这些以外其他的数字旋转以后都不再是有效的数字。

现在我们有一个正整数 N, 计算从 1 到 N 中有多少个数 X 是好数？

示例:
输入: 10
输出: 4
解释:
在[1, 10]中有四个好数： 2, 5, 6, 9。
注意 1 和 10 不是好数, 因为他们在旋转之后不变。

来源：https://leetcode-cn.com/problems/rotated-digits

7.2思路分析

保证每位都在(2, 5, 6, 9, 0, 1, 8)内，至少一位在(2, 5, 6, 9)内即可，采用暴力破解法。

7.3代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def rotatedDigits(self, N: int) -> int:
        s1 = '2569018'
        s2 = '2569'
        result = 0
        for j in range(0,N+1):
            flag1,flag = 0,0
            sN = str(j)
            for i in sN:
                if i in s1 :
                    flag1 = 1
                    if i in s2:
                        flag = 1
                else:
                    flag = 0
                    break
            if flag == 1 and flag1 == 1:
                result+=1
        return result

7.4最优解

思路
根据好数定义，每个好数只能包含数字 0125689，并且至少包含 2569 中的一个。因此可以逐个写出小于等于 N 的所有好数。
这道题目可以使用动态规划解答。状态可以表示为三个变量 i, equality_flag, involution_flag。其中 i 表示当前正在写第 i 位数字；equality_flag 表示已经写出的 j 位数字是否等于 N 的 j 位前缀；involution_flag 表示从最高位到比当前位高一位的这段前缀中是否含有 2569 中的任意一个数字。
dp(i, equality_flag, involution_flag) 表示在特定 equality_flag，involution_flag 的状态下，有多少种从 i 到末尾的后缀能组成一个好数。最终的结果为 dp(0, True, False)。
注：数字 N 从最高位到最低位的索引，从 0 开始，并依次增大。第 i 位表示索引为 i 的位置。
算法
如果 equality_flag 为 true，表示第 i 位能取到的最大数字为 N 的第 i 位对应的数字。并且还需要根据当前状态决定可以写哪些数字。
在代码实现中，我们分别使用了自顶向下的方法和自底向上的方式。Python 代码实现的是自顶向下的方法，从 for d in xrange(…) 到 memo[…] = ans 这四行代码清晰的说明了状态之间的递归关系。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def rotatedDigits(self, N):
        A = map(int, str(N))

        memo = {}
        def dp(i, equality_flag, involution_flag):
            if i == len(A): return +(involution_flag)
            if (i, equality_flag, involution_flag) not in memo:
                ans = 0
                for d in xrange(A[i] + 1 if equality_flag else 10):
                    if d in {3, 4, 7}: continue
                    ans += dp(i+1, equality_flag and d == A[i],
                              involution_flag or d in {2, 5, 6, 9})
                memo[i, equality_flag, involution_flag] = ans
            return memo[i, equality_flag, involution_flag]

        return dp(0, True, False)
#算法
算法练习
https://chujian521.github.io/blog/2020/02/22/算法练习/
作者
Encounter
发布于
2020年2月22日
许可协议