11

《一、链表》

1. 两数之和

/**

* Note: The returned array must be malloced, assume caller calls free().

*/

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {

int a=0, b=0, i, j;

int *arr = malloc(sizeof(int) * 2);

for(i=0; i<numsSize-1; i++){

for(j=i+1; j<numsSize; j++){

if(nums[i] + nums[j] == target){

arr[0] = i;

arr[1] = j;

break;

}

}

}

*returnSize = 2;

return arr;

}

160. 相交链表

//————灵神！！！只是说相交，又没有说后面完全重合。

/**

* //系统已经定义好的结构体

* Definition for singly-linked list.

* struct ListNode {

* int val;

* struct ListNode *next;

* };

*/

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {

struct ListNode* p = headA;

struct ListNode* q = headB;

//如果相交前的距离不同，两人走完自己的路还会走对方的前一段路

while(p != q){

p = p!=NULL ? p->next:headB;

q = q!=NULL ? q->next:headA;

}

return p;

}

206. 反转链表

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* struct ListNode *next;

* };

*/

struct ListNode* reverseList(struct ListNode* head) {

struct ListNode *nxt;

struct ListNode *pre = NULL;

struct ListNode *cur = head;

while(cur){

nxt = cur->next;

cur->next = pre;

pre = cur;

cur = nxt;

}

return pre;

}

234. 回文链表

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* struct ListNode *next;

* };

*/

bool isPalindrome(struct ListNode* head) {

/*第一步————新建一个链表存放反转链表*/

//将反转链表存储在一个新的链表中

struct ListNode* l;

//初始化新的链表

l = (struct ListNode*)malloc(sizeof(struct ListNode));

l->next = NULL;

//进行反转操作，p是用于构造新链表的，q是用于从旧链表取值和遍历的

struct ListNode *q = head, *p; // 这里要对每个变量前面都写*！！！

while(q!=NULL){

//初始化构造结点

p = (struct ListNode*)malloc(sizeof(struct ListNode));

p->val = q->val;

//头插法

p->next = l->next;

l->next = p;

//旧数组再后移

q = q->next;

}

/*第二步————开始逐一对比*/

struct ListNode* i = head;

struct ListNode* j = l->next;

while(i != NULL){

if(i->val != j->val){

return false;

}

i = i->next;

j = j->next;

}

return true;

}

141. 环形链表

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* struct ListNode *next;

* };

*/

/*使用快慢指针，慢指针每次走一步，如果有环，一定会走到环里。

再看相对速度，每次快指针比慢指针多走一步，肯定会追上慢指针。*/

bool hasCycle(struct ListNode *head) {

struct ListNode* slow = head;

struct ListNode* fast = head;

//fast!=NULL保证了快指针没到表尾，fast->next!=NULL保证fast->next->next无空指针

while(fast!=NULL && fast->next!=NULL){

slow = slow->next;

fast = fast->next->next;

if(slow == fast){

return true;

}

}

return false;

}

21. 合并两个有序链表

/*————danny的常规方法，注意和回文链表进行区别，这个可以直接用两个现有的链表进行构造，因为原有链表不需要保留；

而前面的回文链表需要保留原来链表进行对比，所以不能像这题这样操作。*/

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* struct ListNode *next;

* };

*/

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {

//(1)如果l1/l2有空的，则直接将另一个链表给返回

if(!l1){

return l2;

}

if(!l2){

return l1;

}

//(2)创建一个头结点并初始化

struct ListNode *head = (struct ListNode*)malloc(sizeof(struct ListNode));

head->next = NULL; // 防止脏数据

struct ListNode* s = head; // 使用s进行操作，而不是头结点head

//(3)对以head为头结点的链表进行构造（只是对地址操作，并不是创建大量结点）

while(l1 && l2){

if(l1->val < l2->val){

s->next = l1;

l1 = l1->next;

}

else{

s->next = l2;

l2 = l2->next;

}

s = s->next; // 因为x最开始指向的是头结点，每次将下一个位置安排好后，将t移到新链表的最后一个位置

}

//(4)如果都有数据的区间结束，l1还有元素，则t后面直接接剩余的值

if(l1){

s->next = l1;

}

else if(l2){

s->next = l2;

}

//(5)将构造好的链表的第一个具体结点返回

return head->next;

}

《二、树》

94. 二叉树的中序遍历

/** 将遍历的结果保存在数组中

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* struct TreeNode *left;

* struct TreeNode *right;

* };

*/

/**

* Note: The returned array must be malloced, assume caller calls free().

*/

void inOrder(struct TreeNode* root, int *arr, int *arrSize){ // 都传入指针是因为都需要修改

if(!root){

return ;

}

else{

inOrder(root->left, arr, arrSize);

arr[(*arrSize)++] = root->val; // 初始化arrSize为0，所以对应为下标，先赋值再进行++

inOrder(root->right, arr, arrSize);

}

}

int* inorderTraversal(struct TreeNode* root, int* returnSize) {

int *arr = (int*)malloc(sizeof(int)*101); // 如果直接写int arr[101]，就是局部变量定义在栈上；malloc是在堆上

*returnSize = 0; // 要初始化！！！

inOrder(root, arr, returnSize);

return arr;

}

104. 二叉树的最大深度

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* struct TreeNode *left;

* struct TreeNode *right;

* };

*/

int maxDepth(struct TreeNode* root) {

if(!root){

return 0;

}

else{

int lefthigh = maxDepth(root->left);

int righthigh = maxDepth(root->right);

return lefthigh > righthigh ? (lefthigh+1) : (righthigh+1);

}

}

226. 翻转二叉树

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* struct TreeNode *left;

* struct TreeNode *right;

* };

*/

struct TreeNode* invertTree(struct TreeNode* root) {

if(! root){

return NULL;

}

struct TreeNode* p = invertTree(root->left); // 得到翻转过的左子树

struct TreeNode* q = invertTree(root->right); // 得到翻转过的右子树

root->left = q; // 令当前根结点的左子树等于翻转过的右子树

root->right = p;

return root;

}

101. 对称二叉树

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* struct TreeNode *left;

* struct TreeNode *right;

* };

*/

bool isSame(struct TreeNode *p, struct TreeNode *q){

if(p==NULL || q==NULL){

return p==q;

}

return (p->val==q->val && isSame(p->left, q->right) && isSame(p->right, q->left)); // 只是修改100题的返回值

}

bool isSymmetric(struct TreeNode* root) {

return isSame(root->left, root->right);

}

543. 二叉树的直径

/** 深度优先搜索

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* struct TreeNode *left;

* struct TreeNode *right;

* };

*/

// 计算当前结点下面树的高度，并在计算过程中不断更新直径max

int maxNum(struct TreeNode* r, int *max){

if(r == NULL){

return 0;

}

int left = maxNum(r->left, max); // 通过left接收该节点左子树的高度

int right = maxNum(r->right, max); // 通过right接收该节点右子树的高度

*max = *max > (left+right) ? *max : (left+right); // max与当前结点左右子树深度之和进行比较，更新

return (left > right ? left+1 : right+1); // 本质上，这个函数就是为了计算树的深度

}

int diameterOfBinaryTree(struct TreeNode* root) {

int max = 0;

maxNum(root, &max);

return max;

}

108. 将有序数组转换为二叉搜索树

/**

发现子问题和原问题相似，就是递归：

1.先找到数组中间位置i，根为arr[i]，然后左右继续这样操作；

2.递归边界：如果数组长度等于0，返回空节点。

3.注意如果数组长度为偶数，答案就不是唯一的，这里我们约定偶数长度数组根节点为靠右侧的那个结点，下标就是n/2。

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* struct TreeNode *left;

* struct TreeNode *right;

* };

*/

struct TreeNode* bulid(int *nums, int left, int right){ // left是起始下标（包含）；right是结束下标的下一个位置（不包含）

if(left == right){ // 数组起始位置等于数组长度了0==0

return NULL;

}

else{

int m = left+(right-left)/2; // 如果直接“(left+right)/2”可能导致内存溢出

struct TreeNode* n = (struct TreeNode*)malloc(sizeof(struct TreeNode));

n->val = nums[m];

n->left = bulid(nums, left, m);

n->right = bulid(nums, m+1, right);

return n;

}

}

struct TreeNode* sortedArrayToBST(int* nums, int numsSize) {

return bulid(nums, 0, numsSize);

}

20. 有效的括号

// 本题将s看做栈使用，自定义int top，通过top指针模拟栈的操作

bool isValid(char* s) {

// 这样定义后，mp中所有元素初始化为0 ：

char mp[128] = {};

// 这样赋值后，mp中只有右括号的ASCII码值作为下标对应的数组值，其他所有(包括左括号)的ASCII对应的数组值皆为0：

mp[')'] = '(';

mp[']'] = '[';

mp['}'] = '{';

int top = 0; // 定义栈顶指针，但初始化为0，这里不是-1

for(int i=0; s[i]; i++){ // 遍历字符数组s

char c = s[i];

if(mp[c] == 0){ // 左括号

s[top++] = c; // 入栈

}

/*说明：只要不满足if就会进入else if，先判空，如果不空再取栈顶元素(左括号)与右括号进行匹配*/

//这里面--top操作已经完成元素出栈了，如果匹配就出栈后再循环，如果不匹配，直接返回false

else if(top==0 || s[--top] != mp[c]){ // 右括号与上一个入栈的左括号进行匹配

return false;

}

}

return (top == 0); // 全部匹配结束

}

121. 买卖股票的最佳时机

#define MAX(a, b) a>b?a:b // 定义宏，返回两个数中的最大值

#define MIN(a, b) a<b?a:b // 定义宏，返回两个数中的最小值

int maxProfit(int* prices, int pricesSize) {

int ans = 0; // 初始化最大利润为 0

int min_price = prices[0]; // 初始化最低价格为数组的第一个元素

// 同时更新当前最大利润和当前最小买入价格

for (int i = 1; i < pricesSize; i++) {

int p = prices[i]; // 当前价格

ans = MAX(ans, p - min_price); // 更新最大利润为MAX(当前最大利润, 当前价格-当前最低价格)

min_price = MIN(min_price, p); // 更新最低价格为MIN(当前最小价格, 当前价格)

}

return ans; // 返回最大利润

}

70. 爬楼梯

/*递归方程：f[n] = f[n-1] + f[n-2]

因为每次只能走1/2个台阶。 */

int climbStairs(int n) {

// 这块的作用看line10注释

if(n==1){

return 1;

}

int dp[n+1]; // 其中dp[0]的位置是空着的，dp[i]直接表示上i级台阶有多少种方法

dp[1] = 1;

dp[2] = 2; // 这个2是下标2，如果前面没有n=1的判断，n=1时，创造dp[2]，只能访问到dp[1]，这里将会越界

for(int i=3; i<=n; i++){ // 最大的下标为n

dp[i] = dp[i-1] + dp[i-2]; // 从开始条件一步步算到目的情况

}

return dp[n];

}

136. 只出现一次的数字

// 线性时间复杂度————O(n)，不能使用双重循环O(n²)

/*使用位运算“异或”解题：对“ ^ ”，有3^3=0、3^0=3。所以只需定义一个变量，在循环中与数组所有值异或即可，相同的会自动变为0*/

int singleNumber(int* nums, int numsSize) {

int num = 0;

for(int i=0; i<numsSize; i++){

num ^= nums[i]; // num = num^nums[i]

}

return num;

}

169. 多数元素

/*将数组 nums 中的所有元素按照单调递增或单调递减的顺序排序，那么下标为 ⌊2/n​⌋ 的元素（下标从 0 开始）一定是众数。*/

// 说明：因为出现次数大于一半了，就算从头排，中间位置也是他

int majorityElement(int* nums, int numsSize) {

int temp;

//冒泡排序

for(int i=0; i<numsSize; i++){

int change = 0;

for(int j=0; j<numsSize-i-1; j++){

if(nums[j]>nums[j+1]){

temp = nums[j];

nums[j] = nums[j+1];

nums[j+1] = temp;

change = 1;

}

}

if(!change){

break;

}

}

return nums[numsSize/2];

}