qiaoxu123’s gists

qiaoxu123 / test1.cpp

Last active November 22, 2018 06:04

Reverse a singly linked list. ``` Example: Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL ``` Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

	//使用头插入的方式，建立一个新的链表
	// 12 ms
	class Solution {
	public:
	ListNode* reverseList(ListNode* head) {
	ListNode temp = nullptr,nextNode = nullptr;
	while(head){
	nextNode = head->next;
	head->next = temp;
	temp = head;

qiaoxu123 / test.cpp

Last active November 26, 2018 23:56

You're given strings J representing the types of stones that are jewels, and S representing the stones you have. Each character in S is a type of stone you have. You want to know how many of the stones you have are also jewels. The letters in J ar

	//使用哈希法，用数组提前记录所有值，然后再进行遍历
	class Solution {
	public:
	int numJewelsInStones(string J, string S) {
	int array[100] = {0};
	int temp = 0;
	for(int i = 0;i < S.length();i++){
	array[S[i] - 65]++;
	}
	for(int i = 0;i < J.length();i++){

qiaoxu123 / test.cpp

Created November 29, 2018 01:03

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will autom

	//比较巧妙的思路
	class Solution {
	public:
	int rob(vector<int>& nums) {
	int a = 0,b = 0;

	for(int i = 0;i < nums.size();i++){
	if(i % 2 == 0)
	a = (a + nums[i]) > b ? (a + nums[i]) : b;
	else

qiaoxu123 / test.cpp

Created November 30, 2018 01:17

Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, the

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {

qiaoxu123 / test.cpp

Last active December 1, 2018 07:53

Count the number of prime numbers less than a non-negative number, n. ``` Example: Input: 10 Output: 4 Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7. ```

	class Solution {
	public:
	int countPrimes(int n) {
	if(n <= 2) return 0;
	vector<bool> passed(n,false);
	int sum = 1;
	int upper = sqrt(n);

	for(int i = 3;i < n;i += 2){
	if(!passed[i]){

qiaoxu123 / test.cpp

Created December 4, 2018 12:50

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in

	//使用动态规划解答
	class Solution {
	int uniquePaths(int m, int n) {
	if (m > n) return uniquePaths(n, m);
	vector<int> cur(m, 1);
	for (int j = 1; j < n; j++)
	for (int i = 1; i < m; i++)
	cur[i] += cur[i - 1];
	return cur[m - 1];
	}

qiaoxu123 / test.cpp

Last active December 5, 2018 08:29

Given a string S, we can transform every letter individually to be lowercase or uppercase to create another string. Return a list of all possible strings we could create. ``` Examples: Input: S = "a1b2" Output: ["a1b2", "a1B2", "A1b2", "A1B2"] Inpu

	class Solution {
	public:
	vector<string> letterCasePermutation(string S) {
	vector<string> vs;
	helper(vs,S,0);
	return vs;
	}

	void helper(vector<string> & vs,string &S,int p){
	if(p == S.size()){

qiaoxu123 / test.cpp

Last active December 6, 2018 10:40

Say you have an array for which the ith element is the price of a given stock on day i. If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

	class Solution {
	public:
	int maxProfit(vector<int>& prices) {
	int maxPro = 0;
	int minPrice = INT_MAX;
	for(int i = 0;i < prices.size();i++){
	minPrice = min(minPrice,prices[i]);
	maxPro = max(maxPro,prices[i] - minPrice);
	}
	return maxPro;

qiaoxu123 / test1.cpp

Created December 8, 2018 11:10

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 =

	class Solution {
	public:
	double myPow(double x, int n) {
	double ans = 1;
	unsigned long long p;
	if (n < 0) {
	p = -n;
	x = 1 / x;
	}
	else

qiaoxu123 / test1.cpp

Last active January 4, 2020 09:19

第一种方法：使用字符串来代表数字，实现数值相加进位第二种方法：使用递归来实现全排列

	#include <iostream>

	using namespace std;

	bool Increment(char* number);
	void PrintNumber(char* number);

	void Print1ToMaxOfNDigits(int n) {
	if (n <= 0)
	return;

xqiao qiaoxu123