long·pf

do your good at,challenge what do you want to do

50. Pow(x, n) 求x的n次方

Implement pow(x, n), which calculates x raised to the power n (xn). Example 1: Input: 2.00000, 10 Output: 1024.00000 Example 2: Input: 2.10000, 3 Output: 9.26100 Example 3: Input: 2.00000, -2 Output: 0.25000 Explanation: 2-2 = 1/22 = 1/4 = 0.25 Note: -100.0 < x < 100.0 n is a 32-bit signed integer, within the range [−231, 231 − 1] 求x的n次方,利用递归这班计算 double myPow3(double x,int n){ if (n==0) return 1; double half = myPow3(x, n/2); if (n%2==0) return half*half; if (n>0) return half*half*x; return half*half/x; }

49. Group Anagrams 群组错位词

Given an array of strings, group anagrams together. Example: Input: ["eat", "tea", "tan", "ate", "nat", "bat"], Output: [ ["ate","eat","tea"], ["nat","tan"], ["bat"] ] Note: All inputs will be in lowercase. The order of your output does not matter. 解法1 vector<vector<string>> groupAnagrams(vector<string>& strs) { vector<vector<string>> res; unordered_map<string, vector<string>> m; for (string str : strs) { string t = str; sort(t.begin(), t.end()); // 这里可以不用判断m[t]存不存在 m[t].push_back(str); } for (auto a : m) { res.

48. Rotate Image 旋转图像

Medium You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees (clockwise). Note: You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation. Example 1: Given input matrix = [ [1,2,3], [4,5,6], [7,8,9] ], rotate the input matrix in-place such that it becomes: [ [7,4,1], [8,5,2], [9,6,3] ] Example 2: Given input matrix = [ [ 5, 1, 9,11], i=0,j=1,n=4 [ 2, 4, 8,10], [13, 3, 6, 7], [15,14,12,16] ], rotate the input matrix in-place such that it becomes: [ [15,13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7,10,11] ] 这道题让我们将一个n*n的二维矩阵顺时针旋转90度.

47. PermutationsII 全排列2

Given a collection of numbers that might contain duplicates, return all possible unique permutations. Example: Input: [1,1,2] Output: [ [1,1,2], [1,2,1], [2,1,1] ] 跟上道题不一样的地方就是会有重复的数字 vector<vector<int>> permuteUnique(vector<int>& nums) { // 这里用set来去重,因为递归回退的时候可能会有重复的元素 set<vector<int>> res{}; if (nums.size()==0) return vector<vector<int>>(); sort(nums.begin(), nums.end()); permuteUniqueCore(res, nums, 0, nums.size()); return vector<vector<int>> (res.begin(),res.end()); } void permuteUniqueCore(set<vector<int>> &res,vector<int> &nums,int k,int n){ if (k == n) { printArr(nums); res.insert(nums); return; } for (int i = k; i<n; i++) { if (nums[k]==nums[i] && i!

46 Permutations 全排列

Given a collection of distinct(不同) integers, return all possible permutations(全排列). Example: Input: [1,2,3] Output: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 这道题跟这道题https://github.com/longpf/AtOffer#27-字符串的排列简直一模一样 vector<vector<int>> permute(vector<int>& nums) { vector<vector<int>> res{}; if (nums.size() == 0) return res; permuteCore(res, nums, 0, nums.size()); return res; } void permuteCore(vector<vector<int>> &res,vector<int> &num,int k,int n){ if (k == n) { res.push_back(num); return; } for (int i = k; i<n; i++) { swap(num[i], num[k]); permuteCore(res, num, k+1, n); swap(num[i], num[k]); } }

45. Jump Game 2 跳跃游戏2

Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Your goal is to reach the last index in the minimum number of jumps. Example: Input: [2,3,1,1,4] Output: 2 Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Ffmpeg Build 相关

ffmpeg在iOS下的编译(不包括x264,aac的库) 1. 下载gas-preprocessor.pl 下载地址https://github.com/libav/gas-preprocessor 将gas-preprocessor.pl文件拷贝到/usr/local/bin/目录下 chmod 777 /usr/local/bin/gas-preprocessor.pl开启执行权限 2. 安装yasm brew install yasm 3. 下载编译脚本 下载地址https://github.com/applexiaohao/FFmpeg-iOS-build-script,脚本中有下载ffmpeg的操作. 这步也可用x264,fdk-aac编译到ffmpeg中提到的脚本 脚本中要改下SOURCE="ffmpeg-4.0.2"为ffmpeg的版本号我当前为4.0.2. 还需要改下DEPLOYMENT_TARGET="8.0"iOS支持版本. 执行./build-ffmpeg.sh得到FFmpeg-iOS这个文件夹就是我们需要导入的 4. 导入及头文件 导入FFmpeg-iOS文件夹 Header Search Paths中添加$(PROJECT_DIR)/项目名字/FFmpeg-iOS/include 需要的依赖的库如下: VideoToolbox.framework //硬解 AudioToolbox.framework libiconv.tbd libbz2.tbd libz.tbd 编译x264 视频编码用的库 下在x264源码,下载地址http://www.videolan.org/developers/x264.html. 或直接git clone http://git.videolan.org/git/x264.git下载 下载编译脚本https://github.com/kewlbear/x264-ios. 执行脚本./build-x264.sh 如果遇到Out of tree builds are impossible with config.h/x264_config.h in source dir.,需要删除x264中的config.h和x264_config.h 如果编译后只有arm64架构的,则需./build-x264.sh armv7这样编译出其他需要的架构库,之后再./build-x264.sh lipo合成 编译x86_64架构的时候需要先brew install nasm 这样i386架构还是编译出来,因为这个架构已经用到,暂时不纠结 编译faac 音频编码用的库

44. Wildcard Matching 通配符匹配

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'. '?' Matches any single character. '*' Matches any sequence of characters (including the empty sequence). The matching should cover the entire input string (not partial). Note: s could be empty and contains only lowercase letters a-z. p could be empty and contains only lowercase letters a-z, and characters like ?

Small Algorithm

这里简单记录一些常用而又老忘记小算法 快排 红黑树 堆排 合并 打印菱形 验证ipv4,ipv6 二维数组中的查找 链表中倒数第k个结点 翻转链表 二叉树镜像 二叉树遍历 最小的k个数 快排 https://baike.baidu.com/item/快速排序算法/369842?fr=aladdin #include <iostream> using namespace std; void Qsort(int a[], int low, int high) { if(low >= high) { return; } int first = low; int last = high; int key = a[first];/*用字表的第一个记录作为枢轴*/ while(first < last) { while(first < last && a[last] >= key) { --last; } a[first] = a[last];/*将比第一个小的移到低端*/ while(first < last && a[first] <= key) { ++first; } a[last] = a[first]; /*将比第一个大的移到高端*/ } a[first] = key;/*枢轴记录到位*/ Qsort(a, low, first-1); Qsort(a, first+1, high); } 合并

146. LRU Cache 最近最少使用置换缓存器

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put. get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.