Home Authors Posts by 可乐

可乐

419 POSTS 5 COMMENTS

0 127
面试题 16.11. 跳水板难度简单33收藏分享切换为英文关注反馈你正在使用一堆木板建造跳水板。有两种类型的木板，其中长度较短的木板长度为shorter，长度较长的木板长度为longer。你必须正好使用k块木板。编写一个方法，生成跳水板所有可能的长度。
返回的长度需要从小到大排列。
示例：
输入：
shorter = 1
longer = 2
k = 3
输出： {3,4,5,6}
注意：一般来说函数头为：int *，则要求返回指针,这种情况下定义数组最好用malloc()，即指针,方便返回;
int* divingBoard(int shorter, int longer, int k, int* returnSize){
    if(k == 0){                                 //k=0时
        * returnSize = 0;
        return NULL;
    }
    if(shorter == longer){                     //shorter = longter
        *returnSize = 1;                     
        int *p = (int *)malloc(sizeof(int));     //注意:两种特殊情况不可交换
        *p = shorter * k;
        return p;
    }
    *returnSize = k+1;
    int *length = (int *)malloc(sizeof(int)*(k+1));
    for(int i = 0;i<=k;i++){
        length[i] = shorter * (k-i) + longer *i;  //借用数组存储
    }
    return length;
}

0 235

注意二叉树可以为空！

结点数目>=0!!!

根结点为空也可以！

概念

编辑

二叉树是n（n≥0）个结点的有限集合。n=0的树称为空二叉树。n>0的二叉树由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成 [2]  。
显然，二叉树是一种有序树。二叉树中某个结点即使只有一个子树也要区分是左子树还是右子树 [2]  。
二叉树中所有结点的形态共有5种：空结点、无左右子树结点、只有左子树结点、只有右子树结点和左右子树均存在的结点 [2]  。

性质

编辑

性质1：具有n个结点的非空二叉树有且仅有n-1个分支 [3]  。
性质2：非空二叉树的第i层最多有2i-1个结点 [3]  。
性质3：深度为h的非空二叉树最多有2h-1个结点 [3]  。
性质4：在任意非空二叉树中，若叶结点的数目为n0，度为2的结点数目为n2，则有关系n0=n2+1成立 [3]  。
性质5：具有n（n>0）个结点的完全二又树的深度h= log2n+1 [3]  。

二叉树的基本运算

编辑

1、CreateBTree（bt，str）：已知二叉树的括号表示法表达字符串str，建二叉树bt [4]  。
2、BTHeight（bt）：求二叉树bt的高度 [4]  。
3、NodeCount（bt）：求二叉树bt的结点个数 [4]  。
4、LeafCount（bt）：求二叉树bt的叶子结点个数 [4]  。

二叉树拓展

编辑

1、线索二叉树
按照某种遍历方式对二叉树进行遍历，可以把二叉树中所有节点排列为一个线性序列。但是，二叉树中每个节点在这个序列中的直接前驱节点和直接后继节点在二叉树的存储结构中并没有反映出来，只有在对二叉树遍历的动态过程中才能够得到这些信息。线索二叉树就是研究在静态下，如何得到这样的信息 [5]  。
2、二叉排序树
3、最优二叉树（哈夫曼树）
在权为w1，w2，…，wn的n个叶子所构成的所有二叉树中，带权路径长度最小（即代价最小）的二叉树称为最优二叉树或Huffman（赫夫曼）树 [6]  。
4、平衡树
二叉平衡树（balanced binary tree）又称AVL树。它或者是一棵空二叉树，或者是具有下列性质的二叉树： [7] 
（1）它的左、右子树高度之差的绝对值不超过1 [7]  ；
（2）它的左、右子树都是二叉平衡树 [7]  。

0 124
给你一份旅游线路图，该线路图中的旅行线路用数组 paths 表示，其中 paths[i] = [cityAi, cityBi] 表示该线路将会从 cityAi 直接前往 cityBi 。请你找出这次旅行的终点站，即没有任何可以通往其他城市的线路的城市。
题目数据保证线路图会形成一条不存在循环的线路，因此只会有一个旅行终点站。
示例 1：
输入：paths = [[“London”,”New York”],[“New York”,”Lima”],[“Lima”,”Sao Paulo”]]
输出：”Sao Paulo”
解释：从 “London” 出发，最后抵达终点站 “Sao Paulo” 。本次旅行的路线是 “London” -> “New York” -> “Lima” -> “Sao Paulo” 。
解题思路：比较两个字符串使用strcmp函数
char *destCity(char ***paths, int pathsSize, int *pathsColSize)
{
    int i, j;
    int flag;            // 是否终点城市标记
    for (i = 0; i < pathsSize; i++) {
        flag = 0;
        for (j = 0; j < pathsSize; j++) {
            if (strcmp(paths[i][1],paths[j][0])==0) {/*字符串比较要用strcmp函数，而不能使用path[i][1]==paths[j][0];
            因为字符串二维数组是如下定义:
            char c[3][8]={“apple”,”orange”,”banana”}
            等价于char c[3][8]={{“apple”},{“orange”},{“banana”}};
            3表示行，每一行只有一个字符串;
            8表示列，也就是每个字符串的最大长度;
            详情见:  http://c.biancheng.net/view/273.html
            */
                flag = 1; // 标记为1，表示在起点城市中可以找到
            }
        }
        if (flag == 0) {
            return paths[i][1];
        }
    }
    
    // 返回NULL，该句很重要，不然编译有误:control reaches end of non-void function
    return NULL;
}

2 271
给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。
请你返回该链表所表示数字的 十进制值 。
示例 1：
输入：head = [1,0,1]
输出：5
解释：二进制数 (101) 转化为十进制数 (5)
解题思路：把head链表的数挨个取出，再使用二进制转换
方法一：
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
int getDecimalValue(struct ListNode* head){
    struct ListNode* a=head;
    int i=0,arr[50]={0},sum=0,j=0;
    while(a!=NULL){
        arr[i]=a->val;
        a=a->next;
        i++;
    }
    i=i-1;
    //转换成二进制;
    for(;i>=0;i–){
        sum=sum+(arr[i]*pow(2,j));
        j++;
    }//已完成;
    return sum;
}
优化版：
#define null 0
int getDecimalValue(struct ListNode* head){
struct ListNode *a=head;
int num=0;
while(a!=null){
num=num*2+a->val;
a=a->next;
}
return num;
}
最优解：位运算（移位，或）
思路：位运算
每取 1 位数字，将当前所有数位 左移 1 位
通过位运算 或 将取出数字存入最低位
int getDecimalValue(struct ListNode* head){
int res = 0;
for ( ; head; head = head->next)
res = (res << 1) | head->val;
return res;
}

0 54
/输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
示例1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
提示：
1 <= arr.length <= 10^5
-100 <= arr[i] <= 100

解题思路：https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/solution/mian-shi-ti-42-lian-xu-zi-shu-zu-de-zui-da-he-do-2/

动态规划是本题的最优解法，以下按照标准流程解题。
动态规划解析：
状态定义： 设动态规划列表 dpdpdp ，dp[i]dp[i]dp[i] 代表以元素 nums[i]nums[i]nums[i] 为结尾的连续子数组最大和。
为何定义最大和 dp[i]dp[i]dp[i] 中必须包含元素 nums[i]nums[i]nums[i] ：保证 dp[i]dp[i]dp[i] 递推到 dp[i+1]dp[i+1]dp[i+1] 的正确性；如果不包含 nums[i]nums[i]nums[i] ，递推时则不满足题目的 连续子数组 要求。
转移方程： 若 dp[i−1]≤0dp[i-1] \leq 0dp[i−1]≤0 ，说明 dp[i−1]dp[i – 1]dp[i−1] 对 dp[i]dp[i]dp[i] 产生负贡献，即 dp[i−1]+nums[i]dp[i-1] + nums[i]dp[i−1]+nums[i] 还不如 nums[i]nums[i]nums[i] 本身大。
当 dp[i−1]>0dp[i – 1] > 0dp[i−1]>0 时：执行 dp[i]=dp[i−1]+nums[i]dp[i] = dp[i-1] + nums[i]dp[i]=dp[i−1]+nums[i] ；
当 dp[i−1]≤0dp[i – 1] \leq 0dp[i−1]≤0 时：执行 dp[i]=nums[i]dp[i] = nums[i]dp[i]=nums[i] ；
初始状态： dp[0]=nums[0]dp[0] = nums[0]dp[0]=nums[0]，即以 nums[0]nums[0]nums[0] 结尾的连续子数组最大和为 nums[0]nums[0]nums[0] 。
返回值： 返回 dpdpdp 列表中的最大值，代表全局最大值。
 空间复杂度降低：
由于 dp[i]dp[i]dp[i] 只与 dp[i−1]dp[i-1]dp[i−1] 和 nums[i]nums[i]nums[i] 有关系，因此可以将原数组 numsnumsnums 用作 dpdpdp 列表，即直接在 numsnumsnums 上修改即可。
由于省去 dpdpdp 列表使用的额外空间，因此空间复杂度从 O(N)O(N)O(N) 降至 O(1)O(1)O(1) 。
复杂度分析：
时间复杂度 O(N)O(N)O(N) ： 线性遍历数组 numsnumsnums 即可获得结果，使用 O(N)O(N)O(N) 时间。
空间复杂度 O(1)O(1)O(1) ： 使用常数大小的额外空间。

动态规划，小试牛刀，感谢楼主。
1.状态，即子问题。
dp[i] 代表以元素 nums[i] 为结尾的连续子数组最大和。

2.转移策略，自带剪枝。
若 dp[i−1]≤0 ，说明 dp[i−1] 对 dp[i] 产生负贡献，即 dp[i−1]+nums[i] 还不如 nums[i] 本身大。

3.状态转移方程，根据前两步抽象而来。

  • 当 dp[i−1]>0 时：执行 dp[i] = dp[i-1] + nums[i]；
  • 当 dp[i−1]≤0 时：执行 dp[i] = nums[i] ；

4.设计dp数组，保存子问题的解，避免重复计算

5.实现代码

整个动态规划，最难的就是定义状态。一旦状态定义出来，表明你已经抽象出了子问题，可以肢解原来的大问题了。

贪心算法+分治算法https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/solution/tan-xin-fen-zhi-dong-tai-gui-hua-fa-by-luo-jing-yu/

0 82
给你一个非递减的 有序 整数数组，已知这个数组中恰好有一个整数，它的出现次数超过数组元素总数的 25%。
请你找到并返回这个整数
示例：
输入：arr = [1,2,2,6,6,6,6,7,10]
输出：6
解题思路：注意该数组为有序数组，且只有一个符合要求的整数;
方法一:双指针法
  1. 数组有序，且某元素出现次数超过25%
  2. 那么对于此元素第1次出现位置，加25%数组长度，必定仍为它自身

int findSpecialInteger(int* arr, int arrSize) {

    for (int *p = arr, *q = arr + arrSize / 4; ; p++, q++)//有序，若出现次数超过25%，则arr[i]=arr[i+arrSize/4];
        if (*p == *q) return *p;
    return 0;  
}
方法二:遍历
int findSpecialInteger(int* arr, int arrSize){
//int len = arrSize/4;
int i = 1,cou = 0;
int temp = arr[0];
    while(i < arrSize){
if(temp == arr[i]){
cou++;
            if(cou*4 >= arrSize){
                break;
            }
        }
        else{
            cou = 0;
        }
        temp = arr[i];
        i++;//在一次循环中进行移动;
    }
    return temp;
}
方法三:二分查找
对于此题来说二分查找无意义，故不讨论;

0 96

[et_pb_section admin_label=”section”]
[et_pb_row admin_label=”row”]
[et_pb_column type=”4_4″]
[et_pb_text admin_label=”Text”]

A 和 B 在一个 3 x 3 的网格上玩井字棋。
井字棋游戏的规则如下：
玩家轮流将棋子放在空方格 (” “) 上。
第一个玩家 A 总是用 “X” 作为棋子，而第二个玩家 B 总是用 “O” 作为棋子。
“X” 和 “O” 只能放在空方格中，而不能放在已经被占用的方格上。
只要有 3 个相同的（非空）棋子排成一条直线（行、列、对角线）时，游戏结束。
如果所有方块都放满棋子（不为空），游戏也会结束。
游戏结束后，棋子无法再进行任何移动。
给你一个数组 moves，其中每个元素是大小为 2 的另一个数组（元素分别对应网格的行和列），它按照 A 和 B 的行动顺序（先 A 后 B）记录了两人各自的棋子位置。
如果游戏存在获胜者（A 或 B），就返回该游戏的获胜者；如果游戏以平局结束，则返回 “Draw”；如果仍会有行动（游戏未结束），则返回 “Pending”。
你可以假设 moves 都 有效（遵循井字棋规则），网格最初是空的，A 将先行动。
方法一：模拟
我们可以模拟数组 move 中的每一步落子。我们使用两个集合 A 和 B 存放每位玩家当前已经落子的位置，并用集合 wins 存放棋子排成一条直线的所有情况（排成一行或一列各有 3 种，排成对角线有 2 种，总计 8 种）。当某位玩家落子时，我们枚举 wins 中的每一种情况，并判断该玩家是否将棋子落在了这些位置。如果满足了其中一种情况，则该玩家获胜。
如果直到落子完毕仍然没有玩家获胜，那么根据数组 move 的长度返回平局 Draw 或游戏未结束 Pending。
示例 1：
输入：moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
输出：”A”
解释：”A” 获胜，他总是先走。
“X  ”    “X  ”    “X  ”    “X  ”    “X  ”
”   ” -> ”   ” -> ” X ” -> ” X ” -> ” X ”
”   ”    “O  ”    “O  ”    “OO ”    “OOX”
char * tictactoe(int** moves, int movesSize, int* movesColSize){
    // 将 moves 填入虚拟棋盘， a 为 -1 ， b 为 1
    int s[3][3] = {0};
    for (int i = 0; i < movesSize; i++) {
        int x = moves[i][0], y = moves[i][1];
        if (i & 1) s[x][y]++;//按位与判断奇，偶数;第一个i为0,则第一步必将是0，e也就是执行s[x][y]–,即实现了b先走;
        else s[x][y]–;
    }
    // 对角线判断
    int sumD1 = s[0][0] + s[1][1] + s[2][2];
    int sumD2 = s[0][2] + s[1][1] + s[2][0];
    if (sumD1 ==  3 || sumD2 ==  3) return “B”;
    if (sumD1 == -3 || sumD2 == -3) return “A”;
    // 横向、纵向判断
    for (int i = 0; i < 3; i++) {
        int sumR = s[i][0] + s[i][1] + s[i][2];
        int sumC = s[0][i] + s[1][i] + s[2][i];
        if (sumR ==  3 || sumC ==  3) return “B”;
        if (sumR == -3 || sumC == -3) return “A”;
    }
    // 无胜者情况
    return movesSize < 9 ? “Pending” : “Draw”;
}

[/et_pb_text]
[/et_pb_column]
[/et_pb_row]
[/et_pb_section]

0 93
平面上有 n 个点，点的位置用整数坐标表示 points[i] = [xi, yi]。请你计算访问所有这些点需要的最小时间（以秒为单位）。
你可以按照下面的规则在平面上移动：
每一秒沿水平或者竖直方向移动一个单位长度，或者跨过对角线（可以看作在一秒内向水平和竖直方向各移动一个单位长度）。
必须按照数组中出现的顺序来访问这些点。
示例 1：
输入：points = [[1,1],[3,4],[-1,0]]
输出：7
解释：一条最佳的访问路径是： [1,1] -> [2,2] -> [3,3] -> [3,4] -> [2,3] -> [1,2] -> [0,1] -> [-1,0]
从 [1,1] 到 [3,4] 需要 3 秒
从 [3,4] 到 [-1,0] 需要 4 秒
一共需要 7 秒
解题思路：坐标轴上两点的最短距离为切比雪夫距离
方法一：切比雪夫距离
对于平面上的两个点 x = (x0, x1) 和 y = (y0, y1)，设它们横坐标距离之差为 dx = |x0 – y0|，纵坐标距离之差为 dy = |x1 – y1|，对于以下三种情况，我们可以分别计算出从 x 移动到 y 的最少次数：
dx < dy：沿对角线移动 dx 次，再竖直移动 dy – dx 次，总计 dx + (dy – dx) = dy 次；
dx == dy：沿对角线移动 dx 次；
dx > dy：沿对角线移动 dy 次，再水平移动 dx – dy 次，总计 dy + (dx – dy) = dx 次。
可以发现，对于任意一种情况，从 x 移动到 y 的最少次数为 dx 和 dy 中的较大值 max(dx, dy)，这也被称作 x 和 y 之间的 切比雪夫距离。
由于题目要求，需要按照数组中出现的顺序来访问这些点。因此我们遍历整个数组，对于数组中的相邻两个点，计算出它们的切比雪夫距离，所有的距离之和即为答案。
int minTimeToVisitAllPoints(int** points, int pointsSize, int* pointsColSize){
   int sum=0;//总和
   int a,b;//两点x、y距离
   for(int i=0;i<pointsSize-1;i++){
       a=abs(points[i][0]-points[i+1][0]);
       b=abs(points[i][1]-points[i+1][1]);
       sum+=abs(a-b);
       if(a>b) sum+=b;
       else sum+=a;
   }
   *pointsColSize=sum;
   return sum;
}

0 299

给定两个（单向）链表，判定它们是否相交并返回交点。请注意相交的定义基于节点的引用，而不是基于节点的值。换句话说，如果一个链表的第k个节点与另一个链表的第j个节点是同一节点（引用完全相同），则这两个链表相交。

示例 1：输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3输出：Reference of the node with value = 8输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

解题思路：关键在于链表相交那么后期的指向也一定相同（长度和赋值都相同），也就是说相交前可以长短不一内容不一，但相交后全部一致;就算不相交，走完两链表a,b指针所走的长度也是一样，又因为指针的速度一样，所以最后当a->NULL时一定有b->NULL,此时可以跳出循环while(a!=b);

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
                                    struct ListNode *a=headA;
                                    struct ListNode *b=headB;
                                    while(a!=b)
                                   {
                                        if(a==NULL)
                                           {
                                                   a=headB;
                                            }
                                     else
                                            {
                                                   a=a->next;
                                             }
                                      if(b=NULL)  

                                     {
                                                   b=headA;
                                            }
                                     else
                                            {
                                                   b=b->next;
                                             }
                                   }
return  a;
}

0 83
实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。
注意：本题相对原题稍作改动
示例：
输入： 1->2->3->4->5 和 k = 2
输出： 4
解题思路：双指针，同起点出发，A先走K步，之后B再跟A一起出发，当A指向空时，B指向目标值，循环结束;
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
int kthToLast(struct ListNode* head, int k){
                struct ListNode*a=head;
                while(k–)
                {
                       a=a->next;
                }//结束后a指向3;
                while(a)
               { 
                     a=a->next;
                     head=head->next;
                }
return head->val;
}
Prev1...404142Next Page 41 of 42
©