voidquickSort(int a[], int left, int right){ if(left < right) { // exit. good idea! int l = left, r = right, x = a[l]; while(1) { while(l < r && a[r] >= x) r--; while(l < r && a[l] <= x) l++; if(l >= r) break; swap(a[r], a[l]); } swap(a[left], a[l]); quickSort(a, left, l-1); quickSort(a, l+1, right); } }
1.5 调整数组位数使奇数位于前面
voidreorderOddEven(int[] arr, len){ if (arr == NULL || len <= 1 ) { return; } int l = 0, r = len - 1; while (l < r) { while (l < r && arr[r] % 2 == 0) { r--; } while (l < r && arr[l] % 2 == 1) { l++; } if (l < r) { swap(arr[l], arr[r]); l++, r--; } } }
1.6 出现次数超过一半的次数
intcore(int *a, int len){ if (arr == NULL || len <= 0 ) { return; } int target = a[0], cnt = 1; for (int i = 1; i < len; i++) { if (a[i] == target) { cnt++; } else { cnt--; if (cnt == 0) { target = a[i]; cnt = 1; } } } return target; }
1.7 最小的K个数 part 快排思想
constint N = 105; int a[N] = {4, 5, 1, 6, 2, 7, 3, 8}; intpart(int *a, int left, int right){ if(left < right) { int x = a[0], l = left, r = right; while(l < r) { while(l < r && a[r] >= x) r--; while(l < r && a[l] <= x) l++; if(l >= r) break; swap(a[l], a[r]); } swap(x, a[l]); return l; } elsereturn left; }
voidset_k(int *input, int n, int k){ if(input == NULL || k > n || k <= 0 || n <= 0) { return; } int start = 0, end = n - 1; int index = part(input, start, end); while(index != k-1) { if(index > k-1) { end = index - 1; } elseif(index < k - 1) { start = index + 1; } else { break; } index = part(input, start, end); } }
1.8 数组中的逆序对 & 归并排序
voidmergeSort(int a[], int l, int r){ // 8, 5, 4, 9, 2, 3, 6 if(l >= r) return; // exit. int mid = (l+r) / 2; // overflow <-> l + (r-l)/2 mergeSort(a, l, mid); mergeSort(a, mid+1, r); int *arr = newint[r-l+1]; int k = 0; int i = l, j = mid + 1; while(i <= mid && j <= r) { if(a[i] <= a[j]) { arr[k++] = a[i++]; } else { arr[k++] = a[j++]; // ans += (mid-i+1); } } while(i <= mid) arr[k++] = a[i++]; while(j <= r) arr[k++] = a[j++]; for(int i = l; i <= r; i++) { a[i] = arr[i-l]; } delete []arr; }
1.15 约瑟夫环
import java.util.LinkedList; publicclassSolution{ publicintLastRemaining_Solution(int n, int m){ if(n < 1 || m < 1) return -1; LinkedList<Integer> link = new LinkedList<Integer>(); for(int i = 0; i < n; i++) link.add(i); int index = -1; //起步是 -1 不是 0 while(link.size() > 1){ index = (index + m) % link.size(); //对 link的长度求余不是对 n link.remove(index); index --; } return link.get(0); } }
1.17 排序数组中某数字出现的次数
intbina(int *a, int len, int data){ if(a == NULL || len <= 0) return-1; int l = 0, r = len - 1; while(l <= r) { int mid = (l + r) / 2; if(a[mid] == data) return mid; elseif(data < a[mid]) { r = mid - 1; } else l = mid+1; } return-1; }
public ListNode reverseList(ListNode head){ ListNode next = null; ListNode pre = null
while (head != null) { next = head.next; (保存当前头结点的下个节点) head.next = pre; (将当前头结点的下一个节点指向“上一个节点”,这一步是实现了反转) pre = head; (将当前头结点设置为“上一个节点”) head = next; (将保存的下一个节点设置为头结点) } return pre; }
复杂链表的复制:
/* public class RandomListNode { int label; RandomListNode next = null; RandomListNode random = null; RandomListNode(int label) { this.label = label; } } */
import java.util.HashMap; publicclassSolution{ HashMap<Character, Integer> map = new HashMap<Character, Integer>(); StringBuffer s = new StringBuffer(); //Insert one char from stringstream publicvoidInsert(char ch) { s.append(ch); if(map.containsKey(ch)){ map.put(ch, map.get(ch)+1); }else{ map.put(ch, 1); } } //return the first appearence once char in current stringstream publiccharFirstAppearingOnce() { for(int i = 0; i < s.length(); i++){ if(map.get(s.charAt(i)) == 1) return s.charAt(i); } return'#'; } }
/classSolution { public: //Insert one char from stringstream // vector用来记录字符流 vector<char> vec; // map用来统计字符的个数 map<char, int> table; voidInsert(char ch) { table[ch]++; vec.push_back(ch); } //return the first appearence once char in current stringstream charFirstAppearingOnce() { // 遍历字符流,找到第一个为1的字符 for (char c : vec) { if (table[c] == 1) return c; } return'#'; }
};
字符流中第一个不重复的字符 Java
import java.util.HashMap; publicclassSolution{ HashMap<Character, Integer> map = new HashMap<Character, Integer>(); StringBuffer s = new StringBuffer(); //Insert one char from stringstream publicvoidInsert(char ch){ s.append(ch); if(map.containsKey(ch)){ map.put(ch, map.get(ch)+1); }else{ map.put(ch, 1); } } //return the first appearence once char in current stringstream publiccharFirstAppearingOnce(){ for(int i = 0; i < s.length(); i++){ if(map.get(s.charAt(i)) == 1) return s.charAt(i); } return'#'; } }
privateintdiamHelper(TreeNode root){ if(root == null) return0; int left = diamHelper(root.left); int right = diamHelper(root.right); path = Math.max(path, left + right); return Math.max(left, right) + 1; }
4.2 medium code
4.2.1 判断二叉树是不是完全二叉树
boolcheckCompleteTree(Node* root){
bool flag = true; queue<Node*> q;
if (root == null) returntrue;
q.push(root);
while(!q.empty()){ for (int i = 0; i < q.size(); ++i) { Node* tmp = q.front(); q.pop(); if (tmp->lchild == NULL && tmp->rchild != NULL){ flag = false; break; } if (tmp->left != NULL) que.push(tmp->left); if (tmp->right != NULL) que.push(tmp->right); } } return flag; }
4.2.2 分层遍历 (自下而上分层遍历)
vector<vector<int>> bfs(Node* root) {
vector <vector<int> > ans;
if (root == NULL) return ans;
queue<Node*> q; q.push(root);
while(!q.empty()) { vector<int> tv; for (int i = 0; i < q.size(); ++i) { Node* tmp = q.front(); q.pop(); if (tmp->lchild == NULL && tmp->rchild != NULL){ flag = false; break; } if (tmp->left != NULL) que.push(tmp->left); if (tmp->right != NULL) que.push(tmp->right); tv.push_back(tmp->value); } ans.push_back(tv) } return flag; }
// reverse(res[i].begin(), res[i].end());
4.3 difficult code
4.3.1 二叉树中和为某一值的路径
voidf4(Node*, int, int, vector<int>&); voidf4(Node* root, int exSum){ if(root == NULL) return; vector<int> V; int curSum = 0; f4(root, exSum, curSum, V); } voidf4(Node* root, int exSum, int curSum, vecotr<int>& path){ curSum += root->value; path.push_back(root->value); if(curSum == exSum && root->lchild == NULL && root->rchild == NULL) { //; 打印vector中的路径 } if(root->lchild) f4(root->lchild, exSum, curSum, path); if(root->rchild) f4(root->rchild, exSum, curSum, path); curSum -= root->value; path.pop_back(); }
4.3.3 序列化二叉树
public String serialize(TreeNode root){ if(root == null) return"#,"; StringBuffer res = new StringBuffer(root.val + ","); res.append(serialize(root.left)); res.append(serialize(root.right)); return res.toString(); }
// Decodes your encoded data to tree. public TreeNode deserialize(String data){ String [] d = data.split(","); Queue<String> queue = new LinkedList<>(); for(int i = 0; i < d.length; i++){ queue.offer(d[i]); } return pre(queue); }
public TreeNode pre(Queue<String> queue){ String val = queue.poll(); if(val.equals("#")) returnnull; TreeNode node = new TreeNode(Integer.parseInt(val)); node.left = pre(queue); node.right = pre(queue); return node; }
classMyQueue{ Stack<Integer> input = new Stack<Integer>(); Stack<Integer> output = new Stack<Integer>(); /** Push element x to the back of queue. */ publicvoidpush(int x){ input.push(x); } /** Removes the element from in front of queue and returns that element. */ publicintpop(){ peek(); return output.pop(); } /** Get the front element. */ publicintpeek(){ if(output.isEmpty()){ while(!input.isEmpty()) output.push(input.pop()); } return output.peek(); } /** Returns whether the queue is empty. */ publicbooleanempty(){ return input.isEmpty() && output.isEmpty(); } }
6.2 包含min函数的栈
classMinStack{ Stack<Integer> stack = new Stack<Integer>(); Stack<Integer> temp = new Stack<Integer>(); publicvoidpush(int x){ stack.push(x); if(temp.isEmpty() || temp.peek() >= x) temp.push(x); } publicvoidpop(){ int x = stack.pop(); int min = temp.peek(); if(x == min) temp.pop(); } publicinttop(){ return stack.peek(); } publicintgetMin(){ return temp.peek(); } }
6.3 栈的 push pop 序列
栈的 push pop 序列
1 2 3 4 5
4 3 5 1 2
import java.util.ArrayList; import java.util.Stack; publicclassSolution{ publicbooleanIsPopOrder(int [] pushA, int [] popA){ if(pushA.length != popA.length || pushA.length == 0 || popA.length == 0) returnfalse; Stack<Integer> stack = new Stack<>(); int index = 0; for(int i = 0; i < pushA.length; i++){ stack.push(pushA[i]); while(!stack.empty() && stack.peek() == popA[index]){ stack.pop(); index++; } } return stack.empty(); } }
classSolution: defisValid(self, s): """ :type s: str :rtype: bool """ stack = list() match = {'{':'}', '[':']', '(':')'} for i in s: if i == '{'or i == '('or i == '[': stack.append(i) else: if len(stack) == 0: returnFalse